Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 5.00
тым
0 / 0 / 0
Регистрация: 04.04.2013
Сообщений: 10
#1

Вычислить n член F(n) последовательности Фибоначчи - C++

04.04.2013, 16:48. Просмотров 1960. Ответов 16
Метки нет (Все метки)

привет всем!
Вычислите n-й член F(n) последовательности Фибоначчи. В этой последовательности первые два члена равны 1, а каждый последующий равен сумме двух предыдущих
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.04.2013, 16:48     Вычислить n член F(n) последовательности Фибоначчи
Посмотрите здесь:
C++ Вычислить определённый член последовательности Фибоначчи
C++ Найти k-й член последовательности Фибоначчи
Вычислите n-й член F(n) последовательности Фибоначчи C++
Найти k-й член последовательности Фибоначчи; верно ли, что сумма первых n членов есть чётное число? C++
C++ Вычислить n-й член последовательности
В последовательности а1,...,a30 поменять местами наибольший член и член с номером m. C++
C++ Поменять местами наибольший член последовательности и член с номером m
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
06.04.2013, 05:36     Вычислить n член F(n) последовательности Фибоначчи #2
прежде всего нужно понимать, что рекурсией они не считаются. Рекурсия для данной задачи очень медленна. Такой вариант приемлем:
C++
1
2
3
4
5
long long fib[N];
fib[0] = 1;
fib[1] = 1;
for(int i=2; i <= N; i++)
     fib[i] = fib[i-1] + fib[i-2];
Однако стоит понимать, что все равно можно вычислить небольшое количество чисел.
Есть еще более быстрый метод -матричный. Почитайте, если интересно.
MrGluck
Модератор
Эксперт CЭксперт С++
7178 / 4344 / 634
Регистрация: 29.11.2010
Сообщений: 11,821
06.04.2013, 09:27     Вычислить n член F(n) последовательности Фибоначчи #3
Цитата Сообщение от salam Посмотреть сообщение
прежде всего нужно понимать, что рекурсией они не считаются. Рекурсия для данной задачи очень медленна. Такой вариант приемлем:
ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема.
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 09:57     Вычислить n член F(n) последовательности Фибоначчи #4
salam, рекурсия с меморизацией и все круть. А насчет матричного метода - по моему он нужен, когда нужно вычислить число Фибоначчи по модулю, т.е. какие-нибудь огромные числа.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
06.04.2013, 16:55     Вычислить n член F(n) последовательности Фибоначчи #5
Цитата Сообщение от Dani Посмотреть сообщение
рекурсия с меморизацией
это говнореализация обычного подсчета, который я описал, не более...

Добавлено через 1 минуту
Цитата Сообщение от MrGluck Посмотреть сообщение
ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема.
внезапно...) быть может, какое-то доказательство найдется вашей гипотезе?
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,172
06.04.2013, 17:03     Вычислить n член F(n) последовательности Фибоначчи #6
C++
1
Fn = pow(sqrt(5) + 1)/2, n) / (2*sqrt(5));
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
06.04.2013, 17:32     Вычислить n член F(n) последовательности Фибоначчи #7
C++
1
2
3
4
5
6
unsigned long long fibb(int n) {
   if(n == 0 || n == 1)
      return 1;
   else
      return fibb(n-1) + fibb(n-2);
}
эта штука вычисляет 45-ое число Фибоначчи за 8.5 секунд.

C++
1
2
3
4
5
unsigned long long fib[46];
fib[0] = 0;
fib[1] = 1;
for(int i=2; i <= 45; i++)
   fib[i] = fib[i-1] + fib[i-2];
эта штука вычисляет 45-ое число Фибоначчи за 0.1 секунд.

Добавлено через 37 секунд
исполнял на LWS.
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 17:56     Вычислить n член F(n) последовательности Фибоначчи #8
Байт, эта формула не годится для программирования т.к. дает неточности.
salam, и что? и что ты хочешь этим сказать? все и так знают, что итерацией работает быстрее.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
06.04.2013, 17:58     Вычислить n член F(n) последовательности Фибоначчи #9
Цитата Сообщение от MrGluck Посмотреть сообщение
ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема.
я хотел сказать, что эта гипотеза - говно.
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,172
06.04.2013, 18:04     Вычислить n член F(n) последовательности Фибоначчи #10
Рекурсия при вычислении чисел фибоначчи имеет исключительно учебно-демонстрационный смысл. Вроде как рекурентно определено, давайте в лоб рекурсивно считать. А с точки зрения быстродействия и памяти - вещь достаточно бессмысленная. Учитывая, что если надо только конкретное Fn, то и по памяти иттерационный метод выигрывает. (fib[46] не нужен)

Добавлено через 2 минуты
Цитата Сообщение от Dani Посмотреть сообщение
т.к. дает неточности.
Дает, не волнуйтесь. int Fn - округлит в нужную сторону. Может быть для первых нескольких членов... Да вы попробуйте.
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 18:17     Вычислить n член F(n) последовательности Фибоначчи #11
Байт, формула Бине же не так выглядит Там же еще вычитание было.
А насчет того что эта формула не пригодна, это всем известно.
окда. Пусть корень дает неточность в 10^(-6). При возведении этого числа в 10^6 будет неточность уже около единицы, что точно повлияет на ответ. и int не поможет)
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
06.04.2013, 18:45     Вычислить n член F(n) последовательности Фибоначчи #12
Цитата Сообщение от Dani Посмотреть сообщение
Байт, формула Бине же не так выглядит Там же еще вычитание было.
А насчет того что эта формула не пригодна, это всем известно.
окда. Пусть корень дает неточность в 10^(-6). При возведении этого числа в 10^6 будет неточность уже около единицы, что точно повлияет на ответ. и int не поможет)
Вычитания там нет. Но формула для вычисления числа Фибоначчи действительно выглядит не так: делить надо на просто корень из пяти, а не удвоенный. Правда, это её не спасает и она начинает лажать для double начиная с 71-го числа.
Dani
1300 / 637 / 56
Регистрация: 11.08.2011
Сообщений: 2,280
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 19:09     Вычислить n член F(n) последовательности Фибоначчи #13
OhMyGodSoLong, как же? http://ru.wikipedia.org/wiki/Числа_Фибоначчи
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.04.2013, 19:28     Вычислить n член F(n) последовательности Фибоначчи #14
Писал когда-то вычисление по модулю.
Число Фибоначчи номер N
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2013, 19:48     Вычислить n член F(n) последовательности Фибоначчи
Еще ссылки по теме:
Вычислить и вывести номер первого элемента последовательности Фибоначчи > 1000. C++
C++ Вычислить сумму чисел последовательности, порядковые номера которых являются числами Фибоначчи
C++ Вычислить n член последовательности при n=0 Xn=1 , при n=>1 Xn=n*X(n-1)+1/n
В последовательности Фибоначчи найти индекс члена последовательности, удовлетворяющего условию C++
C++ наибольший член в последовательности

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,172
06.04.2013, 19:48     Вычислить n член F(n) последовательности Фибоначчи #15
Цитата Сообщение от Байт Посмотреть сообщение
C++
1
Fn = pow(sqrt(5) + 1)/2, n) / (2*sqrt(5));
Можете считать это шуткой

Добавлено через 6 минут
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
начинает лажать для double начиная с 71-го числа.
Ну с 71-го числа никакая встроенная (int, long) арифметика уже не просто лажает, а дает совершенно неверные результаты. Надо переходить на длинную арифметику, да и та при достаточно большом n (которое тоже неплохо бы представить в виде длинного) исчерпает всю память вашего компа, а также всю память имеющихся у человечества запоминающих устройств (включая стиральные машины и кофеварки).
Yandex
Объявления
06.04.2013, 19:48     Вычислить n член F(n) последовательности Фибоначчи
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru