データ構造とアルゴリズム論 平成 26 年 4 月 18 日 第 1 章．アルゴリズムの表現－流れ図 【学習のねらい】 ① 標準的な流れ図（JIS 規格に準拠）の記述の仕方を学ぶ。 ② 流れ図を用いて簡単なアルゴリズムを記述できるようになる。 ③ アルゴリズムの処理の流れをつかむため、トレースの仕方を身につける。 １－１ 基本的な流れ図記号 以下に基本的な「流れ図記号」を表にまとめておきます。用法は今後の演習でトレーニ ングすれば自然に身につくはずです。 ＜記号一覧（JIS X0121）＞ 記号 名称 意味（機能） 処理 任意の種類の処理を行う。 手操作入力 キーボードなどから手操作でデータを入力す る。 表示 ディスプレイなどに出力結果を表示する。 判断 条件にしたがって幾つかの処理に分岐する ループ端（開始） 繰り返し処理の始まりを表す。 ループ端（終了） 繰り返し処理の終わりを表す 端子 流れ図の始めと終わりを表す 線 データあるいは制御の流れを表す。 定義済み処理 手続きや関数など、すでに定義した一連の処理 を表す。 データ ファイルからの入出力に用いる。 結合子 流れ図の他の場所への接続を表す（流れ図が 1 枚の紙面収まらなくなり、次ページに続く場合 などに用いる） 。 1 データ構造とアルゴリズム論 平成 26 年 4 月 18 日 １－２ 例 基本制御構造の表現 －連接構造（順次処理） 朝起きて顔を洗って歯を磨く。 開始 朝起きる 一つ一つの処理を順番に（上から下へ）行う。 順序を入れ替えると処理がうまく行かない場合 がある。右の例では、 「顔を洗う」と「歯を磨く」 顔を洗う を入れ替えても（全体としては）問題ないが、 「朝 起きる」と「顔を洗う」を入れ替えることはで 歯を磨く きない。 → 一般に順序が意味を持つ！ 終了 １－３ 基本制御構造の表現 －選択構造（分岐処理） Ａ．2 分岐処理 例 テストの得点 X が 50 点以上なら合格、50 点未満なら不合格と表示する。 開始 X：50 X の値を入力 X≧50 ≧ No この書き方も可 Yes “合格”と表示 “不合格”と表示 終了 プログラミング言語（Java）では、if 文によって表現します。 2 ＜ データ構造とアルゴリズム論 平成 26 年 4 月 18 日 Ｂ．多分岐処理 テストの得点 X が８0 点以上なら「よくできました、」80>X≧50 なら「合格」 、50 例１ 点未満なら「不合格」と表示する。→ 分岐が 3 つの場合の例 開始 X の値を入力 No X≧80 Yes X≧50 No Yes “よくできました” “合格”と表示 と表示 “不合格”と表示 終了 学籍番号 X を入力すると、それを４で割ったときの余りの数 Y の値により（次の 例２ 要領で）着席位置を表示する。 Y=0：1～3 列目 Y=1：4～6 列目 Y=2：7～9 列目 Y=3：10～12 列目 → 変数の値で処理を分ける場合の例（Java 言語では switch 文で表現） 開始 学籍番号 X の値を入力 ※ 具体的な値（下では１， Y ← X%4 ２、･･･等）の他に、 「そ れ以外」という指定も可 Y ０ 能。 １ ２ ３ “1～3 列目” “4～6 列目” “7～9 列目” “10～12 列目” と表示 と表示 と表示 と表示 終了 3 データ構造とアルゴリズム論 平成 26 年 4 月 18 日 ※ ＡをＢで割った時の余りを「Ａ % B」と表現します。例えば、「10 % 3」の値は「１」 です。剰余演算子「%」については、「プログラミング」テキスト p.84（2012 年度版 は p.84）で説明しています。 ※ 流れ図では、通常、変数への値の代入を「０→Ｘ」の様に（左辺から右辺への代入と して）表します。しかし、本講義・演習では、プログラム上の表記にそろえて、 「Ｘ← ０」の様に（右辺から左辺への代入の形で）記述することにします。 【基礎課題 1-1】 下は整数Ｘを入力すると、それが偶数か奇数かを表示するアルゴリズムです。空欄を埋 めてアルゴリズム（流れ図）を完成させてください。 開始 X の値を入力 Y ← X%2 No Yes “偶数です”と表示 “奇数です”と表示 終了 【応用課題 1-A】 【基礎課題 1-1】の処理を行う（Java 言語）プログラムを作成してください。ここに、X の入力および、結果の表示（ 「偶数です」など）には、テキストフィールドコンポーネント を用い（2 つ用意します） 、 「判定」ボタンをクリックしたら結果を表示するようにしてくだ さい。 4 データ構造とアルゴリズム論 平成 26 年 4 月 18 日 【基礎課題 1-2】 ある美術館の入場料金は、年齢に応じて次の様になっています。 7 歳未満 7 歳～12 歳 13 歳以上 無料 500 円 800 円 年齢 Age を入力すると、入場料金を表示するアルゴリズムを考えましょう。次の空欄お よび下線部を埋めて流れ図を完成させてください。これは、判断記号の別表記に慣れる練 習です。 開始 Age の値を入力 ≧ Age：７ No ＜ Age： “無料です” “500 円です” “800 円です” と表示 と表示 と表示 終了 【応用課題 1-B】 【基礎課題 1-2】の処理を行うプログラムを作成してください。ここに、年齢 Age の入力 および結果の表示には、テキストフィールドコンポーネントを用い、 ［表示］ボタンをクリ ックすると、料金が表示されるようにしてください。 5 データ構造とアルゴリズム論 平成 26 年 4 月 18 日 １－４ 基本制御構造の表現 Ａ．決まった回数の繰り返し 例 －反復構造（繰り返し処理） 腕立て伏せを５回行う。 ※ 開始 Java 言語では for 文で表 現します。 ① ② i ← 1 No i≦5 Yes ③ 腕立て伏せをする。 ④ i ← i+1 終了 ⑤ 繰り返し処理の流れを理解するためには、変数の変化の動きを追跡（トレース）する必 要があります。 ＜トレース表＞ 処理番号 ｉの値 ① １ ② １ ③ １ ④ ２ ② ２ ③ ２ ④ ３ ② ３ ③ ３ ④ ４ ② ４ ③ ４ ④ ５ ② ５ ③ ５ ④ ６ ② ６ 判定結果 処理 Yes 腕立て伏せをする。 Yes 腕立て伏せをする。 Yes 腕立て伏せをする。 Yes 腕立て伏せをする。 Yes 腕立て伏せをする。 No ⑤ 終了 6 データ構造とアルゴリズム論 平成 26 年 4 月 18 日 アドバイス －トレースの勧め 一般に、アルゴリズム（流れ図）の処理過程を追って行くと、そこに現れる変数の値が （アルゴリズムの進行に伴い）刻々と変化してゆきます。その変数（の値）の変化過程を 追跡することをトレースすると言います。具体的には、前ページのようなトレース表を作 ることです。 あるアルゴリズムを理解する、ということは、その処理過程をトレースして変数（の値） の変化（の流れ）を理解する、ということに他なりません。そして、トレースすること自 体は、労を惜しまなければ誰にでもできることなのです。 今後、本講義・演習で出てくる色々なアルゴリズムを理解できるかどうか、さらには自 在に使えるようになるかどうかは、トレースする習慣を身につけ、地道に理解する作業を 行えるかどうかにかかっています。面倒でも、理解できるまでトレースを行ってください。 トレースの習慣が身に付いて来ると、自然と頭の中で処理内容のトレースができるように なります。そうなればしめたもの！アルゴリズムの理解が飛躍的に速くなりますし、また 自分でアルゴリズムを考案する力もぐんぐんついて来ます。 プログラミングが上達するかどうかは、トレースができるかどうかで決まる、と言って も良いでしょう。 Ｂ．一般的な終了条件による繰り返し 例 可能な限り腕立て伏せを行う。 開始 No 続行可能 Yes 腕立て伏せをする。 終了 ※ Java 言語では、while 文で表現します。 7 データ構造とアルゴリズム論 平成 26 年 4 月 18 日 ループ端記号を使った表現 繰り返し処理は、次の様にループ端記号を使って表すことが出来ます。下の３つの流れ 図はいずれも p.6 の例（決まった回数の繰り返し）の流れ図と同じ処理を表します。 （１） （２） 開始 ループ名 開始 カウンタの値列挙 ループ ループ i=1,2,3,…,5 腕立て伏せをする。 i：1,1,5 腕立て伏せをする。 ループ名 変数名：初期値，増分，終値 ループ ループ 終了 終了 （３） 開始 ｉ←１ ループ i>5 （ と な る ま で ） ループ名 繰り返しの終了条件 （この条件が成立したら、ループから抜 ける事に注意） =1,2,3,…,5 腕立て伏せをする。 ｉ←ｉ＋１ ループ 終了 ※ ループ端記号を用いると、繰り返しループ処理の開始と終了の位置が分かりやすいと いうメリットがあります。実はこれは流れ図としては比較的新しい（新しく採用され た）記号です。最近は、繰り返し処理にループ端記号を用いることが多くなりました。 8 データ構造とアルゴリズム論 平成 26 年 4 月 18 日 【基礎課題 1-3】 下の左図は、１～５までの整数を順に表示させるアルゴリズム（流れ図）です。右は繰 り返しループ中の「ｉを表示」と「i ← i+1」の順序を入れ換えたものです。これが、左図 と同等な処理となるよう、下線部を埋めてください。 開始 開始 i ← i ← 1 No i≦5 No i≦ Yes Yes ｉを表示 終了 終了 i ← i+1 i ← i+1 ｉを表示 ※ いずれの課題もｉに 1,2･･･など具体的な数値を入れてトレ ースして（処理内容を）確かめてみてください。 【基礎課題 1-4】 p.7 「1-4-B．一般的な終了条件による繰り返し」の例の流れ図において、腕立て伏せ を行った回数を表示するよう、改良しました。ｉが腕立て伏せを行った回数となるために は、空欄①～②にどのような処理が入ればよいですか？解答群から選んでください。 ＜解答群＞ (a) 開始 ｉ←０ (b) (d) ｉ←ｉ＋１ ① (f) ｉ←ｉ＋２ 続行可能 No Yes ② ｉを表示 腕立て伏せをする 終了 9 ｉ←１ (c) (e) ｉ←ｉ－１ ｉ←２ データ構造とアルゴリズム論 平成 26 年 4 月 18 日 【基礎課題 1-5】 ある偶数Ｎ（≧０）を入力すると、その値までの偶数の和（=2+4+6+･･･+N）を求めて表 示する処理のアルゴリズムは下の左図の様になります。一方、右図は同様の処理を、ルー プ端記号を用いて表したものです（p.8 の(3)の書式です） 。下線部に入る条件式を、解答群 から選んでください。 開始 開始 N を入力 N を入力 SUM←０ SUM←０ ｉ←０ ｉ←０ ループ ｉ≦Ｎ No Yes SUM←SUM＋ｉ ｉ←ｉ＋２ SUM←SUM＋ｉ SUM を表示 ｉ←ｉ＋２ 終了 ループ SUM を表示 終了 ＜解答群＞ (1) ｉ＞Ｎ (2) ｉ≠Ｎ (3) ｉ≦Ｎ (4) ｉ＝Ｎ 【応用課題 1-C】 【基礎課題 1-5】の処理を行うプログラムを作成してください。繰り返し処理には、while 文を用いてください（左側の流れ図に対応します）。ここに、Ｎの入力および偶数和(SUM) の表示には、テキストフィールドコンポーネントを用い、適当なボタンをクリックすると、 偶数和の計算結果を表示するようにしてください。 10 データ構造とアルゴリズム論 平成 26 年 4 月 18 日 【応用課題 1-D】 日本とヨーロッパ中部時間との時差は７時間です（ヨーロッパが夏時間の場合） 。例えば、 日本の午前 10 時は、ヨーロッパ中部（フランスやイタリアなど）では午前３時になります。 そこで、以下のように日本の時刻を入力すると、ヨーロッパの時刻を表示してくれるアル ゴリズムを考えましょう（時刻は 24 時間表記） 。 ＜変数の意味＞ 開始 ＪＨ：時（日本時間） ＪＭ：分（日本時間） ＥＨ：時（欧州時間） ＥＭ：分（欧州時間） JH，ＪＭを入力 ところが、このプログラムでは例えば、 「3 時 00 分」を入 ＥＭ←ＪＭ 力すると、ヨーロッパ時間が「-4 時 00 分」という奇妙な結 ＥＨ←ＪＨ－７ 果になってしまいます。言うまでもなく、正しくは「20 時 00 分」です。 EH，EM を表示 終了 開始 そこで、全ての入力時刻に対して正しくヨーロッパ時 刻が表示されるように、このアルゴリズムを改良しまし JH，ＪＭを入力 た。左の空欄を埋めてアルゴリズムを完成させてくださ い。 ＥＭ←ＪＭ No Yes ＥＨ←ＪＨ－７ ＥＨ← EH，EM を表示 終了 11 データ構造とアルゴリズム論 平成 26 年 4 月 18 日 【応用課題 1-E】 １日目に１円、２日目に２円、３日目に４円・・というように、前日の２倍ずつ貯金を して行く場合を考えましょう。このときの貯金総額の変化は下表の通りとなります。 日数 １日目 ２日目 ３日目 ４日目 ・・・ 貯金する額 １円 ２円 ４円 ８円 ・・・ 貯金総額 １円 ３円 ７円 １５円 ・・・ こうしたペースで貯金をした場合、貯金総額が１万円を越えるのは何日目でしょうか？ それを求めるアルゴリズムを考えましょう。下線部を埋めてアルゴリズムを完成させてく ださい。 ＜変数の意味＞ 開始 N N：日数 Chokin：貯金する額 Sougaku：貯金総額 ← Chokin ← Sougaku← No Yes N を表示 Chokin← 終了 Sougaku←Sougaku＋Chokin N← N＋１ 【応用課題 1-F】 【応用課題 1-E】の処理を行うプロ グラムを作成してください。ここに、 フレームのデザインは次の通りとし、 ［日数計算］ボタンをクリックすると、 結果（何日目か）を表示するものとし ます。 12
© Copyright 2024 ExpyDoc
