如何实现统计欧几里得算法调用次数的number_of_steps_EA函数

方案一：使用全局计数器 #

这种方法直接通过全局变量记录函数调用次数，在原算法函数中更新计数，再通过number_of_steps_EA完成计数器初始化、算法调用和结果输出。

完整代码：

from math import floor

# 全局计数器变量
call_count = 0

def Euclidean_algorithm(a, b, verbose=True):
    global call_count
    call_count += 1  # 每次调用函数时计数+1
    
    if a < b:
        return Euclidean_algorithm(b, a, verbose)
    
    if verbose:
        print()
    while b != 0:
        if verbose:
            print('%s = %s * %s + %s' % (a, floor(a/b), b, a % b))
        (a, b) = (b, a % b)
            
    if verbose:
        print('The GCD is %s' % a)
    return a

def number_of_steps_EA(a, b):
    global call_count
    call_count = 0  # 每次调用前重置计数器
    gcd = Euclidean_algorithm(a, b, verbose=False)  # 关闭打印避免干扰
    print(f"找到最大公约数{gcd}前，函数共调用了{call_count}次")
    return gcd, call_count

方案二：避免全局变量（更推荐） #

全局变量易引发状态污染，可通过嵌套函数或传递可变对象实现计数，保持代码封装性。

嵌套函数实现 #

from math import floor

def Euclidean_algorithm(a, b, verbose=True):
    if a < b:
        return Euclidean_algorithm(b, a, verbose)
    
    if verbose:
        print()
    while b != 0:
        if verbose:
            print('%s = %s * %s + %s' % (a, floor(a/b), b, a % b))
        (a, b) = (b, a % b)
            
    if verbose:
        print('The GCD is %s' % a)
    return a

def number_of_steps_EA(a, b):
    call_count = 0
    
    # 包装原算法函数，追踪调用次数
    def wrapped_EA(x, y, verbose=True):
        nonlocal call_count
        call_count += 1
        return Euclidean_algorithm(x, y, verbose)
    
    gcd = wrapped_EA(a, b, verbose=False)
    print(f"找到最大公约数{gcd}前，函数共调用了{call_count}次")
    return gcd, call_count

传递可变对象实现 #

通过列表（可变对象）传递计数器，直接在原算法函数内更新计数：

from math import floor

def Euclidean_algorithm(a, b, verbose=True, counter=None):
    if counter is not None:
        counter[0] += 1
    
    if a < b:
        return Euclidean_algorithm(b, a, verbose, counter)
    
    if verbose:
        print()
    while b != 0:
        if verbose:
            print('%s = %s * %s + %s' % (a, floor(a/b), b, a % b))
        (a, b) = (b, a % b)
            
    if verbose:
        print('The GCD is %s' % a)
    return a

def number_of_steps_EA(a, b):
    counter = [0]  # 用列表存储计数，实现可变传递
    gcd = Euclidean_algorithm(a, b, verbose=False, counter=counter)
    print(f"找到最大公约数{gcd}前，函数共调用了{counter[0]}次")
    return gcd, counter[0]

补充说明 #

• 上述方案统计的是函数调用次数，包括a < b时的递归调用。例如计算gcd(3,9)时，原函数会先调用Euclidean_algorithm(9,3)，总调用次数为2次。
• 如果需要统计循环迭代步数（而非函数调用次数），可修改逻辑在循环内计数：

def number_of_iteration_steps(a, b):
    if a < b:
        a, b = b, a
    steps = 0
    while b != 0:
        steps +=1
        a, b = b, a % b
    print(f"找到最大公约数{a}共执行了{steps}次循环迭代")
    return a, steps

内容的提问来源于stack exchange，提问作者Spuddy