アルゴリズム基礎概念-順次探索法と二分探索法

本日のめあて アルゴリズムの基本概念 順次探索法と二分探索法を理解しよう

「アルゴリズムたいそう」 を見たことがある人✋

アルゴリズムたいそう https://www2.nhk.or.jp/school/watch/bangumi/?das_id=D0005260216_0 0000#in=94&out=162アルゴリズム体操

• https://www2.nhk.or.jp/school/watch/bangumi/?das_id=D0005260216_0

「アルゴリズムたいそう」の歌詞 歌詞を見て、気づくことはありますか？ こっちむいて 2人で 前ならえ あっちむいて 2人で 前ならえ こっちむいて 2人で 前ならえ あっちむいて 2人で 前ならえ 手を 横に あら あぶない 頭をさげれば ぶつかりません 手を 横に あら あぶない 頭をさげれば だいじょうぶ ぐるぐるぐる ぐるぐるぐる ぐーるぐる ぐるぐるぐる ぐるぐるぐる ぐーるぐる ぱっちん ぱっちん ガシン ガシン ぱっちん ぱっちん ガシン ガシン ぱっちん ぱっちん ガシン ガシン ぱっちん ぱっちん ガシン ガシン すって はくのが しんこきゅう すって はくのが しんこきゅう

アルゴリズムの基本概念

アルゴリズムの基本概念 ① 順次処理 ② 分岐処理 ③ 繰り返し アルゴリズムの仕組みは3つでできている

アルゴリズムの基本概念 ① 順次処理 処理1 処理2 処理3 上から順番に 処理していく

アルゴリズムの基本概念 ① 順次処理 (例)レシピ ・豚バラを鍋に入れる ・豆腐を鍋に入れる ・鍋の火をつける

アルゴリズムの基本概念 条件によって 処理の内容を変える ② 分岐処理 条件 No Yes 処理1 処理2

アルゴリズムの基本概念 ② 分岐処理 (例)ライト ・スイッチはON？OFF？ ・ライトをつける ・ライトを消す

アルゴリズムの基本概念 条件に当てはまる限り 処理を繰り返す ③ 繰り返し 条件 Yes 処理 No

アルゴリズムの基本概念 ③ 繰り返し (例)プリントを配る ・クラス全員にプリントを 配れたか？ ・次の人にプリントを配る

アルゴリズムとは？

アルゴリズムとは? ナビ レシピ

アルゴリズムとは？ アルゴリズムとは… 処理の手順

「アルゴリズムたいそう」 の歌詞を振り返ろう

「アルゴリズムたいそう」の歌詞を振り返ろう こっちむいて 2人で 前ならえ あっちむいて 2人で 前ならえ こっちむいて 2人で 前ならえ あっちむいて 2人で 前ならえ 順次処理 手を 横に あら あぶない 頭をさげれば ぶつかりません 手を 横に あら あぶない 頭をさげれば だいじょうぶ 分岐処理 ぐるぐるぐる ぐるぐるぐる ぐーるぐる ぐるぐるぐる ぐるぐるぐる ぐーるぐる 繰り返し ぱっちん ぱっちん ガシン ガシン ぱっちん ぱっちん ガシン ガシン ぱっちん ぱっちん ガシン ガシン ぱっちん ぱっちん ガシン ガシン すって はくのが しんこきゅう すって はくのが しんこきゅう 順次処理 「アルゴリズムたいそう」は処理(動き)の手順になっている

「アルゴリズムたいそう」の歌詞 「アルゴリズムたいそう」の歌詞を振り返ろう 実際に、NHKのWebサイトには… 1人でやっても意味がわからない動きでも、 2人が組み合わさることによって意味を持つ、 アルゴリズム（物を解くための手順）をテーマにした体操。

順次探索法と二分探索法

順次探索法と二分探索法 そもそも「探索法」とは？ 多くのデータの中から条件に合致する データを探し出すためのアルゴリズム 名簿から 「田中太郎」 を探して

順次探索法と二分探索法 ① 順次探索法（線形探索法） １つずつ順番に データを探す方法 1 2 3

順次探索法と二分探索法 ① 順次探索法（線形探索法） メリット: 処理の手順を簡単に作成することができる デメリット: データ個数が増えると時間がかかる（最大n回） 3000 3001 3002 3003 300

順次探索法と二分探索法 ② 二分探索法 データを半分に分け続けて探す方法 例）0~5のデータから「1」を探す 0 1 2 0 1 2 0 1 1 3 4 5 1/2にする 1/2にする（余るので＋１） 1/2にする

順次探索法と二分探索法 ① 二分探索法 メリット: log(2)N回で求めることができる。 例）100個のデータのある数を求めるための比較回数 log(2)100 = log(2)10^2 = 2*log(2)10 = 6.643… = 最大7回 ※log(2)10 = 3.3219… デメリット: 1,2,3,~,100など順番に整列(ソート)する必要がある

アルゴリズムで遊んでみよう

アルゴリズムで遊んでみよう アルゴリズムで 誕生日を当ててみよう

アルゴリズムで遊んでみよう 直接答えを聞く以外で 誕生日を当てるには？

アルゴリズムで遊んでみよう 「アルゴリズムで誕生日を当ててみよう」 方法1：当てずっぽうに聞く（乱択アルゴリズム） > 運が良ければ1回で当たるが、1~366回かかる可能性がある 方法2：順番に聞く（順次探索法） > 1月1日からスタートし、12月31日の場合366回かかる可能性がある これらはアルゴリズム（処理の手順）として… 非効率

アルゴリズムで遊んでみよう 「アルゴリズムで誕生日を当ててみよう」 では、どうすればいいのか… 二分探索法

アルゴリズムで遊んでみよう 「アルゴリズムで誕生日を当ててみよう」 「二分探索法」で誕生日を当ててみよう！ ルール： ① 「はい」か「いいえ」で答える ② 1月1日スタート～12月31日 やり方：（例：12月27日） ① 1~12月の半分の【7月1日】より「早い」or「遅い」？ ② 7~12月の半分の【10月1日】より「早い」or「遅い」？ このように、半分にしながら誕生日がある範囲を狭めていく。

なぜ誕生日が分かるのか

なぜ誕生日が分かるのか（目標：12月27日） 紙を使って「二分探索」では何が起きているか知ってみよう ① 1月 2月 3月 ② 7月 8月 9月 10月 11月 12月 11月 12月 1/2にする 4月 5月 6月 7月 8月 9月 10月 11月 12月 1/2にする ③ 10月

なぜ誕生日が分かるのか（目標：12月27日） 紙を使って「二分探索」では何が起きているか知ってみよう ④ ③ 10月 11月 12月 11月 1/2にする 12月 1/2にする ⑤ 12月

なぜ誕生日が分かるのか（目標：12月27日） 紙を使って「二分探索」では何が起きているか知ってみよう ⑤ 1/2にする ⑥ 1/2にする

なぜ誕生日が分かるのか（目標：12月27日） 紙を使って「二分探索」では何が起きているか知ってみよう ⑦ 1/2にする ⑧ 1/2にする

なぜ誕生日が分かるのか（目標：12月27日） 紙を使って「二分探索」では何が起きているか知ってみよう ⑨ 1/2にする ⑩

なぜ誕生日が分かるのか（目標：12月27日） なぜ二分探索法で誕生日を発見できた？： ・カレンダーは順番に月日が並んでいるから 二分探索法はlog(2)N回で求められる： 目標）366日から「12月27日」を求めるための比較回数 log(2)366 = 8.515… = 最大9回

本日のまとめ

本日のまとめ 〇アルゴリズムの基本概念とは？ ・順次処理 ・分岐処理 ・繰り返し 〇アルゴリズムとは？ ・アルゴリズムは「処理の手順」 〇多くのデータからデータを探すアルゴリズムとは？ ①順次探索法（線形探索法） ②二分探索法 〇２つの探索法のそれぞれのメリット／デメリットとは？ ①処理の手順が簡単／データの数が増えると時間がかかる ②log(2)N回で見つかる／データを順番にする必要がある