Document

再帰処理(2)
～基礎コース編～
1
再帰処理 2015年度
はじめに

基礎コースでは、前回に引き続き再帰関数に取
り組み、練習問題13-9まで完成させる!
1.
2.
3.
練習問題13-7: 十進数の二進数表現
練習問題13-8: べき乗の判定
練習問題13-9: 再帰関数による二分探索
その前に…
2
再帰処理 2015年度
フィボナッチ数のおさらい

練習問題13-5: 再帰関数によるフィボナッチ数
–
フィボナッチ数:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
(n > 1 の場合)
の定義に基づき、フィボナッチ数を求める再帰関数
fibonacci(n)を定義し、F(24)の値を求めよ。
3
再帰処理 2015年度
フィボナッチ数のおさらい

練習問題13-5: 再帰関数によるフィボナッチ数
–
フィボナッチ数
fibonacci()関数の引数nが0の場合、
F(0) = 0
return文により0を返す
F(1) = 1
F(n) = F(n-1) + F(n-2)
(n > 1 の場合)
4
再帰処理 2015年度
フィボナッチ数のおさらい

練習問題13-5: 再帰関数によるフィボナッチ数
–
フィボナッチ数
F(0) = 0
fibonacci()関数の引数nが1の場合、
F(1) = 1
F(n) = F(n-1) +return文により1を返す
F(n-2)
(n > 1 の場合)
5
再帰処理 2015年度
フィボナッチ数のおさらい

練習問題13-5: 再帰関数によるフィボナッチ数
–
フィボナッチ数
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
(n > 1 の場合)
fibonacci()関数の引数nが0でも1でもない場合、
fibonacci(n-1)とfibonacci(n-2)を求め、これらを
足した値をreturn文により返す
6
再帰処理 2015年度
フィボナッチ数のおさらい

フィボナッチ数を求める関数の定義
int fibonacci( int n )
{
int f;
if( n == 0 ){
return 0;
} else if( n == 1 ){
return 1;
} else {
f = fibonacci( n-1 ) + fibonacci( n-2 );
return f;
}
}
F(0) = 0
F(1) = 1
7
F(n) = F(n-1) + F(n-2)
再帰処理 2015年度
再帰関数のハイライトのおさらい

練習問題13-6: 複雑な再帰関数の動作の確認
–
フィボナッチ数を求める再帰関数と同様に、
関数の中で自分自身を2回呼び出している。
–
フィボナッチ数では結果のみ確認できればよかった
が…
練習問題13-6では、どのような順番で関数が実行さ
れるのかを確認する必要。
–
8
再帰処理 2015年度
再帰関数のハイライトのおさらい

練習問題13-6: 複雑な再帰関数の動作の確認
main関数:
9
引数、変数なし
再帰処理 2015年度
再帰関数のハイライトのおさらい

練習問題13-6: 複雑な再帰関数の動作の確認
main関数:
引数、変数なし
print_TGU (1回目 … main関数内):
xc: 0
shift: 30
10
gen: 2
再帰処理 2015年度
再帰関数のハイライトのおさらい

練習問題13-6: 複雑な再帰関数の動作の確認
main関数:
引数、変数なし
print_TGU (1回目 … main関数内):
xc: 0
shift: 30
gen: 2
print_TGU (2回目 … 1回目のprint_TGU内にある上のprint_TGU):
xc: xc+shift/2 = 15 shift: shift/2 = 15
gen: gen-1 = 1
11
再帰処理 2015年度
再帰関数のハイライトのおさらい

練習問題13-6: 複雑な再帰関数の動作の確認
main関数:
引数、変数なし
print_TGU (1回目 … main関数内):
xc: 0
shift: 30
gen: 2
print_TGU (2回目 … 1回目のprint_TGU内にある上のprint_TGU):
xc: xc+shift/2 = 15 shift: shift/2 = 15
gen: gen-1 = 1
print_TGU (3回目 … 2回目のprint_TGU内にある上のprint_TGU):
xc: xc+shift/2 = 22 shift → shift/2 = 7
gen → gen-1 = 0
12
再帰処理 2015年度
再帰関数のハイライトのおさらい

練習問題13-6: 複雑な再帰関数の動作の確認
main関数:
引数、変数なし
print_TGU (1回目 … main関数内):
xc: 0
shift: 30
gen: 2
print_TGU (2回目 … 1回目のprint_TGU内にある上のprint_TGU):
xc: xc+shift/2 = 15 shift: shift/2 = 15
gen: gen-1 = 1
print_TGU (3回目 … 2回目のprint_TGU内にある上のprint_TGU):
xc: xc+shift/2 = 22 shift → shift/2 = 7
gen → gen-1 = 0
print_TGU (4回目 … 3回目のprint_TGU内にある上のprint_TGU):
xc: xc+shift/2 = 25 shift → shift/2 = 3
gen → gen-1 = -1
13
再帰処理 2015年度
再帰関数のハイライトのおさらい

14
練習問題13-6: 複雑な再帰関数の動作の確認
main関数:
引数、変数なし
print_TGU (1回目 … main関数内):
xc: 0
shift: 30
gen: 2
print_TGU (2回目 … 1回目のprint_TGU内にある上のprint_TGU):
xc: xc+shift/2 = 15 shift: shift/2 = 15
gen: gen-1 = 1
print_TGU (3回目 … 2回目のprint_TGU内にある上のprint_TGU):
xc: xc+shift/2 = 22 shift → shift/2 = 7
gen → gen-1 = 0
print_TGU (4回目 … 3回目のprint_TGU内にある上のprint_TGU):
xc: xc+shift/2 = 25 shift → shift/2 = 3
gen → gen-1 = -1
print_TGU (5回目 … 3回目のprint_TGU内にある下のprint_TGU):
xc: xc-shift/2 = 19 shift → shift/2 = 3
gen → gen-1 = -1
再帰処理 2015年度
…
再帰関数の応用

練習問題13-7: 十進数の二進表現(下の桁から)
–
考え方(てびきにあるヒントの概要)



15
2で割った余りが１桁目の値(0または1)となる。
2で割った値(小数点以下切り捨て)が0より大きい場合、
2で割った値(小数点以下切り捨て)を使用して
2桁目以降を求める。
2で割った値(小数点以下切り捨て)が0になるまで、
以上を繰り返す。
…
再帰処理 2015年度
再帰関数の応用

練習問題13-7: 十進数の二進表現(下の桁から)
–
具体例: 十進数で510(二進数で1012)の場合

16
先ず、510(1012)を2で割った余りは5%2=1なので、1桁目は1
再帰処理 2015年度
再帰関数の応用

練習問題13-7: 十進数の二進表現(下の桁から)
–
具体例: 十進数で510(二進数で1012)の場合


17
先ず、510(1012)を2で割った余りは5%2=1なので、1桁目は1
次に、510(1012)を2で割った値(小数点以下切り捨て)は210(102)
なので、2桁目以降は210(102)について考えると…
210(102)を2で割った余りは2%2=0なので、2桁目は0
再帰処理 2015年度
再帰関数の応用

練習問題13-7: 十進数の二進表現(下の桁から)
–
具体例: 十進数で510(二進数で1012)の場合



18
先ず、510(1012)を2で割った余りは5%2=1なので、1桁目は1
次に、510(1012)を2で割った値(小数点以下切り捨て)は210(102)
なので、2桁目以降は210(102)について考えると…
210(102)を2で割った余りは2%2=0なので、2桁目は0
さらに、210(102)を2で割った値(小数点以下切り捨て)は110(12)
なので、3桁目以降は110(12)について考えると…
110(12)を2で割った余りは1%2=1なので、3桁目は1
再帰処理 2015年度
再帰関数の応用

練習問題13-7: 十進数の二進表現(下の桁から)
–
具体例: 十進数で510(二進数で1012)の場合




19
先ず、510(1012)を2で割った余りは5%2=1なので、1桁目は1
次に、510(1012)を2で割った値(小数点以下切り捨て)は210(102)
なので、2桁目以降は210(102)について考えると…
210(102)を2で割った余りは2%2=0なので、2桁目は0
さらに、210(102)を2で割った値(小数点以下切り捨て)は110(12)
なので、3桁目以降は110(12)について考えると…
110(12)を2で割った余りは1%2=1なので、3桁目は1
最後に、110(12)を2で割った値(小数点以下切り捨て)は010(02)
なので終わり
再帰処理 2015年度
再帰関数の応用

練習問題13-7: 十進数の二進表現(下の桁から)
–
では、どのようにプログラムしたらよいか?
nの二進表現を求める関数: ten2binary(n)を考える。


先ず、nを2で割った余りを画面に表示。
nを2で割った値(小数点以下切り捨て)が0より大きい場合…
–

→ ten2binary( n/2 );
nを2で割った値(小数点以下切り捨て)が0の場合…
–
20
2桁目以降を求めるためにnを2で割った値(小数点以下切り捨
て)を引数として ten2binary() を実行。
何もせず関数の実行を終了。
→ return;
再帰処理 2015年度
再帰関数の応用

練習問題13-8: 整数aがbのべき乗か否か判定
–
考え方(手引きにある説明の概要)


aをbで割った余りが0でなければ、aはbのべき乗ではない。
aをbで割った余りが0の場合…
–
–
21
aとbが等しければaはbのべき乗。
aとbが等しくない場合、「aをbで割った値」がbのべき乗か否か
を判定し…
 「aをbで割った値」がbのべき乗の場合、aもbのべき乗。
 「aをbで割った値」がbのべき乗ではない場合、
aもbのべき乗ではない。
再帰処理 2015年度
再帰関数の応用

練習問題13-8: 整数aがbのべき乗か否か判定
–
では、どのようにプログラムしたらよいか?
べき乗を判定する関数: isPower( a, b )を考える。


aをbで割った余りが0でなければ、aはbのべき乗ではないこ
とを意味する0を返す( return 0; )。
余りが0の場合…
–
aとbが等しければaはbのべき乗であることを意味する1を返
す( return 1; )。
– aとbが等しくない場合…
 「aをbで割った値」を判定対象としてisPower()を実行した
結果を判定結果として返す( return isPower( a/b, b); )。
22
再帰処理 2015年度
再帰関数の応用

練習問題13-9: 再帰関数による二分探索
–
考え方(手引きにある説明の概要)

探索区間a～bの中から値cを探す関数として
binarySearch( a, b, c) を考える。
探索区間a～bの中間地点の値x = (a+b) / 2 を求める。
– x が c の場合、値c が見つかったので x を戻り値として返す。
– x が c より大きい場合、c はa～(x – 1)の範囲にあるので、
探索区間をa～(x – 1)としてbinarySearch()を実行し、
その結果を戻り値として返す。
– x が c より小さい場合、c は(x + 1)～bの範囲にあるので、
探索区間を(x + 1)～bとしてbinarySearch()を実行し、
その結果を戻り値として返す。
–
23
再帰処理 2015年度

Download Report