sp-17. フィボナッチ数

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

• https://www.kkaneko.jp/pro/scheme/index.html

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

17-1 フィボナッチ数 3

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

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

フィボナッチ数 • 生成的再帰（木構造再帰プロセス）の形で，フィボ ナッチ数 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

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

17-2 パソコン演習 8

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

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

例題１．フィボナッチ数 • 生成的再帰（木構造再帰プロセス）の形で，フィボ ナッチ数 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

「例題１．フィボナッチ数」の手順 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

実行結果の例 13

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

フィボナッチ数 (define (fibo n) (cond [(= n 0) 0] [(= n 1) 1] [else (+ (fibo (- n 1)) (fibo (- n 2)))])) 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 (- 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

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

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

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

例題２．「反復的プロセス」での フィボナッチ数 • フィボナッチ数 f 0 = 0, f1 = 1, f n = f n −1 + f n − 2 (n  1) の i 番めの数 f i を計算するプログラムを作る • 例題１よりも繰り返し回数が少なくなるよう に工夫する 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 a←a+b [(= counter 0) b] [else (fibo-iterate (+ a b) a (- counter 1))])) b← a 27

(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

まとめ • 例題１ • 木構造的な再帰 • 計算が冗長 例） (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