Fibonacci-Zahlen

Definition. Die Fibonacci-Zahlen sind die Folge von Zahlen(Fi)i∈N definiert durch

1. F0 = 0, F1 = 1,2. Fi = Fi−1 + Fi−2 für alle i ∈ N, i ≥ 2.

Berechnung:

fib :: Int -> Intfib 0 = 0fib 1 = 1fib n = (fib (n - 1)) + (fib (n - 2))

Fibonacci-Zahlen

Definition. Die Fibonacci-Zahlen sind die Folge von Zahlen(Fi)i∈N definiert durch

1. F0 = 0, F1 = 1,2. Fi = Fi−1 + Fi−2 für alle i ∈ N, i ≥ 2.

Berechnung:

fib :: Int -> Intfib 0 = 0fib 1 = 1fib n = (fib (n - 1)) + (fib (n - 2))

Fibonacci-Zahlen: Rekursion

fib 5

fib 3 fib 4

fib 1 fib 2 fib 2 fib 3

fib 0 fib 1 fib 0 fib 1 fib 1 fib 2

fib 0 fib 1

. . . F200?! Effizienter durch Memoization.

Fibonacci-Zahlen: Rekursion

fib 5

fib 3 fib 4

fib 1 fib 2 fib 2 fib 3

fib 0 fib 1 fib 0 fib 1 fib 1 fib 2

fib 0 fib 1

. . . F200?! Effizienter durch Memoization.

Fibonacci-Zahlen: Geschlossene Form

Sei ϕ =√

5+12 ≈ 1,618 der goldene Schnitt.

Satz (de Moivre – Binet). Fn = ϕn−(−ϕ)−n

ϕ−(−ϕ)−1 = ϕn−(−ϕ)−n√

5=

[ϕn√

5

]cfib :: Int -> Integercfib n = (round (phi^n / sqrtfive))where sqrtfive = (sqrt 5.0)

phi = ((1 + sqrtfive) / 2)

F200 = 280571172992509965361722520092440986124288

Korollar. limn→∞ Fn+1/Fn = ϕ

11

2 3

58

13 21

3455

11

2 3

58

Sonnenblumen

Größe 5

Größe 5

5

10

2

712

4

9

1

6

11

3

8

13

9

17

4

12

20

7

15

2

10

18

5

1321

8

16

3

11

19

6

14

1

Größe 3, 4

Größe 3, 4

2

4

1

3

5

4

7

25

8

3

61

4

7

2

5

8

3

6

1

5

10

2

7

12

4

9

16

11

3

8

13

Größe 2

Größe 2

2

31

2

4

1

3

5

Größe 6

Größe 6

9

17

4

12

20

7

15

2

10

18

5

13

21

8

16

3

11

19

6

14

1

13

26

5

18

31

10

23

2

15

28

7

20

33

12

25

4

17

30

9

22

1

14

27

6

19 32

11

24

3

16

29

8

21

34