5

リストが[a, b, a, a, a, c, c] あり、各要素をさらに 2 回追加する必要があります。

最終結果は次のようになります。

[a, a, a, b, b, b, a, a, a, a, a, c, c, c, c]

次のアイテムと同じアイテムがリストにある場合、新しいアイテムが見つかるまで続行し、新しいアイテムが見つかると、前のアイテムの2つの出現を追加してから移動します。

これはこれまでの私のコードですが、2つ追加する方法がわかりません...

dbl([], []).
dbl([X], [X,X]).
dbl([H|T], [H,H|T], [H,H|R]) :- dbl(T, R).
4

4 に答える 4

7

最後のルールは 3 つのパラメーターを取るため、コードは少し奇妙に見えます。バイナリ バージョンを呼び出すだけなので、再帰がそれを導出しようとすることはありません。

要素が変化するリストの部分を確認することは、すでに良い考えでした。したがって、次の 4 つのケースがあります。

1) あなたのリストは空です。2) 要素は 1 つだけです。3) あなたのリストは 2 つの等しい要素で始まります。4) あなたのリストは 2 つの異なる要素から始まります。

ケース 1 は指定されていないため、適切な選択を見つける必要があるかもしれません。ケース 2 はケース 4 と似ています。リストの最後は要素の変更と見なされるため、2 つのコピーを追加する必要がありますが、その後は完了です。ケース 3 は非常に単純です。要素を保持し、残りを再帰するだけです。ケース 4 では、2 つのコピーを再度挿入する必要があります。

これは、コードが次のようになることを意味します。

% Case 1
dbl([],[]).
% Case 2
dbl([X],[X,X,X]).
% Case 3
dbl([X,X|Xs], [X|Ys]) :-
   % [...] recursion skipping the leading X
% Case 4
dbl([X,Y|Xs], [X,X,X|Ys]) :-
   dif(X,Y),
   % [...] we inserted the copies, so recursion on [Y|Xs] and Ys

ケース 3 は簡単に終了できます。両方のリストから最初の X を削除し、dbl([X|Xs],Ys) を再帰するだけです。同じ変数を 2 回書き込むことで、最初の 2 つの要素を暗黙的に等しくした (つまり、それらを統合した) ことに注意してください。

ケース 4 の先頭を見ると、説明したパターンを直接模倣できます。リストが X で始まり、次に Y であり、それらが異なると仮定すると (dif(X,Y))、X は単にではなく 3 回繰り返されます。コピーしてから、Y で始まる残りの再帰を続行します: dbl([Y|Xs],Ys)。

それでは、述語を試してみましょう。

?- dbl([a,b,a,a,a,c,c],[a,a,a,b,b,b,a,a,a,a,a,c,c,c,c]).
true ;
false.

テスト ケースは受け入れられ (true)、複数のソリューションは見つかりませんでした (false)。間違った解を見つけるかどうか見てみましょう:

?- dif(Xs,[a,a,a,b,b,b,a,a,a,a,a,c,c,c,c]), dbl([a,b,a,a,a,c,c],Xs).
false.

いや、それもいい。リストに変数があるとどうなりますか?

?- dbl([a,X,a],Ys).
X = a,
Ys = [a, a, a, a, a] ;
Ys = [a, a, a, X, X, X, a, a, a],
dif(X, a),
dif(X, a) ;
false.

X = a の場合、Ys は次のように 5 の単一実行です。または X が a と等しくない場合、3 回の実行すべてでコピーを追加する必要があります。見た目もいい。(*)

ソリューションのみを指定するとどうなるか見てみましょう。

?- dbl(X,[a,a,a,b,b]).
false.

そうです、bs が 2 つしかないリストは、私たちの仕様の結果ではあり得ません。それでは、1つ追加してみましょう：

?- dbl(X,[a,a,a,b,b,b]).
X = [a, b] ;
false.

万歳、うまくいきました！最後のテストとして、述語を 2 つの変数で呼び出すとどうなるか見てみましょう。

?- dbl(Xs,Ys).
Xs = Ys, Ys = [] ;
Xs = [_G15],
Ys = [_G15, _G15, _G15] ;
Xs = [_G15, _G15],
Ys = [_G15, _G15, _G15, _G15] ;
Xs = [_G15, _G15, _G15],
Ys = [_G15, _G15, _G15, _G15, _G15] ;
Xs = [_G15, _G15, _G15, _G15],
Ys = [_G15, _G15, _G15, _G15, _G15, _G15] ;
[...]

正しい答えが得られたように見えますが、1 回の実行の場合しか表示されません。これは、プロローグの検索戦略の結果です (ここでは説明しません)。しかし、長いリストを生成する前に短いリストを見ると、すべての解を見ることができます。

 ?- length(Xs,_), dbl(Xs,Ys).
Xs = Ys, Ys = [] ;
Xs = [_G16],
Ys = [_G16, _G16, _G16] ;
Xs = [_G16, _G16],
Ys = [_G16, _G16, _G16, _G16] ;
Xs = [_G86, _G89],
Ys = [_G86, _G86, _G86, _G89, _G89, _G89],
dif(_G86, _G89) ;
Xs = [_G16, _G16, _G16],
Ys = [_G16, _G16, _G16, _G16, _G16] ;
Xs = [_G188, _G188, _G194],
Ys = [_G188, _G188, _G188, _G188, _G194, _G194, _G194],
dif(_G188, _G194) ;
[...]

したがって、テキストから不足している目標を埋めたと仮定すると、機能する述語 (**) があるようです :)

(*) ここでの注意: このケースは、dif を使用しているためにのみ機能します。等号を伴う最初の述語は、通常、=、==、およびそれぞれの否定 \= および \== です。= は単一化可能性 (引数に変数を代入すると、それらが等しくなる) を表し、 == は構文上の同等性 (用語が完全に等しい) を表します。例えば：

?- f(X) = f(a).
X = a.

?- f(X) \= f(a).
false.

?- f(X) == f(a).
false.

?- f(X) \== f(a).
true.

つまり、X を a で置き換えると、f(X) を f(a) と等しくすることができます。これは、それらを等しくできないかどうか (\=) を尋ねると、答えが false になることを意味します。一方、2 つの項は等しくないため、== は false を返し、その否定 \== は true を返します。

これは、X \== Y が常に true であることも意味するため、コードで \== を使用することはできません。それとは対照的に、 dif は引数が等しいかどうかを判断できるまで待機します。答えを見つけた後もこれが決定されない場合は、「dif(X,a)」ステートメントが出力されます。

(**) ここでの最後の発言: ケース 3 と 4 をマージする if-then-else コンストラクト (test -> goal_if_true; goal_if_false) を使用したソリューションもあります。私はこのソリューションを好むので、他のバージョンを自分で。

于 2013-12-22T01:19:11.520 に答える