3

入力リストを半分に分割するためのこのコードがあります。大丈夫そうです。

halve(List,A,B) :- halve(List,List,A,B), !.
halve(B,[],[],B).
halve(B,[_],[],B).
halve([H|T],[_,_|T2],[H|A],B) :-halve(T,T2,A,B).

わかりました、それで私はそれをデコードしようとしました。始まりは明らかです：

「半分はリストと2つの論理変数を取りました」はこれです：

halve(List,A,B)

（1）次に、この部分を続けます。

:- halve(List,List,A,B).

つまり、最初のリストから新しい2つのリスト（リスト、リスト）を作成しているということですか？「：-」を正確に表すものは何ですか？新しいリスト=半分はAとBになると思いますよね？

（2）次に、次の2行がわかりません。

halve(B,[],[],B).
halve(B,[_],[],B).

いくつかの例で説明してもらえますか？

（3）さて、（1）と（2）の説明が終わったら、最後の部分は自分で手に入れたいと思います...

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B).

助けてくれてありがとう。

さて、私たちの最初の問題はすでに解決策を持っています。簡単に言えば、次のように機能します。

halve([1,2,3,4,5],[1,2],[3,4,5]). 
->true

リストが半分に分割されていることに気付いた場合でも、リストの要素数が奇数の場合は、後半が大きい方になります。

今私が取得したいのは、最初のものを大きくすることです。

だから私はこれについて考えています：

私はこれに到達するつもりです：

Halves_div([1,2,3],A,B).
A=[1,2],
B=[3].

私の入力がリストであるとしましょう：[1,2,3]。それで、リストの頭と尾を分割することから始めます：[H|T]それから、新しい空のリストとマージしHます-私の前半（A）。その後、A = [1]、B = []、Input=[2,3]になります。

マージするために私は持っています：

merge([],List,List).
merge([H|T],List,[H|New]) :- merge(T,List,New).

そしてもう1つ-前半がすでに>=後半であるかどうかを確認する必要がありますよね？

ですから、これは私の考えであり、私があなたに助けてもらいたい唯一のことは、それをプロローグで書くことです。私はそれをどのように組み合わせるか少し混乱しています。

ありがとう！

私の解決策のアイデアは複雑すぎるようで、もっと良いものを見つけました！

4

3 に答える 3

9

まず、Prolog 句は次のようになります。

Head :- Body

Headこれは、「 if Body」または「Bodyimplements 」と読むことができますHead。

時々あなたが持っていることに注意してください

Head

これは、 Head が常にtrue. Headこの場合、節と呼ぶ代わりに事実と呼びます。

ここで、次のようになります。

halve(List,A,B) :- halve(List,List,A,B).

つまり、halve(List, A, B)が true の場合halve(List, List, A, B)は true です。具体的には、いわゆるワーカー述語であるhalve/3toの作業を委譲する方法にすぎません。halve/4

なぜワーカー述語が必要なのですか? ここでは、別の変数を使用してAandB項を計算したいからです。halve/3しかし、 の 3 つの引数スポットは、結果の前半部分と結果の後半部分である入力リスト によって既に取得されているため、これをhalve/3行うことはできませんでした。ListAB

これは、他のプログラミング言語と同じように、同じ第 1 引数と第 2 引数で呼び出してList, Listいることを示す方法にすぎません。halve/4

それから面白いことが始まります。Prolog はhalve/4、与えられたいくつかの引数についてそれが真であることを証明しようとします。この方法で呼び出した実行を説明するとしましょうhalve/3:

?- halve([1, 2], A, B).

次に、前に説明したことに従った場合、Prolog は、次の引数を使用してhalve/3それが真であることを証明することによって、それが真であることを証明しようとします。halve/4halve([1, 2], [1, 2], A, B).

そのために、Prolog には 3 つの選択肢があります。最初の選択肢は次の句です。

halve(B,[],[],B).

明らかに、それはうまくいきません。Prolog が呼び出し元の 2 番目の引数を呼び出し先の 2 番目の引数に統合しようとすると、失敗するためです。[1, 2]と統一できないから []です。

残り2択、次は

halve(B,[_],[],B).

ここでも同じことが言えます。Prolog は単一化できません。これは単なる変数である[1, 2]ためです (問題がある場合は、匿名変数に関する私の投稿を参照してください)。[_]__

したがって、Prolog が提示した問題の解決策を見つけなければならない唯一のチャンスは、最後の節です。

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B).

ここで、Prolog は物事を統一する方法を見つけます。どの方法を見てみましょう:

  • と統一[1, 2]しなければなりません[H|T]。つまりH = 1.、T = [2].
  • と統一[1, 2]しなければなりません[_,_|T2]。つまり、T2 = [].
  • ここで、次の統合で結果を構築し始めます。つまり、変数はローカルにスコープされており、それらは同じではないためA = [H|A']、2 番目の統合を準備しました。Aここで、節の本体から結果を計算するときに、それに加算Hすることを伝えます。の最初の要素が になることHは1すでにわかっています。A1

わかりました、統合に成功しました。すばらしいです。節の本文に進むことができます。halve/4これらの値 (上記で計算) を使用して再帰的に呼び出すだけです。

halve([2], [], A, B).

そして、ここで最初からやり直します。今回は、最初の選択肢である Prolog が適切に適合するため、処理は高速になります。

halve(B,[],[],B).

に統一できる

halve([2], [], A, B).

これらの値:A = []およびB = [2].

これは良いステップです。再帰の「基本ケース」に到達しました。今は結果を下から上に構築する必要があります。halve/4数ステップ上で述語を再帰的に呼び出したときのことを覚えていますか? Aの最初の要素は になるとすでに述べました1。これで、テールが であることがわかった[]ので、 と述べることができますA = [1]。特に記載はありませんでしたBのでB = [2]結果はそのままです。

実行の詳細を説明したので、なぜこれが機能するのか疑問に思うかもしれません。注意を払えば、 の 2 番目の引数がhalve/4最初の引数の 2 倍の速さで処理されることに気付くでしょう。[H|T]対[_, _|T2]。つまり、2 番目の引数でリストの最後に到達しても、最初の引数はまだリストの中央にあるということです。このようにして、物事を 2 つの部分に分けることができます。

ここで働いている微妙な事柄のいくつかを理解するのに役立つことを願っています.

于 2012-04-08T15:47:27.360 に答える
1

halve(List,A,B)の前半をListto にコピーし、後半を toAで統合しますB

これは、リストの長さが偶数の場合に当てはまります。halve(B,[],[],B).

これは、out リストの長さが奇数の場合に当てはまります。halve(B,[_],[],B).

halve([H|T],[_,_|T2],[H|A],B) :- halve(T,T2,A,B).

Aここでは、最初の半分を取得したいので、リストの先頭から 1 つの要素をコピーする各ステップでそれらを「ポインター」と呼ぶように 2 を設定しています。
各ステップでリストから 2 つの要素を削除しているため、[_,_|T2]述語は、リストに残っている要素が 1 つしかないか空の場合に停止し、残りのリストを で統合しBます。使い方が分からない場合trace/0

于 2012-04-08T15:57:19.353 に答える