データ構造とアルゴリズム論 第８章　再帰処理 平成15年12月2日 森田　彦.

Presentation on theme: "データ構造とアルゴリズム論 第８章　再帰処理 平成15年12月2日 森田　彦."— Presentation transcript:

1 データ構造とアルゴリズム論 第８章　再帰処理 平成15年12月2日 森田　彦

2 基礎課題提出状況(11/25) 平均提出数=36.8　(全課題数41) このままでは危険! 66.7%が36題以上を提出

3 応用課題提出状況（11/25） 平均提出課題数＝8.7 13題以上提出は約27%

4 再帰とは？ 自身の定義（の一部）に自身を含むこと。 日常的な例 鏡を持って鏡に向かった場合→鏡の中に鏡が映る・・・鏡の列が続く
　鏡を持って鏡に向かった場合→鏡の中に鏡が映る・・・鏡の列が続く プログラムの世界では 　メソッドの再帰的呼び出し、あるいはデータ構造の再帰的定義に用いられる。

5 本章（本日）の学習のねらい メソッドの再帰的定義（呼び出し）の例を学習する。→“再帰”の概念を理解する。
再帰処理の応用例としてフラクタル図形の描画を学習する。

6 8-1 再帰処理 例：階乗の計算 5!=5×4×3×2×1 一般的には・・・ n!=n×(n-1)×(n-2)×･･･×2×1
8-1　再帰処理 例：階乗の計算 　5!=5×4×3×2×1 　　一般的には・・・ 　n!=n×(n-1)×(n-2)×･･･×2×1 　　これを書き直すと・・・ 　n!=n×(n-1)! 　　→　再帰的定義 プログラムで表現するためにn!を計算するメソッドFact(n)を定義 階乗：factorial →　Fact(n)=n×Fact(n-1)

7 n!の計算（関数の再帰的定義による） 終了条件が必要！ 関数呼び出しの連鎖→p.126参照 プログラムの作成→【基礎課題8-1 】
Fact(n) n≧2 X ←n*Fact(n-1) Xの値を返す 戻る X ←1 No Yes 開始 nの入力 Ans ←Fact(n) Ansの表示 終了 メソッドの呼び出し 値を返す 終了条件が必要！ 関数呼び出しの連鎖→p.126参照 プログラムの作成→【基礎課題8-1 】

8 【基礎課題8-2】－コラッツの予想 コラッツ（Collatz）の予想 ある数字が偶数なら２で割る 奇数なら3倍して1を加える
という操作を繰り返すと必ず１になる。 例：５→１６→８→４→２→１ ＜課題の内容＞ 　コラッツの操作を再帰的に繰り返すことで、上の予想を実際に確かめるプログラムを作成する。

9 8-2 再帰処理の応用 フラクタル図形 どの一部をとっても全体と同じパターン（形）になっている図形
8-2　再帰処理の応用 フラクタル図形 　どの一部をとっても全体と同じパターン（形）になっている図形 コッホ（Koch）曲線→【応用課題8-A】 植物(!?)　→　【応用課題8-B】

10 第２回目テストのアナウンス 日時：12/9 13:15～14:15 （13:10までに着席しておいて下さい）
日時：12/9　13:15～14:15　（13:10までに着席しておいて下さい） 実施形態：ペーパーテスト形式（テスト中はＰＣを使用できません） 参照等：テキスト、プリント、自作ノート参照可 出題範囲：第５章～第７章まで アドバイス：暗記ではなく、処理の流れを“理解する”事に重点を置いて下さい。

11 テスト準備のポイント 問題１ レコード構造－クラスの利用
問題１　レコード構造－クラスの利用 　　クラスの定義・利用の仕方をよく理解しておくこと→【基礎課題5-1】、【基礎課題5-2】を（暗記ではなく）を自分の頭で作成できるようにしておいて下さい。 問題２　ソートのアルゴリズム 　　バブルソート、選択ソート、挿入ソートの処理の流れをトレースしておくこと→p.88～89、p.96～97、p.100～101を（自分で手を動かして）良く確認しておいて下さい。

12 テスト準備のポイント 問題３ 探索のアルゴリズム
問題３　探索のアルゴリズム 　　線形探索（番兵法）と２分探索のアルゴリズム（流れ図）をよく理解しておくこと（p.107,p.108～109,p.115）→具体的なデータを用いて、処理の流れをトレースしておいて下さい。 １両日中にHPにより詳細な情報を掲載します。参考にして下さい。

13 鏡の中の鏡 ずっと際限なく鏡の列が続く。 「鏡に映す」という操作の再帰的呼び出しの例