情報Ｂ アルゴリズム 栃木県立鹿沼東高等学校 情報科 山﨑 貴史. アルゴリズムとコンピュータ z コンピュータ（計算機） 「命令しないとただの箱」 処理手順（アルゴリズム）が必要 → 表現方法はプログラム言語 z プログラム言語 Ｃ言語、ＣＯＢＯＬ、ＢＡＳＩＣ など → コンピュータ・人間どちらにとっても.

Presentation on theme: "情報Ｂ アルゴリズム 栃木県立鹿沼東高等学校 情報科 山﨑 貴史. アルゴリズムとコンピュータ z コンピュータ（計算機） 「命令しないとただの箱」 処理手順（アルゴリズム）が必要 → 表現方法はプログラム言語 z プログラム言語 Ｃ言語、ＣＯＢＯＬ、ＢＡＳＩＣ など → コンピュータ・人間どちらにとっても."— Presentation transcript:

1 情報Ｂ アルゴリズム 栃木県立鹿沼東高等学校 情報科 山﨑 貴史

2 アルゴリズムとコンピュータ z コンピュータ（計算機） 「命令しないとただの箱」 処理手順（アルゴリズム）が必要 → 表現方法はプログラム言語 z プログラム言語 Ｃ言語、ＣＯＢＯＬ、ＢＡＳＩＣ など → コンピュータ・人間どちらにとっても わかりやすさが必要！

3 アルゴリズムのわかりやすさ （１） z 複雑なものを整理 シンプル イズ ベスト！ → 箇条書き（場合分け）、短文・記号化 ＜文章＞ 図形の面積を求めるとき、その形で求め方が 変わります。正方形や長方形それから平行四 辺形の場合はたてと横をかけて計算しますが 、台形の場合はまず上底と下底を加え、それ に高さをかけてさらに２で割ります。三角形 の場合は底辺と高さをかけて２で割り、円の 場合半径と半径をかけたものに円周率 π をか けて計算します。 ＜わかりやすくした例＞ 図形の面積の求め方 たてａ, 横ｂ, 上底ｊ, 下底ｋ, 底辺ｔ, 高さｈ, 半 径ｒとする①正方形、長方形、平行四辺形 ａ × ｂ ②台形 （ｊ＋ｋ） × ｈ／２ ③三角形 ｔ × ｈ／２ ④円 ｒ × ｒ ×π

4 アルゴリズムのわかりやすさ （２） z 構造化 「１つの入口と１つの出口」をもつ → ミスが減る、直しやすい → 高品質のプログラ ム ３つの基本制御構造の組合せ 順次選択くりかえ し

5 アルゴリズムのわかりやすさ （３） z 図式化（流れ図） 流れ図記号で表現 → 処理手順わかりやすい

6 流れ図（フローチャート） （１） z 流れ図記号（ＪＩＳ規格） 端子 流れ図の開始・ 終了 データ データの入出力 処理 あらゆる種類の 処理 判断 条件による判断 （選択） 書類 書類に印字 表示 ディスプレイへ の表示 準備 初期値の設定等 の処理の準備 ループ始端 ループ終端 ループ（繰り返 し）の始まりと 終わり これらを実線や矢線で結んで、流れを表現する。

7 流れ図（フローチャート） （２） z 流れ図の例 端子 準備 判断 処理 データ 表示 （初期処理）面積を保存する変数Ｓに０を代入 （判断）図形の形によって、処理を分岐する データ入力を求め る z みんなの起床から学校到着 を流れ図に表現しよう！

8 流れ図（フローチャート）とプログ ラム z プログラミング アルゴリズムを図式した流れ図をもとに、 プログラムを作成すること。 z マクロ 処理を自動的に実行するプログラム → 手作業を自動化する （ミスが減る、作業時間の短縮） この教室のＰＣでは、これらマクロをプログラミング言語 VBA で記 述する。 Visual Basic for Applications （ Microsoft 製） ＜先生が開発した流れ図作成支援ツールも、 VBA でかいています。＞

9 アルゴリズム基礎（１） 順次構造 ● キーボードから変数 a に 3 ，変数 b に 5 を入力し，その和を求めて表示する。 データを保存する容器にあたるもの 箇条書き フローチャート ①変数 a ，変数 b の値をキーボードから入力 ②変数 a と変数 b の値を加算して，変数 c に代入 ③変数 c の値をディスプレイ（画面）に表示 プログラム例および実行結 果

10 アルゴリズム基礎（２） 選択構造 ● 得点が 50 点以上のときは変数 G に 1 ， 50 点未満のときは変数 G に 0 を代入して表示する。 箇条書き フローチャート ①変数 tokuten に値を入力 ② tokuten が 50 点以上ならば， ③ G に 1 を代入 ④ tokuten が 50 点未満ならば， ⑤ G に 0 を代入 ⑥変数 G の値を表示 プログラム例および実行結 果

11 アルゴリズム基礎（３） くりかえ し構造 ● 変数ｘに 1 から 10 までの値を代入して表示する。 箇条書き フローチャート (1) 繰り返し 1 （繰り返し回数が明確） (2) 繰り返し 2 （繰り返し回数が明確でない） ①x←1①x←1 ② x ≦ 10 の間，繰り返す ③ x を表示 ④x←x＋1④x←x＋1 ⑤ x の繰り返しはここまで ① x を 1 から 10 まで 1 ずつ 増やしながら繰り返す ② x を表示 ③ x の繰り返しはここまで プログラム例および実行結 果

12 アルゴリズム応用（１） 逐次探索 逐次探索 表の先頭から順番に 1 つずつ探しだす 77635842362411 「 36 」を探す 36 ≠ ≠ ＝ アルゴリズ ム フローチャー ト ① j は 1 から 7 まで 1 ずつ増やしながら繰り返す ②もし a(j) ＝ 36 ならば ③「あり」と表示して終了 ④ j の繰り返しはここまで

13 アルゴリズム応用（２） 二分探索 二分探索 探索範囲を半分ずつに分けて探索する 77635842362411 「 36 」を探す 36 ≠ ≠ ＝ アルゴリズ ム フローチャー ト ① i と j に添字の下限と上限をいれる ② i ≦ j の間繰り返す ③ m ← (i ＋ j)÷2 ④もし a(m) ＜ 36 ならば， i ← m ＋ 1 36 ＜ 4211 ＜ 36 ⑤もし a(m) ＞ 36 ならば， j ← m － 1 ⑥それ以外ならば，「あり」と表示して終了 ⑦繰り返しはここまで

14 アルゴリズムの応用 探索ま とめ ①逐次探索（ちくじ） 表の先頭から順番に１つずつ探していく ○ アルゴリズムは簡単 ○ データは順番に並んでいなくても良い × 探索データが（すごく）多いときはちょっと使えない ※比較回数（データ 1000 件だと最悪 1000 回。平均 500 回） ②二分探索（にぶん） 探索範囲を半分に分けて探していく ○ 探索が速い × アルゴリズムはちょっと複雑 × データは順番に並べておく必要がある ※比較回数（データ 1000 件だと 10 回くらい。ちなみにｎ件だとｌｏｇ ２ ｎ回で す。） 「簡単だが遅い」 「複雑だが速い」 みなさんならどっちを選びます か？

15 アルゴリズム応用（３） 並べかえ データを交換法で昇順に並べかえる 24171618 最も大きいデータを一番最後にもっていく 24 ＞ 17 入れかえる 1724 24 ＞ 16 入れかえる 1624 24 ＞ 18 入れかえる 1824 最も大きな値が確定 2 番目に大きいデータを確定する 17 ＞ 16 入れかえる 1617 17 ＜ 18 入れかえなし 2 番目に大きいデータが確定 18 3 番目に大きいデータを確定する 16 ＜ 17 入れかえなし 3 番目に大きいデータが確定 17 最後のデータが自動的に確定 16 データの入れかえ手順 ① a と b を入れかえるため c を用意 ②c←a②c←a ③a←ｂ③a←ｂ ④b←c④b←c アルゴリズム ① i は 3 から 1 まで 1 ずつ減らしながら繰り返す ② j は 1 から i まで 1 ずつ増やしながら繰り返す ③もし a(j) ＞ a(j ＋ 1) ならば a(j) と a(j ＋ 1) を入れかえる ④ j の繰り返しはここまで ⑤ i の繰り返しはここまで フローチャート

16 アルゴリズム応用 並べかえまと め z 並べかえ（ソート） ①交換法（バブルソート） となりあったデータを比較し、その大小により入れかえを行 う ※比較回数（データ 1000 件だと 499500 回なのです・・・ ちなみにｎ件だと n(n-1)/2 回で す） 「ソートはソートー時間がかかる」などどいうオヤジギャグを言いたくなるね え・・・ 並べ替えには他のアルゴリズムもありますが、比較回数はあまり変わりません・・・ ②データ交換 となりあう 2 つのデータＡ，Ｂを入れかえるには？ はじ め Ａ→ＣＡ→Ｃ Ｂ→ＡＢ→Ａ Ｃ→ＢＣ→Ｂ できた！ → 別の変数Ｃが必要！