-1

Python で最大公約数カウンターを作成したかったのですが、どのように行えばよいのか、どこから始めればよいのか正確にはわかりません... 私が持っているのはほとんどこの方程式だけです (a と b は数値です):

a = b * quotient + remainder

そして、残りが a 未満になるまですべてのステップをカウンターに出力してから、GCD を表示するようにします。

また、さらに検索したところ、2つの数値の商は // コマンドで簡単に実行でき、剰余は % コマンドで簡単に実行できることがわかりました。基本的には次のとおりです。

a = b * (a // b) + (a % b)

カウンターのループが必要であることも認識していますが、その方法がわかりません...助けていただければ幸いです。

GCD のコードをいくつか見たことがありますが、すべての手順を示すコードは見つかりませんでした。

4

1 に答える 1

0 
def gcd_steps(a, b):
    steps = []
    # this is the standard GCD finding algorithm;
    # we simply amend it with "step tracking"
    while b:
        # a, b = b, a % b
        tmp = a
        a = b
        b = tmp % b
        steps.append(a)
    return steps  # normally we'd want to return `a`
                  # but you want the steps not just the result

steps = gcd_steps(125 * 123 * 12314, 25 * 149)

# print the list with `->` between the steps
print(" -> ".join(str(x) for x in steps))

(結果は、リストの最後の要素を取得することでアクセスできる最後のステップになりますsteps[-1]:)

出力：

3725 -> 900 -> 125 -> 25
于 2013-10-05T22:23:47.407 に答える