7. 数论算法

最大公约数（辗转相除法）

输入两个正整数，求它们的最大公约数。辗转相除法（欧几里得算法）比暴力遍历高效得多。

python

# 方法一：暴力遍历（从大到小找）
x = int(input('x = '))
y = int(input('y = '))
for i in range(x, 0, -1):
    if x % i == 0 and y % i == 0:
        print(f'最大公约数：{i}')
        break

python

# 方法二：辗转相除法（欧几里得算法）
# 原理：gcd(a, b) = gcd(b, a % b)，直到 a % b == 0
x = int(input('x = '))
y = int(input('y = '))
while y % x != 0:
    x, y = y % x, x  # 多重赋值：同时更新 x 和 y
print(f'最大公约数：{x}')

💡 多重赋值

x, y = y % x, x 先计算右边的 y % x 和 x，然后同时赋值给左边的 x 和 y。不需要临时变量即可完成交换。

百钱百鸡问题

公鸡 5 钱一只，母鸡 3 钱一只，小鸡 1 钱三只。用 100 钱买 100 只鸡，公鸡、母鸡、小鸡各多少只？

python

# 穷举法：三重循环（低效版本）
for i in range(0, 21):       # 公鸡最多 20 只
    for j in range(0, 34):   # 母鸡最多 33 只
        for k in range(0, 100):  # 小鸡最多 99 只
            if 5*i + 3*j + k/3 == 100 and i + j + k == 100:
                print(f"公鸡{i}只，母鸡{j}只，小鸡{k}只")

▶ 运行结果：

输出

公鸡0只，母鸡25只，小鸡75只
公鸡4只，母鸡18只，小鸡78只
公鸡8只，母鸡11只，小鸡81只
公鸡12只，母鸡4只，小鸡84只

python

# 优化版本：两重循环，小鸡数量 = 100 - 公鸡 - 母鸡
for i in range(0, 21):       # 公鸡
    for j in range(0, 34):   # 母鸡
        k = 100 - i - j      # 小鸡数量由总数推出
        if 5*i + 3*j + k/3 == 100:
            print(f"公鸡{i}只，母鸡{j}只，小鸡{k}只")

▶ 运行结果：

输出

公鸡0只，母鸡25只，小鸡75只
公鸡4只，母鸡18只，小鸡78只
公鸡8只，母鸡11只，小鸡81只
公鸡12只，母鸡4只，小鸡84只

💡 穷举法优化思路

当三个变量满足 i + j + k = 100 时，已知 i 和 j 就能算出 k，无需第三重循环。减少一层循环可将效率提升数十倍。