Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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

1 プログラミング2 関数の再帰呼び出し

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

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(){ func0(); 12 } main() func0() 実行結果 func0() func0 start! func0 end!

4 関数の多段呼び出し 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(){ func1(); 12 } 実行結果 func1 start! func0 start! func0 end! func1 end!

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

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

7 関数の再帰呼び出し 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 } 動作の解説は次ページ 注意!これは失敗例です.

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

9 再帰: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!

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

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

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

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

14 失敗例 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 ); printf("%d! = %d\n", n, k); 11 }

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

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

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

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

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

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

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

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

23 ハノイの塔: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

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

25 ハノイの塔: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

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

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

28 ハノイの塔を解く関数 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);

29 フィボナッチ数列 以下の数列がフィボナッチ数列 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文で加算した方が短時間で計算可能

30 フィボナッチ数列 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

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

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


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

Similar presentations


Ads by Google