引数
このプログラムが要求している「引数」は N と Dist [ ][ ] なのですが、N は駅の数のことでプログラムの中で変化しませんし、Dist [ ][ ] は説明文に「初期値」として既に表になっているので新たに作る必要がありません。
またトレースによって作ろうとしている表も、説明文の中にすべて表として用意されているので、新たに作る必要がありません。与えられた表を使ってトレースしていきます。
トレース
From と To と Via が 1 から 5 まで変化して 5 × 5 × 5 回、同じ処理をします。
Dist[From][To] より Dist[From][Via] + Dist[Via][To] の方が小さかったら、Dist[From][To] を上書きするのですが、表を見ていくと Via = 1 , From = 1 で To を 1 から 5 まで変化させても一度も判定にひっかかりません。
はじめて上書き処理をするのが Via = 1 , From = 2 で To が 4 になったときで、 Dist[2][1] + Dist[1][4] を Dist[2][4] に上書きしますが、 「駅2」から「駅1」間の距離と「駅1」から「駅4」間の距離を足すのですから「駅2」から「駅1」を経由して「駅4」までいく距離ということになります。
よって空欄の「a」は「駅1」から「駅2」を経由して「駅3」までいく距離なので「ウ」です。
「b」は「駅3」から「駅2」を経由して「駅5」までいく距離なので「ア」です。
| (1,1) | (1,2) | (1,3) a | (1,4) | (1,5) |
| (2,1) | (2,2) | (2,3) | (2,4) | (2,5) |
| (3,1) a | (3,2) | (3,3) | (3,4) | (3,5) b |
| (4,1) | (4,2) | (4,3) | (4,4) | (4,5) |
| (5,1) | (5,2) | (5,3) b | (5,4) | (5,5) |
空欄「c」は、計算を 5 × 5 × 5 回するので Nの３乗「エ」です。
空欄「d」は、Via1 の計算が終了した時点で 5 × 5 ＝ 25 個の数値を保持していますが、その後の処理ではその数字を上書きするだけで、保持する数値の数は変わりませんので Nの２乗「ウ」です。
空欄「e」
変更されたプログラムでは From が 1 から 4 までしか変化しません。
空欄「e」による変化をひとつづつ見ていきます。
Dist[From][To] には○をつけます。
Dist[To][From] には×をつけます。
空欄が「ア」のとき判定するマスは以下になります。
| (1,1) ○× | (1,2) × | (1,3) × | (1,4) × | (1,5) |
| (2,1) ○ | (2,2) ○× | (2,3) × | (2,4) × | (2,5) |
| (3,1) ○ | (3,2) ○ | (3,3) ○× | (3,4) × | (3,5) |
| (4,1) ○ | (4,2) ○ | (4,3) ○ | (4,4) ○× | (4,5) |
| (5,1) | (5,2) | (5,3) | (5,4) | (5,5) |
空欄が「イ」のとき判定するマスは以下になります。
| (1,1) ○× | (1,2) ○ | (1,3) × | (1,4) × | (1,5) |
| (2,1) ○× | (2,2) ○× | (2,3) ○× | (2,4) × | (2,5) |
| (3,1) ○ | (3,2) ○× | (3,3) ○× | (3,4) ○× | (3,5) |
| (4,1) ○ | (4,2) ○ | (4,3) ○× | (4,4) ○× | (4,5) ○ |
| (5,1) | (5,2) | (5,3) | (5,4) × | (5,5) |
空欄が「ウ」のとき判定するマスは以下になります。
| (1,1) ○× | (1,2) ○ | (1,3) ○ | (1,4) ○ | (1,5) |
| (2,1) × | (2,2) ○× | (2,3) ○ | (2,4) ○ | (2,5) |
| (3,1) × | (3,2) × | (3,3) ○× | (3,4) ○ | (3,5) |
| (4,1) × | (4,2) × | (4,3) × | (4,4) ○× | (4,5) |
| (5,1) | (5,2) | (5,3) | (5,4) | (5,5) |
空欄が「エ」のとき判定するマスは以下になります。
| (1,1) | (1,2) ○ | (1,3) ○ | (1,4) ○ | (1,5) ○ |
| (2,1) × | (2,2) | (2,3) ○ | (2,4) ○ | (2,5) ○ |
| (3,1) × | (3,2) × | (3,3) | (3,4) ○ | (3,5) ○ |
| (4,1) × | (4,2) × | (4,3) × | (4,4) | (4,5) ○ |
| (5,1) × | (5,2) × | (5,3) × | (5,4) × | (5,5) |
空欄「 f 」
駅 i から 駅 j までの最短距離を求めるとき 空欄「 f 」の判定が、
True なら 「ToKL[i] - ToKL[j] 、 D1 、 D2 、 D3 、 D4 のうちの最小値、 False なら D1 、 D2 、 D3 、 D4 のうちの最小値になります。
「ToKL[ i ] - ToKL[ j ]」で駅間の距離を求められるのは同じ Sec の駅同士のときだけですので 空欄「 f 」は2駅が同じ区間かどうかを判定しています。
空欄「 f 」は「ウ」です。
空欄「g」
変更されたプログラムでは
K が 5 駅、N が 5 駅のとき Dist[ ][ ]は 25個 の数値を保持し、表1 は 1駅 につき 5個 の数値を保持しますので 5駅 で 25個、合計で 50個 の数値を保持します。
N が 6駅 のときは 25+5*6=55
N が 8駅 のときは 25+5*8=65
N が 9駅 のときは 25+5*9=70
N が 14駅 のときは 25+5*14=95
一方最初のプログラムでは
Nが 6駅 のときは 36
Nが 8駅 のときは 64
Nが 9駅 のときは 81
Nが 14駅 のときは 196
よって空欄「g」は「ウ」です。
ホームに戻るボタン↓
