sp-17. フィボナッチ数

255 Views

January 26, 22

スライド概要

Scheme プログラミング
URL: https://www.kkaneko.jp/pro/scheme/index.html

金子邦彦研究室
URL: https://www.kkaneko.jp/index.html

profile-image

金子邦彦(かねこくにひこ) 福山大学・工学部・教授 ホームページ: https://www.kkaneko.jp/index.html 金子邦彦 YouTube チャンネル: https://youtube.com/user/kunihikokaneko

シェア

埋め込む »CMSなどでJSが使えない場合

関連スライド

各ページのテキスト
1.

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

2.

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

3.

17-1 フィボナッチ数 3

4.

フィボナッチ数 1 1 2 3 5 8 13 21 34 4

5.

フィボナッチ数 8 5 1 2 3 5

6.

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

7.

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

8.

17-2 パソコン演習 8

9.

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

10.

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

11.

例題1.フィボナッチ数 • 生成的再帰(木構造再帰プロセス)の形で,フィボ ナッチ数 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

12.

「例題1.フィボナッチ数」の手順 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) ☆ 次は,例題2に進んでください 12

13.

実行結果の例 13

14.

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

15.

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

16.

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

17.

(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

18.

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

19.

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

20.

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

21.

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

22.

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

実行結果 23

24.

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

25.

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

26.

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

27.

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

28.

(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

29.

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

30.

17-3 課題 30

31.

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