KM-09｜情報Ⅰ 対策問題
試作問題 第3問 問3 関数「枚数(金額)」は、引数として「金額」が与えられ、ちょうどその金額となる硬貨の組合せの中で、枚数が最小となる硬貨枚数が戻り値となる関数である。 Sさんは、この関数を使って、客と店が交換する硬貨の合計が最小となる枚数(最小交換硬貨枚数)を計算するプログラムを作成した(図2)。変数 kakaku に与えられる商品の価格に対して、釣り銭を表す変数 tsuri を用意し、妥当な tsuri のすべての値に対して交換する硬貨の枚数を調べ、その最小値を求めるプログラムである。ここでは例として商品の価格を46円としている。 このプログラムでは、釣り銭無しの場合も含め、99円までのすべての釣り銭に対し、その釣り銭になるように支払う場合に交換される硬貨の枚数を求め、その最小値を最小交換硬貨枚数として計算している。最小値の計算では、これまでの払い方での最小枚数を変数 min_maisu に記憶しておき、それより少ない枚数の払い方が出るたびに更新している(min_maisu の初期値には、十分に大きな値として100を用いている)。 図2の空欄【サ】【シ】に入れるものの組み合わせとして正しいものを選べ(空欄【ス】〜【タ】には適切な内容が入るものとする)。
解答・解説を見る
正解: 1
正答
1
問題の整理
「46円の買い物で、客と店の間で動く硬貨の合計枚数を最小にしたい」という問題です。たとえば50円玉1枚で払って4円のお釣り(1円×4)なら、支払い1枚+釣り4枚=5枚。ちょうど46円払う(6枚)より少なくなります。
そこでプログラムは、釣り銭 tsuri を0円から99円まで全部試して、それぞれの合計枚数を計算し、最小値を記録します。これは全探索と呼ばれる、候補をすべて試す基本的な方法です。
解き方
- サ (ループで動かす変数): (4)行を見ると shiharai = kakaku + tsuri と、shiharai は tsuri から計算されています。maisu も(5)行で計算される結果です。自分で値を変えながら試す変数は tsuri だけです。
- シ (開始値): 「釣り銭なし(ちょうど支払う)」の場合も候補に含める必要があります。釣り銭なし= tsuri が 0 の場合なので、開始は0からです。1から始めると「ちょうど払う」パターンを試し損ね、それが最小のときに間違った答えを出してしまいます。
「ループで動かすのは独立に決められる変数、それ以外は計算で決まる従属変数」という区別と、「開始値は問題の条件(0を含むか)を反映する」という2点がポイントです。
選択肢の確認
1．○ tsuriを0から99まで全探索する。
2．× 1からでは「釣り銭なし」の候補が抜ける。
3．× shiharaiは(4)行で計算される従属変数。
4．× maisuは(5)行で計算される結果の変数。
ここだけは覚えよう
全探索=候補を全部試して最小(最大)を記録 — 動かすのは独立変数、開始値は「0を含むか」に注意。