10
правок
Изменения
→Фибоначева Система Исчисления
|definition = '''Числа Фибоначчи''' -- числовая последовательность первые два члена которой равны 0 и 1, либо 1 и 1, а каждый последующий равен сумме двух предыдущих
}}
[[Файл:FibonacciBlocks.png|thumb|Черепица с квадратами, длина сторон которых является последовательными числами Фибоначчи: 1, 1, 2, 3, 5, 8, 13 и 21]]
$F_1=1, F_2=1, F_n=F_{n-1} + F_{n-2}$,
где $n>=2$ <br>пример: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, …<br> Числа также числа Фибоначчи задаются можно обобщить на произвольные начальные значения $F_1$ и $F_2$ например [https://ru.wikipedia.org/wiki/%D0%9BA7%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%80%D0%B5%D0%BD%D1%82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D1%81%D0%BB%D0%B5B0_%D0%B49B%D0D1%BE8E%D0%B2BA%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C|линейным рекуррентным соотношениемЧисла Люка] $F_1$=1, $F_2$=1, $F_n$=$F_{n-1}$ + $F_{n-2}$, где $n>=2$
==Числа Фибоначчи и золотое сечение==
[[Файл:0_L7N1ispU7cFS4HV8.jpeg|200px|thumb|спираль золотого сечения]]
[https://ru.wikipedia.org/wiki/%D0%97%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B5_%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D0%B5| Золотое сечение] может быть выражено, с помощью чисел Фибоначчи: $$\Phi=\lim\limits_{x \to \infty} \dfrac{F_{n+1}}{F_n}$$
Формула $Бине$ выражает в явном виде значение $F_{n}$ как функцию от $n$:
$F_n=\dfrac{\phi^n - (-\phi)^{-n}}{2\phi - 1}$,где <br>$\phi=\dfrac{\sqrt5 + 1}{2}$ - золотое сечение
===Доказательство===
:$\psi=\dfrac{1-\sqrt{5}}{2}=-\dfrac{1}{\phi}$
Докажем формулу по индукции. Для этого нужно доказать равенство $\phi^n - \psi^n + \phi^{n+1} - \psi^{n+1}= \psi^{n+2} - \phi^{n+2}$,
которое после преобразования превращается в $\phi^n(1 - \phi - \phi^2) = \psi^n(1 - \psi - \psi^2)$. Осталось заметить, что оба числа, $\phi$ и $\psi$, служат корнями многочлена $1 - a - a^2$, так что выражения в скобках в обеих частях равенства обращаются в ноль одновременно. Вот и доказан индуктивный переход. Что же касается базы индукции, то она совершенно очевидна при n=0 и n=1.
==Тождества==
:Из этой формулы следует, что сумма биномиальный коэффициентов на диагонали<br>треугольника паскаля есть число Фибоначчи<br>
==Фибоначева Система Исчислениясчисления=='''Фибоначчева Фибоначчива Система исчеслениясчисления''' - позиционная система исчесления счисления для целых чисел на основе чисел Фибоначчи.
===Представление натуральных чисел===
{{Теорема
==Наихудший случай алгоритма Евклида==
Если для алгоритма Евклида требуются N шагов для пары натуральных чисел $a > b > 0$, наименьшие значения a и b, для которых это выполняется — числа Фибоначчи $F_{N+2}$ и $F_{N+1}$ соответственно. Тогда, если алгоритм Евклида требует N шагов для пары чисел $(a,b)$, где $a > b$, выполняются следующие неравенства $a ≥ F_{N+2}$ и $b ≥ F_{N+1}$. Доказать это можно по математической индукции. Если N = 1, тогда a делится на b без остатка. Наименьшие натуральные числа, для которых это верно, равны b = 1 и a = 2, соответственно F2 и F3. Предположим теперь, что результат выполняется для всех значений N до M − 1. Первый шаг алгоритма Евклида с M шагами $a = q0b q_0b + r0r_0$, и алгоритм Евклида для пары чисел $(b,r0r_0)$, где b > r0, требует M − 1 шагов. По предположению индукции имеем $b ≥ F_{M+1}$ и $r0 r_0 >= F_M$. Следовательно, $a = q_0b + r_0 ≥ b + r_0 ≥ F_{M+1} + F_M = F_{M+2}$, что является искомым неравенством. Это доказательство, опубликованное Габриэлем Ламе в 1844 году
== Источники информации ==
*[http://ru.wikipedia.org/wiki/Числа_Фибоначчи {{---}} Числа Фибоначчи]
*[http://ru.wikipedia.org/wiki/Алгоритм_Евклида {{---}} Алгоритм Евклида]
