基本情報技術者 2018年 秋期 午後 問09
次のCプログラムの説明及びプログラムを読んで、設問1～3に答えよ。
本問は、図1に示す路線構成の鉄道模型における列車の運行をシミュレーションするプログラムである。表1は、図1の説明である。
〔列車を進行させるルール〕
(1) 各列車は、あらかじめ決められた始発駅から、あらかじめ決められた終着駅を行先として、路線を後戻りすることなく進行する。
(2) 一つの区間には、同時に一つの列車しかいることができない。
(3) 各区間の入口には信号機があり、赤又は緑を表示する。
(4) 各列車は、終着駅を出口とする区間にいるときは無条件に進行できる。終着駅を出口とする区間にいる列車が進行した場合、その列車は路線上から取り除かれる。
(5) 各列車は、現在いる区間の出口で接続する区間（以下、次区間という）が次の条件をいずれも満たしたとき、次区間に進行できる。
① 次区間の信号機の表示が緑である。
② 次区間に進行すると、最終的には行先とする終着駅に到達できる。
(6) 次の二つの処理を繰り返し実行して各列車を進行させる。
① 路線を構成する全ての区間の信号機それぞれについて、区間内に列車がいるときは表示を赤に、列車がいないときは表示を緑にする。
② 路線を構成する全ての区間それぞれについて、次の処理を行う。
（ア）終着駅を出口とする区間に列車がいる場合は、(4)に従って列車を進行させ、路線上から取り除く。
（イ）(ア)で述べた以外の区間に列車がいる場合は、(5)に従って進行できる列車を進行させ、進行した区間の信号機の表示を赤にする。
〔プログラム1の説明〕
(1) 構造体block_infoは、鉄道模型の区間を表現する。
struct block_info {
struct train_info* train;
struct block_info* next[2];
int signal;
};
train：区間内にいる列車を表現した、構造体train_infoへのポインタである。区間内に列車がいないとき、NULLを設定する。
next：次区間を表現した、構造体block_infoへのポインタを格納する配列（配列の大きさは2）である。終着駅を出口とする区間では、いずれの要素にもNULLを設定する。次区間が一つしかなければ、そのポインタは最初の要素に設定し、2番目の要素にはNULLを設定する。
signal：信号機に表示する色を示す。次のいずれかの定数値をとる。
RED 表示は赤
GREEN 表示は緑
(2) 構造体train_infoは、鉄道模型の列車を表現する。
struct train_info {
int number;
struct block_info* dest;
};
number：列車の番号である。
dest：列車の終着駅を出口とする区間を表現した、構造体block_infoへのポインタである。
(3) 関数set_signalsの仕様は、次のとおりである。
機能：全ての区間の信号機それぞれについて、区間内に列車がいるときは表示を赤に、列車がいないときは表示を緑にする。
引数：blocks 全ての区間を表現した、構造体block_infoの配列
nblocks blocksの要素数
設問1：
問題文を見る プログラム1中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：block->next[0]->train == NULL
イ：block->next[1]->train == NULL
ウ：block->next[0]->train == NULL || block->next[1]->train == NULL
エ：block->next[0]->train == NULL && block->next[1]->train == NULL
オ：block->signal == RED
カ：block->train == NULL
キ：block->train != NULL
模範解答
a：カ
解説
解答の導き方
この空欄では、区間の信号機を緑にするか、赤にするかを判断する条件を考えます。
まず、関数の仕様には「区間内に列車がいるときは表示を赤に、列車がいないときは表示を緑にする」とあります。つまり、確認するのは、信号を設定する区間そのものに列車がいるかどうかです。
プログラムでは、blockが処理中の区間を指しています。ポインタ（データの場所を指し示すもの）を使って、その区間の列車を表すメンバーを調べるには、block->trainと書きます。説明にも、trainには「区間内にいる列車」を表す情報が入り、列車がいないときはNULL（何も指していないことを表す値）を設定するとあります。
したがって、block->train == NULLなら区間に列車がいないので、信号をGREENにします。条件に当てはまらない、つまり列車がいる場合は、信号をREDにします。空欄には、区間内に列車がいないことを表す「block->train == NULL」が入ります。
ほかの選択肢が適さない理由も確認します。
- ア、イ、ウ、エは、次区間の列車の有無を調べています。信号を設定する対象は現在の区間なので、現在の区間の列車を調べる条件にはなりません。また、次区間がない場合には、存在しない次区間の情報を調べることになります。
- オは、信号の現在の表示が赤かどうかを調べています。列車がいるかどうかを直接調べていません。
- キは、列車がいる場合に真になります。列車がいる場合は信号を赤にするため、この条件のままでは、信号を緑にする条件として逆になります。
誤りやすいポイント
- 次区間の空き状況と、現在の区間の信号表示を混同しないようにします。この関数は、現在の区間に列車がいるかを調べます。
- trainに列車がいないときはNULLが入ります。列車がいるかどうかを判定する際は、NULLと等しいかどうかを確認します。
- ifの条件が真のときに実行されるのはGREENを設定する処理です。条件が「列車がいる」か「いない」かを、処理内容と合わせて確認します。
FAQ
Q: なぜblock->signalではなく、block->trainを調べるのですか？
A: 信号の色を決める基準は、区間内に列車がいるかどうかだからです。block->signalを調べても、列車がいるかどうかは分かりません。
A: 信号の色を決める基準は、区間内に列車がいるかどうかだからです。block->signalを調べても、列車がいるかどうかは分かりません。
Q: block->trainがNULLでない場合は、どうなりますか？
A: 列車が区間内にいることを意味します。ifの条件は偽になるため、elseの処理で信号にREDが設定されます。
A: 列車が区間内にいることを意味します。ifの条件は偽になるため、elseの処理で信号にREDが設定されます。
Q: この関数は、どの区間を処理しますか？
A: blocksの要素を先頭から順に処理します。ループのたびにblockが対象の区間を指し、その区間の信号表示を設定します。
A: blocksの要素を先頭から順に処理します。ループのたびにblockが対象の区間を指し、その区間の信号表示を設定します。
関連キーワード: C言語、構造体、ポインタ、配列、NULL、条件分岐
設問2：
問題文を見る 関数proceedは、進行できる全ての列車を進行させるプログラムである。プログラム2中のに入れる正しい答えを、解答群の中から選べ。
〔プログラム2の説明〕
(1) 関数proceedの仕様は、次のとおりである。
機能：全ての区間それぞれについて、進行できる列車がいるかどうかを判定し、進行できると判定された列車を進行させる。終着駅を出口とする区間にいる列車を進行させた場合、その列車を路線上から取り除く。出口で他の区間と接続する区間にいる列車を進行させた場合、進行した区間の信号機の表示を赤にする。
引数：blocks 全ての区間を表現した、構造体block_infoの配列
nblocks blocksの要素数
(2) 関数proceedから呼び出される関数find_blockの仕様は、次のとおりである。
機能：引数blockで示す区間が、引数destで示す区間に最終的に到達できる経路上にあるかどうかを判定する。
引数：block 判定対象の区間を表現した、構造体block_infoへのポインタ
dest 列車の終着駅を出口とする区間を表現した、構造体block_infoへのポインタ
返却値：到達できるとき、1
到達できないとき、0
bに関する解答群
ア：block->train->dest == NULL
イ：block->train->dest != NULL
ウ：block == block->train->dest
エ：block != block->train->dest
cに関する解答群
ア：break
イ：continue
ウ：return
dに関する解答群
ア：dest, block
イ：dest, block->next[i]
ウ：block, dest
エ：block, block->next[i]
オ：block->next[i], dest
カ：block->next[i], block
模範解答
b：ウ、c：ア、d：オ
解説
解答の導き方
まず、プログラム2は、各区間にいる列車について「終着駅を出口とする区間に着いたか」「次の区間へ進めるか」を調べています。
ここで、ポインタ（データを指し示す値）であるtrain->destは、その列車が目指す終着駅を出口とする区間を指しています。現在の区間を指すblockとtrain->destが同じなら、列車は終着駅を出口とする区間にいます。
その場合は、問題文の「終着駅を出口とする区間にいる列車が進行した場合、その列車は路線上から取り除かれる」というルールに従い、列車を取り除きます。したがって、bには、現在の区間と行先の区間が同じかを調べる条件が入ります。該当するのは「block == block->train->dest」です。
次に、次の区間へ進めるかを調べる処理を考えます。進行先の候補はblock->next[j] です。候補の区間が緑信号であっても、その先から列車の行先に到達できなければ進めません。そのため、find_blockで候補の区間から行先までの経路を調べています。
find_blockでは、まず現在調べている区間が行先の区間と同じかを確認します。同じでなければ、その区間の次の区間を順番に調べます。再帰呼出し（関数が自分自身を呼ぶ処理）では、調べる区間を一つ先へ進め、行先は変えません。よって、dには「block->next[i], dest」が入ります。
最後に、列車を次の区間へ移した後の処理を見ます。列車は、次の区間の一方だけへ進みます。移動後にjの繰返しを続けると、別の分岐先も調べてしまいます。また、block->trainにはNULLが設定されているため、次の分岐先も調べようとすると、列車の行先を参照できません。
そこで、進行先を決めて列車を移したら、次の区間を調べる繰返しだけを終了します。これを行うのがbreakです。continueでは繰返しを続けてしまい、returnではproceed全体が終了して、ほかの区間の列車まで処理されなくなります。
誤りやすいポイント
- bでtrain->destがNULLかどうかを調べるのではありません。問題文では、destは列車の終着駅を出口とする区間を指しています。列車を路線上から取り除くタイミングは、現在の区間がその区間と一致したときです。
- dでは、調べる区間と行先の順番を入れ替えません。find_blockの引数は「調べる区間、行先」の順なので、再帰呼出しでもその役割を保ちます。
- cにcontinueを選ぶと、次の候補の確認を続けてしまいます。一方、returnを選ぶと、ほかの列車を処理する外側の繰返しまで終わってしまいます。
FAQ
Q: 次の区間が緑なら、必ず進めますか？
A: いいえ。問題文では、次区間の信号機が緑であることに加え、その区間から行先に到達できることも条件です。そのため、find_blockで経路を調べます。
A: いいえ。問題文では、次区間の信号機が緑であることに加え、その区間から行先に到達できることも条件です。そのため、find_blockで経路を調べます。
Q: breakは、どの繰返しを終了しますか？
A: 直近の繰返し、つまり次区間の候補を調べるjの繰返しです。proceed全体の処理は続くため、ほかの区間にいる列車も調べられます。
A: 直近の繰返し、つまり次区間の候補を調べるjの繰返しです。proceed全体の処理は続くため、ほかの区間にいる列車も調べられます。
Q: find_blockは、なぜ自分自身を呼び出すのですか？
A: 行先が次の区間のすぐ先にあるとは限らないためです。次の区間、その先の区間というように、行先に着くまで経路を順番に調べます。
A: 行先が次の区間のすぐ先にあるとは限らないためです。次の区間、その先の区間というように、行先に着くまで経路を順番に調べます。
関連キーワード: ポインタ、構造体、配列、再帰呼出し、深さ優先探索
設問3：
問題文を見る 図1に示した鉄道模型の路線構成及び列車位置を表現した、構造体block_infoの配列を第1引数とし、その要素数9を第2引数として、プログラム3を実行した。プログラム3の実行が終了したときの状態について述べた次の記述中のに入れる正しい答えを、解答群の中から選べ。ここで、blocks[n]は区間nを示す。
列車4がいるのは区間eである。また、区間eの出口で接続する区間はf。
eに関する解答群
ア：0
イ：2
ウ：3
エ：7
fに関する解答群
ア：一つあり、その信号機は緑を表示している
イ：一つあり、その信号機は赤を表示している
ウ：二つあり、それらの信号機はいずれも緑を表示している
エ：二つあり、それらの信号機はいずれも赤を表示している
オ：二つあり、それらの信号機は、一方が緑を、もう一方が赤を表示している
模範解答
e：イ、f：ア
解説
解答の導き方
列車4が最終的にどこにいるかを、4回の進行処理に沿って追います。信号機は、列車がいる区間では赤、いない区間では緑になります。また、進行処理の中では区間番号の大きい方から小さい方へ確認します。
列車4の行先は終着駅Zです。終着駅Zへ向かうには、区間0から区間2、区間3、区間7、区間8へ進む必要があります。一方、区間3にいる列車2や列車3は、行先に合わせて別の区間へ向かいます。
それぞれの動きを確認します。
-
1回目
区間1の列車3は、空いている区間2へ進みます。区間2の信号機は赤になるため、区間0の列車4は区間2へ進めません。
列車1は区間4から区間5へ進みます。列車0は終着駅Zを出口とする区間8にいるので、路線上から取り除かれます。 -
2回目
列車1は区間5が終着駅Xを出口とする区間なので、路線上から取り除かれます。列車2は区間3から区間4へ進みます。
列車3は区間2にいますが、区間3の信号機は、列車2が区間3にいたときに赤になっています。この処理中に列車2が区間3を出ても、信号機は次の信号更新まで赤のままです。そのため、列車3は区間3へ進めません。 -
3回目
列車2は区間4から、行先の終着駅Yへ到達できる区間6へ進みます。列車3は区間2から区間3へ進みます。
区間2の信号機は、処理開始時には列車3が区間2にいたため赤です。列車3が区間2を出ても、この処理中は赤のままなので、列車4はまだ区間2へ進めません。 -
4回目
列車2は終着駅Yを出口とする区間6にいるので、路線上から取り除かれます。列車3は区間3から、行先の終着駅Xへ到達できる区間4へ進みます。
列車4は、空いている区間2へ進みます。区間2から進める区間は区間3だけです。
最後に、信号機は区間内に列車がいるかどうかに合わせて更新されます。列車3は区間4へ進んでおり、区間3には列車がいません。問題文には「区間内に列車がいるときは表示を赤に、列車がいないときは表示を緑にする」とあるため、区間3の信号機は緑です。
したがって、区間eは区間2であり、その出口で接続する区間は一つで、信号機は緑を表示しています。
誤りやすいポイント
- 列車が区間を出た直後、その区間の信号機がすぐ緑になると思い込まないようにしましょう。信号機は、信号を更新する処理で改めて設定されます。
- 列車3と列車4は、どちらも区間2へ進もうとします。区間番号の大きい方から順に確認するため、区間1の列車3が先に区間2へ進み、列車4は待つことになります。
- 列車が進んだ後、同じ進行処理の中でもう一度その列車が進むとは限りません。進行先の区間がすでに確認された後なら、その列車は次の進行処理までそこにとどまります。
- 区間2の出口で接続する区間の数と、その区間の信号機の色は別々に確認します。ここでは、接続先は区間3の一つで、信号機は緑です。
FAQ
Q: 列車2は、区間3から区間7へ進めないのですか？
A: 区間7から先は終着駅Zへ向かう経路です。列車2の行先は終着駅Yなので、区間7へは進まず、区間4から区間6へ向かいます。
A: 区間7から先は終着駅Zへ向かう経路です。列車2の行先は終着駅Yなので、区間7へは進まず、区間4から区間6へ向かいます。
Q: 列車4は、4回目の処理で区間2から区間3へ進まないのですか？
A: 区間番号の大きい方から確認するため、区間2は区間0より先に確認済みです。列車4が区間0から区間2へ進むのはその後なので、区間2からさらに進む処理は次の進行処理まで行われません。
A: 区間番号の大きい方から確認するため、区間2は区間0より先に確認済みです。列車4が区間0から区間2へ進むのはその後なので、区間2からさらに進む処理は次の進行処理まで行われません。
Q: 列車が区間から出たら、信号機もすぐ緑になりますか？
A: すぐには変わりません。信号機の表示は、set_signalsによって区間内の列車の有無を調べたときに更新されます。
A: すぐには変わりません。信号機の表示は、set_signalsによって区間内の列車の有無を調べたときに更新されます。
関連キーワード: 配列、状態遷移、シミュレーション、信号制御、経路探索
