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

>100 Views

September 14, 22

スライド概要

基本情報技術者試験のアルゴリズムの解説を行いました。
試験を頑張っている皆さまのお役に立てればと思います。

profile-image

情報系の指導員をしてます。 AIやXR等を適度にかじっています。

シェア

※このスライドは限定公開です。一般公開されていないためご注意ください

埋め込む »CMSなどでJSが使えない場合

各ページのテキスト
1.

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

2.

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

3.

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

4.

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

5.

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

6.

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

7.

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

8.

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

9.

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

10.

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

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18.

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

19.

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

20.

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

21.

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

22.

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

23.

二次配布禁止 「選択処理 1回目」をトレース 処理 サブ 処理 ⑥ 配列x Top 3 5 6 4 7 2 1 1 i ⑤ ⑥ ①② ③ ② ⑤ ④ ③ k 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

24.

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

25.

二次配布禁止 「選択処理 2回目」をトレース 処理 サブ 処理 ⑥ 配列x Top 3 5 1 4 2 7 6 1 i ⑤ ⑥ ①② ③ ② ⑤ ④ Pivot k 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

26.

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

27.

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

28.

二次配布禁止 めげずに「設問2」をトレース 処理 サブ 処理 ⑥ 配列x 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 ③ k 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

29.

二次配布禁止 めげずに「設問2」をトレース 処理 サブ 処理 ⑤ ①② 配列x Top 1 2 2 4 2 2 3 1 Last Pivot k 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

30.

二次配布禁止 めげずに「設問2」をトレース 処理 サブ 処理 ⑤ ①② 配列x Top ⑥ Pivot k 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

31.

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

32.

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

33.

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

34.

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

35.

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

36.

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

37.

二次配布禁止 再度めげずに「設問3」をトレース 処理 サブ 処理 ⑥ 配列x Top 1 3 2 4 2 2 1 i ⑤ ⑥ ①② ③ ④ 6 2 3 J 1 2 2 4 2 3 I ①② k 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

38.

二次配布禁止 再度めげずに「設問3」をトレース 処理 サブ 処理 ④ 配列x Top 1 2 2 2 4 3 1 Last Pivot k 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

39.

二次配布禁止 再度めげずに「設問3」をトレース 処理 サブ 処理 ④ 配列x Top 1 2 2 2 4 3 1 Last Pivot k 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

40.

二次配布禁止 再度めげずに「設問3」をトレース 処理 サブ 処理 ④ 配列x Top 1 2 2 2 4 3 1 Last Pivot k 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

41.

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

42.

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

43.

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

44.

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

45.

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

46.

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

47.

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

48.

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

49.

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