31

だから私はPythonでプログラムを書いて、任意の数のGCDを取得しています。

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]


    # i'm stuck here, this is wrong
    for i in range(len(numbers)-1):
        print GCD([numbers[i+1], numbers[i] % numbers[i+1]])


print GCD(30, 40, 36)

この関数は、数値のリストを受け取ります。これは 2 を出力するはずです。ただし、複数の数値を処理できるようにアルゴリズムを再帰的に使用する方法がわかりません。誰か説明できますか？

更新されましたが、まだ機能していません:

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]

    gcd = 0

    for i in range(len(numbers)):
        gcd = GCD([numbers[i+1], numbers[i] % numbers[i+1]])
        gcdtemp = GCD([gcd, numbers[i+2]])
        gcd = gcdtemp

    return gcd

わかりました、解決しました

def GCD(a, b):

    if b == 0:
        return a
    else:
        return GCD(b, a % b)

そして、次のようにreduceを使用します

reduce(GCD, (30, 40, 36))
4

10 に答える 10

40

GCD は連想なのでGCD(a,b,c,d)、 と同じGCD(GCD(GCD(a,b),c),d)です。この場合、Python の関数は、ケースを単純な 2 つの数値の比較reduceに減らすための良い候補になります。len(numbers) > 2コードは次のようになります。

if len(numbers) > 2:
    return reduce(lambda x,y: GCD([x,y]), numbers)

Reduce は指定された関数をリスト内の各要素に適用するため、次のようになります。

gcd = reduce(lambda x,y:GCD([x,y]),[a,b,c,d])

するのと同じです

gcd = GCD(a,b)
gcd = GCD(gcd,c)
gcd = GCD(gcd,d)

あとは when をコーディングするだけですlen(numbers) <= 2。GCDin に引数を 2 つだけ渡すreduceと、関数の再帰が最大で 1 回 (元の呼び出しでのみ) になることが保証されますlen(numbers) > 2。これには、スタックがオーバーフローしないという追加の利点があります。

于 2013-05-18T19:53:10.867 に答える
28

使用できますreduce：

>>> from fractions import gcd
>>> reduce(gcd,(30,40,60))
10

これは次と同等です。

>>> lis = (30,40,60,70)
>>> res = gcd(*lis[:2])  #get the gcd of first two numbers
>>> for x in lis[2:]:    #now iterate over the list starting from the 3rd element
...    res = gcd(res,x)

>>> res
10

ヘルプreduce: _

>>> reduce?
Type:       builtin_function_or_method
reduce(function, sequence[, initial]) -> value

Apply a function of two arguments cumulatively to the items of a sequence,
from left to right, so as to reduce the sequence to a single value.
For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
((((1+2)+3)+4)+5).  If initial is present, it is placed before the items
of the sequence in the calculation, and serves as a default when the
sequence is empty.
于 2013-05-18T19:27:33.797 に答える
0

GCD()次のように呼び出してみてください。

i = 0
temp = numbers[i]
for i in range(len(numbers)-1):
        temp = GCD(numbers[i+1], temp)
于 2013-05-18T19:28:00.513 に答える
0

2 つの数値の GCD を見つける簡単な方法を次に示します。

a = int(input("Enter the value of first number:"))
b = int(input("Enter the value of second number:"))
c,d = a,b
while a!=0:
    b,a=a,b%a
print("GCD of ",c,"and",d,"is",b)
于 2020-10-24T05:35:36.170 に答える
0

Pythonでそれを解決する私の方法。それが役に立てば幸い。

def find_gcd(arr):
    if len(arr) <= 1:
        return arr
    else:
        for i in range(len(arr)-1):
            a = arr[i]
            b = arr[i+1]
            while b:
                a, b = b, a%b
            arr[i+1] = a
        return a
def main(array):
    print(find_gcd(array))

main(array=[8, 18, 22, 24]) # 2
main(array=[8, 24]) # 8
main(array=[5]) # [5]
main(array=[]) # []

私がそれをどのように理解しているか、いくつかのダイナミクス：

ex. [8, 18] -> [18, 8] -> [8, 2] -> [2, 0]

18 = 8x + 2 = (2y)x + 2 = 2z ここで、z = xy + 1

ex. [18, 22] -> [22, 18] -> [18, 4] -> [4, 2] -> [2, 0]

22 = 18w + 4 = (4x+2)w + 4 = ((2y)x + 2)w + 2 = 2z

于 2018-07-24T02:06:16.490 に答える