基本情報技術者試験H27_s_Q8の解説

二次配布禁止 2015春 問8の解説 ～クイックソートの考え方～ 基本情報技術者試験に 興味のある皆さまへ 1

二次配布禁止 アジェンダ • • • • • • • 本日のゴール 基本情報技術者試験回答の戦略 疑似言語の表記方法について 問題演習① 20分 解説 25分 問題演習② 20分 解説 20分 2022/09/11 2

二次配布禁止 本日の講義のゴール 1. 基本情報技術者試験（FE）合格には、戦略が 必要なことを理解 2. FEのアルゴリズムの問題の雰囲気を掴む 3. アルゴリズムのトレース方法を理解 ※トレース：実際に値を入れて、アルゴリズムを動かしてみる 2022/9/11 3

二次配布禁止 基本情報技術者試験回答の戦略 • 配点に応じた時間配分をすべし！ • 解けなくても落ち込まない。 6割取ればいい！ – 見切りをつけ、他の問題で挽回 午後試験 問 配点 時間 試験時間 150分 問１ 20点 25分 出題形式 多岐選択方式 15点x2 20分 x 2 回答数 5問 問2~5 から2問 問6 25点 25点 40分 合格基準点 60% 2022/9/11 問7~11 40分 4

二次配布禁止 基本情報技術者試験回答の戦略 • 配点に応じた時間配分をすべし！ 2022年3月までの試験配点だが、 • 解けなくても落ち込まない。 アルゴリズム（問６）は得点比率が高い 6割取ればいい！ 今年度も配点が高そう！！ – 見切りをつけ、他の問題で挽回 午後試験 問 配点 時間 試験時間 150分 問１ 20点 25分 出題形式 多岐選択方式 15点x2 20分 x 2 回答数 5問 問2~5 から2問 問6 25点 25点 40分 合格基準点 60% 2022/9/11 問7~11 40分 5

二次配布禁止 問題を解く前に！ 疑似言語の表記方法について 2022/9/11 6

二次配布禁止 問題を解く前に！ 疑似言語の表記方法について もし、JOJOがすきなら（条件式） 好きなスタンドを教えて（処理） 2022/9/11 7

二次配布禁止 問題を解く前に！ 疑似言語の表記方法について もし、JOJOがすきなら（条件式） 好きなスタンド教えて（処理１） そうでなければ JOJOを紹介する（処理２） 2022/9/11 8

二次配布禁止 問題を解く前に！ 疑似言語の表記方法について 体重が７０kg以上なら（条件式） 走る（処理１） 体重が減るまで走り続ける（繰り返し） 2022/9/11 9

二次配布禁止 問題 2022/9/11 10

二次配布禁止 解説① 【ポイント】 1. 解答すべきことを問題文と設問から読み取る 2. 問題文と設問を精読して、アルゴリズムを理解 3. 繰り返しや条件判定等は、必ずチェック 4. 設問を読みつつ、値をトレースしていく ※トレース： 実際に値を入れて、アルゴリズムを動かしてみる 2022/9/11 11

二次配布禁止 解答すべきことを設問から把握する なるほど、具体的なことはわからないけど、 Topと Lastって変数の値を追いかければいいのか！ 2022/9/11 12

二次配布禁止 解答すべきことを設問から把握する なるほど、具体的なことはわからないけど、 αとγって処理は数を数えておかなければならない！ 2022/9/11 13

二次配布禁止 問題文を読み取る • 必要な情報を斜め読み 2022/9/11 14

二次配布禁止 問題文を読み取る 解答すべきことの TopとLastの意味がわかる クイックソートでいう 基準値がPivot 2022/9/11 15

二次配布禁止 繰り返し条件や記号に注意 2020/4/22 16

二次配布禁止 繰り返し条件や記号に注意 これが処理の終了条件 条件が満たされなくなったら終了 i,jは配列中の 探索場所を指し示すもの この処理の回数が 必要となる 2020/4/22 17

二次配布禁止 設問１を読みつつ、値をトレース 2022/9/11 18

二次配布禁止 設問１を読みつつ、値をトレース 配列の中身 x={3,5,6,4,7,2,1} k=3 Pivot=x[3]=6 i,jは配列の要素を 指し示すインデックス 2022/9/11 ↑ ↑ i ｊ 19

二次配布禁止 「選択処理 1回目」をトレース トレース（追跡）しやすいように 処理に番号を振る アルゴリズムの挙動全てを 一度に考えられる人は少ない。 分解して考えましょう 2020/4/22 20

二次配布禁止 「選択処理 1回目」をトレース ・トレース（追跡）しやすいように 処理に番号を振る ⑥ ・トレースが必要な値を把握する 特に条件の判定に利用されているもの ① ・Top,Last,Pivot,I,j,kは条件判定に 利用されているので把握が必要 ② ⑤ ④ ③ 2022/9/11 21

二次配布禁止 「選択処理 1回目」をトレース ⑥ TopがLastより小さければ Pivotにx[k]を代入 iにTopを代入 ｊにLastを代入 ① x[i]がpivotより小さかったら、 iを足すことを繰り返す ⑥ ① ② x[i]がpivotより大きかったら jを引くことを繰り返す ② ⑤ ④ iがｊより大きければ、 ⑤の繰り返しを抜ける ④ ③ ③ iとjが指し示す値を入れ替え、 I,jの値を更新 ⑤ 常に繰り返す ※④で強制的に抜けなければ続ける 2022/9/11 ⑤を抜けたら、TopとLastの値を更新 22

二次配布禁止 「選択処理 1回目」をトレース 処理 サブ 処理 ⑥ 配列ｘ Top 3 5 6 4 7 2 1 1 i ⑤ ⑥ ①② ③ ② ⑤ ④ ③ ｋ 7 6 3 3 5 6 4 7 2 1 j 3 5 1 4 7 2 6 i ①② Pivot j i ① Last j 3 5 1 4 7 2 6 i j ③ 3 5 1 4 2 7 6 j i ①②④ 2022/9/11 3 5 1 4 2 7 6 1 5 23

二次配布禁止 よって、aの答えは ア Topに値１、Lastに値５ 2022/9/11 24

二次配布禁止 「選択処理 2回目」をトレース 処理 サブ 処理 ⑥ 配列ｘ Top 3 5 1 4 2 7 6 1 i ⑤ ⑥ ①② ③ ② ⑤ ④ Pivot ｋ 5 1 3 j 3 5 1 4 2 7 6 i ① Last j 1 5 3 4 2 7 6 i,j ①② ③ 1 5 3 4 2 7 6 j i ④ 1 5 3 4 2 7 6 2 5 j i 2022/9/11 25

二次配布禁止 よって、bの答えは ウ Topに値２、Lastに値５ 2022/9/11 26

二次配布禁止 設問２を読みつつ、値をトレース 配列の値が変わったから、もう一回同じことをしないと アルゴリズムはコツコツと解いていくものだなぁ αは⑥の処理、βは①の処理、γは、③の処理の回数 だから、トレースして、数えよう 2022/9/11 27

二次配布禁止 めげずに「設問２」をトレース 処理 サブ 処理 ⑥ 配列ｘ Top 1 3 2 4 2 2 2 1 i ⑤ ⑥ ①② ③ ② ⑤ ④ ③ 7 2 3 j 1 2 2 4 2 2 3 j 1 2 2 4 2 2 3 i ③ ｋ 1 3 2 4 2 2 2 i ①② Pivot j i ① Last j 1 2 2 4 2 2 3 i j ①② 1 2 2 4 2 2 3 i j 2020/4/22 28

二次配布禁止 めげずに「設問２」をトレース 処理 サブ 処理 ⑤ ①② 配列ｘ Top 1 2 2 4 2 2 3 1 Last Pivot ｋ 7 2 3 2 3 i j ③ ⑥ 1 2 2 2 4 2 3 j i ① ①② 1 2 2 2 4 2 3 ② ⑤ j i ④ ④ 1 2 2 2 4 2 3 1 ③ j i ⑥ 1 2 2 2 4 2 3 i ⑤ ①② j 1 2 2 2 4 2 3 i 2022/9/11 4 j 29

二次配布禁止 めげずに「設問２」をトレース 処理 サブ 処理 ⑤ ①② 配列ｘ Top ⑥ Pivot ｋ 2 3 1 2 2 2 4 2 3 i ③ Last j 1 2 2 2 4 2 3 I,j ① ①② I,j ② ⑤ ④ ③ 1 2 2 2 4 2 3 ④ 1 2 2 2 4 2 3 4 2 I,j Top > Lastとなるので、処理終了 2022/9/11 30

二次配布禁止 よって、設問２の答えは αは⑥の処理の回数： 2回 γは③の処理の回数： 4回 2022/9/11 ｃ：イ d:エ 31

二次配布禁止 設問３の解説 【ポイント】 1. 解答すべきことを問題文と設問から読み取る 2. 問題文と設問を精読して、アルゴリズムを理解 3. 設問を読みつつ、値をトレースしていく ※トレース： 実際に値を入れて、アルゴリズムを動かしてみる 2022/9/11 32

二次配布禁止 解答すべきことを読み取る 2022/9/11 33

二次配布禁止 解答すべきことを読み取る そうだ！トレースしよう 2022/9/11 34

二次配布禁止 再度めげずに「設問３」をトレース 処理 サブ 処理 ⑥ 配列ｘ 1 1 1 1 1 1 1 i ⑤ ⑥ Top ① Last Pivot ｋ 6 1 3 j 1 1 1 1 1 1 iが配列外を参照 ① ② ⑤ ④ ③ 2022/9/11 35

二次配布禁止 よって、設問３のeの答えは eの答えは、オ 2022/9/11 36

二次配布禁止 再度めげずに「設問３」をトレース 処理 サブ 処理 ⑥ 配列ｘ Top 1 3 2 4 2 2 1 i ⑤ ⑥ ①② ③ ④ 6 2 3 J 1 2 2 4 2 3 I ①② ｋ 1 3 2 4 2 2 ② ⑤ Pivot j i ① Last j 1 2 2 4 2 3 ③ i J ③ 1 2 2 2 4 3 J i ④ 1 2 2 2 4 3 1 4 j i 2022/9/11 37

二次配布禁止 再度めげずに「設問３」をトレース 処理 サブ 処理 ④ 配列ｘ Top 1 2 2 2 4 3 1 Last Pivot ｋ 2 3 2 3 4 j i ⑥ ⑥ 1 2 2 2 4 3 i ① ①② 1 2 2 2 4 3 ② ⑤ j j i ④ ④ 1 2 2 2 4 3 ③ j i ⑥ 1 2 2 2 4 3 i ①② 1 4 j 1 2 2 2 4 3 j i 2022/9/11 38

二次配布禁止 再度めげずに「設問３」をトレース 処理 サブ 処理 ④ 配列ｘ Top 1 2 2 2 4 3 1 Last Pivot ｋ 2 3 2 3 4 j i ⑥ ⑥ 1 2 2 2 4 3 i ① ①② 1 2 2 2 4 3 ② ⑤ j j i ④ ④ 1 2 2 2 4 3 ③ j i ⑥ 1 2 2 2 4 3 i ①② 1 4 j 1 2 2 2 4 3 j i 2022/9/11 39

二次配布禁止 再度めげずに「設問３」をトレース 処理 サブ 処理 ④ 配列ｘ Top 1 2 2 2 4 3 1 Last Pivot ｋ 2 3 2 3 4 j i ⑥ ⑥ 1 2 2 2 4 3 i ① ①② 1 2 2 2 4 3 赤字を繰り返す j i ② ⑤ j ④ ④ 1 2 2 2 4 3 ③ j i ⑥ 1 2 2 2 4 3 i ①② 1 4 j 1 2 2 2 4 3 j i 2022/9/11 40

二次配布禁止 よって、設問３のfの答えは eの答えは、オ fの答えは、エ 2022/9/11 41

二次配布禁止 最後に • アルゴリズムの挙動を、一度に考えられる人は 少ないので、自分が理解できる単位で考え、併 せると、答えが見えてきます。 • 他の問題、プログラミングや仕事でも、分解の 考え方は、大事です。 2022/9/11 42

二次配布禁止 最後に • アルゴリズムの挙動を、一度に考えられる人は 少ないので、自分が理解できる単位で考え、併 せると、答えが見えてきます。 ⑥ • 他の問題、プログラミングや仕事でも、分解の ① 考え方は、大事です。 ② ⑤ ④ ③ 2022/9/11 43

二次配布禁止 最後に • アルゴリズムの挙動を、一度に考えられる人は 少ないので、自分が理解できる単位で考え、併 せると、答えが見えてきます。 • 他の問題、プログラミングや仕事でも、分解の 考え方は、大事です。 • アルゴリズムは、頭がこんがらがりますが、 解けた時の喜びも、ひとしおです。 楽しんで、勉強してみてください 2022/9/11 44

二次配布禁止 試験で、 知らないアルゴリズムが出てきたら • あきらめないでください。 • 問題文に、アルゴリズムの説明がありま す。理解すれば、時間はかかるけれど、 問題を解くことができます。 2022/9/11 45

二次配布禁止 問題文にアルゴリズムの説明がある 2022/9/11 46

二次配布禁止 プログラムの説明も 解答すべきことの TopとLastの意味がわかる クイックソートでいう 基準値がPivot 2022/9/11 47

二次配布禁止 まとめ 1. 基本情報技術者試験（FE）合格には、 得点配分、時間配分、当日の問題の選択等の戦略が必要 2. FEのアルゴリズムの問題の雰囲気を、過去問題を通して把握。 一発で回答できるものではなく、一つ一つの積み重ね 3. 条件分岐や処理の切り替わり、終了の時に利用される変数は かならずチェック 4. アルゴリズムのトレース方法を理解 アルゴリズム中の条件分岐や繰り返しの条件に利用されている変 数に特に着目して、トレースする。 2022/9/11 48

二次配布禁止 ご清聴ありがとうございました 皆様の基本情報技術者試験の合格を 心よりお祈り申し上げます 49