【 問 題 】

50円玉が１枚、10円玉が９枚、 ５円玉が19枚、１円玉が99枚 ある。
これらの硬貨を使用して 99円 を作るには何通りあるか？

【 解 答 】

50円玉が R₅₀ 枚、10円玉が R₁₀ 枚、 ５円玉が R₅ 枚、１円玉が R₁ 枚 でちょうど 99円 になるとする。
　　　50×R₅₀ ＋ 10×R₁₀ ＋ 5×R₅ ＋ 1×R₁　＝　99

R₅₀ ＝ 0　のとき
　　10×R₁₀ ＝ 0　のとき　（ 実は 20 通りある ）
　　　　5×R₅ ＝ 0　のとき
　　　　　　R₁　＝　99　の１通り
　　　　5×R₅ ＝ 1　のとき
　　　　　　R₁　＝　94　の１通り
　　　　　　　　（ 略 ）
　　　　5×R₅ ＝ 19　のとき
　　　　　　R₁　＝　4　の１通り
　　10×R₁₀ ＝ 1　のとき　（ 実は 18 通りある ）
　　　　5×R₅ ＝ 0　のとき
　　　　　　R₁　＝　89　の１通り
　　　　5×R₅ ＝ 1　のとき
　　　　　　R₁　＝　84　の１通り
　　　　　　　　（ 略 ）
　　　　5×R₅ ＝ 17　のとき
　　　　　　R₁　＝　4　の１通り
　　10×R₁₀ ＝ 2　のとき　（ 実は 16 通りある ）
　　　　5×R₅ ＝ 0　のとき
　　　　　　R₁　＝　79　の１通り
　　　　5×R₅ ＝ 1　のとき
　　　　　　R₁　＝　74　の１通り
　　　　　　　　（ 略 ）
　　　　5×R₅ ＝ 15　のとき
　　　　　　R₁　＝　4　の１通り
　　　　　　　　（ 略 ）
　　　　　　　　（ 略 ）
　　10×R₁₀ ＝ ９　のとき　（ 実は ２通りある ）
　　　　5×R₅ ＝ 0　のとき
　　　　　　R₁　＝　9　の１通り
　　　　5×R₅ ＝ 1　のとき
　　　　　　R₁　＝　4　の１通り

よって、R₅₀ ＝ 0　のときの場合の数は、 20 ＋ 18 ＋ ・・・ ＋ 2　＝→　110 通り

R₅₀ ＝ 1　のとき
　　10×R₁₀ ＝ 0　のとき　（ 実は 10 通りある ）
　　　　5×R₅ ＝ 0　のとき
　　　　　　R₁　＝　49　の１通り
　　　　5×R₅ ＝ 1　のとき
　　　　　　R₁　＝　44　の１通り
　　　　　　　　（ 略 ）
　　　　5×R₅ ＝ 9　のとき
　　　　　　R₁　＝　4　の１通り
　　10×R₁₀ ＝ 1　のとき　（ 実は８通りある ）
　　　　5×R₅ ＝ 0　のとき
　　　　　　R₁　＝　39　の１通り
　　　　5×R₅ ＝ 1　のとき
　　　　　　R₁　＝　34　の１通り
　　　　　　　　（ 略 ）
　　　　5×R₅ ＝ 7　のとき
　　　　　　R₁　＝　4　の１通り
　　10×R₁₀ ＝ 2　のとき　（ 実は６通りある ）
　　　　5×R₅ ＝ 0　のとき
　　　　　　R₁　＝　29　の１通り
　　　　5×R₅ ＝ 1　のとき
　　　　　　R₁　＝　24　の１通り
　　　　　　　　（ 略 ）
　　　　5×R₅ ＝ 5　のとき
　　　　　　R₁　＝　4　の１通り
　　　　　　　　（ 略 ）
　　　　　　　　（ 略 ）
　　10×R₁₀ ＝ ４　のとき　（ 実は ２通りある ）
　　　　5×R₅ ＝ 0　のとき
　　　　　　R₁　＝　9　の１通り
　　　　5×R₅ ＝ 1　のとき
　　　　　　R₁　＝　4　の１通り

よって、R₅₀ ＝ 1　のときの場合の数は、 10 ＋ 8 ＋ 6 ＋ 4 ＋ 2　＝→　30 通り

したがって、答えは　110 ＋ 30　＝→　140 通り

　プログラミングして答えを確かめる：

　　　　 通り


プログラムの内容：