基本情報技術者 2010年 秋期 午後 問09
次のCプログラムの説明及びプログラムを読んで、設問1，2に答えよ。
〔プログラムの説明〕
5台のバスが走行する路線上の10か所の停留所（以下、バス停という）のそれぞれに取り付けられた表示装置に、バスの運行時間中、次のバスが到着するまでの待ち時間（以下、到着待ち時間という）を分単位で表示するシステムがある。関数update_wait_timeは、このシステムにおいて、各バス停に表示する到着待ち時間を計算するプログラムである。表示する到着待ち時間は、関数update_wait_timeが実行されたときに更新される。
(1) 関数update_wait_timeの引数は、次のとおりである。ここで、引数の値に誤りはないものとする。
bus_id バスの車体番号
busstop バス停の番号
route 路線表（構造体BUSSTOPの配列）
bus 路線上を走行するバスの一覧（構造体BUSの配列）
(2) 構造体BUSSTOPの構造は、次のとおりである。
typedef struct {
int std_time; /* 前のバス停からこのバス停までの標準所要時間（分） */
int wait_time; /* 到着待ち時間（分） */
} BUSSTOP;
(3) 構造体BUSの構造は、次のとおりである。
typedef struct {
int id; /* バスの車体番号 */
int cur_pos; /* バスの走行位置 */
} BUS;
(4) 路線表routeは、バス停の番号（以下、バス停番号という）0～9を添字とする配列である。routeには、図1のようにデータを格納する。
① route[i].std_time (i=1, 2, …, 9)は、前のバス停(i-1)からこのバス停iまでの標準所要時間である。バス停0におけるroute[0].std_timeの値は0とする。
② 各バス停iの到着待ち時間route[i].wait_time (i=1, 2, …, 9)は、次に到着するバスが最後に発車したバス停aからこのバス停iまでの標準所要時間route[k].std_time (k=a+1, …, i)の合計である。乗客の乗降にかかる時間は0とする。バス停0におけるroute[0].wait_timeの値は0とする。次に到着するバスがバス停0を発車していないとき、そのバス停iにおける到着待ち時間route[i].wait_timeには0を格納する。
(5) バスの走行位置bus[j].cur_pos (j=0, 1, …, 4)には、走行中の区間番号を格納する。あるバス停から次のバス停までの区間に対する区間番号には、区間の始まりとなるバス停番号を割り当てる。バス停0を発車していないバスの走行位置bus[j].cur_posには-1を格納する。また、バス停9に到着したバスの走行位置bus[j].cur_posには9を格納する。
(6) プログラム中で使われる変数precedingとsucceedingの意味は次のとおりである。
preceding busstopが示すバス停を直前に発車したバスが走行中の区間番号を格納する。busstopが示すバス停からバス停9までの区間に走行中のバスがない場合は9とする。
succeeding busstopが示すバス停に次に到着するバスが走行中の区間番号を格納する。バス停0からbusstopが示すバス停までの区間に走行中のバスがない場合は-1とする。
バス停5をバスBが発車するとき、バス停5を直前に発車したバスAが区間6を走行し、次にバス停5に到着するバスCが区間3を走行しているときの例を、図2に示す。
(7) 関数update_wait_timeは、バスがバス停0～8を発車するとき又はバス停9に到着したときに呼び出され、bus_idで識別されるバスの走行位置を更新し、busstopが示すバス停からprecedingが示す区間の始まりとなるバス停までの、各バス停に表示する到着待ち時間route[i].wait_time (i=busstop, …, preceding)を計算する。
なお、複数台のバスがバス停0～8の異なるバス停を同時に発車する場合、又はあるバスがバス停9に到着したときに別のバスがバス停0～8を発車する場合には、関数update_wait_timeは、バスの一覧busの添字の昇順に1台分ずつ実行される。
(8) 一つの区間を複数台のバスが同時に走ることはない。
設問1：
問題文を見る プログラム中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：bus_id == bus[j].id
イ：bus_id != bus[j].id
ウ：bus_id == j
エ：bus_id != j
bに関する解答群
ア：-1
イ：busstop
ウ：bus[j].cur_pos
エ：bus[j].cur_pos + 1
オ：bus[j].cur_pos - 1
カ：j
cに関する解答群
ア：preceding == -1
イ：preceding == STPNUM - 1
ウ：preceding != -1
エ：succeeding == -1
オ：succeeding == 0
カ：succeeding != 0
dに関する解答群
ア：+= route[i - 1].std_time
イ：+= route[i - 1].wait_time
ウ：+= route[i].std_time
エ：= route[i - 1].std_time
オ：= route[i - 1].wait_time
カ：= route[i].std_time
模範解答
a：ア、b：ウ、c：エ、d：イ
解説
解答の導き方
このプログラムは、今回発車または到着したバスの位置を更新し、そのバス停と後続のバス停の到着待ち時間を計算します。空欄をプログラムの流れに沿って考えます。
-
a：今回のバスを車体番号で特定します本文では、引数bus_idは「バスの車体番号」と説明されています。構造体BUSのidも「バスの車体番号」です。したがって、今回のバスかどうかは、bus_idとbus[j].idが等しいかで判定します。一致したバスは、今回busstopを発車または到着したバスなので、走行位置をbusstopに更新します。jは配列busの要素を順に調べるための添字です。車体番号そのものではないため、bus_idとjを比べるのではありません。
-
b：今回のバス停の前後にいるバスの位置を記録します今回のバス以外について、bus[j].cur_posがbusstopより小さければ、そのバスは今回のバス停より手前にいます。手前にいるバスのうち、今回のバス停に最も近いものの走行位置をsucceedingに記録します。一方、bus[j].cur_posがbusstop以上なら、そのバスは今回のバス停より先にいます。その中で最も今回のバス停に近いものの走行位置をprecedingに記録します。どちらも記録するのは走行位置そのものです。したがって、bにはbus[j].cur_posが入ります。例えば図2では、busstopが5で、バスCは区間3、バスAは区間6を走行しています。このとき、succeedingは3、precedingは6です。
-
c：手前にバスがいないときは待ち時間を0にしますsucceedingは最初に -1に設定されています。手前にバスが見つかると、そのバスの走行位置が入ります。見つからない場合は -1のままです。本文には、次に到着するバスがバス停0を発車していないとき、到着待ち時間に0を格納するとあります。今回のバス停より手前にバスがいない場合がこれに当たるので、succeedingが -1のとき、route[busstop].wait_timeを0にします。手前にバスがいる場合は、今回のバス停の標準所要時間に、1つ前のバス停までの到着待ち時間を加えます。バス停0には前のバス停がないため、手前にバスがいない場合の処理と分けることで、前の要素を参照せずに済みます。
-
d：到着待ち時間を、前のバス停までの合計に足します繰返し処理では、busstopの次のバス停からprecedingが示すバス停まで、到着待ち時間を計算します。最初のバス停では、その区間の標準所要時間を待ち時間にします。それより先のバス停では、前のバス停までに計算した待ち時間に、今回の区間の標準所要時間を加えます。つまり、前のバス停までの合計を引き継いで、区間ごとの時間を積み上げます。41行目で今回の区間の標準所要時間を設定しているので、43行目では前のバス停までの到着待ち時間を加える必要があります。したがって、dには += route[i - 1].wait_timeが入ります。
誤りやすいポイント
- bus_idは車体番号、jは配列の添字です。今回のバスを特定するときは、車体番号同士を比べます。
- succeedingとprecedingには、バスの走行位置を記録します。配列の添字jや、走行位置に1を足した値ではありません。
- succeedingが -1の場合は、到着待ち時間を -1にするのではありません。手前にバスがいないことを示す値として使い、待ち時間は0にします。
- 到着待ち時間は、直前の区間の標準所要時間だけではなく、前のバス停までに計算した待ち時間に今回の区間の標準所要時間を加えて求めます。
FAQ
Q: precedingの初期値が9なのはなぜですか？
A: 今回のバス停より先を走るバスが見つからなければ、バス停9までの待ち時間を計算するためです。先にいるバスが見つかると、そのバスの走行位置に更新されます。
Q: 今回のバスも、前後のバスを探す処理に含まれますか？
A: 含まれません。今回のバスは、車体番号が一致した時点で走行位置を更新します。前後のバスを探す処理は、それ以外のバスについて行います。
Q: 待ち時間を計算するとき、なぜ前のバス停の標準所要時間ではなく、待ち時間を加えるのですか？
A: 前のバス停の待ち時間には、そこまでの区間の所要時間が合計されています。その合計に今回の区間の標準所要時間を加えることで、今回のバス停までの到着待ち時間を求められます。
関連キーワード: 配列、構造体、条件分岐、繰返し処理、累積計算
設問2：
問題文を見る 次の記述中のに入れる正しい答えを、解答群の中から選べ。
サービス向上のため、路線上のそれぞれのバス停に取り付けられた表示装置に、到着待ち時間に加えて、そのバスの運行遅延時間を分単位で表示することにした。そのために、関数update_wait_timeに、各バス停に表示する運行遅延時間を計算する処理を追加する。ここで、プログラム中のa〜dには、正しい答えが入っているものとする。
(1) バスの運行遅延時間は、バス停0から最後に発車したバス停までの標準所要時間の合計と実際にかかった時間の合計の差である。
(2) 関数update_wait_timeの引数に、前のバス停からの実際にかかった時間（分）act_timeを追加する。ここで、引数の値に誤りはないものとする。
(3) 構造体BUSSTOPの要素に、次に到着するバスの運行遅延時間（分）delay_timeを追加する。
(4) 構造体BUSの要素に、バスの運行遅延時間（分）cur_delayを追加する。
(5) バスが定刻よりも早くバス停0～8を発車することはない。
(6) 処理の追加に対応するために、プログラムを表のとおりに変更する。
eに関する解答群
ア：= act_time - route[busstop].std_time
イ：= bus[j - 1].cur_delay
ウ：= route[busstop].delay_time
エ：+= act_time - route[busstop].std_time
オ：+= bus[j - 1].cur_delay
カ：+= route[busstop].delay_time
fに関する解答群
ア：= act_time
イ：= bus[j].cur_delay
ウ：= route[busstop].delay_time
エ：+= act_time
オ：+= bus[j].cur_delay
カ：+= route[busstop].delay_time
模範解答
e：エ、f：イ
解説
解答の導き方
この設問では、バス停に表示する「運行遅延時間」を、バスの走行位置と合わせてどのように更新するかを考えます。
1. 遅延時間は、区間ごとの遅れを積み上げます
問題文では、遅延時間を、バス停0から最後に発車したバス停までの標準所要時間と実際にかかった時間の差としています。
バスがある区間を走るとき、遅延時間は次のように変化します。
今回、バスはバス停を定刻より早く発車しないため、遅延時間は「実際にかかった時間」から「標準所要時間」を引く向きで計算します。
2. eには、これまでの遅延時間に今回の区間分を加える式が入ります
バス停を発車するとき、bus[j].cur_delayには、そのバスが前のバス停までに積み上げた遅延時間が入っています。また、act_timeは前のバス停から今回のバス停までに実際にかかった時間で、route[busstop].std_timeは同じ区間の標準所要時間です。
したがって、今回の区間で増減した分を、これまでの遅延時間に加えます。bus[j].cur_delayを今回の区間の差だけで置き換えると、それまでに積み上げた遅延が失われてしまいます。
このため、eには「act_timeからroute[busstop].std_timeを引いた値を、現在の遅延時間に加える」式が入ります。解答群ではエです。
3. fには、対象となるバスの遅延時間をそのまま代入します
delay_precedingは、今回発車したバスの遅延時間を保持します。プログラムでは、先にそのバスのcur_delayを更新してから、delay_precedingに値を入れています。そのため、更新後のbus[j].cur_delayをそのまま代入します。
一方、delay_succeedingは、今回のバス停に次に到着するバスの遅延時間を保持します。バスの走行位置を調べて、次に到着するバスの候補が見つかったとき、そのバスのcur_delayをそのまま代入します。
どちらの場合も、遅延時間を複数のバスから足し合わせるのではなく、該当するバスの値を記録します。したがって、fにはbus[j].cur_delayをそのまま代入する式が入ります。解答群ではイです。
誤りやすいポイント
- act_time - route[busstop].std_timeの引き算を逆にしないようにします。実際の時間が標準より長いとき、遅延は増えるためです。
- eでは、今回の区間分だけでなく、それまでの遅延も残す必要があります。したがって、単純に今回の区間分を代入するのではなく、現在の遅延に加算します。
- fは、該当するバスの遅延時間を記録する処理です。複数台のバスの遅延時間を合計する処理ではありません。
- delay_succeedingには、今回のバス停に次に到着するバスの遅延時間が入ります。今回発車するバスの遅延時間と混同しないようにします。
FAQ
Q: cur_delayには、直前の区間で発生した遅延だけが入りますか？
A: いいえ。それまでの区間で積み上げた遅延時間に、今回の区間での実際の所要時間と標準所要時間の差を加えた値が入ります。
A: いいえ。それまでの区間で積み上げた遅延時間に、今回の区間での実際の所要時間と標準所要時間の差を加えた値が入ります。
Q: なぜfは、両方の箇所で同じ値を使うのですか？
A: どちらも、選ばれたバスの遅延時間を記録する処理だからです。一方では今回発車するバスを記録し、もう一方では今回のバス停に次に到着するバスの候補を記録します。
A: どちらも、選ばれたバスの遅延時間を記録する処理だからです。一方では今回発車するバスを記録し、もう一方では今回のバス停に次に到着するバスの候補を記録します。
Q: delay_succeedingが初期値0なのはなぜですか？
A: 今回のバス停より前の区間に、次に到着するバスが見つからない場合に、初期値の0が使われるためです。
A: 今回のバス停より前の区間に、次に到着するバスが見つからない場合に、初期値の0が使われるためです。
関連キーワード: 累積計算、配列、構造体、条件分岐、運行遅延時間
