データ構造とアルゴリズム論第1章アルゴリズムの表現－流れ図平成15年9月30日森田彦アルゴリズムとは？問題を解決するための手順例：1缶110円のジュースの（自動）販売を行う ① ② ③ ＜処理の流れ（アルゴリズム）＞料金を投入する料金が不足していないかどうかを判定し、料金≧110なら「ありがとうございます」と表示。それ以外（料金＜110）なら「お金が不足しています」と表示。流れ図による表現開始料金を入力料金≧110 No 「お金が不足しています」と表示 Yes 「ありがとうございました」と表示終了プログラムとは？アルゴリズムをプログラミング言語で表現したもの Javaで記述 C++で記述本章（本日）の学習のねらい ① 標準的な流れ図（JIS規格に準拠）の記述の仕方を学ぶ。 ② 流れ図を用いて簡単なアルゴリズムを記述できるようになる。 ③ アルゴリズムの（処理の）流れをつかむため、トレースの仕方を身につける。重要！基本制御構造 1. 連接構造（順次処理） 2. 選択構造（分岐処理） 3. 反復構造（繰り返し処理）これら３つの制御構造の組み合わせであらゆるアルゴリズムが表現可能。 1-2 連接構造（順次処理）開始朝起きる顔を洗う歯を磨く終了例：朝起きて顔を洗って歯を磨く 上から下へ順番に処理 （一般に）順序が意味を持つ。 1-3 選択構造（分岐処理）  2分岐処理開始例：テストの得点Xが50点以上なら合格、50点未満なら不合格と表示する。 Xの値を入力 X≧50 X：50 ≧ No Yes “合格”と表示終了 “不合格”と表示＜選択構造その２  多分岐処理１開始例：テストの得点Xが80点以上なら「よくできました」、80＞X≧50なら「合格」、50点未満なら「不合格」と表示する。 Xの値を入力 X≧80 Yes No X≧50 No Yes “よくできました” と表示終了 “合格”と表示 “不合格”と表示選択構造その３  多分岐処理２変数の値に応じて処理を分ける。開始 Xの値を入力「その他」は省略可 X ０処理１１２処理２処理３終了その他処理４ Java言語ではswitch文で表現【基礎課題1-1 】開始 Xを入力すると、それが偶数か奇数かを表示するアルゴリズム Xの値を入力 Y← X % 2 Y=0 No Yes “偶数です”と表示終了 “奇数です”と表示 1-4 反復構造（繰り返し処理）  決まった回数の繰り返し例：腕立て伏せを5回行う。開始トレース表ｉ←1 ｉの値 No 腕立て伏せ回数５１２３４ i≦5 Yes 腕立て伏せをする。 i ← i+1 １２３４６５終了反復構造その２トレースとは？  アルゴリズム（流れ図）の処理過程をたどって行くこと。具体的には、変数の値の変化をたどること。 → トレース表  アルゴリズムの理解 ← トレースが不可欠  本講義で学習するアルゴリズムを理解できるかどうか？ → 理解できるまでトレースするかどうかにかかっている。反復構造その３  【基礎課題1-3】１~５までを順に表示させる開始開始ｉ←１ｉｉ← ←０ｉ≦５ Yes ｉ≦ ｉ≦４ No Yes ｉ ← ｉ＋１ｉを表示ｉ ← ｉ＋１ No 終了ｉを表示終了 ※ 「iを表示」と「ｉ ← i+1」を入れ替え反復構造その４ループ端記号を使った表現例：処理ＡをN回繰り返す (1)列挙型 (2)「変数名：初期値，増分，終値」提示型 (3)終了条件提示型 i←1 ループ i=1,2,3,・・・,N ループ i:1,1,N 処理Ａ処理Ａループループループ i>N （となるまで）処理Ａ i ← i+1 ループ理解度チェック → 【基礎課題1-5】反復構造その５  一般的な終了条件による繰り返し例：可能な限り腕立て伏せを行う開始続行可能 No Java言語ではwhile 文で表現 Yes 腕立て伏せをする。終了理解度チェック → 【基礎課題1-4】、【応用課題1-E】  演習にとりかかってください。  少なくとも、基礎課題のチェックは終えること。  演習の時間内に基礎課題を終了できなかった場合は、必ず次週までに課題を終えておいて下さい。基礎課題を翌週に持ち越すと、本科目の修学が困難になります。