Project Euler第31题暴力解法结果错误（73681≠73682）求助

你的代码返回结果比正确答案少1，核心原因是漏掉了使用单个£2（200p）硬币凑成200p的情况。

错误分析 #

题目中的8种硬币包含£2（200p），但你的代码只处理了7种：£1（100p）、50p、20p、10p、5p、2p，最后用1p补全。在你的循环结构里，没有任何变量对应£2硬币的数量——唯一能凑出200p的方式是两个£1硬币，但直接用一个£2硬币的组合完全没被统计到，这正好是缺失的那1种。

另外，你代码中最后判断总和<=200的逻辑是对的：因为剩下的金额可以用1p硬币补足，每种总和≤200的情况对应唯一一种凑200p的方式（加上对应数量的1p），这部分没有问题。

修正后的代码 #

只需要添加一个对应£2硬币数量的循环（范围是0或1，因为2×200=400>200），并在总和计算中加入200p的面值：

counter = 0
# 新增£2硬币的循环，数量只能是0或1
for two_pound in range(2):
    for one_pound in range(3):
        total = 200 * two_pound + 100 * one_pound
        if total > 200:
            break
        for fifty_p in range(5):
            total_50 = total + 50 * fifty_p
            if total_50 > 200:
                break
            for twenty_p in range(11):
                total_20 = total_50 + 20 * twenty_p
                if total_20 > 200:
                    break
                for ten_p in range(21):
                    total_10 = total_20 + 10 * ten_p
                    if total_10 > 200:
                        break
                    for five_p in range(41):
                        total_5 = total_10 + 5 * five_p
                        if total_5 > 200:
                            break
                        for two_p in range(101):
                            current_total = total_5 + 2 * two_p
                            if current_total <= 200:
                                counter += 1
print(counter)

验证 #

当two_pound=1，其他所有变量都为0时，current_total=200，会被计入counter，补上了缺失的那1种组合。运行修正后的代码，结果会正确输出73682。

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