解答
ア
解説
アルゴリズムの設計
このプログラムは，10 円玉の枚数を 0 枚→1 枚→2 枚… と増やしながら，残り金額（rest）を 1 円玉と 5 円玉で支払う組合せ数を加算していきます。
- 1 回のループで次の処理をします。
- `(rest ÷ 5 の商) ＋ 1`：rest 円を 5 円玉と 1 円玉で支払う方法の数
- 5 円玉 0 枚：1 円玉 rest 枚
- 5 円玉 1 枚：1 円玉 (rest-5) 枚
- ……
- 5 円玉 k 枚（k = rest ÷ 5 の商）：1 円玉 (rest – 5k) 枚
- 計 (rest ÷ 5 の商) ＋ 1 通り
- `rest ← rest – 10`：10 円玉を 1 枚追加した場合の残り金額へ
`(rest ÷ 5 の商) ＋ 1`としているのは、「5 円玉 0 枚」というケースを考慮する必要があるためです。(rest ÷ 5 の商)だけだと、5円玉が1枚～(rest ÷ 5 の商)枚のケースしかカバーできません。
n=12 の場合で確認
- 1回目のループ（10円玉0枚の場合：rest=12 でスタート）
- (12÷5の商)+1 = 2+1 = 3 で 3通り → count = 3
- 5円玉を 0枚、1枚、2枚使う3通りが発生
- rest = 2 として、次のループへ。
- 2回目のループ（10円玉1枚の場合：rest=2 でスタート）
- (2÷5の商)+1 = 0+1 = 1 で 1通り → count = 3 + 1 = 4
- 5円玉0枚のケース1通りだけ
- rest = -8 として、次のループへ。
- 3回目のループ（10円玉2枚の場合：rest=-8 でスタート）
- 元が12円なので、10円玉2枚のケースはあり得ない。よって、ここで処理終了とする。
ということで、この時点で count=4 となっており、4通りという結果が求められるので、問題文の説明（3 + 1 = 4）と一致します。
rest = 0 のケースが重要
rest = 0 の場合，(0 ÷ 5 の商) ＋ 1 = 1 が加算されます。これは「10 円玉を n÷10 枚使い，残りが 0 円 → 1 円玉 0 枚・5 円玉 0 枚の 1 通り」に相当します。
具体的には、元の n が 20 や 50 など、10の倍数だった場合に、ループの過程で rest=0 になるケースが発生します。（rest の値はループごとに必ず10減算されていくため）
n=20 の場合で確認
- 1回目のループ（10円玉0枚の場合：rest=20 でスタート）
- (20÷5の商)+4 = 4+1 = 5 で 5通り → count = 5
- 5円玉を 0枚～4枚使う5通りが発生
- rest = 10 として、次のループへ。
- 2回目のループ（10円玉1枚の場合：rest=10 でスタート）
- (10÷5の商)+1 = 2+1 = 3 で 3通り → count = 5 + 3 = 8
- 5円玉を 0枚、1枚、2枚使う3通りが発生
- rest = 0 として、次のループへ。
- 3回目のループ（10円玉2枚の場合：rest=0 でスタート）
- (0÷5の商)+1 = 0+1 = 1 で 1通り → count = 8 + 1 = 9
- 5円玉を 0枚、1円玉を0枚使う1通りが発生（＝10円玉のみ使う1通り）
- rest = -10 として、次のループへ。
- 4回目のループ（10円玉3枚の場合：rest=-10 でスタート）
- 元が20円なので、10円玉3枚のケースはあり得ない。よって、ここで処理終了とする。
といったように、rest = 0 になったときにもループに入る必要があることがわかります。
＊選択肢 エ だと rest=0 で処理が終了してしまうため不正解。
rest が負の値になるようなケースは、n=20 の場合の4回目ループなど、その枚数の10円玉を使うケースはあり得ない、という場合に起こります。負の値に対して、5円玉・1円玉を使って組み合わせが実現できるケースもありませんので、rest が負の値になってしまう場合は、それ以上組み合わせは増えません。
逆に rest が正の値になっているケースは、5円玉・1円玉を使って組み合わせが実現できるケースがまだ残っていることを示しています。この時点でループが終了してしまうと、n=12 の場合の2回目ループの処理が行われないことになってしまい、正しい組み合わせ数になりません。
＊選択肢 イ、ウ、オ、カ はこのケースに該当するため不正解。
ここまでの情報を踏まえると、rest が負の値になる = それ以上組み合わせが増えない ということになるので、restが負の値になった時点でループを終了させるのが正しい処理となります。
これを式の形に置き換えると、while(rest ≧ 0) という形にすれば、restが負の値になった時点でループを終了できるので、ア が正しいとなります。