Найти 10-й член последовательности Фибоначчи

[silalex]

Всем привет! Такая задача: требуется найти 10-й член последовательности Фибоначчи. Кто сможет показать, как это правильно делать?

[RIP]

Проще и быстрее всего по рекуррентной формуле $F_{n+2}=F_{n+1}+F_n$.

[Lion]

Можно записать общий член последовательности как функцию от $n$. Для этого докажите, что $x$ --- корень уравнения $x^2=x+1$, то $a_n=x^n$ --- удовлетворяет последовательности Фиббоначи. Далее, нужно взять линейные комбинации решений этого уравнение: $F_n=C_1x_1^n+C_2x_2^n$. Константы $C_1, C_2$ находятся из начальных условий ($F_1=F_2=1$). Поскольку $|x_2|<1$, то при больших $n$ можно пользоваться приближенной формулой $F_n\approx C_1x_1^n$.

[RIP]

Конкретнее, $F_n$ - ближайшее к $\frac1{\sqrt5}\left(\frac{\sqrt5+1}2\right)^n$ целое число. Но $F_{10}$ проще всего считать по рекуррентной формуле (вычисления занимают от силы полминуты)

[Tarsik]

Скажите пожалуйста как прийти к тому что $a_n=x_n$?
Как найти $x$?
Я пробовал рассматривать последовательность Фибоначчи как геометрическую прогрессию. Тогда з формули $FQ^n=FQ^{n-1}* FQ^{n-2}$ я нашел $q_1=\frac {\sqrt5+1}{2}$ и $q_2=\frac{1-\sqrt5}{2}$. Подскажите правильно ли я делал?

[Brukvalub]

Вот хорошая книжка про эти числа: http://ilib.mccme.ru/plm/ann/a06.htm

[Invisible]

Подскажите, какое время работы и сложность алгоритма для поиска
n-ого числа Фибоначчи при помощи рекурсивного алгоритма.
Формула для расчета:

Fib(n) = Fib(n-1)+Fib(n-2)

[AD]

Invisible писал(а):

Подскажите, какое время работы и сложность алгоритма для поиска n-ого числа Фибоначчи при помощи рекурсивного алгоритма.

Время работы и сложность отвратительные. Не делайте так никогда. Если делать обычным циклом, забывая предыдущие n-3 значения, то будет надежно O(n) по времени и O(1) по памяти.

А вот рекурсивно ...

Ну представьте как это будет. Чтобы посчитать Fib(n), вы что делаете? Сначала считаете Fib(n-2), а потом считаете Fib(n-1), в процессе чего во второй раз вычисляете Fib(n-2).

А теперь намек на точную цифру. Обозначим через T(n) количество операций сложения, требуемых для подсчета Fib(n). Очевидны следующие факты:
T(1)=0;
T(2)=0;
T(n)=T(n-1)+T(n-2)+1 при n>2.

Ну хотя бы из этих соображений видно, что скорость роста T(n) как минимум экспоненциальна.

Аналогичную оценку можно провести и для используемой алгоритмом памяти: при вызове каждой новой функции в стеке выделяется фиксированное количество места под аргумент. Количество вызовов функции фактически тоже равно T(n) - ведь при каждом вызове совершается ровно одно сложение. Так что не избежать вам переполнения стека в таких условиях ...

[Invisible]

AD писал(а):

Время работы и сложность отвратительные. Не делайте так никогда.

да, я знаю, так как если представить в виде дерева например оно будет сильно разрастаться, что увеличит время работы выполнения

Мне просто надо было вычислить какое будет время работы и сложность

AD писал(а):

А теперь намек на точную цифру. Обозначим через T(n) количество операций сложения, требуемых для подсчета Fib(n). Очевидны следующие факты:
T(1)=0;
T(2)=0;
T(n)=T(n-1)+T(n-2)+1 при n>2.

Ну хотя бы из этих соображений видно, что скорость роста T(n) как минимум экспоненциальна.

AD спасибо за помощь, если я правильно посчитал
время выполнения: 2^\frac n 2
сложность: О(2^n)