アルゴリズム基礎解説（平成15年秋期問4）
| 解説 |
|---|
|
プログラムの動作をトレースしながら解説します。 まず、初期設定において各配列を初期化していきます。このときC[i,j]に関してはまず最初の情報として、地点1から各地点への距離の値を代入します。それが終わったら地点1の処理を終了したという証明としてP[1]に１を代入します。Pはフラグのような役割と思われます。 その後、最初の空欄のある｛最短経路を求める手順｝の部分に移ります。まず、繰り返し用の変数であるXに２を代入します。以降はXがNのときまで（図1の場合は５）繰り返されます。次に地点を表す変数Yに２を代入し、最短距離を表す変数Zに初期値∞を代入します。ここからが空欄aの部分になります。ループはY=5のときまで繰り返されます。 では、値を代入しながら見ていきます。 Y=2 1. P[2]=0であり、かつD[2](=30)<Z(=∞）であるので処理を続行。 2. 最短地点を格納する変数Tに2を代入。 3. 空欄a 4. Y←3 この3.の部分で何をするのかというと、次の動作に移っていく上で最短距離を表す変数Zの値を更新していかなければならないのです。よってここではZにD[2]の値を格納し、Y=3に移行します。従ってaに入るのはキのZ←D[Y]となります。 トレースを続けると、 Y=3 1. P[3]=0だが、D[3](=∞)>Z(=30)なので処理をしない。 2. Y←4 Y=4 1. P[4]=0で、かつD[4](=20)<Z(=30)なので処理を続行。 2. Tに４を代入し、さらにZに20を代入 3. Y←5 Y=5 1. P[5]=0だがD[5](=120)>Z(=20)なので処理をしない。この時点でT=4が確定 2. Y←6。このあとループを抜ける そしてP[4]←１となります。これで以上の部分ではもう地点4に関する処理は行われません。次に地点4から最も短い経路の探索を行います。 Y=2 1. P[2]=0だがD[2](=30)＜D[4]＋C[4,2](=20+∞)なので何もしない。 2. Y←3 Y=3 1. P[3]=0でありD[3](=∞)＜D[4]+C[4,3](=20+50)なので続行。 2. D[3]に70を代入し、bを実行 3. Y←4 2つ目の空欄が出てきます。問題文を見ると、Dを置換した時は直前地点を格納する配列SにTを代入するとあります。ここではS[3]に4(＝T)を代入します。よってbはエのS[Y]←Tとなります。この処理をY=5のときまで行います。ちなみにこの後はDは置換されないので、S[3]=4が確定します。ここを抜けるとX←3となり、また最初から以上を行います。 次に出力処理を見ていきます。まず繰り返し変数Xに1、Yにこの場合は5を代入します。その下のループでは、 1. YをW[X]という配列に（印字のために使う）代入。ここではW[1]←5。 2. cを実行してX←2 このcですが、この部分の変数はXとYの2種類しかないので、事実上オとカの2択になります。 オのY←S[X]だとこの後YにS[1]が入ることになるのですが、地点1の前には何もありません。このあと誤動作が起きてしまいます。 カのY←S[Y]では、YにS[5](=3)が入ります。この後Xが2になって、次のループのときはW[2]に3が入ります。そしてYにはS[3](=4)が代入され、次のX=3のとき、W[3]に4が代入されます。最後にS[4](=1)がYに代入されます。 Y=1なのでループから抜け、その後W[4]に1が代入されます。 最後にWの内容をXの降順に表示していき、Xが1の時まで繰り返します。これで図にある様に1→4→3→5と表示できます。 以上のことからcはカのY←S[Y]、dはアのX>0になります。 |
匿名様 ご投稿
メニューへ戻る