プログラミング2 関数の再帰呼び出し http://www.ns.kogakuin.ac.jp/~ct13140/ProgC/

Slides:



Advertisements
Similar presentations
知能情報工学演習 I 第 12 回( C 言語第6 回) 課題の回答 岩村雅一
Advertisements

ハノイの塔 1年9組 馬部 由美絵.
第11回 整列 ~ シェルソート,クイックソート ~
2009/10/9 良いアルゴリズムとは 第2講: 平成21年10月9日 (金) 4限 E252教室 コンピュータアルゴリズム.
プログラミング論 I 関数の再帰呼び出し
OSとコマンド OS:コンピュータを使うための基本プログラム コマンド:OS上で使用できる命令 OS本体であるカーネルの内部コマンド
Stack & Queue & List 3.
二分探索木によるサーチ.
プログラミング論 関数ポインタ と 応用(qsort)
ちょっとした練習問題① 配列iroを['R', 'W', 'R', 'R', 'W' , 'W' , 'W']を宣言して、「W」のときの配列の番号をprintfで表示するようなプログラムを記述しなさい。
プログラミング2 関数
岩村雅一 知能情報工学演習I 第11回(後半第5回) 岩村雅一
プログラミング論 ファイル入出力
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
プログラミング論 I 2008年07月03日 2008年07月10日 2008年7月11日 関数,再帰
関数の定義.
第10回関数 Ⅱ (ローカル変数とスコープ).
アルゴリズムとデータ構造1 2006年6月16日
高度プログラミング演習 (03).
知能情報工学演習I 第12回(後半第6回) 課題の回答
2011/06/21-24 情報知能学科「アルゴリズムとデータ構造」 担当:白井英俊
今までの練習問題の復習.
復習 前回の関数のまとめ(1) 関数はmain()関数または他の関数から呼び出されて実行される.
プログラミング言語論 第五回 理工学部 情報システム工学科 新田直也.
高度プログラミング演習 (08).
プログラミング論 ファイル入出力
高度プログラミング演習 (05).
関数の再帰呼び出しとは ハノイの塔 リダイレクト レポート課題
プログラミング 4 整列アルゴリズム.
プログラミング言語論 第四回 理工学部 情報システム工学科 新田直也.
岩村雅一 知能情報工学演習I 第11回(後半第5回) 岩村雅一
アルゴリズムとデータ構造 2010年7月26日
情報とコンピュータ 静岡大学工学部 安藤和敏
オブジェクト指向プログラミングと開発環境
再帰的手続き.
2011年度 情報科学&情報科学演習 ~ 定番プログラム(2) ~.
演習0 func0, func1, func2を作成せよ. main()関数の中で,func0()を呼び出しを実行せよ.
演習07-0 “Hello\n” “World!\n”と
アルゴリズムとデータ構造1 2006年7月11日
プログラミング論 I 2008年07月03日 関数,再帰
補講:アルゴリズムと漸近的評価.
IF文 START もしも宝くじが当たったら 就職活動する 就職活動しない YES END NO.
情報基礎演習B 後半第2回 担当 岩村 TA 谷本君.
アルゴリズムとデータ構造1 2008年7月24日
バブルソート,バケツソート,クイックソート
アルゴリズムとデータ構造 2013年7月1日
第5回 プログラミングⅡ 第5回
アルゴリズムとデータ構造 補足資料9-1 「ハノイの塔」
オブジェクト指向言語論 第五回 知能情報学部 新田直也.
ループだよ!難しいよ! 第5章 while(ループ);.
演習00-0 “Hello\n” “World!\n”と
プログラミング2 関数の再帰呼び出し
プログラミング入門2 第6回 関数 情報工学科 篠埜 功.
知能情報工学演習I 第12回( C言語第6回) 課題の回答
高度プログラミング演習 (07).
関数と再帰 教科書13章 電子1(木曜クラス) 2005/06/22(Thu.).
プログラミング演習I 2003年6月11日(第9回) 木村巌.
第10回 関数と再帰.
オブジェクト指向言語論 第三回 知能情報学部 新田直也.
情報処理Ⅱ 小テスト 2005年2月1日(火).
プログラミング入門2 第3回 条件分岐(2) 繰り返し文 篠埜 功.
計算技術研究会 第5回 C言語勉強会 関数(function)を使う
岩村雅一 知能情報工学演習I 第13回(後半第7回) 岩村雅一
知能情報工学演習I 第10回( C言語第4回) 課題の回答
プログラミング演習I 補講用課題
第1章 文字の表示と計算 printfと演算子をやります 第1章 文字の表示と計算.
第1章 文字の表示と計算 printfと演算子をやります.
プログラミング 2 静的変数.
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

プログラミング2 関数の再帰呼び出し http://www.ns.kogakuin.ac.jp/~ct13140/ProgC/

概要 関数 関数を再帰的に使用する プログラミング2で最も重要な事項 プログラミング3で最も重要な事項 結構難しい. 関数の作成 と 呼び出し がC言語の真骨頂 プログラミング2で最も重要な事項 関数 プログラミング3で最も重要な事項 ポインタ

関数の多段呼び出し 0/3 実行結果 main() func0() func0() func0 start! func0 end! 1 void func0(){ 2 printf("func0 start!\n"); 3 printf("func0 end!\n"); 4 } 10 void main(){ 11 func0(); 12 } main() func0() 実行結果 func0() func0 start! func0 end!

関数の多段呼び出し 1/3 実行結果 1 void func0(){ 2 printf("func0 start!\n"); 3 printf("func0 end!\n"); 4 } 5 void func1(){ 6 printf("func1 start!\n"); 7 func0(); 8 printf("func1 end!\n"); 9 } 10 void main(){ 11 func1(); 12 } 実行結果 func1 start! func0 start! func0 end! func1 end!

関数の多段呼び出し 2/3 func0() func0() func1() func1() main()

関数の再帰呼び出し ある関数から,自分自身を呼び出すことを再帰呼び出しという. 例えば,関数funct() の中で,funct() を呼び出すなど. 使い方を間違えると,永遠に終了しないプログラムになりやすいので注意.

関数の再帰呼び出し 1 void pr_hl(){ 2 printf("Hello!start\n"); 3 pr_hl(); 4 printf("Hello!end\n"); 5 } 6 void main(){ 7 pr_hl(); 8 } 動作の解説は次ページ 注意!これは失敗例です.

呼び出しを永遠に続け, このプログラムは 終わらない. main() pr_hl()が 呼ばれたので, pr_hl()に移動.

再帰:nの階乗 0/5 nの階乗を,n!と記述する. n! は,n×(n-1)×(n-2)×…×2×1 n! は,n × (n-1)! 5! は,5×4×3×2×1 5! は,5×4!

再帰:nの階乗 1/5 nの階乗は もし n == 1 なら, 答えは,1 もし n > 1 なら, 答えは,n×(n-1)!

再帰:nの階乗 2/5 1 int kaijoh(int x){ 2 int r; 3 if( x == 1 ){ 4 return 1; 5 } else { 6 r = x * kaijoh(x-1); 7 return r; 8 } 9 } 10 void main(){ 11 int n, k; 12 n = 5; 13 k = kaijoh( n ); 14 printf("%d! = %d\n", n, k); 15 }

再帰:nの階乗 3/5 main() kaijoh(3) kaijoh(3)は,3*kaijoh(2) kaijoh(2) これ以上再帰呼び出ししない. これがないと 無限に続く kaijoh(2)=2 kaijoh(3)は,3*2 kaijoh(3)=6

再帰:nの階乗 4/5 kaijoh( 4 ) =4* kaijoh( 3 ) =4* (3* kaijoh( 2 ) ) =4* (3* (2* 1 ) ) =4* (3* ( 2 ) ) =4* ( 6 ) =24

失敗例 1 int kaijoh(int x){ 2 int r; 3 r = x * kaijoh(x-1); 4 return r; ↓ kaijoh(4)を呼び出し kaijoh(3)を呼び出し kaijoh(2)を呼び出し kaijoh(1)を呼び出し kaijoh(0)を呼び出し kaijoh(-1)を呼び出し kaijoh(-2)を呼び出し kaijoh(-3)を呼び出し 無限に続く 1 int kaijoh(int x){ 2 int r; 3 r = x * kaijoh(x-1); 4 return r; 5 } 6 void main(){ 7 int n, k; 8 n = 5; 9 k = kaijoh( n ); 10 printf("%d! = %d\n", n, k); 11 }

再帰:組み合わせ nCr 組み合わせ(Conbination) nCr は, r>1なら, nCr=n-1Cr-1 * n / r

再帰:ハノイの塔 ハノイの塔というパズル ルール 円盤置き場が3カ所ある. 円盤がn枚あり,全て大きさが異なる. 通常,円盤の中心に穴があり, 円盤置き場には杭が立っている. 円盤がn枚あり,全て大きさが異なる. 小さい円盤の上に大きな円盤は置けない. 円盤置き場の1番上の1枚を別の円盤置き場に移動することができる. 引用 奥野かるた店より http://www.okunokaruta.com/ goods/goods12e10.jpg

再帰:ハノイの塔 目的 解法 n枚の円盤を,ある円盤置き場から別の円盤置き場に移動する. できるだけ少ない円盤移動が好ましい. 最適解は, 円盤がn枚の場合,2n-1回の円盤移動. プログラミングでは,再帰的手法で解ける.

ハノイの塔:2枚の例 円盤 1 2 円盤置き場 ↓開始!(円盤2枚を左から中央に) 1 2 1回目の移動. 円盤1を左から右に. 2 1

ハノイの塔:2枚の例 2 1 2回目の移動. 円盤2を左から中央に. 2 1 2 1 3回目の移動. 円盤1を右から中央に. 22-1=3回で終了. 1 2 完了!

ハノイの塔:3枚の例 1 2 1回目の移動. 円盤1を左から中央に. 3 2 2回目の移動. 円盤2を左から右に. 円盤3の上が空に. 3 3回目の移動. 円盤1を中央から右に. 中央の円盤置き場が 空いた.円盤3を 中央に移動可能. 1 3 2

ハノイの塔:3枚の例 4回目の移動. 円盤3を左から中央に. ついに円盤3が移動! 1 3 2 1 5回目の移動. 円盤1を左から右に. 3 6回目の移動. 円盤2を右から中央に. 1 3 2 2 7回目の移動. 円盤1を左から中央に. 1 3 1 2 3

ハノイの塔:4枚の例 24-1=15回の移動. 円盤3枚の移動方法(7回)は分かっている... ↓ 円盤3枚の移動方法を使えば, 円盤4枚の移動方法を導き出せる.

ハノイの塔:4枚の例 合計 7+1+7=15回 1 先ほどの方法で, 円盤3枚(1~3)を 左から右に移動. 7回の円盤移動. 2 3 4 円盤4を左から中央に. 1回の円盤移動. 4 3 1 先ほどの方法で, 円盤3枚(1~3)を 右から中央に移動. 7回の円盤移動. 2 4 3 1 2 3 合計 7+1+7=15回 4

ハノイの塔:5枚の例 合計 15+1+15=31回 1 先ほどの方法で, 円盤4枚(1~4)を 左から右に移動. 15回の円盤移動. : 4 円盤5を左から中央に. 1回の円盤移動. 5 4 1 先ほどの方法で, 円盤4枚(1~4)を 右から中央に移動. 15回の円盤移動. : 5 4 1 : 4 合計 15+1+15=31回 5

ハノイの塔:n枚 合計 (2n-1)+1+(2n-1)=2n+1-1回 1 : n枚を左から右に 移動する. 移動回数2n-1回. n 移動回数1回. : n+1 n 1 : n枚を右から中央に 移動する. 移動回数2n-1回. n+1 n 1 : n 合計 (2n-1)+1+(2n-1)=2n+1-1回 n+1

ハノイの塔:n枚 n枚の移動方法が分かれば, それを用いて n+1枚の移動方法が分かる. 1枚の移動方法は分かる. ↓ 任意の枚数の移動方法が分かる

ハノイの塔を解く関数 ハノイの塔の移動(移動枚数,移動元の円盤置場,移動先の円盤置場,待避円盤置場) もし,移動枚数が1なら, 1枚を「移動元」から「移動先」に移動する. もし,移動枚数が1より大きければ, (n-1)枚を「移動元」から「待避」に移動. n枚目を「移動元」から「移動先」に移動. (n-1)枚を「待避」から「移動先」に移動.

ハノイの塔を解く関数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <stdio.h> void hanoi(int n, int plFrom, int plTo, int plOther){ if( n == 1 ){ printf("move disk.%d ", n); printf("[%d -> %d]\n", plFrom, plTo); } else { hanoi(n-1, plFrom, plOther, plTo); hanoi(n-1, plOther, plTo, plFrom); } void main(){ hanoi(5, 0, 1, 2);

フィボナッチ数列 以下の数列がフィボナッチ数列 1,1,2,3,5,8,13,21,34,… an+an+1=an+2 となる. ただし,a0=1,a1=1 fibo(n)=fibo(n-1)+fibo(n-2) という再帰的な発想で記述可能. ただし,for文で加算した方が短時間で計算可能

フィボナッチ数列 fibo(5) fibo(4) fibo(3) fibo(1) =1 fibo(2) fibo(3) fibo(2) 同じ処理を何度も 行っている. 大変に非効率的 fibo(0) =1 fibo(1) =1 fibo(0) =1 fibo(1) =1

計算量/計算時間 n枚のハノイの塔 n個の数字をバブルソートで並び替える. n個の数字をクイックソートで並び替える n×log(n) に比例する計算量/時間 n個の数字をバケツソートで並び替える n に比例する計算量/時間

練習 (い) fibo(n)=fibo(n-1)+fibo(n-2) という 再帰的な考え方で,