Liczby Fibonacciego

Liczby Fibonacciego

Zarys historyczny problemu

Zarys historyczny problemu

1202 rok

- włoski matematyk

Leonardo Pisano

Leonardo Pisano

odkrył sekwencję liczb

analizując rozwój populacji królików w zagrodzie.

Matematyk chciał przewidzieć, ile królików będzie w zagrodzie

po określonej

liczbie miesięcy.

Przyjął kilka założeń:

•

początkowo rodzi się

1 para królików

•

po miesiącu osiąga dojrzałość

•

po kolejnym miesiącu rodzi następną parę i tak dalej,

tzn. pierwsza para wydaje potomstwo co miesiąc

•

każda nowa para królików po miesiącu osiąga dojrzałość

i po każdym następnym wydaje na świat kolejną parę królików

•

proces ten nie ma końca

•

zakładamy, że króliki żyją wiecznie.

problem

problem

Pytanie:

Pytanie:

Ile królików będzie po

n

- miesiącach?

Liczba królików w danym miesiącu

(za wyjątkiem pierwszego i

drugiego)

zależy od dwóch wartości z poprzedniego miesiąca:

1.

liczby par królików dorosłych

2.

liczby par królików młodych.

Młodych jest tyle, ile było dorosłych dwa miesiące wcześniej.
Jeśli

Fn

Fn

to liczba królików w

n

n

-tym miesiącu to:

 



















3

dla

2

,

1

dla

1

2

1

n

n

F

F

F

n

n

n

Liczby Fibonacciego

Liczby Fibonacciego

–

ciąg liczb naturalnych, o własności: każdy

nastęny wyraz ciągu (z wyjątkiem pierwszego i drugiego) jest sumą

dwóch poprzednich, (tj. 1, 1, 2, 3, 5, 8,…).

Graficzna prezentacja

Graficzna prezentacja

M

M

D

D

D

D

M

M

D

D

D

D

M

M

D

D

M

M

D

D

D

D

M

M

D

D

M

M

D

D

D

D

M

M

D

D

D

D

M

M

D

D

D

D

M

M

D

D

M

M

D

D

D

D

M

M

D

D

D

D

M

M

D

D

M

M

Ciekawostki

Ciekawostki

Istnieje ciekawa zależność między wyrazami ciągu Fibonacciego:

Stosunek sąsiednich wyrazów wynosi około 0,618 lub

1,618.

Liczba 1,618

nosi nazwę

złotej proporcji

złotej proporcji

.

.

W odcinku podzielonym na dwie części zgodnie z zachowaniem
złotej proporcji większa część pozostaje takiej samej relacji do
mniejszej, jak całość do większej.

Złote proporcje są wykorzystywane (w architekturze-Partenon w
Atenach gotyckie katedry; dzieła Mozarta i Bethowena, wysokość
do pępka to 0,618 wysokości ciała, konstrukcje wiolonczeli).

Algorytm obliczania liczb

Algorytm obliczania liczb

Fibonacciego

Fibonacciego

Dane:

n

–

który wyraz ciągu Fibonacciego ma być policzony (liczba naturalna)

Wynik:

Fn

- wartość

n

- tego wyrazu ciągu (liczba naturalna)

1.

Rozpocznij algorytm

2.

Podaj wartość

n

3.

Jeżeli

n

=1 lub

n

=2 to

Fn

przypisz wartość 1 (

Fn

:=1) i przejdź do

kroku 5

w przeciwnym razie

f1

:=1,

f2

:=1

, i

:=2 i przejdź do

kroku 4

4.

Dopóki

i

nie jest równe

n

wykonuj:

Fn

:=

f1

+

f2

,

f1

:=

f2

,

f2

:=

Fn

,

i:=i+1

5.

Wyprowadź wynik

Fn

6.

Zakończ algorytm.

Zmienne pomocnicze:

f1

,

f2

– sąsiednie wyrazu ciagu;

i

- licznik pętli -kolejny wyraz

Schemat blokowy

Schemat blokowy

START

Wprowadź
(n)

n>2

i=n

STOP

n=4

4>2 (n>2) Tak

f1=1, f2=1, i=2

KROK I

2=4

Nie

Fn=1+1; f1=1; f2=2; i=2+1

KROK II

3=4

Nie

Fn=1+2; f1=2; f2=3; i=3+1

KROK III

4=4

Tak

Wypr

3

f1:=1
f2:=1

i:=2

TA
K

TA
K

Fn:=f1+f2

f1:=f2

f2:=Fn

i:=i+1

NIE

NIE

Fn:=1

Wypr (Fn)

Zadania

Zadania

Zadanie1

Napisz program wyznaczający wyraz ciągu Fibonacciego,
którego numer wprowadzany jest z klawiatury.

Zadanie2

Zmodyfikuj program z zadania 1, tak aby sprawdzał czy
wprowadzony numer ciągu jest mniejszy od 24, jeśli nie jest –
ponownie prosi o jego podanie instruując przy tym, jaką
wartość może osiągać ten numer.

Zadanie3

Zmodyfikuj program wyznaczający wyraz ciągu Fibonacciego.
Zdefiniuj procedurę z parametrem przekazywanym przez
wartość,
np.

procedure fib(k:integer);

parametr to numer elementu

ciągu