HOME»基本情報技術者試験掲示板»平成29年春  問8

基本情報技術者試験掲示板

掲示板検索:

平成29年春  問8[2494]

かいさん(No.1)

最短経路の問題について、以下2点質問させてください。

・質問1(アルゴリズムの挙動について)
初めて31行目の処理を行うときの判定は偽なのですが、その時は33行目にいくでしょうか?それとも30行目のループにもどるでしょうか?
初回処理で31行目は偽なのですが33行目に行く場合、newDistにはまだ何も値が入っていないのですがその場合は値が入っていないから33行目は判定すらできないので偽で30行目にもどると解釈していますが、その理解で相違ないでしょうか?


・質問2
空欄Aについて、答えはnot(pFixed[j])なのですが、not(pFixed[i])と判断しないのはどういうロジックで導くのでしょうか?設問2を回答するためには3回処理をトレースすれば回答ができますが、not(pFixed[j])でもnot(pFixed[i])でもどちらでも3回までのトレースは問題なくできると思います。23行目でJを初期値としているのでという理由でnot(pFixed[j])を選びましたが確証を持っての回答ではないので、考え方教えてください。

どうぞよろしくお願いいたします。

2020.09.20 08:48
翔太さん(No.2)

取り急ぎ質問1だけ…

結論から申し上げると、31行目が偽の時は33行目ではなく30行目に戻ります。
31の▲と対応しているのは37行目の▼ですね。
31行目の条件が真だったら32〜37行目に書かれている処理や条件判断を行い、偽の場合はこの範囲の処理をしません。

2020.09.20 09:08
QMさん(No.3)

では私は質問2のほうを。
なぜnot(pFixed[j])なのか、ではなく、なぜnot(pFixed[i])ではないのか、というご質問なので、その観点で行くと。

jを変えながら探しているので・・・という見分け方で特に問題はないと思います。
iは変わらないのでnot(pFixed[i])をここで毎回判定する意味はない、そんなコードは書かないだろう、と。
また、15行目でnot(pFixed[i])で繰返しを抜けてから来ているので(抜けていなければ20行目で終わる)、やはり23行目でnot(pFixed[i])をあらためて判定するのは意味がないとわかります。

2020.09.20 11:04
かいさん(No.4)

翔太さん
回答ありがとうございます。
37行目に▼がありますね。
31〜37の動きを正しく理解していませんでした。
しっくりきました!

2020.09.22 15:22
かいさん(No.5)

QMさん

解説ありがとうございます。
非常に分かりやすかったです。

>jを変えながら探しているので・・・という見分け方で特に問題はないと思います。
>iは変わらないのでnot(pFixed[i])をここで毎回判定する意味はない、そんなコードは書かないだろう、と。

他の問題でもなんとなく繰り返し条件でインクリする値と同じものを
次の行の判定で選んでいましたが、そもそも毎回判定する意味がない
という部分は自分では気づけておらず、やっと腹落ちしました。

ありがとうございました。

2020.09.22 15:37
QMさん(No.6)

>他の問題でもなんとなく繰り返し条件でインクリする値と同じものを
>次の行の判定で選んでいましたが、
ほとんどはそれで正解ですが、絶対とは言えません。
繰返しのカウンタ変数とは別に、繰り返しの中で変わるものがあって、それをチェックする必要がある場合もあります。

ん?よく見ると今回の問題でも繰り返しの中でiの値が変わる可能性があるから、チェック不要とは言い切れないのか。
ええと、もう少しきちんと処理を見て説明しないといけないですね・・・

2020.09.23 22:54
QMさん(No.7)

うん、納得していただいたところをひっくり返すような感じで申し訳ないですが。
やっぱり形からではなく、意味から考えて判断したほうがいいですね。

未確定の地点から探しているのだから、not(pFixed[i])は必ずtrue。
もっと近い地点が見つかった(i←j)としても、それも未確定地点のはず。
ただ、そもそも「未確定の地点から探す」という条件が必要だから、それがaに入っていないといけなくて、
それはすでに見つけているiではなくて次に見ようとしているjのはずで。

結局、iだと意味がない、ではなくて、jでないとおかしい、でした。
まあ、「jを変えながら探しているので」で合ってはいるんですが。

2020.09.23 23:22
かいさん(No.8)

QMさん

追加、詳しくありがとうございます。

>やっぱり形からではなく、意味から考えて判断したほうがいいですね。
→意味からは正直まだハードル高く感じちゃいますね。。
  アルゴリズム(トレーズ)の動きと図@がまだ同時に動かないですね。
  なので、プログラムの意味は実はよく分かっていないです。。
  本問に限らず問8はトレースで答え導いているだけですので、正直。。

なので、QMさんの読み解き方はすごく勉強になります。
やはりそこまで(意味まで)理解しないとですかね、。

「25行目のiも、結局はjの値を入れている」
という部分を読み解けるかがキーと理解しました。

ここも機械的にトレースしてるだけなので、
その観点は新しく、勉強になりました。

別の過去問でももう少し読み解きながら
トレースしてみようと思います。

ありがとうございます!

  

2020.09.25 19:37

【返信投稿用フォーム】

お名前(10文字以内)

顔アイコン


本文(2,000文字以内)

記事削除用パスワード(20文字以内)

プレビュー

※宣伝や迷惑行為を防止するため当サイトとIPAサイト以外のURLを含む記事の投稿は禁止されています。

投稿記事削除用フォーム

投稿No. パスワード 
© 2010-2020 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop