データ構造とアルゴリズム論 第1章 アルゴリズムの表現－流れ図

Presentation on theme: "データ構造とアルゴリズム論 第1章 アルゴリズムの表現－流れ図"— Presentation transcript:

1 データ構造とアルゴリズム論 第1章 アルゴリズムの表現－流れ図
データ構造とアルゴリズム論 第1章　アルゴリズムの表現－流れ図 平成15年9月30日 森田　彦

2 アルゴリズムとは？ 問題を解決するための手順 例：1缶110円のジュースの（自動）販売を行う ＜処理の流れ（アルゴリズム）＞ 料金を投入する
　問題を解決するための手順 　例：1缶110円のジュースの（自動）販売を行う ＜処理の流れ（アルゴリズム）＞ 料金を投入する 料金が不足していないかどうかを判定し、 料金≧110なら「ありがとうございます」と表示。 　　それ以外（料金＜110）なら「お金が不足しています」と表示。

3 流れ図による表現 開始 料金を入力 料金≧110 No 「お金が不足しています」と表示 Yes 「ありがとうございました」と表示 終了

4 プログラムとは？ 　アルゴリズムをプログラミング言語で表現したもの Javaで記述 C++で記述

5 本章（本日）の学習のねらい 標準的な流れ図（JIS規格に準拠）の記述の仕方を学ぶ。 流れ図を用いて簡単なアルゴリズムを記述できるようになる。
アルゴリズムの（処理の）流れをつかむため、トレースの仕方を身につける。 重要！

6 基本制御構造 連接構造（順次処理） 選択構造（分岐処理） 反復構造（繰り返し処理）
これら３つの制御構造の組み合わせであらゆるアルゴリズムが表現可能。

7 1-2 連接構造（順次処理） 例：朝起きて顔を洗って歯を磨く 開始 上から下へ順番に処理 朝起きる （一般に）順序が意味を持つ。 顔を洗う
1-2　連接構造（順次処理） 例：朝起きて顔を洗って歯を磨く 開始 朝起きる 上から下へ順番に処理 （一般に）順序が意味を持つ。 顔を洗う 歯を磨く 終了

8 1-3 選択構造（分岐処理） 2分岐処理 例：テストの得点Xが50点以上なら合格、50点未満なら不合格と表示する。 No Yes 開始
1-3　選択構造（分岐処理） 2分岐処理 例：テストの得点Xが50点以上なら合格、50点未満なら不合格と表示する。 開始 Xの値を入力 X：50 ≧ ＜ X≧50 No Yes “合格”と表示 “不合格”と表示 終了

9 選択構造その２ 多分岐処理１ 例：テストの得点Xが80点以上なら「よくできました」、80＞X≧50なら「合格」、50点未満なら「不合格」と表示する。 開始 Xの値を入力 X≧80 No X≧50 No Yes Yes “よくできました” と表示 “合格”と表示 “不合格”と表示 終了

10 多分岐処理２ 選択構造その３ 変数の値に応じて処理を分ける。 「その他」は省略可 Java言語ではswitch文で表現 開始 Xの値を入力
０ １ ２ その他 処理１ 処理２ 処理３ 処理４ Java言語ではswitch文で表現 終了

11 【基礎課題1-1 】 Xを入力すると、それが偶数か奇数かを表示するアルゴリズム No Y=0 Yes 開始 Xの値を入力 Y← X % 2
“偶数です”と表示 “奇数です”と表示 終了

12 1-4 反復構造（繰り返し処理） 決まった回数の繰り返し 例：腕立て伏せを5回行う。 トレース表 開始 ｉ ← 1 ｉの値 腕立て伏せ回数
1-4　反復構造（繰り返し処理） 決まった回数の繰り返し 例：腕立て伏せを5回行う。 開始 トレース表 ｉ ← 1 ｉの値 腕立て伏せ回数 ４ ２ １ ３ ５ ６ No No i≦5 ２ ３ ５ ４ １ Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes 腕立て伏せをする。 腕立て伏せをする。 腕立て伏せをする。 腕立て伏せをする。 腕立て伏せをする。 腕立て伏せをする。 腕立て伏せをする。 腕立て伏せをする。 腕立て伏せをする。 腕立て伏せをする。 腕立て伏せをする。 終了 終了 i ← i+1 i ← i+1 i ← i+1 i ← i+1 i ← i+1 i ← i+1 i ← i+1 i ← i+1 i ← i+1 i ← i+1 i ← i+1

13 トレースとは？ アルゴリズム（流れ図）の処理過程をたどって行くこと。 具体的には、変数の値の変化をたどること。 → トレース表
反復構造その２ アルゴリズム（流れ図）の処理過程をたどって行くこと。　具体的には、変数の値の変化をたどること。　→　トレース表 アルゴリズムの理解　←　トレースが不可欠 本講義で学習するアルゴリズムを理解できるかどうか？　→　理解できるまでトレースするかどうかにかかっている。

14 【基礎課題1-3】 反復構造その３ １~５までを順に表示させる 開始 開始 ｉ ← ｉ ← ０ ｉ ← １ No No ｉ≦ ｉ≦４ ｉ≦５
Yes Yes ｉ ← ｉ＋１ ｉを表示 ｉを表示 終了 ｉ ← ｉ＋１ 終了 ※　「iを表示」と「ｉ ← i+1」を入れ替え

15 ループ端記号を使った表現 反復構造その４ 例：処理ＡをN回繰り返す 理解度チェック → 【基礎課題1-5】
(2)「変数名：初期値，増分，終値」　提示型 (3)終了条件提示型 (1)列挙型 i ← 1 ループi=1,2,3,・・・,N ループ i:1,1,N ループ i>N （となるまで） 処理Ａ 処理Ａ 処理Ａ ループ ループ i ← i+1 ループ 理解度チェック → 【基礎課題1-5】

16 一般的な終了条件による繰り返し 反復構造その５ 例：可能な限り腕立て伏せを行う Java言語ではwhile文で表現
開始 Java言語ではwhile文で表現 続行可能 No Yes 腕立て伏せをする。 終了 理解度チェック　→　【基礎課題1-4】、【応用課題1-E】

17 演習にとりかかってください。 少なくとも、基礎課題のチェックは終えること。 演習の時間内に基礎課題を終了できなかった場合は、必ず次週までに課題を終えておいて下さい。基礎課題を翌週に持ち越すと、本科目の修学が困難になります。