计数步骤python中的欧几里德算法程序(counting

计数步骤python中的欧几里德算法程序(counting-steps Euclidean algorithm program in python)

我需要一个程序来计算Euclid算法在Python中查找gcd（a，b）所需的步数。 该计划可能基于Lam'e定理。 到目前为止，我刚刚得到了简单的欧几里得算法程序：

def gcd(a, b): while b: a, b = b, a%b return a

我不知道如何编写我需要的程序。

I need a program to count the number of steps required by Euclid’s algorithm to find gcd(a, b) in Python. The program may based on Lam´e’s theorem. I just got the simple Euclidean algorithm program so far which is:

def gcd(a, b): while b: a, b = b, a%b return a

I have no idea how to write the program I need.

最满意答案

初始化一个计数器整数对象， count为零并在每次循环循环时递增它：

def gcd(a, b): count = 0 while b: a, b = b, a%b count += 1 print(count) return a

拉姆定理说，步count ， count永远不会超过b中数字的5倍（数字越小）。 要验证这一点：

import math def gcd(a, b): ndigits = int(math.log10(b)) + 1 count = 0 while b: a, b = b, a%b count += 1 print(count) print("Lame's theorem holds?", count <= 5*ndigits) return a

Initialize a counter integer object, count to zero and increment it each time round the loop:

def gcd(a, b): count = 0 while b: a, b = b, a%b count += 1 print(count) return a

Lamé's theorem says that the number of steps, count will never exceed 5 times the number of digits in b (the smaller number). To verify this:

import math def gcd(a, b): ndigits = int(math.log10(b)) + 1 count = 0 while b: a, b = b, a%b count += 1 print(count) print("Lame's theorem holds?", count <= 5*ndigits) return a