0

リストとして表される 2 つの 2 進数を加算する方法を見つけようとしています。例: addNumbers([1,0,1], [1,1,0,0], X)。X = [1,0,0,0,1] を返す必要があります。

この問題を解決するためにカット (!) を使用することはあまりありません。したがって、ある種の加算器を実装する必要があることはわかっています。現在、必要な述語で実装された Digits を追加しています。

addDigits(A,B,X,Y) :- myXor(A,B,X), myAnd(A,B,Y).

myAnd(A,B,R) :- A == 1, B == 1, R is 1.
myAnd(A,B,R) :- A == 0, B == 0, R is 0.
myAnd(A,B,R) :- A == 1, B == 0, R is 0.
myAnd(A,B,R) :- A == 0, B == 1, R is 0.
myOr(A,B,R) :- A == 0, B == 0, R is 0.
myOr(A,B,R) :- A == 0, B == 1, R is 1.
myOr(A,B,R) :- A == 1, B == 0, R is 1.
myor(A,B,R) :- A == 1, B == 1, R is 1.

これは、X を 2 進数の合計として、Y を桁上げとして正しく返します。これで、加算器にこれが必要であることがわかりました。addDigits を実際に実装することは、私が立ち往生しているところです。これは現在私が持っているものですが、機能しません。注: ヒントは LSB の開始でしたが、現在は行っていません。

addNumbers([HA|TA],[HB|TB],X) :- adder(HA,HB,Cin,Sum,Cout,X),
    append(Sum, X, X),
    addNumbers(TA,TB,X).

adder(X,Y,Cin,Sum,Cout) :- addDigits(X,Y,Sum1,Carry1),
    addDigits(Sum1, Cin, Sum, Carry2),
    myOr(Carry1, Carry2, Cout).

ヘルプ/提案をいただければ幸いです。

乾杯

4

1 に答える 1

2

あなたは良い軌道に乗っています。主な問題は、典型的な Prolog 再帰を理解することです。

しかし、最初に、バイナリ関数: それらは正しいですが、次のように簡単で読みやすいです (とにかくこれがありません):

myXor(1,0,1).
myXor(0,1,1).
myXor(1,1,0).
myXor(0,0,0).

あなたの 4 番目のケースにはタイプミスがありますmyOr。小文字の「o」でつづっています。これを定義すると、adder実際に正しく動作します!

ここで、再帰について: 実際には LSB から始める必要があります。そうしないと、数値が必ずしも同じ長さであるとは限らないため、どのビットを追加すればよいかさえわかりません。reverse幸いなことに、呼び出しをsでラップすることにより、これを簡単に行うことができます。

addNumbers(N1, N2, Sum) :- 
    reverse(N1, N12), 
    reverse(N2, N22),
    addNumbers(N12, N22, 0, [], Sum0),
    reverse(Sum0, Sum).

これは Prolog で非常に一般的なパターンです: addNumbers/3 が addNumbers/5 を呼び出し、再帰に必要なパラメーターがさらに必要です。「0」は最初のキャリー、[] は結果のアキュムレータです。あなたのバージョンからいくつかの変更を加えた addNumbers/5 は次のとおりです。

addNumbers([HA|TA],[HB|TB],Cin,X0,X) :- 
    adder(HA,HB,Cin,Sum,Cout),
    append(X0, [Sum], X1),
    addNumbers(TA,TB,Cout,X1,X).

まず、ここで Cin を入力パラメーターとして受け取る必要があることに注意してください。また、「アキュムレータ」変数として X0 があります。つまり、再帰呼び出しごとに長くなります。最後の呼び出しには結果があるため、出力変数に入れることができます。そのためには、基本ケースも必要です。

addNumbers([],B,Cin,X0,X) :- % TODO: Respect Cin
    append(X0,B,X).
addNumbers(A,[],Cin,X0,X) :- % TODO: Respect Cin
    append(X0,A,X).

append の結果が上記の X1 (別の中間変数) ではなく、X であることがわかりますか? これは、最終的な結果であり、呼び出しスタックのずっと下まで同じ X で統合されるためです。このようにして、addNumbers/5 呼び出し全体の出力になります!

ただし、未完成のままにしておいたので、いくつかの（ほとんど）作業が残っています。また、基本ケースではCinを考慮する必要があります...

于 2012-11-19T07:35:12.247 に答える