python - 欧拉计划挑战的逻辑谬误 31

Question

也许我误解了这个问题。对于那些不熟悉 Project Euler's Problem 31 的人，这里是问题所在:

Investigating combinations of English currency denominations.

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

可以通过以下方式赚取 2 英镑:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

使用任意数量的硬币可以有多少种不同的方式来制作 2 英镑？

我知道这怎么可能是一个动态规划问题，但我忍不住走捷径:

为了解决这个问题，我分解了使用 1p、1p 和 2p 以及 1p、2p 和 5p 硬币赚取 1 到 6 便士的方法有多少种。

仅使用一便士硬币

1. 1个组合
   • 1p
2. 1个组合
   • 2×1p
3. 1个组合
   • 3×1p
4. 1个组合
   • 4×1p
5. 1个组合
   • 5×1p
6. 1个组合
   • 6×1p

---

仅使用一便士和两便士硬币

1. 1个组合
   • 1p
2. 2 种组合
   • 2p
   • 2×1p
3. 2 种组合
   • 2p + 1p
   • 3×1p
4. 3 种组合
   • 2×2p
   • 2p + 2×1p
   • 4×1p
5. 3 种组合
   • 2×2p + 1p
   • 2p + 3×1p
   • 5×1p
6. 4 种组合
   • 3×2p
   • 2×2p + 2×1p
   • 2p + 4×2p
   • 6×2p

---

仅使用一便士、两便士和五便士硬币

1. 1 种组合
   • 1p
2. 2 种组合
   • 2p
   • 2×1p
3. 2 种组合
   • 2p + 1p
   • 3×1p
4. 3 种组合
   • 2×2p
   • 2p + 2×1p
   • 4×1p
5. 4 种组合
   • 5p
   • 2×2p + 1p
   • 2p + 3×1p
   • 5×1p
6. 5 种组合
   • 5p + 1p
   • 3×2p
   • 2×2p + 2×1p
   • 2p + 4×2p
   • 6×2p

我注意到这种疯狂有一种模式。显然，最多只有一种方法可以只使用一种硬币来获得所需的“余额”。对于这个问题的情况，不用计入零头。因此，仅使用一便士硬币，只有一种方法可以获得任何非负余额。请注意，只有一种方法可以获得零余额:没有硬币。

快速浏览了一下，我注意到第二个示例中的一个模式。可能组合的数量等于 n/2 加 1 的商，其中 n 是任何非负整数。在 Python(我编写解决方案的语言)中，这看起来像下面这样:

n // 2 + 1

我注意到 + 1 正在为特定的“目标余额”添加上一个示例的结果。巧合？或许。但是在查看第三个示例之后，我很快注意到可能的组合数量如下:

n // 5 + n // 2 + 1

我实现了这个模式，它可以解释所有八个硬币:

n // 200 + n // 100 + n // 50 + n // 20 + n // 10 + n // 5 + n // 2 + 1

将 n 设置为 200，我推断答案是 178。这个数字对我来说很有意义，但我不会自己写出所有可能的组合。然而，Project Euler 声明这是不正确的。

我在网上查到正确答案是73682。

所以我想问你，仍在阅读的 Stack Overflow 用户，我的推理中的谬误在哪里？

Answer 1

仅使用 [1, 2, 5] 制作 10p 的正确组合数是 10，而您的解决方案给出 10/5 + 10/2 + 1 = 2 + 5 + 1 = 8。显然您的假设是不正确的.

错误在于您只是在尝试一些案例，并假设适用于少数小案例的方法适用于所有案例，而没有任何证据。