(モジュロを使用せずに)GCDを見つけるためのコードをPrologで書き込もうとしましたが、このプログラムの何が問題になっているのか誰か教えてもらえますか?
gcd(X,Y,Z):- X>=Y, X1=X-Y, gcd(X1,Y,Z).
gcd(X,Y,Z):- X<Y, X1=Y- X, gcd(X1,X,Z).
gcd(0,X,X):- X>0.
元の実装が機能しない理由については、2つの理由があります。
述語=/2
は、算術割り当てではなく、統合用です。
式X1 = X - Y
は、結果を減算Y
しX
て結果をに格納しませんX1
。むしろ、それX1
は用語、と統合し-(X,Y)
ます。もし、例えば、X=5
そしてY=3
、その結果は、なりX1=5-3
ません、X1=2
。解決策は、is/2
評価された算術式を割り当てるを使用することですX1 is X - Y
。
ベースケース述語以外の他の述語は、ベースケースと正常に一致します
この句gcd(0,X,X) :- X > 0.
は妥当な基本ケースですが、2番目の句(gcd(X,Y,Z):- X<Y,...
)が常に最初に同じ条件に正常に一致し、無限再帰とスタックオーバーフローが発生するため、試行されることはありません。
これを修正する1つの方法は、ベースケースを最初の句に移動し、正常に実行された後のバックトラックを回避するためにカットを使用することです。
gcd(0, X, X):- X > 0, !.
gcd(X, Y, Z):- X >= Y, X1 is X-Y, gcd(X1,Y,Z).
gcd(X, Y, Z):- X < Y, X1 is Y-X, gcd(X1,X,Z).
これは今動作します:
| ?- gcd(10,6,X).
X = 2 ? ;
(1 ms) no
| ?- gcd(10,5,X).
X = 5 ? ;
no
(注:ここでの「いいえ」は、最初の解決策を見つけた後、それ以上解決策が見つからないことを意味します)
上記の実装には、まだいくつかの「ギャップ」が残っています。1つは、gcd(0, 0, R)
正常に処理されない(オーバーフローする)ことです。第二に、それは負の値を処理しません。考えられる解決策の1つは、次のケースを詳しく説明することです。
gcd(X, Y, Z) :-
X < 0, !,
gcd(-X, Y, Z).
gcd(X, Y, Z) :-
Y < 0, !,
gcd(X, -Y, Z).
gcd(X, 0, X) :- X > 0.
gcd(0, Y, Y) :- Y > 0.
gcd(X, Y, Z) :-
X > Y, Y > 0,
X1 is X - Y,
gcd(Y, X1, Z).
gcd(X, Y, Z) :-
X =< Y, X > 0,
Y1 is Y - X,
gcd(X, Y1, Z).
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加