0

2 つの数値の HCF を見つけるアルゴリズムはr = a*aqr + b*bqr、正しい式をすべて入力したと確信しているにもかかわらず、部分的にしか機能していません。基本的には、HCF を見つけることができますが、ベズーの補題のデモンストレーションも提供しようとしているので、前述の表示された正当化を表示する必要があります。プログラム：

# twonumbers.py
inp = 0
a = 0
b = 0
mul = 0
s = 1
r = 1
q = 0
res = 0
aqc = 1
bqc = 0
aqd = 0
bqd = 1
aqr = 0
bqr = 0
res = 0
temp = 0
fin_hcf = 0
fin_lcd = 0
seq = []
inp = input('Please enter the first number, "a":\n')
a = inp
inp = input('Please enter the second number, "b":\n')
b = inp
mul = a * b # Will come in handy later!
if a < b:
    print 'As you have entered the first number as smaller than the second, the program will swap a and b before proceeding.'
    temp = a
    a = b
    b = temp
else:
    print 'As the inputted value a is larger than or equal to b, the program has not swapped the values a and b.'
print 'Thank you. The program will now compute the HCF and simultaneously demonstrate Bezout\'s Lemma.'
print `a`+' = ('+`aqc`+' x '+`a`+') + ('+`bqc`+' x '+`b`+').'
print `b`+' = ('+`aqd`+' x '+`a`+') + ('+`bqd`+' x '+`b`+').'
seq.append(a)
seq.append(b)
c = a
d = b
while r != 0:
    if s != 1:
        c = seq[s-1]
        d = seq[s]
    res = divmod(c,d)
    q = res[0]
    r = res[1]
    aqr = aqc - (q * aqd)#These two lines are the main part of the justification
    bqr = bqc - (q * aqd)#-/
    print `r`+' = ('+`aqr`+' x '+`a`+') + ('+`bqr`+' x '+`b`+').'
    aqd = aqr
    bqd = bqr
    aqc = aqd
    bqc = bqd
    s = s + 1
    seq.append(r)
fin_hcf = seq[-2] # Finally, the HCF.
fin_lcd = mul / fin_hcf
print 'Using Euclid\'s Algorithm, we have now found the HCF of '+`a`+' and '+`b`+': it is '+`fin_hcf`+'.'
print 'We can now also find the LCD (LCM) of '+`a`+' and '+`b`+' using the following method:'
print `a`+' x '+`b`+' = '+`mul`+';'
print `mul`+' / '+`fin_hcf`+' (the HCF) = '+`fin_lcd`+'.'
print 'So, to conclude, the HCF of '+`a`+' and '+`b`+' is '+`fin_hcf`+' and the LCD (LCM) of '+`a`+' and '+`b`+' is '+`fin_lcd`+'.'

これで何が問題なのかを見つけるのを手伝っていただければ幸いです。

4

3 に答える 3

9

うーん、あなたのプログラムはかなり冗長で、読みにくいです。たとえば、最初の数行でこれらの変数を多数初期化する必要はありません。inpまた、変数に代入してからコピーする必要はありませaんb。seqまた、リストやs変数はまったく使用しません。

とにかくそれは問題ではありません。2 つのバグがあります。印刷された中間の回答を手作業の例と比較した場合、問題を見つけることができたはずです。

最初の問題は、次の 2 行目にタイプミスがあることです。

aqr = aqc - (q * aqd)#These two lines are the main part of the justification
bqr = bqc - (q * aqd)#-/

2行目でaqd、bqd

2番目の問題は、このコードのビットで

aqd = aqr
bqd = bqr
aqc = aqd
bqc = bqd

あなたがするaqdしaqr、その後aqcになりますaqd。だからaqc、aqd結局同じです。実際には別の順序で割り当てが必要ですが、次のようになります。

aqc = aqd
bqc = bqd
aqd = aqr
bqd = bqr

その後、コードが機能します。しかし、私はそれがこのようにもっと書かれているのを見たいと思っています。プリントを省略しましたが、追加していただけると確信しています。

a = input('Please enter the first number, "a":\n')
b = input('Please enter the second number, "b":\n')
if a < b:
    a,b = b,a

r1,r2 = a,b
s1,s2 = 1,0
t1,t2 = 0,1
while r2 > 0:
    q,r = divmod(r1,r2)
    r1,r2 = r2,r
    s1,s2 = s2,s1 - q * s2
    t1,t2 = t2,t1 - q * t2

print r1,s1,t1

最後に、ソリューションの構造をより明確に表現する再帰バージョンを検討する価値があると思います。

お役に立てれば。

于 2013-06-02T21:01:41.730 に答える
2

これは、ベズーのアイデンティティの単純なバージョンです。aとbを指定すると、 x、y、およびg = gcd( a , b )が返されます。

function bezout(a, b)
    if b == 0
        return 1, 0, a
    else
        q, r := divide(a, b)
        x, y, g := bezout(b, r)
        return y, x - q * y, g

このdivide関数は、商と剰余の両方を返します。

于 2013-06-03T00:43:05.860 に答える