硬貨の組合せ計算アルゴリズム

■ 解き方の方針 restが何を表すかを先に固定します。restは、10円玉の枚数を決めた後に、1円玉と5円玉で作るべき 残額 です。ループを続ける境界が0を含むかどうかがポイントです。 ■ 1回のループで数えているもの 初期状態： rest＝nなので、10円玉を0枚使う場合を数えます。 組合せ数： 5円玉を0枚からrest÷5の商まで選べます。5円玉の枚数を決めると1円玉の枚数は一意に決まるため、組合せは「rest÷5の商＋1」通りです。 次の状態： restから10を引き、10円玉を1枚多く使う場合へ進みます。 ■ 境界値rest＝0を確認する rest＝0は処理不要な状態ではありません。残額0円を1円玉0枚、5円玉0枚で作る 1通り を数える必要があります。式でも0÷5の商＋1＝1になります。 例えばn＝20なら、restは20→10→0→－10と変化します。rest＝0の回も数え、－10になった時点で終了するのが正しい動きです。 10円玉の枚数 rest（残額） 5円玉の枚数の選び方 数える組合せ 0枚 20 0〜4枚 20÷5の商＋1＝5 1枚 10 0〜2枚 10÷5の商＋1＝3 2枚 0 0枚だけ 0÷5の商＋1＝1 （終了） −10 − rest≧0 が偽 n＝20 の組合せは $5+3+1=9$ 通りです。rest＝0 の行を数えないと8通りになってしまいます。 ループはrestが0以上の間だけ続けるので、条件は $rest \ge 0$ です。 ■ 正解と誤答の見分け方 正解は ア です。$rest \gt 0$ではrest＝0の1通りを落とします。$rest \ge 5$や$rest \ge 10$では、1円玉と5円玉で作れる正の残額まで途中で除外してしまいます。

次のプログラム中の 　　 に入れる正しい答えを、解答群の中から選べ。
関数 changeは、10より大きい整数を引数nで受け取り、1円玉,5円玉,10円玉を使ってちょうどn円にする組合せの総数を返す。

例えば、12円にする組合せは、次のように数えられる。10円玉を使わない場合には、1円玉と5円玉だけでちょうど12円にすることになる。その組合せは、使える5円玉の枚数が0以上 (12÷5の商) 以下なので、 (12÷5の商) + 1 = 3通りある。同様に、10円玉を1枚使う場合には、1円玉と5円玉だけでちょうど2円にすることになり、その組合せは (2÷5の商) + 1 = 1通りある。10円玉を2枚以上使う組合せはない。よって、1円玉,5円玉 10円玉を使ってちょうど12円にする組合せは、 3+1=4 通りである。

[プログラム]
○整数型:change(整数型:n)
整数型:count ← 0
整数型:rest ← n
while ( 　　 )
count ← count + (rest ÷ 5の商) + 1
rest ← rest - 10
endwhile
return count

出典令和7年度 基本情報技術者試験 科目B 問2
ア
rest≥0rest \ge 0
イ
rest≥5rest \ge 5
ウ
rest≥10rest \ge 10
エ
rest>0rest \gt 0
オ
rest>5rest \gt 5
カ
rest>10rest \gt 10