Олімпіади з інформатики: Задача. Числа Фібоначчі.

Задача. Числа Фібоначчі.

Задача. Числа Фібоначчі.

Алгоритм утворення чисел Фібоначчі мовою Паскаль

Program Fibonachi_1; {Рекурсивна форма}

Var N:Integer; A:Array[1..46] of LongInt;

Function Fibo(X:Integer):LongInt;

Begin if A[X]=0 then if (X=1) or (X=2) then A[X]:=1 else

A[X]:=Fibo(X-1)+Fibo(X-2); Fibo:=A[X]; end; {End Fibo}

begin write('Введіть N:'); readln(N); writeln(Fibo(N)); end.

Завдання для самостійного програмування.

1. Записати алгоритм, який знаходить суму чисел Фібоначчі і їх кількість, що менші натурального числа N.

2. Записати алгоритм, який знаходить суму парних чисел Фібоначчі і їх кількість, що менші натурального числа N.

3. Записати алгоритм, який знаходить суму простих чисел Фібоначчі і їх кількість, що менші натурального числа N.

4. Записати алгоритм, який знаходить числа Фібоначчі і їх кількість, що діляться націло на 3 і менші натурального числа N.

5. Записати алгоритм, який знаходить числа Фібоначчі, що діляться націло на 5 і на 2 їх кількість, які менші натурального числа N.

теорія

Послідо́вність Фібона́ччі, чи́сла Фібона́ччі — у математиці числова послідовність

{F_n},

задана

рекурентним співвідношенням другого порядку

F_1=1, F_2=1, F_{n+2}=F_{n}+F_{n+1}, n=1,2,3,\ldots,

F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, F_7=13, F_8=21, \,

і т. д. Ця послідовність виникає у найрізноманітніших математичних ситуаціях — комбінаторних, числових, геометричних.

Суцвіття соняшника з 34 спіралями в один бік і 55 в інший

В природі числа Фібоначчі часто трапляються в різних спіральних формах. Так, черешки листя примикають до стебла по спіралі, що проходить між двома сусідніми листками: 1/3 повного оберту в ліщини, 2/5 — у дуба, 3/8 — у тополі і груші, 5/13 — у верби; лусочки на ялиновій шишці, насіння соняшника розташовані спіралями, причому кількості спіралей кожного напрямку також, як правило, числа Фібоначчі.

Зміст

[сховати]

Формула Біне[ред. • ред. код]

Числа Фібоначчі тісно пов'язані з золотим перетином

\phi=\frac{1 + \sqrt{5}}{2}.

Формула Біне виражає за допомогою

\phi

значення

F_n

в явному вигляді як функцію від

n

F_n = \frac{\phi^n - (-\phi )^{-n}}{\phi - (-\phi )^{-1}} = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}}\approx\frac{\phi^n}{\sqrt{5}}\quad (n\geqslant 1).

При цьому

\phi=1,618\ldots\,\!

(-\phi)^{-1}=1-\phi=-0,618\ldots\,\!

є коренями квадратного рівняння

x^2-x-1=0\,\!

Оскільки

-1<1-\phi<0,

знаходимо, що при

n\geqslant 1,\ -1<(1-\phi)^n<1.

Тому з формули Біне випливає, що для всіх натуральних

n,\, F_n

є найближчим до

\frac{\phi^n}{\sqrt{5}}\,

цілим числом, тому

F_n = \left[\frac{\phi^n}{\sqrt{5}}\right]

або

F_n = \left\lfloor\frac{\phi^n}{\sqrt{5}}+\frac12\right\rfloor

. Зокрема, справедливаасимптотика

F_n\sim \frac{\phi^n}{\sqrt{5}},\ n\to\infty.

Властивості чисел Фібоначчі[ред. • ред. код]

Найбільший спільний дільник двох чисел Фібоначчі дорівнює числу Фібоначчі з індексом, рівним найбільшому спільному дільнику індексів, тобто: . Внаслідок цього:
- $F_m$ ділиться $F_n$ тоді й тільки тоді, коли $m$ ділиться на $n$ (за винятком $n=2$ );
- кожне третє число Фібоначчі парне ( $F_3=2, F_6=8, F_9=34$ );
- кожне четверте ділиться на три ( $F_4=3, F_8=21, F_12=144$ );
- кожне п'ятнадцяте закінчується нулем ( $F_{15}=610$ );
- два сусідніх числа Фібоначчі взаємно прості;
- $F_m$ може бути простим тільки для простих $m$ (за єдиним винятком $m=4,$ що пов'язано з $F_2=1$ ). Зворотне твердженняневірне: $F_{19}=4181=37\cdot 113,$ хоча $19$ — просте число. Тепер невідомо, чи існує нескінченно багато простих чисел Фібоначчі.
Використовуючи те саме рекурентне співвідношення, що і на початку, у вигляді $F_n=F_{n+2}-F_{n+1}$ , можливо поширити визначення чисел Фібоначчі і на від'ємні індекси: $F_0=0, F_{-1} = 1, F_{-2} = -1, F_{-3} = 2, F_{-4} = -3, F_{-5}=5, \ldots.$ Неважко переконатися, що $F_{-n}=(-1)^{n+1}F_{n},$ тобто одержуємо таку саму послідовність із знаками, що чергуються.
Послідовність чисел Фібоначчі є частковим випадком генерованої послідовності, її характеристичний многочлен рівний $x^2 - x - 1$ й має корені $\phi$ і $-1/\phi$ .
Генератрисою послідовності чисел Фібоначчі є:

0 + x + x^2 + 2 x^3 + 3 x^4 + 5 x^5 + \dots = \sum_{n=0}^{\infty} F_n x^n = \frac{x}{1-x-x^2}

Числа Фібоначчі можна представити значеннями континуант на наборі одиниць: $F_n = K_n(1,\dots,1)$ , тобто

F_n = \det \begin{pmatrix} 1 & 1 & 0 &\cdots & 0 \\ -1 & 1 & 1 & \ddots & \vdots\\ 0 & -1 & \ddots &\ddots & 0 \\ \vdots & \ddots & \ddots &\ddots & 1 \\ 0 & \cdots & 0 & -1 & 1 \end{pmatrix}

, а також

\ F_{n+1} = \det \begin{pmatrix} 1 & i & 0 &\cdots & 0 \\ i & 1 & i & \ddots & \vdots\\ 0 & i & \ddots &\ddots & 0 \\ \vdots & \ddots & \ddots &\ddots & i \\ 0 & \cdots & 0 & i & 1\end{pmatrix}

де матриці мають розмір

n\times n

i

— уявна одиниця.

Для будь-якого n,

\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.

Ця формула надає швидкий алгоритм обчислення чисел Фібоначчі за допомогою матричного варіанта алгоритма швидкого піднесення до степеня. Обчислення визначників дає:

(-1)^n = F_{n+1} F_{n-1} - F_n^2

Відношення $\frac{F_{n+1}}{F_n}$ є підходящими дробами золотого перетину $\phi$ і, зокрема, $\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\phi$ .
Суми біноміальних коефіцієнтів на діагоналях трикутника Паскаля є числами Фібоначчі з огляду на формулу

F_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor} {n-k\choose k}

У 1964 р. J. H. E. Cohn довів, що єдиними точними квадратами серед чисел Фібоначчі є $F_0=0, F_1=F_2=1$ і $F_{12}=144=12^2.$

Множина чисел Фібоначчі збігається з множиною натуральних значень наступного полінома двох змінних

P(x,y)= 2xy^4 + x^2 y^3 - 2 x^3 y^2 - y^5 - x^4 y + 2y,

де

x,y\in\mathbb{Z}

— цілі числа, див. P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, стор. 153. Цей факт, знайдений Дж. Джоунзом, відіграє ключову роль у теоремі Матиясевича (негативному розв'язанні десятої проблеми Гільберта), тому що він надає спосіб задати експоненціально зростаючу послідовність чисел Фібоначчі у вигляді діофантової множини.

Числа Фібоначчі за logN[ред. • ред. код]

Ідея полягає в наступному.

F_n = F_(n-1) + F_(n-2)
F_(n+1) = F_n + F_(n-1) = 2*F_(n-1) + F_(n-2)

Можна користуватися цими формулами в початковому вигляді, проте більш раціонально буде наступне матричне рівняння:

| F_n    |        | 1   1 |   | F_(n-2)|
|        |   =    |       |   |        |
| F_(n+1)|        | 1   2 |   | F_(n-1)|.

Якщо через A позначити матрицю

    | 1   1 |
A = |       |
    | 1   2 |,

то отримаєм

| F_(2n)  |             | 1 |
|         |   =  A^n *  |   |
| F_(2n+1)|             | 1 |.

Отже, щоб вирахувати 2n-е/2n +1- е число Фібоначчі, треба матрицю A піднести до n-ого степеня, а це можна зробити за O (log n)операцій.

Історія відкриття[ред. • ред. код]

У XIII столітті італійський математик Фібоначчі розв'язував таку задачу:

Фермер годує кроликів. Кожен кролик народжує одного кролика, коли йому стає 2 місяці, а потім дає потомство в 1 кролик кожен місяць. Скільки кроликів буде у фермера через n місяців, якщо спочатку у нього був лише один (вважаємо, що кролики не гинуть і кожен народжений дає потомство за вище описаною схемою)?

Очевидно, що першого та другого місяця у фермера залишається один кролик, оскільки потомства ще немає. На третій місяць буде два кролики, оскільки перший через два місяці народить другого кролика. На четвертий місяць перший кролик дасть ще одного, а другий кролик потомства не дасть, оскільки йому ще тільки один місяць. Отже на четвертий місяць буде три кролики.

Можна помітити, що кількість кроликів після n — го місяця дорівнює кількості кроликів, які були у n — 1 місяці плюс кількість народжених кроликів. Останніх буде стільки, скільки є кроликів що дають потомство, або дорівнює кількості кроликів, яким вже виповнилося 2 місяці (тобто кількості кроликів після n — 2 місяця).

Якщо через F_n позначити кількість кроликів після n — го місяця, то має місце наступне рекурентне співвідношення:

F_n = F_n-1 + F_n-2, F₁ = F₂ = 1

Покладемо F₀ = 0, при цьому співвідношення при n = 2 залишиться істинним. Таким чином утворюється послідовність

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … ,

Олімпіади з інформатики

четвер, 11 грудня 2014 р.

Задача. Числа Фібоначчі.

Зміст

Формула Біне[ред. • ред. код]

Властивості чисел Фібоначчі[ред. • ред. код]

Числа Фібоначчі за logN[ред. • ред. код]

Історія відкриття[ред. • ред. код]

Немає коментарів:

Дописати коментар

четвер, 11 грудня 2014 р.

Задача. Числа Фібоначчі.

Зміст

Формула Біне[ред. • ред. код]

Властивості чисел Фібоначчі[ред. • ред. код]

Числа Фібоначчі за logN[ред. • ред. код]

Історія відкриття[ред. • ред. код]

Немає коментарів:

Дописати коментар

четвер, 11 грудня 2014 р.