問2 硬貨の組合せの数を数える繰返しの条件

基本情報​技術者試験 令和7年度 公開問題 科目B、全6問のうちの問2。

出典:令和7年度 基本情報技術者試験 公開問題 科目B 問2(プログラムは原本の画像を文字に書き起こし、字下げは 1 段を空白 2 つで表した。空欄は[  ]で表した)

次のプログラム中の[  ]に入れる正しい答えを,解答群の中から選べ。

関数 change は,1⁠0 より大きい整数を引数 n で受け取り,1 円玉,5 円玉,1⁠0 円玉を使ってちょうど n 円にする組合せの総数を返す。

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

〔プログラム〕
○整数型: change(整数型: n)
整数型: count ← 0
整数型: rest ← n
while ([  ])
count ← count + (rest ÷ 5 の商) + 1
rest ← rest - 10
endwhile
return count
  1. アrest ≧ 0
  2. イrest ≧ 5
  3. ウrest ≧ 1⁠0
  4. エrest > 0
  5. オrest > 5
  6. カrest > 1⁠0
答えと解説を開く

正解はアです。

繰返しの 1 回目は 1⁠0 円玉を 0 枚使う場合、2 回目は 1 枚使う場合、と 1⁠0 円玉を 1 枚ずつ増やします。rest は残りの金額で、その残りを 1 円玉と 5 円玉で払う方法は (rest ÷ 5 の商) + 1 通りです。残りが 0 円のときも、1 円玉も 5 円玉も使わない 1 通りがあり、式も (0 ÷ 5 の商) + 1 = 1 です。残りが負になったら、1⁠0 円玉を使いすぎなので止めます。だから条件は rest ≧ 0 です。n = 1⁠2 で追うと、rest = 1⁠2 で count = 0 + 2 + 1 = 3、rest ← 2、rest = 2 で count = 3 + 0 + 1 = 4、rest ← −8 で止まり、4 を返します。n = 2⁠0 では、rest = 2⁠0 で count = 0 + 4 + 1 = 5、rest = 1⁠0 で 5 + 2 + 1 = 8、rest = 0 で 8 + 0 + 1 = 9、rest ← −1⁠0 で止まり、9 を返します。1⁠0 円玉 2 枚の 1 通りまで数えられています。正解はアです。

ほかの選択肢が違う理由

  • イ残りが 0 から 4 円の場合を数えません。n = 1⁠2 では rest = 2 の回を飛ばし、3 を返します。
  • ウ残りが 1⁠0 円未満の場合を数えません。n = 1⁠2 では rest = 2 の回を飛ばし、3 を返します。
  • エ残りがちょうど 0 円の場合を数えません。n = 1⁠2 では 4 で合いますが、n = 2⁠0 では rest = 0 の回 (1⁠0 円玉 2 枚) を飛ばし、8 を返します。
  • オ残りが 5 円以下の場合を数えません。n = 1⁠2 では rest = 2 の回を飛ばし、3 を返します。
  • カ残りが 1⁠0 円以下の場合を数えません。n = 1⁠2 では rest = 2 の回を飛ばし、3 を返します。

仕組み

組合せの数は、大きい硬貨の枚数を 1 つ決めるごとに、残りを小さい硬貨で払う方法を数えて足すと求められます。ここでは 1⁠0 円玉の枚数で場合を分けています。

繰返しの条件は、境目の値 (ここでは残りがちょうど 0 円) で 1 回多く回るか少なく回るかを決めます。境目の値を入れて 1 回だけ追うと、≧ と > の違いが見えます。

この問に出る言葉