5

私は質問を受けました：

整数のリストが正しく昇順になっているかどうかをチェックする述語、ordered/1 を定義します。たとえば、ゴールordered([1,3,7,11])は成功する必要がordered([1,3,3,7])ありますが、ゴールordered([1,7,3,9])は失敗する必要があります。

これまでのところ、私はこれを持っています：

ordered([]).    
ordered([N, M|Ns]):-
    append(M, Ns, Tail),
    ordered(Tail),
    N =< M.

しかし、すべてのリストで失敗します。

失敗する理由は、リストの最後の番号に到達し、その番号を空のリストと比較しようとするためだと推測しました。整数を空のリストと比較できないため、明らかにこれは失敗します。可能で、たとえば、0空のリストに対して返されたとしても、数値が よりも大きくなり0、未満ではないため、 false が返されます。

解決策が見つかりません...何かアイデアはありますか? ありがとう、ジョン。

編集

したがって、いくつかのわずかに修正されたコード:

ordered([]).
ordered([N]):-
    N >= 0.
ordered([N, M|Ns]):-
    append(M, Ns, Tail),
    ordered(Tail),
    N =< M.

これは で機能するようになりましordered([1])たが、より大きなリストはまだ正しく動作しません。

ordered([N, M|Ns])のようなものを定義に含める必要がありますか?

4

7 に答える 7

5

（これが宿題だと仮定すると、完全な解決策を提供するのをためらっています）。

コードを見て、それがどのように統合されるかを調べてみてください。?- ordered([1]). このクエリを精神的に (または trace/0 を使用して) 実行し、それが何を行うか、ステップごとに確認し、結果をどのように計算するかを確認してください。

また、プロローグを考えるときは、「値を返す」ことを忘れるようにしてください。プロローグ述語は何も返しません。

于 2009-08-26T12:34:28.333 に答える
2

あなたのソリューションも末尾再帰に適していないと思います。そのようなことを考えてください：

ordered([]) :-!.
ordered([_]):-!.
ordered([A,B|T]) :-
    A =< B,
    !,
    ordered([B|T]).
于 2009-08-27T14:03:38.413 に答える
2

Prolog システムがをサポートしている場合は、ライブラリ述語が提供されているかどうかを確認してくださいclpfd:chain/2。

:- use_module(library(clpfd)).

もしそうなら、単に書く：

?- chain([1,3,7,11],#<).
true.

?- chain([1,3,3,7],#=<).
true.
?- chain([1,3,3,7],#<).
false.

?- chain([1,7,3,9],#<).
false.
于 2015-06-23T08:07:56.523 に答える
1

おっしゃる通りです。あなたのコードによれば、リストが可能な方法は 2 つしかありませんordered。

  1. 空っぽです
  2. 最初の 2 つの項目は正しい順序で、残りのリストは次のとおりです。ordered

どちらも確かに正しいステートメントですが、リストは[3]どうでしょうか? それもそうじゃないordered？明らかに、要素が 1 つだけのリストは順序付けされていますが、それを表現する準備がありません。基本ケースにも再帰ケースにも適合しません。

単一要素リストは、まだ対処していない別のケースです。これは、既に定義した 2 つのルールとは無関係であるため、この特殊なケースに個別に対処する方法を検討することをお勧めします。

于 2009-08-26T12:36:37.130 に答える
0

結局、それはばかばかしいほど簡単に修正できました。

これが正しいコードです。

ordered([]).

ordered([N, M|Ns]):-
 append([M], Ns, Tail),
 ordered(Tail),
 N =< M.

ordered([M]).

注文済み([M])。上記のように単一要素リストを扱います。

私の問題の本当の根源は、追加機能の M の周りに [] を含めていませんでした。

正解を与えるためのエチケットは？お二人には大変お世話になりました。

ジョン

于 2009-08-26T14:48:00.910 に答える
0

使用しないでくださいappend/3。

edit1 @falseを満たすようにします。末尾再帰に適したものにするためには、バックトラッキングを排除する必要があります。これは末尾再帰であり、@Xonix ではわずかに異なります。

ordered([X|[]]):-!.

ordered([X,Y|Ys]) :- 
    X =< Y,
    !,
    ordered([Y|Ys]).

edit2さらに一歩進んで、要素が 2 つ未満のリストを削除します

ordered([X,Y|[]]):- X =< Y,!.

ordered([X,Y|Ys]) :- 
    X =< Y,
    !,
    ordered([Y|Ys]).
于 2015-06-23T11:33:07.800 に答える