「最小交換貨幣枚数」による上手な払い方
冨澤眞樹（前橋工科大学）
令和7年度大学入学共通テスト試作問題「情報Ⅰ」の第3問を取り上げる．第3問は，釣り銭に関する問題であり，アルゴリズムに関連した問題である．キーワード “お釣り 最適化” や “お釣り 最小” でネット検索すれば，釣り銭に関する問題やアルゴリズムに関するウェブサイトが多く見つかる．釣り銭問題は馴染みのある問題なのだろう．しかし，電子マネーやバーコード決済を使っている受験生には，釣り銭問題は馴染みが薄いかもしれない．試作問題としては良い題材だが，令和時代の問題としてはちょっと古臭いかな．それでは，昭和時代の私が，問1から解説していく．解説では，正解だけでなく，解答群にある誤選択肢（錯乱肢）についても触れる．
問1は，最小交換貨幣枚数と関数「枚数(金額)」の理解を問う問題である．この問1の内容が理解できれば，問2と問3は見通しよく解けるだろう．それでは，問題文を見てみよう．
下線Bが「上手な払い方」である．このような払い方を実生活でも実践していれば，「上手な払い方」の意味はすぐに分かるだろう．この上手な払い方を，下線Cのように定式化し，それを「最小交換硬貨枚数」と呼んでいる．
（ア）の正解は，下線Aに6枚と書いてあり，数字の6である．ここで，【関数の説明と例】を読んで，関数「枚数(46)」の戻り値は6になることを理解しておこう．
（イ）について考える．下線Dより，客から店に支払う枚数が枚数(51)，店から客に支払う枚数が枚数(5)なので，（イ）の正解は⓪枚数(51)＋枚数(5)である．あるいは，“客が51円支払う”ので，枚数(46)の計算は不適であり，枚数(46)を含む解答群①と③は誤選択肢である．また枚数の合計を求めるので，減算を含む②も誤選択肢である．このように消去法で考えると，残りの⓪が正解になる．
正解を得るには，問題を解いて正攻法で正解を得る方法と，解答群から消去法で正解を得る方法がある．両方が使える場合は，正攻法で解いて，消去法で検算するのがよいだろう．
（ウ）と（エ）は，この問題の要である．
（イ）の正解が⓪枚数(51)＋枚数(5)なので，商品の価格が46円の場合は，51円支払って，5円の釣り銭を受け取ればよいことが分かる．商品の価格x円と釣り銭y円に，具体例を当てはめれば，x＝46，y＝5，x＋y＝51となる．したがって，（ウ）と（エ）の正解は，順不同で，①yと②x＋yである．選択肢②x＋yは客から店に支払う金額である．xが価格，yが釣り銭であることが分かれば，ウ・エの解答群にある価格xから釣り銭yを引くという③x−yは，誤選択肢らしいと分かる．
入試問題では，問1が，その後の問いを解くための前提条件となっていることが多い．このため，問1にあるT先生とSさんの会話も一字一句漏らさず理解しておこう．問1の問題文から分かることを整理する．要点は次の4つである．
価格はx，釣り銭はy，客から店に支払う金額はx＋yである．
下線Eと下線Gより，yは0から99まで調べる．
硬貨枚数の合計は枚数(x＋y)＋枚数(y)で計算できる．
下線Fの意味は，yを0から99まで変化させながら，枚数(x＋y)＋枚数(y)の一番小さな値を見つける，である．
問2について考える．（オ）と（カ）は，演算子「÷」と「%」の使い方を問う問題である．金額が46円で支払いに10円玉を使う場合，支払う10円玉の枚数は46÷10＝4枚，残金は46%10＝6円と計算できる．演算子「÷」を使うと枚数が求まり，演算子「%」を使うと金額が求まる．枚数を求める（オ）の正解は②46÷10，残金を求める（カ）の正解は③46%10である．オ・カの解答群の⓪と①は，見るからに “＋1” や “−1” が怪しいので，誤選択肢らしいと分かる．現状では，受験生にとって演算子「%」は馴染みが薄いかもしれないが，情報Ⅰが浸透すれば，このような基本的な演算子の使い方を問う問題はなくなるだろう．
次の問題文と図1を見て，（キ）から（コ）について考える．
（キ）について考える．変数iがどのように使われるかが分かると簡単である．ケ・コの解答群を見ると，Kouka[i]って書いてある！ 解答群にヒントがある場合がある．また，下線Hと下線Iより，Kouka[i]は100, 50, …, 5, 1となればよい．すなわち，Kouka[i]は，Kouka[4], Kouka[3], …, Kouka[0]と変化すればよい．（キ）の正解は①4から0まで1ずつ減らし，である．解答群の⓪と③は，配列の添え字が1から始まる場合には正解かもしれない選択肢である．現在の受験生が学ぶプログラミング言語の配列は，ほとんど（すべて？）0から始まる．このことより，受験生が⓪と③を選択することはないだろう．私（本解説の著者）としては，高額の貨幣から使うので，Kouka = [100, 50, 10, 5, 1]として，（キ）の正解は②0から4まで1ずつ増やし，とする方が好みである．これだとキの難易度は少し下がるだろう．
（ク）について考える．図1の(3)行目より，maisuの初期値は0である．下線Jより，図1のプログラムの(5)行目は，maisu = maisu + ケという式になる．（ク）の正解は①maisuである．
（ケ）と（コ）について考える．解答群は同じなので，（ケ）と（コ）は同時に考えていこう．maisuは硬貨の枚数を保持し，nokoriは残金を保持する．ここで，（オ）と（カ）の正解を思い出してほしい．演算子「÷」を使うと枚数が求まり，演算子「%」を使うと残金が求まる．図1の(5)行目は maisu = maisu + ケより，（ケ）は額面がKouka[i]の硬貨の枚数である．すなわち（ケ）の正解は⓪nokori ÷ Kouka[i] である．
図1の(3)行目を見ると，nokori = kingakuとある．nokoriは，初期値がkingakuであり，繰り返すごとに，額面Kouka[i]の硬貨で支払ったあとの残金となる．残金を求めるには演算子「%」を使えばよいので，（コ）の正解は①nokori % Kouka[i]である．
ここで，演算子「÷」と「%」について復習しておこう．nokoriの値よりKouka[i]の方が大きい場合，nokori ÷ Kouka[i]の値は0となり，nokori % Kouka[i]の値はnokoriと同じになる．これは，図1の(5)と(6)行目で，nokoriの値よりKouka[i]の方が大きい場合，maisuは増えずnokoriは減らないこと，すなわちKouka[i]に対応する硬貨は使わない，ことを意味する．
ケ・コの解答群を見てみよう．解答群の②と③は枚数maisuを硬貨1枚当たりの金額Kouka[i]で割っているので，枚数÷金額／枚数すなわち「枚数を1枚当たりの金額で割った数」となる．これが金額であるとは思えないので，②と③は誤選択肢らしいと分かる．解答群の⓪と①は，金額÷金額／枚数すなわち「金額を1枚当たりの金額で割った数」なので，これはなんらかの枚数であると推測できる．このように，（ケ）と（コ）については，解答群を見ただけで，正解の見当がつけられる．
さて，図1のプログラムは，最小の硬貨枚数を計算すると書いてあるが，硬貨の額面が異なる場合でも必ずそうなるだろうか．たとえば，Kouka = [1, 5, 20, 40, 50, 100]で，金額が80円だとする．図1のプログラムは高額硬貨から優先して支払うので，金額80円の場合は，50円玉1枚＋20円玉1枚＋5円玉2枚で，枚数は4枚になる．これは最小の硬貨枚数ではない．最小の硬貨枚数は，40円玉2枚で，枚数は2枚である．図1のプログラムが，最小の硬貨枚数を計算できるかどうかは，配列Koukaの値と関係している．高額貨幣から優先して支払う方法は，いつも最小の硬貨枚数が計算できるわけではない．しかし，現実社会では，20円玉や40円玉はないので，図1のプログラムで最小の硬貨枚数が計算できる．安心してください．
問3について考える．
T先生は，図1のプログラムを使って，関数「枚数(金額)」のプログラムができるといっている．しかし，下線Kについては，参考文献¹⁾ ²⁾を見ても，具体的な書き方は分からない．関数の戻り値の書き方は，必要に応じて公開されるだろう．また，図1のプログラムで使われたmaisu，nokori，Koukaについては，問3では使われない．これらの変数は，関数「枚数(金額)」の中だけで使われる変数である．
問3では，関数「枚数(金額)」が使える前提で解けばよい．それでは，問3の問題文をよく読むことにしよう．
まず，問1の4つの要点を思い出そう．この問題文から，商品の価格xがkakakuに，釣り銭yがtsuriに対応することが分かる．また，下線Lは，問1の下線E，FとGに対応する．そして，問1の2番目の要点 “yは0から99まで調べる” は，tsuriは0から99まで調べる，と読み換えることができる．それでは，図2の（サ）から（タ）について考えていこう．
（サ）と（シ）について考える．99まで1ずつ増やす変数は，tsuriであり，初期値は0である．（サ）の正解は③tsuriであり，（シ）の正解は⓪0である．
（ス）と（セ）について考える．これらは，問1の4番目の要点である “枚数(x＋y)＋枚数(y)” に対応する．“枚数(x＋y)” は枚数(kakaku + tsuri)となるが，これは解答群にはない．図2の(4)行目を見ると，shiharai = kakakku + tsuriとなっている．（ス）と（セ）の正解は，順不同で，⓪枚数(shiharai)と②枚数(tsuri)である．
（ソ）と（タ）について考える．下線Mより，(5)行目で計算したmaisuがmin_maisuより小さい場合，min_maisuをmaisuで更新すればよい．（ソ）の正解は⓪maisuであり，（タ）の正解は①min_maisuである．
さて，図2のプログラムの(6)行目を，maisu ≦ min_maisu に変更したら，どうなるだろうか．この変更でも最小交換硬貨枚数は正しく求まる．Kouka = [1,5,10,50,100]では，この変更の影響はない．もし，10円玉と50円玉の代わりに30円玉と40円玉があるとすると，Kouka = [1, 5, 30, 40, 100]となる．このKoukaで，金額75円の最小交換硬貨枚数を求めてみる．最小交換硬貨枚数は3枚である．そうなる払い方は，枚数(75)＋枚数(0)，枚数(80)＋枚数(5)，枚数(105)＋枚数(30)の3通りである．(6)行目を，maisu < min_maisu とした場合は枚数(75)＋枚数(0)が求まり，maisu ≦ min_maisu とした場合は枚数(105)＋枚数(30)が求まる．現実的には，30円玉と40円玉はないので，このようなことはないが，プログラム中に大小比較があったときは，こんな風にいろいろ検討してみるとよい．
プログラムを書くと，そのプログラムの実行時間が気になるだろう．図1のプログラムの実行時間は，実行時間の大半を占める繰り返し部分だけに注目し，(4)行目からの繰り返し回数と比例すると考えられる．繰り返す回数は，kingakuの値に関係なく，配列Koukaの要素数と同じ5回になる．
図2のプログラムの実行時間はどうだろうか．注目するのは，図2の(3)行目からの繰り返し回数である．商品の価格が100円以下だと，0から99までなので100回になる．商品の価格が1,000円以下だと，(3)行目を，tsuriを0から999まで1ずつ増やしながら繰り返す，と変更するので，0から999までの1,000回になる．商品の価格に応じて，繰り返す回数が増えるので，実行時間も長くなる．図2のプログラムは，払い枚数と釣り銭枚数の組合せを求めながら，その中から最小交換硬貨枚数を見つけている．図2のプログラム（アルゴリズム）は，図1のプログラムと比べて，効率が悪いといえる．ここでは，実行時間の代わりに繰り返し回数でプログラム（アルゴリズム）の効率を評価してみた．このような評価を計算量という．
第3問は，「最小交換硬貨枚数」について，問1で定式化し，問3で，そのプログラムを扱っている．問2は，問3の2カ所で使われる関数「枚数(金額)」を扱っている．問1から問3までの流れは，受験生にとって，解きやすい流れである．また，問題文を注意深く読んでから解答群を見れば，誤選択肢の見当がつく．また，解答の解説だけでなく，Koukaの値を替えてみたり，<を≦に変更してみたりと，ちょっとプログラムで遊んでみた．理解を深めるには，この手の遊びは有効だと思う．最後に，第3問に興味を持った読者は，貪欲法，整数計画法，最適化や計算量などについて調べるとよいだろう．
参考文献
1）水野修治：令和7年度大学入学共通テスト『情報I』の実施に向けて～問題作成方針に関する検討の方向性と試作問題～，情報処理，Vol.64, No.2, pp.74-77 (2023).
https://doi.org/10.20729/00223448
2）大学入試センター：令和7年度試験の問題作成の方向性，試作問題等
https://www.dnc.ac.jp/kyotsu/shiken_jouhou/r7/r7_kentoujoukyou/r7mondai.html
（2024年1月26日受付）
（2024年2月21日note公開）
■冨澤眞樹（正会員）
東京農工大学大学院工学研究科電子情報工学専攻博士後期課程修了，博士（工学）．情報システムの開発と，少しだけ計算量とグラフアルゴリズムに興味を持つ．
情報処理学会ジュニア会員へのお誘い
小中高校生，高専生本科～専攻科1年，大学学部１～3年生の皆さんは，情報処理学会に無料で入会できます．会員になると有料記事の閲覧，情報処理を学べるさまざまなイベントにお得に参加できる等のメリットがあります．ぜひ，入会をご検討ください．入会はこちらから！
この記事が気に入ったらサポートをしてみませんか？