1

1 つのリストを 2 つのリスト (半分) に分割する述語を作成する必要があります。

halve(X-Y, X-Z, Z-Y) :- halve_pom(X-Y, X-Y, Z), !.

halve_pom(Z-Y, Y-Y, Z).

halve_pom([_|A]-Y, [_,_|B]-Y, Z) :- halve_pom(A-Y, B-Y, Z).

それは簡単でしたが、今度はマージソートを行うアルゴリズムを書かなければなりません - 私にはわかりません。このアルゴリズムは差分リストを使用する必要があります。

助けてください。

4

1 に答える 1

1

いいえ、残念ながら機能しないため、「簡単」ではありませんでした。halve([1,2,3]-[],A,B)動作しません。halve_pom([1,2,3]-[],A,B)どちらも機能しません。また、どちらの分割スキームを好むか、[1,2,3,4,5,6,7] -> ([1,3,5,7] , [2,4,6])または-> ([1,2,3,4] , [5,6,7]).

halve述語が機能する場合はmerge、 を定義するだけで済みます。これにより、リストの 2 つの半分が順番にマージされます。それで、

mergesort(A,S):- halve(A,B-[],C-[]), mergesort(B,SB), mergesort(C,SC),
  merge(SB,SC,S-[]).

おそらく通常の list で呼び出すことに注意してくださいA。つまり、halve述語は最初の引数が通常のリスト (差分リストではない) であることを期待する必要があります。

Prolog でリストを扱うとき、"-" 記号は何を意味するのですか?も参照してください。. は'-'不要です。代わりに、その 2 つの構成要素を、述語に対する 2 つの別個の引数として使用する必要があります。

したがって、コーディングする1つの方法halveは

halve([A,B|C],[A|X]-ZX,[B|Y]-ZY):- halve(C,X-ZX,Y-ZY). 
halve([A],[A|X]-X,Y-Y). 
halve([],X-X,Y-Y).

コーディングにも同じアプローチを使用できますmerge。

merge(SB,SC,S-Z):- SB=[A|B], SC=[C|D], A=<C, S=[A|T], merge(B,SC,T-Z).
merge(SB,SC,S-Z):- SB=[A|B], SC=[C|D], A>C,  ... ,    ... .
merge(SB,SC,S-Z):- SB=[A|B], SC=[],          ... ,    ... .
merge(SB,SC,S-Z):- SB=[], SC=[C|D],          S=[C|T], ... .
merge([],[],Z-Z).
于 2013-03-27T11:49:48.673 に答える