おそらく私は質問を誤解しています。プロジェクト オイラーの問題 31に慣れていない人のために、ここに問題があります。
英貨単位の組み合わせを調査中。
イングランドでは、通貨はポンド (£) とペンス (p) で構成されており、一般に流通している硬貨は 8 種類あります。
1p、2p、5p、10p、20p、50p、£1 (100p)、£2 (200p)。
次の方法で £2 を作ることができます。
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
任意の数の硬貨を使って £2 を作るには、何通りの方法がありますか?
これが動的プログラミングの問題になる可能性があることはわかりましたが、近道を取らざるを得ませんでした。
これを解決するために、1 ペンス、1 ペンスと 2 ペンス、および 1 ペンスと 2 ペンスと 5 ペンスの硬貨を使って 1 ～ 6 ペンスを作る方法をいくつか調べました。
1ペニー硬貨のみ使用
- 1 組み合わせ
- 1p
- 1 組み合わせ
- 2×1p
- 1 組み合わせ
- 3×1p
- 1 組み合わせ
- 4×1p
- 1 組み合わせ
- 5×1p
- 1 組み合わせ
- 6×1p
1 ペンス硬貨と 2 ペンス硬貨のみを使用する
- 1 組み合わせ
- 1p
- 2つの組み合わせ
- 2p
- 2×1p
- 2つの組み合わせ
- 2p + 1p
- 3×1p
- 3つの組み合わせ
- 2×2p
- 2p + 2×1p
- 4×1p
- 3つの組み合わせ
- 2×2p＋1p
- 2p + 3×1p
- 5×1p
- 4つの組み合わせ
- 3×2p
- 2×2p + 2×1p
- 2p + 4×2p
- 6×2p
1 ペンス、2 ペンス、5 ペンスの硬貨のみを使用する
- 1 組み合わせ
- 1p
- 2つの組み合わせ
- 2p
- 2×1p
- 2つの組み合わせ
- 2p + 1p
- 3×1p
- 3つの組み合わせ
- 2×2p
- 2p + 2×1p
- 4×1p
- 4つの組み合わせ
- 5p
- 2×2p＋1p
- 2p + 3×1p
- 5×1p
- 5つの組み合わせ
- 5p + 1p
- 3×2p
- 2×2p + 2×1p
- 2p + 4×2p
- 6×2p
この狂気にはパターンがあることに気づきました。明らかに、1 種類のコインだけで目的の「バランス」を取得する方法は多くても 1 つしかありません。この問題の場合、ペニーの端数を考慮する必要はありません。したがって、1 ペニー硬貨のみを使用して、負でない残高を取得する方法は 1 つだけです。ゼロの残高を取得する方法は 1 つだけであることに注意してください: コインはありません。
ざっと見ただけで、2 番目の例のパターンに気付きました。可能な組み合わせの数は、n / 2 に 1 を足した商に等しくなります。ここで、n は負でない任意の整数です。Python (私がソリューションを書いた言語) では、これは次のようになります。
n // 2 + 1
+ 1その特定の「目標残高」に対して、前の例の結果が追加されていることに気付きました。一致？多分。しかし、3 番目の例を見た後、考えられる組み合わせの数は次のとおりであることにすぐに気付きました。
n // 5 + n // 2 + 1
8 つのコインすべてを説明するこのパターンを実装しました。
n // 200 + n // 100 + n // 50 + n // 20 + n // 10 + n // 5 + n // 2 + 1
200にn設定すると、答えは 178 であると推測されました。この数は私には理にかなっていますが、考えられるすべての組み合わせを自分で書くつもりはありません。ただし、Project Euler は、これは正しくないと述べています。
Web で、正しい解決策は 73682 であることがわかりました。
では、まだ読んでいるスタック オーバーフロー ユーザーへの質問ですが、私の推論の誤りはどこにあるのでしょうか。