福嶋先生の「基本情報技術者試験 午後・アルゴリズム編」を勉強していて、少し理解に時間がかかったところ
<__「(p.49)ループ端記号」__について個人的なまとめ>
前判定ループ:終端に終了条件があるため、1回も処理を実行しないことがある
後判定ループ:始端に終了条件があるため、必ず1回は処理を実行する
したがって
前判定では、いつまで繰り返せばよいのかわかっている場合に用いる。
後判定では、いつまで繰り返せばよいのか処理実行後の値で判断する場合に用いる。
上記二文がこの本には強調して記載されていなかったので、なんのために後判定が存在しているのか?など少し考えてしまいました。
また、本文には
例えば、10万回入力する場合、前判定が10万回の比較に対し、後判定は20万回の比較が行われるので、その違いは明らかである
という記述があり、最初???となりました。
以下図を見て考えます。
ループ前に1件目を入力するのか、ループ後に1件目を入力するのかが主な違い。
ループの前で1件目を入力するようにすると、(2)の前判定型ループとなり、効率的になる。
(1)後判定ループ (2)前判定ループ
フローチャートはこちらのサイトで作成→ https://app.diagrams.net/
繰り返し回数が決まっている場合は、後判定では各ループ2回ずつ(ひし形部分と合計金額の一つ前の部分)比較してしまうので、処理が2倍になり、非効率ということになります。
いまいちイメージしずらかったので、こんな具体例を考えました。
徒競走でA~Zまでランダムに1人ずつ走り、Gが到着した時点で試合終了とし、そこまでに走った合計走者数をカウントします。
(1)後判定ループでは、__合計走者数を算出する(処理実行)か判断する__ためにスタート地点で走者がGであることをチェック(ひし形部分)し、__試合終了する(ループから抜ける)__ためにゴール地点で再びランナーがGであるかチェックしています。毎レースごとにスタート地点(1回目)とゴール地点(2回目)でGであるかどうかのチェックが行われ、非効率です。自分が審判だった場合、合計走者数算出を行うかどうかと試合を終了するかどうかをいっぺんにしたい!と思います。
(2)前判定ループでは、スタート地点でランナーがGであるかチェックすると、そいつにたすきをかけてゴール地点に知らせることで、試合終了の判断をしなくていいよう工夫しています。これにより、スタート地点(1回目)でのチェックだけでよくなるので比較回数が減らせるということになります。
この例では、前判定が推奨されますが、ここからさらに__各ランナーは1~9までの数字カードを持っていてその合計が30を超えた場合でもループを抜けることができる__といったような条件を付けた場合、これは__何回繰り返したらその条件を満たすか不明__ですので前判定できないですよね。この場合、後判定を用います。