基于Stern-Brocot序列处理分数列表时Python出现内存错误

看起来你遇到了典型的组合爆炸导致的内存溢出问题——这两个规则如果不加限制地应用，会让分数数量指数级增长，很快把内存吃光。让我们一步步拆解问题并给出解决方案：

一、内存错误的核心原因 #

• 规则2的无限制组合：任意两个分数生成新分数，假设列表有n个分数，就会产生n*(n-1)/2个新分数，每个新分数又会和现有分数继续组合，数量呈指数级膨胀，短时间内就会耗尽内存。
• 规则1的叠加效应：每个分数都会生成对应的b/(2a)，进一步扩大分数池，加剧内存消耗。
• 无终止条件的无限生成：Stern-Brocot序列本身是无限的，再加上两个扩展规则，程序会一直生成分数直到内存被占满。

二、针对性解决方案 #

1. 必须设定明确的终止条件 #

你需要给生成的分数设定边界，比如：

• 限制分子与分母的总和（如分子+分母 ≤ N）
• 限制分子/分母的最大值（如分子 ≤ 100且分母 ≤ 100）
• 限制生成的分数总数上限
• 只生成指定数值区间内的分数（如0到1之间）

2. 用集合替代列表存储分数 #

列表的查找效率是O(n)，而集合是O(1)，用集合可以快速检查分数是否已存在，避免重复存储相同的最简分数，大幅减少内存占用。我们可以用元组(a, b)存储最简分数（元组是可哈希的，能放进集合）。

3. 迭代生成+增量更新 #

不要一次性生成所有可能的分数，而是用迭代的方式：每次从现有集合中取出元素应用规则，生成新分数后先检查是否符合终止条件、是否已存在，再加入集合。这样可以逐步扩展，避免一次性爆内存。

4. 优化规则2的应用 #

规则2不需要对所有两两组合都生成新分数，这会导致大量无效操作。可以参考Stern-Brocot树的生成逻辑，只对相邻分数生成中间分数，或者仅让新增分数与现有分数组合，减少不必要的计算。

三、示例代码实现 #

下面是一个带终止条件（分子分母总和不超过指定值）的实现，用集合存储，迭代生成符合规则的分数：

import math

def reduce_fraction(a, b):
    """将分数a/b约分为最简形式，确保分母为正"""
    if b == 0:
        raise ValueError("分母不能为0")
    # 保证分母为正，统一分数的符号
    sign = 1 if b > 0 else -1
    gcd_val = math.gcd(abs(a), abs(b))
    return (sign * (a // gcd_val), abs(b) // gcd_val)

def generate_restricted_fractions(max_sum):
    # 用集合存储最简分数，避免重复
    fractions = set()
    # 从Stern-Brocot序列的初始元素开始（比如(1,1)）
    initial_frac = reduce_fraction(1, 1)
    if sum(initial_frac) <= max_sum:
        fractions.add(initial_frac)
    
    # 迭代更新，直到没有新分数可以加入
    updated = True
    while updated:
        updated = False
        # 复制当前集合，避免迭代时修改原集合导致异常
        current_fracs = list(fractions)
        
        # 应用规则1：每个a/b必须存在b/(2a)
        for a, b in current_fracs:
            new_a, new_b = b, 2 * a
            reduced_new = reduce_fraction(new_a, new_b)
            if sum(reduced_new) <= max_sum and reduced_new not in fractions:
                fractions.add(reduced_new)
                updated = True
        
        # 应用规则2：优化为仅对现有分数两两组合，但加入总和限制（可进一步优化为相邻分数组合）
        for i in range(len(current_fracs)):
            a1, b1 = current_fracs[i]
            for j in range(i + 1, len(current_fracs)):
                a2, b2 = current_fracs[j]
                new_a = a1 + b1
                new_b = a2 + b2
                reduced_new = reduce_fraction(new_a, new_b)
                if sum(reduced_new) <= max_sum and reduced_new not in fractions:
                    fractions.add(reduced_new)
                    updated = True
    
    # 转换为有序列表返回（按分数值排序）
    return sorted(fractions, key=lambda x: (x[0]/x[1], x[0], x[1]))

# 测试：限制分子分母总和不超过20
try:
    result = generate_restricted_fractions(20)
    print("生成的最简分数列表：")
    for num, den in result:
        print(f"{num}/{den}")
except MemoryError:
    print("内存错误：请缩小max_sum的取值")

四、额外优化建议 #

• 使用生成器：如果需要处理更大范围的分数，可以用生成器逐个输出分数，而不是一次性存储所有结果，内存占用会极低。
• 规则2的深度优化：参考Stern-Brocot树的生成方式，仅在相邻分数之间生成中间分数，这样既符合规则2，又能避免大量无效组合，保证生成效率。
• 记录已处理的组合：用哈希表记录已经生成过的分数组合，避免重复生成相同的(a+b)/(c+d)。

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