アウトライン
17-1 フィボナッチ数
17-2 パソコン演習
17-3 課題
2
17-1 フィボナッチ数
3
１ １ ２ ３ ５ ８ １３ ２１ ３４
フィボナッチ数
4
１
２
３
５
８
フィボナッチ数
5
•生成的再帰（木構造再帰プロセス）の形で，フィボ
ナッチ数
のi 番めの数 を計算するプログラムを作る
例） 0,1,1,2,3,5,8,13,21,34,55,89,144,....
)1(
,1
,0
21
1
0
nfff
f
f
nnn
i
f
フィボナッチ数
6
)1(
,1
,0
21
1
0
nfff
f
f
nnn
フィボナッチ数
7
17-2 パソコン演習
8
•資料を見ながら，「例題」を行ってみる
•各自，「課題」に挑戦する
•自分のペースで先に進んで構いません
パソコン演習の進め方
9
•DrScheme の起動
プログラム → PLT Scheme → DrScheme
•今日の演習では「Intermediate Student」
に設定
Language
→ Choose Language
→ Intermediate Student
→ Execute ボタン
DrScheme の使用
10
•生成的再帰（木構造再帰プロセス）の形で，フィボ
ナッチ数
のi 番めの数 を計算するプログラムを作る
例） 0,1,1,2,3,5,8,13,21,34,55,89,144,....
)1(
,1
,0
21
1
0
nfff
f
f
nnn
i
f
例題１．フィボナッチ数
11
1. 次を「定義用ウインドウ」で，実行しなさい
•入力した後に，Execute ボタンを押す
(define (fibo n)
(cond
[(= n0) 0]
[(= n1) 1]
[else (+ (fibo (- n1)) (fibo (- n2)))]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆次は，例題２に進んでください
(fibo 5)
(fibo 6)
(fibo 7)
「例題１．フィボナッチ数」の手順
12
実行結果の例
13
fibo
3
入力 出力
4
入力は数値 出力は数値
入力と出力
14
(define (fibo n)
(cond
[(= n0) 0]
[(= n1) 1]
[else (+ (fibo (- n1)) (fibo (- n2)))]))
フィボナッチ数
15
1. n = 0 ならば：→終了条件
0 →自明な解
2. n = 1 ならば：→終了条件
1 →自明な解
3. そうで無ければ：
–(fibo (- n 2)) と(fibo (- n 1)) を足す
⇒結局，fibo の実行を繰り返す
フィボナッチ数
16
(fibo 4)から
3 が得られる過程の概略 (1/2)
(fibo 4)
= …
= (+ (fibo (- 4 1))
(fibo (- 4 2)))
= …
= (+ (+
(fibo (- 3 1))
(fibo (- 3 2)))
(fibo (- 4 2)))
= …
= (+ (+ (+
(fibo (- 2 1))
(fibo (- 2 2)))
(fibo (- 3 2)))
(fibo (- 4 2)))
= …
= (+ (+ (+
1
0)
(fibo (- 3 2)))
(fibo (- 4 2))) 17
(fibo 4)から
3 が得られる過程の概略 (2/2)
= …
= (+ (+ 1
1)
(fibo (- 4 2)))
= …
= (+ 2
(+
(fibo (- 2 1))
(fibo (- 2
2))))
= …
= (+ 2
(+ 1 0))
= …
= 3
18
(fibo 4)
(fibo 3)
(fibo 2)
(fibo 1) (fibo 0)
(fibo 1)
(fibo 2)
(fibo 1) (fibo 0)
fibo の計算パターンは、木構造再帰である
19
フィボナッチ数
•関数 fibo は，n > 1 のとき，fibo を2
回呼び出す
例） (fibo 10) を計算するために (fibo
9) と(fibo 8) を計算している
•計算パターンは，木構造再帰(tree
recursion)をなす
•樹木状をなす （前ページ）
20
•フィボナッチ数
のi番めの数 を計算するプログラムを作る
•例題１よりも繰り返し回数が少なくなるよう
に工夫する
)1(
,1
,0
21
1
0
nfff
f
f
nnn
i
f
例題２．「反復的プロセス」での
フィボナッチ数
21
1. 次を「定義用ウインドウ」で，実行しなさい
•入力した後に，Execute ボタンを押す
(define (fibo n)
(fibo-iterate 1 0 n))
(define (fibo-iterate a b counter)
(cond
[(= counter 0) b]
[else (fibo-iterate (+ a b) a(- counter 1))]))
2. その後，次を「実行用ウインドウ」で実行しなさい
☆次は，課題に進んでください
(fibo 5)
(fibo 6)
(fibo 7)
「例題２．反復的プロセスでのフィボナッチ数」の手順
22
実行結果
23
(define (fibo n)
(fibo-iterate 1 0 n))
(define (fibo-iterate a b counter)
(cond
[(= counter 0) b]
[else (fibo-iterate (+ a b) a(- counter 1))]))
「反復的プロセス」でのフィボナッチ数
24
1. まず，f1(=1), f0(=0) から始め
る
2. 次に，f0, f1を使って，f2を求
める
3. ・・・
4. n に達するまで続ける
「反復的プロセス」でのフィボナッチ数
25
a=1, b=0 から開始して，
a ← a + b
b ← a
を繰り返す．
「反復的プロセス」でのフィボナッチ数
26
(define (fibo-iterate a b counter)
(cond
[(= counter 0) b]
[else (fibo-iterate (+ a b) a(- counter
1))]))
a ← a + b
b← a
終了条件
27
(fibo 4)
= (fibo-iterate 1 0 4)
=...
= (fibo-iterate 1 1 3)
=...
= (fibo-iterate 2 1 2)
=...
= (fibo-iterate 3 2 1)
=...
= (fibo-iterate 5 3 0)
=...
= 3
a, b, counter の
値が変化する
(fibo 4) から 3 が得られる過程の概略
28
•例題１
•木構造的な再帰
•計算が冗長
例） (fibo 4) の計算では，(fibo 2), (fibo 1), (fibo 0) が
繰り返し現れる
•例題２
•反復的プロセス
•例題１ではあった「冗長な計算」が、例題２で無い
まとめ
29
17-3 課題
30
•例題１と例題２のフィボナッチ数のプログラムを，性
能の面から比較せよ
•例題１と例題２のプログラムについて，(fibo 6) を計算する
ために，例題１の fibo, 例題２の fibo-iterate が何回繰り返し
実行されるか数えよ
•例題１と例題２のプログラムを，DrScheme のstepper で実
行し，最終的な結果が得られるまでに「next」ボタンを押し
た回数（置き換えが起こった回数）を数えてみよ
•これは，(fibo 3), (fibo 4), (fibo 5), (fibo 6) について行え
課題１
31
