2

リストの再帰的な検索と、結果からリストのリストを作成するのに苦労しています..

ナレッジ ベースには、チーム名、勝利数、所属ゾーンが含まれており、すべてチーム番号に関連付けられています。チーム番号のリストを に渡しTeams、 で一致するペアを検索していfindMinMax/3ます。必要な結果は...

ペアになったチームのリストのリスト (例X = [[gonzaga, washington], [iowa, oklahoma], …]) および 1 つの不一致チーム (チームの数が奇数の場合) または 0 (偶数の場合)

私は他のすべてを理解し、その部分に到達できますが[gonzaga, washington]、再帰部分で失敗しています...

findPair(Teams,[HL|TL],Rest) :-
    findMinMax(Teams,Min,Max),
    delete(Teams,Min,TeamsNoMin),
    delete(TeamsNoMin,Max,Rest),
    createPair(Min,Max,Pair), %Pair = "["Min_team","Max_team"]"
    append(HL,[Pair],TL),
    findPair(Rest,TL,[]).
4

1 に答える 1

6

一般的な再帰スキーム

ここでは、通常、Prolog で再帰を実行する方法を示します。リストは「後方」に構築されているため、初心者にとって取得するのは簡単ではありません。リストの最後に到達するまで、実際には何も構築されません。

この「後方構築」の原則の理由は、変数が設定されると、それを別の値に設定することができないためです。たとえば、結果が[1]再帰の最初のステップにあり、次にになり[1, 2]ます。代わりに、Prolog で言うことは、結果の先頭は1再帰呼び出しの結果であり、結果の末尾は再帰呼び出しの結果であるということです (そう、面倒な場合は 2 回読んでください : d)。したがって、基本ケース (再帰が実行されないケース) にヒットしない限り、変数を明確にバインドしません (つまり、常に項の一部をバインド解除します)。

rec/2: rec(Input, Result)要素を でリンクすることによって入力リストから結果リストを生成する述語の場合、次のsomepredicate/2ように記述します。

rec([InputHead|InputTail], [ResultHead|ResultTail]) :-
    somepredicate(InputHead, ResultHead),
    rec(InputTail, ResultTail).

それを表すために。

ResultHeadここで、結果の先頭は であり、その末尾は呼び出しのおかげで計算されると述べたことがわかります。rec(InputTail, ResultTail).

これで問題ありませんが、たとえばリストが空の場合など、ある時点で停止する必要があります。次のように書きます。

rec([], []).

つまり、入力リストが空の場合、結果リストも空です。

述語への適用

問題を解決するには、まず再帰句を修正する必要があります。

findPair(Teams,[HL|TL],Rest) :-
    findMinMax(Teams,Min,Max),
    delete(Teams,Min,TeamsNoMin),
    delete(TeamsNoMin,Max,Rest),
    createPair(Min,Max,Pair), %Pair = "["Min_team","Max_team"]"
    append(HL,[Pair],TL),
    findPair(Rest,TL,[]).

になるだろう

findPair(Teams, [Pair|Tail], LeftOver) :-
    findMinMax(Teams, Min, Max),
    delete(Teams, Min, TeamsNoMin),
    delete(TeamsNoMin, Max, Rest),
    createPair(Min, Max, Pair), %Pair = "["Min_team","Max_team"]"
    findPair(Rest, Tail, LeftOver).

重要な注意事項:Restは 2 つの別個の変数になりました。の最後の引数はfindPair/3もう変更されません。再帰呼び出しではそれについてまだ何もわからないため、それをバインドすることができず、Restしたがって in-predicate は独立しており、まだ変更されていないチームを表すだけです。まだ処理されていないため、結果リストの末尾 (およびLeftOver) に関心があります。

次に、基本ケースを処理する必要があります。

  • チームが残っていないとき

    findPair([], [], []).

    ここで、 whenTeamsが空であると言うと、ResultandもそうLeftOverです。

  • チームが1つ残っているとき

    findPair([Last], [], [Last]).

    ここで、whenTeamsは要素が 1 つしかない、LeftOver等しい、TeamsおよびResult空であると言います。

結果のコードは次のとおりです。

findPair([], [], []).
findPair([Last], [], [Last]).
findPair(Teams, [Pair|Tail], LeftOver) :-
    findMinMax(Teams, Min, Max),
    delete(Teams, Min, TeamsNoMin),
    delete(TeamsNoMin, Max, Rest),
    createPair(Min, Max, Pair), %Pair = "["Min_team","Max_team"]"
    findPair(Rest, Tail, LeftOver).

Teams句を排他的[Not, Empty|AtAll]にするには、最後の句が長さ 2 以上のリストでのみ使用されるように置き換えるかTeams = [_, _|_],、句の先頭などにガードを追加するだけです。

それが役に立てば幸いです。コメントで説明を求めることを躊躇しないでください:)

于 2012-08-20T00:00:11.147 に答える