5

自然数を使用して、2の累乗のProlog述語を作成する必要があります。自然数は次のとおりです：0、s（0）、s（s（0））ansなど。

例えば：

?- pow2(s(0),P).
P = s(s(0));
false.
?- pow2(P,s(s(0))).
P = s(0);
false.

これは私のコードです：

times2(X,Y) :-
  add(X,X,Y).

pow2(0,s(0)).
pow2(s(N),Y) :-
  pow2(N,Z),
  times2(Z,Y).

そして、それは最初の例で完全に機能しますが、2番目の例では無限ループに入ります。
これを修正するにはどうすればよいですか？

4

2 に答える 2

8

これは、バインドされている最初または2番目の引数で終了するバージョンです。

pow2（E、X）：-
  pow2（E、X、X）。

pow2（0、s（0）、s（_））。
pow2（s（N）、Y、s（B））：-
   pow2（N、Z、B）、
   add（Z、Z、Y）。

cTIを使用してその終了条件を判別できます。

それで、どうやってその解決策を思いついたのですか？アイデアは、2番目の引数が最初の引数のサイズを決定する方法を見つけることでした。重要なアイデアは、すべてのi∈N ：2i > iについてです。

そこで、この関係を表現するためにさらに引数を追加しました。多分あなたはそれをもう少し強化することができますか？

そして、これが元のプログラムが終了しない理由です。理由をとして示します。詳細およびその他の例については、タグを参照してください。

？-pow2（P、s（s（0）））、false。

pow2（0、s（0））：- false。
pow2（s（N）、Y）：-
  pow2（N、Z）、false、
   times2（Z、Y）。

非終了の原因となるのはこの小さな断片です！Zどれが新鮮な新しい変数であるかを見てください！この問題を修正するには、このフラグメントをなんらかの方法で変更する必要があります。

そして、これが@Keeperのソリューションがで終了しない理由ですpow2(s(0),s(N))。

？-pow2（s（0）、s（N））、false。

add（0、Z、Z）：- false。
add（s（X）、Y、s（Z））：-
  add（X、Y、Z）、false。

times2（X、Y）：-
  add（X、X、Y）、false。

pow2（0、s（0））：- false。
pow2（s（N）、Y）：- false、
   var（Y）、
   pow2（N、Z）、
   times2（Z、Y）。
pow2（s（N）、Y）：-
  nonvar（Y）、
  times2（Z、Y）、false、
   pow2（N、Z）。
于 2012-03-16T17:10:18.913 に答える
4

これは、pow2の評価順序が原因で発生します。pow2の順序を切り替えると、最初の例が無限ループに陥ります。したがって、最初にYがavarまたは。であるかどうかを確認できますnonvar。

そのようです：

times2(X,Y) :-
  add(X,X,Y).

pow2(0,s(0)).
pow2(s(N),Y) :-
  var(Y),
  pow2(N,Z),
  times2(Z,Y).
pow2(s(N),Y) :-
  nonvar(Y),
  times2(Z,Y),
  pow2(N,Z).
于 2012-03-16T15:41:06.463 に答える