HOME»基本情報技術者試験掲示板»平成29年春 問８
投稿する
ほとんどはそれで正解ですが、絶対とは言えません。
繰返しのカウンタ変数とは別に、繰り返しの中で変わるものがあって、それをチェックする必要がある場合もあります。
ん？よく見ると今回の問題でも繰り返しの中でiの値が変わる可能性があるから、チェック不要とは言い切れないのか。
ええと、もう少しきちんと処理を見て説明しないといけないですね・・・
平成29年春 問８ [2494]
かいさん(No.1)
最短経路の問題について、以下２点質問させてください。
・質問１（アルゴリズムの挙動について）
初めて３１行目の処理を行うときの判定は偽なのですが、その時は33行目にいくでしょうか？それとも30行目のループにもどるでしょうか？
初回処理で３１行目は偽なのですが３３行目に行く場合、newDistにはまだ何も値が入っていないのですがその場合は値が入っていないから３３行目は判定すらできないので偽で３０行目にもどると解釈していますが、その理解で相違ないでしょうか？
・質問２
空欄Aについて、答えはnot(pFixed[j])なのですが、not(pFixed[i])と判断しないのはどういうロジックで導くのでしょうか？設問２を回答するためには３回処理をトレースすれば回答ができますが、not(pFixed[j])でもnot(pFixed[i])でもどちらでも３回までのトレースは問題なくできると思います。23行目でJを初期値としているのでという理由でnot(pFixed[j])を選びましたが確証を持っての回答ではないので、考え方教えてください。
どうぞよろしくお願いいたします。
・質問１（アルゴリズムの挙動について）
初めて３１行目の処理を行うときの判定は偽なのですが、その時は33行目にいくでしょうか？それとも30行目のループにもどるでしょうか？
初回処理で３１行目は偽なのですが３３行目に行く場合、newDistにはまだ何も値が入っていないのですがその場合は値が入っていないから３３行目は判定すらできないので偽で３０行目にもどると解釈していますが、その理解で相違ないでしょうか？
・質問２
空欄Aについて、答えはnot(pFixed[j])なのですが、not(pFixed[i])と判断しないのはどういうロジックで導くのでしょうか？設問２を回答するためには３回処理をトレースすれば回答ができますが、not(pFixed[j])でもnot(pFixed[i])でもどちらでも３回までのトレースは問題なくできると思います。23行目でJを初期値としているのでという理由でnot(pFixed[j])を選びましたが確証を持っての回答ではないので、考え方教えてください。
どうぞよろしくお願いいたします。
2020.09.20 08:48
翔太さん(No.2)
取り急ぎ質問1だけ…
結論から申し上げると、31行目が偽の時は33行目ではなく30行目に戻ります。
31の▲と対応しているのは37行目の▼ですね。
31行目の条件が真だったら32～37行目に書かれている処理や条件判断を行い、偽の場合はこの範囲の処理をしません。
結論から申し上げると、31行目が偽の時は33行目ではなく30行目に戻ります。
31の▲と対応しているのは37行目の▼ですね。
31行目の条件が真だったら32～37行目に書かれている処理や条件判断を行い、偽の場合はこの範囲の処理をしません。
2020.09.20 09:08
QMさん(No.3)
★FE ゴールドマイスター
では私は質問２のほうを。
なぜnot(pFixed[j])なのか、ではなく、なぜnot(pFixed[i])ではないのか、というご質問なので、その観点で行くと。
jを変えながら探しているので・・・という見分け方で特に問題はないと思います。
iは変わらないのでnot(pFixed[i])をここで毎回判定する意味はない、そんなコードは書かないだろう、と。
また、15行目でnot(pFixed[i])で繰返しを抜けてから来ているので（抜けていなければ20行目で終わる）、やはり23行目でnot(pFixed[i])をあらためて判定するのは意味がないとわかります。
なぜ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)
翔太さん
回答ありがとうございます。
３７行目に▼がありますね。
３１～３７の動きを正しく理解していませんでした。
しっくりきました！
回答ありがとうございます。
３７行目に▼がありますね。
３１～３７の動きを正しく理解していませんでした。
しっくりきました！
2020.09.22 15:22
かいさん(No.5)
QMさん
解説ありがとうございます。
非常に分かりやすかったです。
他の問題でもなんとなく繰り返し条件でインクリする値と同じものを
次の行の判定で選んでいましたが、そもそも毎回判定する意味がない
という部分は自分では気づけておらず、やっと腹落ちしました。
ありがとうございました。
解説ありがとうございます。
非常に分かりやすかったです。
＞jを変えながら探しているので・・・という見分け方で特に問題はないと思います。
＞iは変わらないのでnot(pFixed[i])をここで毎回判定する意味はない、そんなコードは書かないだろう、と。
他の問題でもなんとなく繰り返し条件でインクリする値と同じものを
次の行の判定で選んでいましたが、そもそも毎回判定する意味がない
という部分は自分では気づけておらず、やっと腹落ちしました。
ありがとうございました。
2020.09.22 15:37
QMさん(No.6)
★FE ゴールドマイスター
>他の問題でもなんとなく繰り返し条件でインクリする値と同じものを
>次の行の判定で選んでいましたが、
ほとんどはそれで正解ですが、絶対とは言えません。
繰返しのカウンタ変数とは別に、繰り返しの中で変わるものがあって、それをチェックする必要がある場合もあります。
ん？よく見ると今回の問題でも繰り返しの中でiの値が変わる可能性があるから、チェック不要とは言い切れないのか。
ええと、もう少しきちんと処理を見て説明しないといけないですね・・・
2020.09.23 22:54
QMさん(No.7)
★FE ゴールドマイスター
うん、納得していただいたところをひっくり返すような感じで申し訳ないですが。
やっぱり形からではなく、意味から考えて判断したほうがいいですね。
未確定の地点から探しているのだから、not(pFixed[i])は必ずtrue。
もっと近い地点が見つかった（i←j）としても、それも未確定地点のはず。
ただ、そもそも「未確定の地点から探す」という条件が必要だから、それがaに入っていないといけなくて、
それはすでに見つけているiではなくて次に見ようとしているjのはずで。
結局、iだと意味がない、ではなくて、jでないとおかしい、でした。
まあ、「jを変えながら探しているので」で合ってはいるんですが。
やっぱり形からではなく、意味から考えて判断したほうがいいですね。
未確定の地点から探しているのだから、not(pFixed[i])は必ずtrue。
もっと近い地点が見つかった（i←j）としても、それも未確定地点のはず。
ただ、そもそも「未確定の地点から探す」という条件が必要だから、それがaに入っていないといけなくて、
それはすでに見つけているiではなくて次に見ようとしているjのはずで。
結局、iだと意味がない、ではなくて、jでないとおかしい、でした。
まあ、「jを変えながら探しているので」で合ってはいるんですが。
2020.09.23 23:22
かいさん(No.8)
QMさん
追加、詳しくありがとうございます。
→意味からは正直まだハードル高く感じちゃいますね。。
アルゴリズム（トレーズ）の動きと図①がまだ同時に動かないですね。
なので、プログラムの意味は実はよく分かっていないです。。
本問に限らず問８はトレースで答え導いているだけですので、正直。。
なので、QMさんの読み解き方はすごく勉強になります。
やはりそこまで（意味まで）理解しないとですかね、。
「25行目のiも、結局はjの値を入れている」
という部分を読み解けるかがキーと理解しました。
ここも機械的にトレースしてるだけなので、
その観点は新しく、勉強になりました。
別の過去問でももう少し読み解きながら
トレースしてみようと思います。
ありがとうございます！
追加、詳しくありがとうございます。
＞やっぱり形からではなく、意味から考えて判断したほうがいいですね。
→意味からは正直まだハードル高く感じちゃいますね。。
アルゴリズム（トレーズ）の動きと図①がまだ同時に動かないですね。
なので、プログラムの意味は実はよく分かっていないです。。
本問に限らず問８はトレースで答え導いているだけですので、正直。。
なので、QMさんの読み解き方はすごく勉強になります。
やはりそこまで（意味まで）理解しないとですかね、。
「25行目のiも、結局はjの値を入れている」
という部分を読み解けるかがキーと理解しました。
ここも機械的にトレースしてるだけなので、
その観点は新しく、勉強になりました。
別の過去問でももう少し読み解きながら
トレースしてみようと思います。
ありがとうございます！
2020.09.25 19:37