計算機プログラミングI 第11回 再帰 再帰的なメソッド定義 帰納的定義 再帰的なデータ構造 計算機プログラミングI (増原) 2003年度.

Presentation on theme: "計算機プログラミングI 第11回 再帰 再帰的なメソッド定義 帰納的定義 再帰的なデータ構造 計算機プログラミングI (増原) 2003年度."— Presentation transcript:

1 計算機プログラミングI 第11回 再帰 再帰的なメソッド定義 帰納的定義 再帰的なデータ構造 計算機プログラミングI (増原) 2003年度

2 フラクタル図形 自己相似形とも言う 自然界の形状によく見られる 木の形・山の形・・・
quote from 計算機プログラミングI (増原) 2003年度

3 フラクタル図形と木 木を描くプログラムを作ろう 計算機プログラミングI (増原) 2003年度

4 フラクタル図形と木 木 = ? 計算機プログラミングI (増原) 2003年度

5 フラクタル図形と木 木 = 1段目の幹 + (小さく傾いた木)×2 ? = ? 計算機プログラミングI (増原) 2003年度

6 フラクタル図形と木 木 = 1段目の幹 + (小さく傾いた木)×2 ? = 1段目の幹 + (2段目の幹 + (小さく傾いた木)×2)×2
= 1段目の幹 + (2段目の幹 (小さく傾いた木)×2)×2 = ? 計算機プログラミングI (増原) 2003年度

7 フラクタル図形と木 木 = 1段目の幹 + (小さく傾いた木)×2 ? = 1段目の幹 + (2段目の幹 + (小さく傾いた木)×2)×2
= 1段目の幹 + (2段目の幹 (小さく傾いた木)×2)×2 = 1段目の幹 + (2段目の幹 (3段目の幹+(小さく傾いた木)×2)×2)×2 = ? 計算機プログラミングI (増原) 2003年度

8 フラクタル図形と木 木 = 1段目の幹 + (小さく傾いた木)×2 ? = 1段目の幹 + (2段目の幹 + (小さく傾いた木)×2)×2
= 1段目の幹 + (2段目の幹 (小さく傾いた木)×2)×2 = 1段目の幹 + (2段目の幹 (3段目の幹+(小さく傾いた木)×2)×2)×2 = … 計算機プログラミングI (増原) 2003年度

9 フラクタル図形と木 木 = 1段目の幹 + (小さく傾いた木)×2 ? = 1段目の幹 + (2段目の幹 + (小さく傾いた木)×2)×2
= 1段目の幹 + (2段目の幹 (小さく傾いた木)×2)×2 = 1段目の幹 + (2段目の幹 (3段目の幹+(小さく傾いた木)×2)×2)×2 = … ところで、本物の 木はどうやって 生える? DNA=プログラムだとすると、1段目のプログラム・2段目のプログラム・3段目のプログラム… があるのか? 計算機プログラミングI (増原) 2003年度

10 タートルグラフィクスによる木:1 m.tree1(200); public class Tree extends Turtle {
public void tree1(int length){ fd(length/3); //幹を描く lt(30); //左を向く tree0(2*length/3); //2/3の高さの枝を描く rt(60); //右を向く lt(30); //正面を向き直す bk(length/3); //元の位置に戻る } public void tree0(int length){ fd(length); //枝を描く bk(length); //元の位置に戻る m.tree1(200); 計算機プログラミングI (増原) 2003年度

11 タートルグラフィクスによる木:2 m.tree1(200); m.tree2(200);
public class Tree extends Turtle { public void tree2(int length){ fd(length/3); //幹を描く lt(30); //左を向く tree1(2*length/3); //2/3の高さの枝を描く rt(60); //右を向く lt(30); //正面を向き直す bk(length/3); //元の位置に戻る } public void tree1(int length){ tree0(2*length/3); //2/3の高さの枝を描く public void tree0(int length){ fd(length); //枝を描く bk(length); //元の位置に戻る m.tree1(200); m.tree2(200); 計算機プログラミングI (増原) 2003年度

12 タートルグラフィクスによる木:3 m.tree2(200); m.tree3(200);
public class Tree extends Turtle { public void tree3(int length){ fd(length/3); //幹を描く lt(30); //左を向く tree2(2*length/3); //2/3の高さの枝を描く rt(60); //右を向く lt(30); //正面を向き直す bk(length/3); //元の位置に戻る } public void tree2(int length){ tree1(2*length/3); //2/3の高さの枝を描く public void tree1(int length){ tree0(2*length/3); //2/3の高さの枝を描く public void tree0(int length){ fd(length); //枝を描く bk(length); //元の位置に戻る m.tree2(200); m.tree3(200); 計算機プログラミングI (増原) 2003年度

13 タートルグラフィクスによる木:4 m.tree3(200); m.tree4(200);
public class Tree extends Turtle { public void tree4(int length){ fd(length/3); //幹を描く lt(30); //左を向く tree3(2*length/3); //2/3の高さの枝を描く rt(60); //右を向く lt(30); //正面を向き直す bk(length/3); //元の位置に戻る } public void tree3(int length){ tree2(2*length/3); //2/3の高さの枝を描く public void tree2(int length){ tree1(2*length/3); //2/3の高さの枝を描く public void tree1(int length){ tree0(2*length/3); //2/3の高さの枝を描く public void tree0(int length){ fd(length); //枝を描く bk(length); //元の位置に戻る m.tree3(200); m.tree4(200); 計算機プログラミングI (増原) 2003年度

14 タートルグラフィクスによる木 プログラムの全体像
public void tree4(int length){ fd(length/3); lt(30); tree3(2*length/3); rt(60); bk(length/3); } public void tree3(int length){ fd(length/3); lt(30); tree2(2*length/3); rt(60); bk(length/3); } public void tree2(int length){ fd(length/3); lt(30); tree1(2*length/3); rt(60); bk(length/3); } public void tree1(int length){ fd(length/3); lt(30); tree0(2*length/3); rt(60); bk(length/3); } よく見ると、tree1～tree4はほとんど同じ! 違いは treen は treen-1 を呼び出していること tree0 は全く違う public void tree0(int length){ fd(length);//枝を描く bk(length); } 計算機プログラミングI (増原) 2003年度

15 タートルグラフィクスによる木 再帰 よく見ると、tree1～tree4は ほとんど同じ! ならば、1つのメソッドにして
public void tree4(int length){ fd(length/3); lt(30); tree3(2*length/3); rt(60); bk(length/3); } public void tree3(int length){ fd(length/3); lt(30); tree2(2*length/3); rt(60); bk(length/3); } public void tree2(int length){ fd(length/3); lt(30); tree1(2*length/3); rt(60); bk(length/3); } public void tree1(int length){ fd(length/3); lt(30); tree0(2*length/3); rt(60); bk(length/3); } よく見ると、tree1～tree4は ほとんど同じ! ならば、1つのメソッドにして 自分で自分を呼び出そう! = 再帰 public void tree(int length){ fd(length/3); lt(30); tree(2*length/3); rt(60); bk(length/3); } public void tree0(int length){ fd(length);//枝を描く bk(length); } 計算機プログラミングI (増原) 2003年度

16 タートルグラフィクスによる木 再帰: 実際の定義
public void tree(int length){ if (length>5) { fd(length/3); lt(30); tree(2*length/3); rt(60); bk(length/3); } else { fd(length);//枝を描く bk(length); } 高さが充分ある間は 1. 幹を描く 2. 自分自身を呼び出して まわり小さい左右の枝を描く 高さが一定値より低くなったら 直線を描く 計算機プログラミングI (増原) 2003年度

17 帰納的定義 関数や処理を定義する方法 パラメータ x に注目して を定義し、全ての場合を定義する 例: 木 基底の場合 1つ進めた場合
1つ進めた場合: x段の木をx-1段の木を組み合わせて描く →x>0 全ての場合に定義される 計算機プログラミングI (増原) 2003年度

18 p(x,n) = 1 (n=0) x*p(x,n-1) (n>0)
冪数の帰納的定義 p(x,n) = (n=0) x*p(x,n-1) (n>0) 全ての自然数nについて定義されている。 * 0については定義されている * 0からkまで定義されているとする(帰納法の仮定)と k+1についても定義されている 計算機プログラミングI (増原) 2003年度

19 p(x,n) = 1 (n=0) x*p(x,n-1) (n>0)
再帰的なメソッド定義 p(x,n) = (n=0) x*p(x,n-1) (n>0) 帰納的な定義は、再帰的なメソッド呼出によって、ほとんどそのままメソッド定義にできる public static int p(int x,int n) { if (n == 0) { return 1; } else { return x*p(x,n-1); } 計算機プログラミングI (増原) 2003年度

20 再帰的メソッドの応用 ? ハノイの塔 d0 d1 d2 d3 d4 p1 p2 p0 一番上の円盤のみ動かせる
より大きい円盤の上にしか 置けない ? d0 d1 d2 d3 d4 p1 p2 p0 計算機プログラミングI (増原) 2003年度

21 ハノイの塔 = di ,..., d0をpfからptに動かす pf pt di-1,..., d0 di pt pf pe
di-1,..., d0をpfからpeに動かす di ,..., d0をpeからptに動かす diをpfからptに動かす 計算機プログラミングI (増原) 2003年度

22 コッホ曲線 計算機プログラミングI (増原) 2003年度

23 コッホ曲線 k段目のコッホ曲線 =k-1段準のコッホ曲線×4 0段目のコッホ曲線 =直線 = 計算機プログラミングI (増原) 2003年度

24 データ構造 データ構造: データ型の設計 (例: 銀行口座) データが持つ情報の種類 (例: 口座は持主・残高・・・)
データ構造: データ型の設計 (例: 銀行口座) データが持つ情報の種類 (例: 口座は持主・残高・・・) データとデータの関係 (例: 支店は口座と店員を管理) どのように使われるか (例: 入金処理・口座開設・・・) 銀行 支店リスト 支店 住所 店員リスト 顧客リスト 店員 氏名 役職 給料 口座 種別 持主 残高 暗証番号 顧客 氏名 住所 電話 口座リスト 計算機プログラミングI (増原) 2003年度

25 データ構造 Java言語のデータ型 オブジェクト指向言語におけるデータ構造
基本型 (a.k.a. 原始型): 整数(int), 実数(double), … 配列型 ― 例: 整数の配列, Turtleの配列, … オブジェクト型 ― 例: Turtle, Complex, … オブジェクト指向言語におけるデータ構造 クラスの設計; 特にインスタンス変数の型 複数データの組合わせは 実用的プログラムで必須 計算機プログラミングI (増原) 2003年度

26 例題: リスト構造 カラオケの予約リスト 予約が一列に並んだもの + 追加・削除機能 cf. 配列: 個数が固定・・・追加・削除が難しい
予約を追加する 先頭の予約を演奏 予約を取り消す 先頭に予約を割り込ませる cf. 配列: 個数が固定・・・追加・削除が難しい 予約 予約 予約 予約 予約 予約 予約 予約 計算機プログラミングI (増原) 2003年度

27 予約リスト with 配列 int[ ] requests = new int[10]; //予約は最大10までとする
int n = 0; //予約の個数は最初は0 10個以上の 曲を追加できない if (n <= requests.length) { //予約songを追加する requests[n]=song; n=n+1; } n = 4 play(requests[0]); //先頭の曲を演奏する for (int i = 1; i < n; i++) { //先頭の曲を消す requests[i-1]=requests[i]; } n=n-1; 7 54 6 24 計算機プログラミングI (増原) 2003年度

28 予約リスト with 配列 int[ ] requests = new int[10]; //予約は最大10までとする
int n = 0; //予約の個数は最初は0 10個以上の 曲を追加できない if (n <= requests.length) { //予約songを追加する requests[n]=song; n=n+1; } n = 3 「つめる」作業が 必要 play(requests[0]); //先頭の曲を演奏する for (int i = 1; i < n; i++) { //先頭の曲を消す requests[i-1]=requests[i]; } n=n-1; 54 6 24 計算機プログラミングI (増原) 2003年度

29 予約リスト with 配列 int[ ] requests = new int[10]; //予約は最大10までとする
int n = 0; //予約の個数は最初は0 for (int i = 0; i < n; i++) { //全体を右へずらす requests[i+1]=requests[i]; } requests[0]=song; //先頭に挿入 n=n+1; n = 3 play(requests[0]); //先頭の曲を演奏する for (int i = 1; i < n; i++) { //先頭の曲を消す requests[i-1]=requests[i]; } n=n-1; 54 6 24 計算機プログラミングI (増原) 2003年度

30 予約リスト with 配列 int[ ] requests = new int[10]; //予約は最大10までとする
int n = 0; //予約の個数は最初は0 for (int i = 0; i < n; i++) { //全体を右へずらす requests[i+1]=requests[i]; } requests[0]=song; //先頭に挿入 n=n+1; 間違いやすい n = 4 play(requests[0]); //先頭の曲を演奏する for (int i = 1; i < n; i++) { //先頭の曲を消す requests[i-1]=requests[i]; } n=n-1; 54 54 54 54 計算機プログラミングI (増原) 2003年度

31 予約リスト with 配列 int[ ] requests = new int[10]; //予約は最大10までとする
int n = 0; //予約の個数は最初は0 ずらす作業が 必要 for (int i = n; i > 0; i++) { //全体を右へずらす requests[i]=requests[i-1]; } requests[0]=song; //先頭に挿入 n=n+1; n = 4 play(requests[0]); //先頭の曲を演奏する for (int i = 1; i < n; i++) { //先頭の曲を消す requests[i-1]=requests[i]; } n=n-1; 16 54 6 24 計算機プログラミングI (増原) 2003年度

32 データ構造としてのリスト構造 鎖状に並んだデータ 一つの輪が一つのデータを持つ 一つの輪は隣の輪だけを知っている
追加・挿入・削除: 輪をつなぐ・切る操作 次の予約 次の予約 次の予約 次の予約 予約 曲番号 予約情報 予約 曲番号 予約情報 予約 曲番号 予約情報 予約 曲番号 予約情報 計算機プログラミングI (増原) 2003年度

33 例題: タートルのリスト プログラム ListDemo 画面上にタートルが置かれる 機能: 画面上のボタンをクリックして (実演)
タートルをリストに追加 リスト上のタートルを前進 リスト上のタートルを回転 リストからタートルを削除 (実演) 計算機プログラミングI (増原) 2003年度

34 リスト構造: クラス定義 自分自身の定義を使用 →再帰的なデータ構造
public class LinkedTurtle extends Turtle { //数珠つなぎタートル LinkedTurtle next; //次のタートル public LinkedTurtle(int x, int y, int angle, LinkedTurtle next) { super(x, y, angle); this.next = next; } 自分自身の定義を使用 →再帰的なデータ構造 next next next LinkedTurtle LinkedTurtle LinkedTurtle null 計算機プログラミングI (増原) 2003年度

35 リスト構造の操作: リストを作る public class ListDemo {
public static void main(String[] args) { ウインドウを作る LinkedTurtle l = null; while (true) { if (追加ボタンが押された) { int x = …, y = …; l = new LinkedTurtle(x, y, 0, l); f.add(l); l.fd(0); } else 他のボタンが押されたときの処理(略) } 「何も参照していない」値 → 空を表わす (null: 全ての参照型に 共通する特別な値) 今までの「先頭」を 「次」とするような タートルを作り、 「先頭」lにしまう 計算機プログラミングI (増原) 2003年度

36 リスト構造の操作: リストを作る LinkedTurtle l = null; l = new LinkedTurtle(x,y,0,l);

37 リスト構造の操作: リストを作る LinkedTurtle l = null; l = new LinkedTurtle(x,y,0,l);
next LinkedTurtle null 計算機プログラミングI (増原) 2003年度

38 リスト構造の操作: リストを作る LinkedTurtle l = null; l = new LinkedTurtle(x,y,0,l);
next next LinkedTurtle LinkedTurtle null 計算機プログラミングI (増原) 2003年度

39 リスト構造の操作: リストを作る LinkedTurtle l = null; l = new LinkedTurtle(x,y,0,l);
next next next LinkedTurtle LinkedTurtle LinkedTurtle null 計算機プログラミングI (増原) 2003年度

40 リスト構造の操作: 繰り返し 再帰的なメソッド呼び出し (※for文などでも可能)
例: リストの全ての要素に対して何かをする = リストの先頭に何かをする + 続くリストの全ての要素に対して何かをする public class LinkedTurtle { インスタンス変数 コンストラクタの定義 public void forwardAll(int s) { fd(s); if (next != null) { next.forwardAll(s); } 再帰的なメソッド呼出 リストの最後でない場合は 繰り返す next next LinkedTurtle LinkedTurtle null 計算機プログラミングI (増原) 2003年度

41 リスト構造の操作: 要素の追加 先頭に追加: 新しいタートルを作るだけ 末尾に追加: 途中に追加: 先頭から順に末尾までたどる
末尾の「次」に新しいタートルをつなげる 途中に追加: 追加したい場所の「次」を書き換える next LinkedTurtle next next next LinkedTurtle LinkedTurtle LinkedTurtle null 計算機プログラミングI (増原) 2003年度

42 リスト構造の操作: 要素の追加 先頭に追加: 新しいタートルを作るだけ 末尾に追加: 途中に追加: 先頭から順に末尾までたどる
末尾の「次」に新しいタートルをつなげる 途中に追加: 追加したい場所の「次」を書き換える next LinkedTurtle next next next LinkedTurtle LinkedTurtle LinkedTurtle null 計算機プログラミングI (増原) 2003年度

43 リスト構造の操作: 要素の追加 先頭に追加: 新しい要素を作るだけ 末尾に追加: 途中に追加: 先頭から順に末尾までたどる
public class LinkedTurtle { インスタンス変数・コンストラクタ・他のメソッド(略) public void append(LinkedTurtle m) { if (next == null) { next = m; } else { next.append(m); } 先頭に追加: 新しい要素を作るだけ 末尾に追加: 先頭から順に末尾までたどる 末尾の「続く要素」に新しい要素をつなげる 途中に追加: 追加したい場所の「続く要素」を書き換える next LinkedTurtle next next next LinkedTurtle LinkedTurtle LinkedTurtle null 計算機プログラミングI (増原) 2003年度

44 リスト構造の操作: 要素を削除する 先頭から削除: 「次」を先頭にする 途中を削除: 削除する要素の手前の「次」を書き換える
プログラム上のテクニック: (途中に追加する場合も同様のテクニック) l next next next LinkedTurtle LinkedTurtle LinkedTurtle null 計算機プログラミングI (増原) 2003年度

45 リスト構造の操作: 要素を削除する 先頭から削除: 「次」を先頭にする 途中を削除: 削除する要素の手前の「次」を書き換える
プログラム上のテクニック: (途中に追加する場合も同様のテクニック) next next next LinkedTurtle LinkedTurtle LinkedTurtle null 計算機プログラミングI (増原) 2003年度

46 リスト構造の操作: 要素を削除する 先頭から削除: 「続くリスト要素」を先頭にする 途中を削除:
削除する要素の手前の「続くリスト要素」を書き換える プログラム上のテクニック: (途中に追加する場合も同様のテクニック) next next next LinkedTurtle LinkedTurtle LinkedTurtle null 計算機プログラミングI (増原) 2003年度

47 リスト構造の操作: 要素を削除する 先頭から削除: 「続くリスト要素」を先頭にする 途中を削除:
public LinkedTurtle delete(LinkedTurtle m) { if (this == m) { return next; } else { next = next.delete(m); return this; } 先頭から削除: 「続くリスト要素」を先頭にする 途中を削除: 削除する要素の手前の「続くリスト要素」を書き換える プログラム上のテクニック: (途中に追加する場合も同様のテクニック) 自身が削除される要素だったら 次の要素を返す l = l.delete(m); l next next next LinkedTurtle LinkedTurtle LinkedTurtle null 計算機プログラミングI (増原) 2003年度

48 フラクタル図形のヒント = = = 計算機プログラミングI (増原) 2003年度

49 フラクタル図形のヒント = = = 計算機プログラミングI (増原) 2003年度

50 フラクタル図形のヒント = = 計算機プログラミングI (増原) 2003年度

51 フラクタル図形のヒント = = = = 計算機プログラミングI (増原) 2003年度

52 色々なフラクタル図形 http://www.seanet.com/~garyteachout/fill.html
Copyright © 2002 by Hidehiko Masuhara 計算機プログラミングI (増原) 2003年度

53 色々なフラクタル図形 計算機プログラミングI (増原) 2003年度
Copyright © 2002 by Hidehiko Masuhara 計算機プログラミングI (増原) 2003年度