---
title: sp-17. フィボナッチ数
tags:  #scheme #フィボナッチ数  
author: [kunihikokaneko](https://www.docswell.com/user/6674398749)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/57GGMP247L.jpg?width=480
description: Scheme プログラミング URL: https://www.kkaneko.jp/pro/scheme/index.html  金子邦彦研究室 URL: https://www.kkaneko.jp/index.html
published: January 26, 22
canonical: https://www.docswell.com/s/6674398749/ZJ84EZ-2022-01-26-145136
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/57GGMP247L.jpg)

sp-17. フィボナッチ数
（Scheme プログラミング）
URL: https://www.kkaneko.jp/pro/scheme/index.html
金子邦彦
1


# Page. 2

![Page Image](https://bcdn.docswell.com/page/4EQXR2PR7P.jpg)

アウトライン
17-1 フィボナッチ数
17-2 パソコン演習
17-3 課題
2


# Page. 3

![Page Image](https://bcdn.docswell.com/page/KJ468LYQ71.jpg)

17-1 フィボナッチ数
3


# Page. 4

![Page Image](https://bcdn.docswell.com/page/LE1V2L6L7G.jpg)

フィボナッチ数
１
１
２
３
５
８
１３
２１
３４
4


# Page. 5

![Page Image](https://bcdn.docswell.com/page/GEWLRVWQ72.jpg)

フィボナッチ数
８
５
１
２
３
5


# Page. 6

![Page Image](https://bcdn.docswell.com/page/47ZMR453E3.jpg)

フィボナッチ数
• 生成的再帰（木構造再帰プロセス）の形で，フィボ
ナッチ数
f 0 = 0,
f 1 = 1,
f n = f n −1 + f n − 2 ( n  1)
の i 番めの数
を計算するプログラムを作る
fi
例） 0,1,1,2,3,5,8,13,21,34,55,89,144,....
6


# Page. 7

![Page Image](https://bcdn.docswell.com/page/YJ6NR39ZJV.jpg)

フィボナッチ数
f 0 = 0,
f 1 = 1,
f n = f n −1 + f n − 2 ( n  1)
7


# Page. 8

![Page Image](https://bcdn.docswell.com/page/GJ558LN9J4.jpg)

17-2 パソコン演習
8


# Page. 9

![Page Image](https://bcdn.docswell.com/page/LE3N8L22E5.jpg)

パソコン演習の進め方
• 資料を見ながら，「例題」を行ってみる
• 各自，「課題」に挑戦する
• 自分のペースで先に進んで構いません
9


# Page. 10

![Page Image](https://bcdn.docswell.com/page/8EDWMNZ67G.jpg)

DrScheme の使用
•
DrScheme の起動
プログラム
•
→ PLT Scheme → DrScheme
今日の演習では「Intermediate Student」
に設定
Language
→ Choose Language
→ Intermediate Student
→ Execute ボタン
10


# Page. 11

![Page Image](https://bcdn.docswell.com/page/V7P9R5YZJ8.jpg)

例題１．フィボナッチ数
• 生成的再帰（木構造再帰プロセス）の形で，フィボ
ナッチ数
f 0 = 0,
f 1 = 1,
f n = f n −1 + f n − 2 ( n  1)
の i 番めの数
を計算するプログラムを作る
fi
例） 0,1,1,2,3,5,8,13,21,34,55,89,144,....
11


# Page. 12

![Page Image](https://bcdn.docswell.com/page/2JVMRPGMJQ.jpg)

「例題１．フィボナッチ数」の手順
1. 次を「定義用ウインドウ」で，実行しなさい
•
入力した後に，Execute ボタンを押す
(define (fibo n)
(cond
[(= n 0) 0]
[(= n 1) 1]
[else (+ (fibo (- n 1)) (fibo (- n 2)))]))
2. その後，次を「実行用ウインドウ」で実行しなさい
(fibo 5)
(fibo 6)
(fibo 7)
☆
次は，例題２に進んでください
12


# Page. 13

![Page Image](https://bcdn.docswell.com/page/5EGGMP8XEL.jpg)

実行結果の例
13


# Page. 14

![Page Image](https://bcdn.docswell.com/page/4JQXR295EP.jpg)

入力と出力
3
4
fibo
入力
入力は数値
出力
出力は数値
14


# Page. 15

![Page Image](https://bcdn.docswell.com/page/K7468LXVE1.jpg)

フィボナッチ数
(define (fibo n)
(cond
[(= n 0) 0]
[(= n 1) 1]
[else (+ (fibo (- n 1)) (fibo (- n 2)))]))
15


# Page. 16

![Page Image](https://bcdn.docswell.com/page/LJ1V2LN4EG.jpg)

フィボナッチ数
1. n = 0 ならば：
0
→ 終了条件
→ 自明な解
2. n = 1 ならば：
1
→ 終了条件
→ 自明な解
3. そうで無ければ：
– (fibo (- n 2)) と (fibo (- n 1)) を足す
⇒ 結局，fibo の実行を繰り返す
16


# Page. 17

![Page Image](https://bcdn.docswell.com/page/GJWLRV4ZE2.jpg)

(fibo 4)から
3 が得られる過程の概略 (1/2)
(fibo 4)
= (+ (+ (+
=…
(fibo (- 2 1))
(fibo (- 2 2)))
= (+ (fibo (- 4 1))
(fibo (- 3 2)))
(fibo (- 4 2)))
(fibo (- 4 2)))
=…
=…
= (+ (+
(fibo (- 3 1)) = (+ (+ (+
1
(fibo (- 3 2)))
0)
(fibo (- 4 2)))
(fibo (- 3 2)))
=…
(fibo (- 4 2)))
17


# Page. 18

![Page Image](https://bcdn.docswell.com/page/4EZMR42LJ3.jpg)

(fibo 4)から
3 が得られる過程の概略 (2/2)
=…
= (+ (+
1
1)
(fibo (- 4 2)))
=…
= (+ 2
(+
2))))
=…
= (+ 2
(+ 1 0))
=…
=3
(fibo (- 2 1))
(fibo (- 2
18


# Page. 19

![Page Image](https://bcdn.docswell.com/page/Y76NR3VM7V.jpg)

(fibo 4)
(fibo 3)
(fibo 2)
(fibo 1)
(fibo 2)
(fibo 1) (fibo 1)
(fibo 0)
(fibo 0)
fibo の計算パターンは、木構造再帰である
19


# Page. 20

![Page Image](https://bcdn.docswell.com/page/G7558LDQ74.jpg)

フィボナッチ数
• 関数 fibo は，n > 1 のとき，fibo を2
回呼び出す
例） (fibo 10) を計算するために (fibo
9) と (fibo 8) を計算している
• 計算パターンは，木構造再帰(tree
recursion)をなす
• 樹木状をなす （前ページ）
20


# Page. 21

![Page Image](https://bcdn.docswell.com/page/9J2NKL8WER.jpg)

例題２．「反復的プロセス」での
フィボナッチ数
• フィボナッチ数
f 0 = 0,
f1 = 1,
f n = f n −1 + f n − 2 (n  1)
の i 番めの数 f i を計算するプログラムを作る
• 例題１よりも繰り返し回数が少なくなるよう
に工夫する
21


# Page. 22

![Page Image](https://bcdn.docswell.com/page/DEYPNQ69EM.jpg)

「例題２．反復的プロセスでのフィボナッチ数」の手順
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


# Page. 23

![Page Image](https://bcdn.docswell.com/page/VJN5XKZD78.jpg)

実行結果
23


# Page. 24

![Page Image](https://bcdn.docswell.com/page/YE9Y8VZ8J3.jpg)

「反復的プロセス」でのフィボナッチ数
(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


# Page. 25

![Page Image](https://bcdn.docswell.com/page/GE868P1Z7D.jpg)

「反復的プロセス」でのフィボナッチ数
1. まず，f1 (=1), f0 (=0) から始め
る
2. 次に，f0, f1 を使って，f2 を求
める
3. ・・・
4. n に達するまで続ける
25


# Page. 26

![Page Image](https://bcdn.docswell.com/page/LEL9R1Q1JR.jpg)

「反復的プロセス」でのフィボナッチ数
a=1, b=0 から開始して，
a←a+b
b←a
を繰り返す．
26


# Page. 27

![Page Image](https://bcdn.docswell.com/page/4JMZRW15EW.jpg)

終了条件
(define (fibo-iterate a b counter)
(cond
a←a+b
[(= counter 0) b]
[else (fibo-iterate (+ a b) a (- counter
1))]))
b← a
27


# Page. 28

![Page Image](https://bcdn.docswell.com/page/PJR6RYLZ79.jpg)

(fibo 4) から 3 が得られる過程の概略
(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 の
値が変化する
28


# Page. 29

![Page Image](https://bcdn.docswell.com/page/PEXMRGW17X.jpg)

まとめ
• 例題１
• 木構造的な再帰
• 計算が冗長
例） (fibo 4) の計算では，(fibo 2), (fibo 1), (fibo 0) が
繰り返し現れる
• 例題２
• 反復的プロセス
• 例題１ではあった「冗長な計算」が、例題２で無い
29


# Page. 30

![Page Image](https://bcdn.docswell.com/page/3EKGR4VMJD.jpg)

17-3 課題
30


# Page. 31

![Page Image](https://bcdn.docswell.com/page/L73N8LM275.jpg)

課題１
• 例題１と例題２のフィボナッチ数のプログラムを，性
能の面から比較せよ
• 例題１と例題２のプログラムについて，(fibo 6) を計算する
ために，例題１の fibo, 例題２の fibo-iterate が何回繰り返し
実行されるか数えよ
• 例題１と例題２のプログラムを，DrScheme のstepper で実
行し，最終的な結果が得られるまでに「next」ボタンを押し
た回数（置き換えが起こった回数）を数えてみよ
• これは，(fibo 3), (fibo 4), (fibo 5), (fibo 6) について行え
31