指定された座席に座り、出 席メールを送信して下さい。 講義開始後30分以上経 過した出席メールは欠席 扱いになります。 データ構造とアルゴリズム論 第1章 アルゴリズム の表現－流れ図 平成16年9月28日 森田 彦 アルゴリズムとは？ 問題を解決するための処理手順 例：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 “合格”と表示 終了 “不合格”と表示 Java言語ではif文で表現 選択構造その２ 多分岐処理１ 開始 例：テストの得点Xが80点以上なら「よくで きました」、80＞X≧50なら「合格」、50点未 満なら「不合格」と表示する。 Xの値を入力 X≧80 Yes No X≧50 No Yes “よくできました” と表示 終了 “合格”と表示 “不合格”と表示 選択構造その３ 多分岐処理２ 変数の値に応じて処理を分ける。 開始 Xの値を入力 「その他」は省略可 X ０ 処理１ １ ２ 処理２ 処理３ 終了 その他 処理４ Java言語ではswitch文 で表現 【基礎課題1-1 】（p.4） 開始 Xを入力すると、それが偶数か 奇数かを表示するアルゴリズム Xの値を入力 Y← X % 2 Y=0 No Yes “偶数です”と表示 終了 “奇数です”と表示 1-4 反復構造（繰り返し処理） 決まった回数の繰り返し 例：腕立て伏せを5回行う。 開始 トレース表 ｉ←1 ｉの値 No １ ２ ３ ４ ６ ５ 腕立て伏せ回数 ５ １ ２ ３ ４ i≦5 Yes 腕立て伏せをする。 i ← i+1 終了 Java言語ではfor文で表現 反復構造その２ トレースとは？ アルゴリズム（流れ図）の処理過程をた どって行くこと。 具体的には、変数の値 の変化をたどること。 → トレース表 アルゴリズムの理解 ← トレースが不可 欠 本講義で学習するアルゴリズムを理解で きるかどうか？ → 理解できるまでト レースするかどうかにかかっている。 反復構造その３ 【基礎課題1-3】 （p.9） １~５までを順に表示させる 開始 開始 ｉ←１ ｉ ｉ← ←０ ｉ≦５ 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】 演習にとりかかってください。 少なくとも、基礎課題のチェックは終える こと。 演習の時間内に基礎課題を終了できな かった場合は、必ず次週までに課題を終 えておいて下さい。基礎課題を翌週に持 ち越すと、本科目の修学が困難になりま す。
© Copyright 2024 ExpyDoc
