欧拉挑战项目的逻辑谬误31

Question

也许我误解了这个问题.对于那些不熟悉Project Euler问题31的人来说,问题是:

调查英国货币面额的组合.

在英格兰,货币由英镑,英镑和便士p组成,一般流通中有八个硬币:

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

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

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

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

我看到这可能是一个动态编程问题,但我忍不住走捷径:

为了解决这个问题,我分解了使用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这个数字对我来说很有意义,不过,我不会给自己写的所有可能的组合.但是,欧拉计划表明这是不正确的.

我在网上发现正确的解决方案是73682.

所以我的问题,Stack Overflow用户还在阅读,我的推理中的谬误在哪里？

Answer 1

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

错误在于您只是尝试了一些案例并假设适用于少数案例的案例适用于所有案例,没有任何证据.