HOME»基本情報技術者試験掲示板»平成27年春期午後問8
投稿する

平成27年春期午後問8 [4078]

 さっちーさん(No.1) 
  行番号25~30で、「走査範囲が基準値以下の値から成るグループと基準値以上の値から成るグループに分割されるので,k番目に小さい値が含まれるグループを新たな走査範囲とする」とあります。
ここで分からない部分があり、なぜ「iがk以下ならば探索範囲の先頭を j+1 に変更し、jがk以上ならば探索範囲の末尾を i-1 に変更」することが、「k番目に小さい値が含まれるグループを新たな走査範囲とする」ことになるのかが分かりません。

  意味を理解しなくとも、時間をかけてトレースすると解けたのですが、やはり意味を理解しながらトレースできたほうが良いのでしょうか?
2022.04.02 20:43
FE受かりたいマンさん(No.2) 
iとjがクロスする、または重なる要素番号より左側に設定された基準値より低い値、
そして右側に大きい値がまとめられてることはトレースされているのなら理解されてると思います。
ここの部分をもっと細かく見ていきます。

例えば7つの数字が入った配列xが与えられて3番目に小さい数字を求めるために
SELECT()が実行されて、最初に設定されたPivotの値が全体の5番目に小さい値だったとします。
この時左側の小さいグループに1番目から5番目、右側の大きいグループに6番目から7番目が
まとめられています。(何番目までを小さい側に入れるかは配列によって多少ずれる)
何故なら5番目に小さい値を基準にして小さい値を左側、大きい値を右側に分けているからです。
3番目に小さい数字を求めるのであれば右側のグループを更にソートする必要はありません。
右側には目的の数字が入っていないからです。
基準値で分けた二つのまとまりのどちら側を更に調べていくのかを決めるのが
25行から30行目までの処理なのです。
小さい値のまとまりを更に調べるならLastにiとjがぶつかった要素番号を
大きい値のまとまりを更に調べるならTopにiとjがぶつかった要素番号を設定しています。

>意味を理解しなくとも、時間をかけてトレースすると解けたのですが、やはり意味を理解しながらトレースできたほうが良いのでしょうか?
ちゃんと疑似言語の意味を理解してトレース出来るのが一番望ましいです。
何より理解出来ればそもそも1行1行しっかりトレースせず後半の問題が解けるようになります。
ただ、初見のアルゴリズムで短い時間の中そこまで理解するのは厳しいのも事実です。
ですがクイックソートみたいなメジャーなアルゴリズムは再度問われる可能性があるので
じっくり研究して意味を理解された方がいいと思います。
2022.04.02 21:42
 さっちーさん(No.3) 
ありがとうございます!
長い時間考えても理解できなかったので質問投稿しましたが、理解できました!
メジャーなアルゴリズムは仕組みをしっかり理解できるよう勉強します…
2022.04.03 17:05
返信投稿用フォームスパム防止のためにスレッド作成日から30日経過したスレッドへの投稿はできません。
© 2010- 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop