基本情報技術者 2013年 春期 午後 問08
次のプログラムの説明及びプログラムを読んで、設問1，2に答えよ。
ある食料品店では、従来の特売方法に加えて、新たに選択型特売を始めることになった。選択型特売とは、例えば3種類の商品中から合計3個（3商品を各1個、同一商品を3個など）を選択して購入すれば値引きをするという特売方法である。
このプログラムは、レジ用プログラムの一部として、選択型特売の値引き処理をする。プログラムの実行は、顧客がレジに持ち込んだ商品のバーコードを全て読み込んで、購入する商品が確定した時点で行うものとする。
〔プログラムの説明〕
(1) 顧客がレジに持ち込んだ商品の情報（以下、購入情報という）及び1種類の選択型特売についての商品の情報（以下、特売情報という）は、次のように宣言された大域の変数及び配列で他のレジ用プログラムと受け渡す。配列の添字は、1から始まる。
(2) 購入情報の内容は、次のとおりである。図1は、購入情報のデータ例である。
① 購入[ ]は、ptr、品番、品名、単価、数量、金額のメンバから成る1レコードを1要素とする構造型の配列である。
② 購入[ ]には、購入する商品の情報が、バーコードを読み込んだ順に添字1の要素から格納されている。同一品番の商品の情報は、1レコードにまとめられており、品番の重複はない。
③ 購入[ ]中のptrは、レコードを品番の昇順にたどるポインタであり、次に大きい品番をもつレコードが格納されている要素の添字が入っている。最も大きい品番をもつレコードのptr値は0である。
④ ptr起点は、最も小さい品番をもつレコードが格納されている購入[ ]の要素の添字を示す。
⑤ 購入行数は、購入[ ]中に格納されたレコード件数を示す。
(3) 特売情報の内容は、次のとおりである。
① 特売は、品番、品名、単価、数量のメンバから成る構造型の変数である。品番、品名、単価には、特売を一つの商品とみなして付けた品番、特売の名称、値引き額が、それぞれ格納されている。
② 対象[ ]は、品番、数量のメンバから成る1レコードを1要素とする構造型の配列である。品番には、特売対象の商品の品番が格納されている。対象[ ]には、要素が品番の昇順に添字1から格納されている。
③ 対象行数は、対象[ ]中に格納されたレコード件数を示す。
④ 指定数量は、特売対象の商品を合計何個購入する必要があるかを示す。
⑤ 対象[ ]中及び特売中の数量には、初期値0が格納されている。
⑥ 図2には、特売情報のデータ例として、次の特売例を示してある。
例 B社緑茶500ml（品番222）、B社ほうじ茶500ml（品番223）、B社麦茶500ml（品番224）のどれでも、合わせて3本の買上げごとに100円引きとする。
(4) 処理は、検索部、計算部、更新部から成り、この順に実行する。
① 検索部では、対象[ ]中の各品番が購入[ ]中にあれば、購入[ ]中の該当するレコードの数量の値を、対象[ ]中の数量に格納する。
② 計算部では、対象[ ]中の各数量の値の合計を指定数量で割った商を、特売中の数量に格納する。
③ 更新部では、特売中の数量の値が1以上であれば、購入[ ]に特売のレコードを追加し、購入情報を更新する。
(5) メンバの参照は、例えば、購入[3]の品番を参照するときは、購入[3].品番と記述する。
(6) 図1及び図2のデータ例を用いてプログラムを実行した結果は、図3及び図4のとおりである。図3及び図4中の網掛け部分は、実行によって内容が変更された箇所であることを示す。
設問1：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
a, bに関する解答群
ア：K ← K + 1
イ：K ← ptr起点
ウ：K ← 購入[K].ptr
エ：T ← 1
オ：T ← T + 1
c, dに関する解答群
ア：K
イ：Kp
ウ：購入[K].ptr
エ：購入[Kp].ptr
オ：購入[購入行数].ptr
カ：購入行数
模範解答
a：ウ、b：オ、c：カ、d：ア
解説
解答の導き方
この問題では、特売対象の商品を購入情報から探し、対象商品の合計数量から値引き回数を求め、特売のレコードを購入情報に追加します。
まず、購入情報の並び方に注意します。購入[ ]の要素はバーコードを読み込んだ順に格納されていますが、購入[ ]のptrをたどると品番の昇順になります。ptrは「次のレコードが入っている要素の添字」を表す値です。つまり、次の商品へ進むときは、添字に1を足すのではなく、現在のレコードのptrを使います。
1. 検索部では、購入側と対象側の位置を進めます
購入情報では、ptr起点が2です。図1のデータをptrでたどると、品番は次の順になります。
検索では、Kが購入情報の位置、Tが対象情報の位置を表します。品番を比べて、次のように進めます。
- 購入側の品番が対象側より小さいときは、購入側だけを次へ進めます。この処理が「K ← 購入[K].ptr」です。
- 品番が一致したときは、数量を対象[T].数量に移し、購入側と対象側の両方を次へ進めます。
- 購入側の品番が対象側より大きいときは、その対象品番は購入情報にないので、対象側だけを次へ進めます。この処理が「T ← T + 1」です。
したがって、aには購入側を進める処理である「K ← 購入[K].ptr」、bには対象側を進める処理である「T ← T + 1」が入ります。
実際に検索すると、次のように進みます。
このように、購入側の品番が対象側より小さい場合は購入側だけを進めるため、aは選択肢ウです。一致したときや購入側の品番が大きいときに対象側を進める処理が必要なので、bは選択肢オです。
2. 計算部では、特売の回数を求めます
対象[ ]の数量は、対象[1]から順に5、0、2です。合計は次のとおりです。
指定数量は3なので、特売.数量には、7を3で割った商を格納します。
3個ごとの特売を適用できるのは2回です。残った1個は、もう1回分の特売には足りません。
3. 更新部では、品番の順番を保ってレコードを追加します
特売の品番は229です。購入情報の品番を昇順に並べると、229は224と333の間に入ります。
更新部では、Kが今見ている購入情報の位置、Kpがその直前の位置を表します。処理を追うと、次のようになります。
品番333は229より大きいので、探索を終えます。このとき、Kpは品番224のレコードを、Kは品番333のレコードを指しています。
新しいレコードは購入行数を1増やした要素、つまり購入[6]に格納します。購入[4]の次の位置を購入[6]にし、購入[6]の次の位置をK、すなわち購入[5]にします。これで、品番224、229、333の順につながります。
そのため、Kpが指すレコードのptrに入れるのは追加した要素の添字である購入行数です。cは選択肢カです。また、新しく追加するレコードのptrには、追加位置の次にあたるKを入れます。dは選択肢アです。
誤りやすいポイント
- 購入[ ]の添字順と品番順を混同しないでください。購入情報はバーコードを読み込んだ順に格納されているため、品番順に進むにはptrをたどります。
- K ← K + 1では、配列上で隣の要素に進むだけです。品番順の次のレコードへ進むには、K ← 購入[K].ptrを使います。
- 購入側の品番が対象側より小さいときに、Tも進めてはいけません。対象品番が購入情報の後ろの方にある可能性があるため、購入側だけを進めます。
- 新しいレコードを購入[6]に格納しても、品番順の並びは添字順ではありません。ptrをつなぎ替えて、品番順を保ちます。
- 7を3で割った商は2です。合計数量をそのまま特売.数量に入れるわけではありません。
FAQ
Q: 対象[2].数量が0のままなのはなぜですか？
A: 品番223の商品が購入情報に見つからなかったためです。対象[ ]の数量は初期値0なので、該当商品がなければ0のままです。
A: 品番223の商品が購入情報に見つからなかったためです。対象[ ]の数量は初期値0なので、該当商品がなければ0のままです。
Q: なぜ購入[6].ptrにKを入れるのですか？
A: Kは新しく追加する品番229より大きい品番333のレコードを指しているためです。購入[6]の次に購入[5]をたどれるようにします。
A: Kは新しく追加する品番229より大きい品番333のレコードを指しているためです。購入[6]の次に購入[5]をたどれるようにします。
Q: 対象商品の合計数量が7なのに、特売.数量が2なのはなぜですか？
A: 指定数量の3個ごとに特売を1回適用するためです。7個の中に3個のまとまりは2組あり、残り1個ではもう1回分に足りません。
A: 指定数量の3個ごとに特売を1回適用するためです。7個の中に3個のまとまりは2組あり、残り1個ではもう1回分に足りません。
関連キーワード: 配列、ポインタ、連結リスト、逐次探索、整数除算、挿入処理
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
商品のバーコードを読み込む段階で、その時点までに読み込んだ商品の金額の小計を、値引きを反映した金額で表示したい。そこで、商品のバーコードを読み込んだときに選択型特売に該当する商品ならば、都度このプログラムを実行するように修正したい。また、読込み済み商品の購入の取消しにも対応したい。ここで、対象[ ]中及び特売中の数量には、初期値0を格納してプログラムを呼び出す。
この方法では、特売のレコードを購入[ ]に書き込むとき、既に購入[ ]中にその特売のレコードが存在していることがある。また、値引きが成立していた特売のレコード中の数量が0になったとき、その特売のレコードの削除が必要になることがある。
特売のレコードの取扱いは、表1に示す処理に分けられる。
処理①〜④のうち、eは特売のレコードの更新処理であり、fは特売のレコードの削除処理である。
そこで、プログラムの修正方法として、検索部と計算部は変更せず、更新部を次のように変更することにした。
(1) プログラム中の破線で囲んだ部分を、次の条件式で置き換える。
(2) プログラムの末尾に、次の処理を追加する。
なお、更新処理では、更新前と更新後の特売のレコード中の数量が同じになる場合でも処理を行う。また、削除処理では、該当する特売のレコードを格納していた配列の要素はそのまま残し、ポインタの付替えによってレコードを無効にする。
e, fに関する解答群
ア：処理①
イ：処理②
ウ：処理③
エ：処理④
gに関する解答群
ア：K
イ：Kp
ウ：購入[K].ptr
エ：購入[Kp].ptr
オ：購入[購入行数].ptr
カ：購入行数
模範解答
e：イ、f：ア、g：ウ
解説
解答の導き方
この設問では、特売のレコードを、既にあるかどうかと、特売の数量が0かどうかで分けて考えます。
まず、購入情報は配列の添字順ではなく、ptrをたどって品番の昇順に調べます。ptrは「次にたどるレコードの位置」を示す値です。検索中のレコードを示すKと、その一つ前のレコードを示すKpを使います。
更新部では、特売の品番を通り過ぎるまで、Kを次のレコードへ進めます。そのため、検索が止まったときの状態は次のどちらかです。
- Kが0、または購入[K].品番が特売.品番より大きい場合：同じ品番のレコードはありません。
- 購入[K].品番が特売.品番と等しい場合：同じ品番のレコードがあります。
この判定に、特売.数量が0かどうかを組み合わせると、処理は次のように分かれます。
したがって、既存のレコードを更新するのは「存在する・数量が0より大きい」場合の処理②です。eの解答群ではイに当たります。既存のレコードを削除するのは「存在する・数量が0」の場合の処理①です。fの解答群ではアに当たります。
次に、削除時に代入する値を考えます。Kは削除対象のレコードを指し、購入[K].ptrはその次のレコードを指しています。削除対象を飛ばして次のレコードへつなぐには、直前のレコードのptrを購入[K].ptrにします。
削除対象が先頭のレコードなら、直前のレコードはありません。その場合は、ptr起点を購入[K].ptrにします。どちらの代入にも入るgは、購入[K].ptrです。解答群ではウに当たります。
この値が必要なのは、削除対象のレコード自体を配列から移動したり消したりするのではなく、ptrのつなぎ替えでレコードを無効にするためです。
図3のデータ例でも、特売の品番229は購入情報にまだありません。対象の数量は5、0、2なので合計は7です。指定数量3で割ると、商は2です。つまり、特売の数量は2になります。
更新部で品番229の位置を探すと、購入[4]の品番224の次にある購入[5]の品番333で検索が止まります。333は229より大きいので、品番229のレコードはありません。特売の数量は0より大きいため、新たなレコードを購入[6]に追加します。購入[4]のptrを6にし、購入[6]のptrを5にすれば、品番224、229、333の順につながります。
一方、バーコードの読込みや取消しに応じて同じ特売処理を繰り返す場合は、特売のレコードが既に存在することがあります。そこで、置き換え後の条件は、数量が0より大きく、かつ同じ品番のレコードが見つからない場合だけ追加するようにしています。同じ品番が見つかった場合は、追加ではなく数量と金額を更新します。数量が0になった場合は、追加せず、既存レコードがあれば削除します。
誤りやすいポイント
- 配列の添字が品番順に並んでいるとは限りません。品番順に調べるときは、配列の添字を順に増やすのではなくptrをたどります。
- Kは検索中のレコード、Kpはその一つ前のレコードです。削除では、削除対象の次につながる購入[K].ptrを使います。
- 特売の数量が0より大きいだけでは、追加とは限りません。同じ品番のレコードが既にある場合は、追加せず更新します。
- 特売の数量が0で、同じ品番のレコードもない場合は、削除する対象がないため何もしません。
- 問題文では、更新前後の数量が同じでも更新処理を行います。値が変わったかどうかではなく、レコードの有無と数量で処理を決めます。
FAQ
Q: Kが0のときは、何を表していますか？
A: ptrをたどって調べるレコードがなくなった状態です。検索中に品番が見つからず、購入情報の末尾まで進んだ場合も含みます。
A: ptrをたどって調べるレコードがなくなった状態です。検索中に品番が見つからず、購入情報の末尾まで進んだ場合も含みます。
Q: 削除するレコードの配列要素も消したり、後ろの要素を詰めたりするのですか？
A: いいえ。問題文では配列要素をそのまま残し、ptrのつなぎ替えでレコードを無効にします。削除対象を指すつながりを外すことで、通常の検索経路からたどれなくします。
A: いいえ。問題文では配列要素をそのまま残し、ptrのつなぎ替えでレコードを無効にします。削除対象を指すつながりを外すことで、通常の検索経路からたどれなくします。
Q: 対象の数量の合計が7で、指定数量が3の場合、特売の数量が2になるのはなぜですか？
A: 指定数量の3個を1組として、作れる組の数を数えるためです。の商は2で、余りの1個は組になりません。
A: 指定数量の3個を1組として、作れる組の数を数えるためです。の商は2で、余りの1個は組になりません。
関連キーワード: 配列、構造体、ポインタ、連結リスト、整数除算
