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

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

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

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

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

привет всем!
Вычислите n-й член F(n) последовательности Фибоначчи. В этой последовательности первые два члена равны 1, а каждый последующий равен сумме двух предыдущих
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.04.2013, 16:48     Вычислить n член F(n) последовательности Фибоначчи
Посмотрите здесь:

Вычислить и вывести номер первого элемента последовательности Фибоначчи > 1000. C++
C++ наибольший член в последовательности
C++ Вычислить n член последовательности при n=0 Xn=1 , при n=>1 Xn=n*X(n-1)+1/n
В последовательности а1,...,a30 поменять местами наибольший член и член с номером m. C++
Вычислите n-й член F(n) последовательности Фибоначчи C++
C++ Поменять местами наибольший член последовательности и член с номером m
C++ Вычислить определённый член последовательности Фибоначчи
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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Эксперт С++
 Аватар для MrGluck
6225 / 3470 / 424
Регистрация: 29.11.2010
Сообщений: 9,178
06.04.2013, 09:27     Вычислить n член F(n) последовательности Фибоначчи #3
Цитата Сообщение от salam Посмотреть сообщение
прежде всего нужно понимать, что рекурсией они не считаются. Рекурсия для данной задачи очень медленна. Такой вариант приемлем:
ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 09:57     Вычислить n член F(n) последовательности Фибоначчи #4
salam, рекурсия с меморизацией и все круть. А насчет матричного метода - по моему он нужен, когда нужно вычислить число Фибоначчи по модулю, т.е. какие-нибудь огромные числа.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
06.04.2013, 16:55     Вычислить n член F(n) последовательности Фибоначчи #5
Цитата Сообщение от Dani Посмотреть сообщение
рекурсия с меморизацией
это говнореализация обычного подсчета, который я описал, не более...

Добавлено через 1 минуту
Цитата Сообщение от MrGluck Посмотреть сообщение
ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема.
внезапно...) быть может, какое-то доказательство найдется вашей гипотезе?
Байт
Эксперт C
 Аватар для Байт
15050 / 9452 / 1383
Регистрация: 24.12.2010
Сообщений: 17,500
06.04.2013, 17:03     Вычислить n член F(n) последовательности Фибоначчи #6
C++
1
Fn = pow(sqrt(5) + 1)/2, n) / (2*sqrt(5));
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
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
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 17:56     Вычислить n член F(n) последовательности Фибоначчи #8
Байт, эта формула не годится для программирования т.к. дает неточности.
salam, и что? и что ты хочешь этим сказать? все и так знают, что итерацией работает быстрее.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
06.04.2013, 17:58     Вычислить n член F(n) последовательности Фибоначчи #9
Цитата Сообщение от MrGluck Посмотреть сообщение
ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема.
я хотел сказать, что эта гипотеза - говно.
Байт
Эксперт C
 Аватар для Байт
15050 / 9452 / 1383
Регистрация: 24.12.2010
Сообщений: 17,500
06.04.2013, 18:04     Вычислить n член F(n) последовательности Фибоначчи #10
Рекурсия при вычислении чисел фибоначчи имеет исключительно учебно-демонстрационный смысл. Вроде как рекурентно определено, давайте в лоб рекурсивно считать. А с точки зрения быстродействия и памяти - вещь достаточно бессмысленная. Учитывая, что если надо только конкретное Fn, то и по памяти иттерационный метод выигрывает. (fib[46] не нужен)

Добавлено через 2 минуты
Цитата Сообщение от Dani Посмотреть сообщение
т.к. дает неточности.
Дает, не волнуйтесь. int Fn - округлит в нужную сторону. Может быть для первых нескольких членов... Да вы попробуйте.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 18:17     Вычислить n член F(n) последовательности Фибоначчи #11
Байт, формула Бине же не так выглядит Там же еще вычитание было.
А насчет того что эта формула не пригодна, это всем известно.
окда. Пусть корень дает неточность в 10^(-6). При возведении этого числа в 10^6 будет неточность уже около единицы, что точно повлияет на ответ. и int не поможет)
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1240 / 989 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
06.04.2013, 18:45     Вычислить n член F(n) последовательности Фибоначчи #12
Цитата Сообщение от Dani Посмотреть сообщение
Байт, формула Бине же не так выглядит Там же еще вычитание было.
А насчет того что эта формула не пригодна, это всем известно.
окда. Пусть корень дает неточность в 10^(-6). При возведении этого числа в 10^6 будет неточность уже около единицы, что точно повлияет на ответ. и int не поможет)
Вычитания там нет. Но формула для вычисления числа Фибоначчи действительно выглядит не так: делить надо на просто корень из пяти, а не удвоенный. Правда, это её не спасает и она начинает лажать для double начиная с 71-го числа.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 19:09     Вычислить n член F(n) последовательности Фибоначчи #13
OhMyGodSoLong, как же? http://ru.wikipedia.org/wiki/Числа_Фибоначчи
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.04.2013, 19:28     Вычислить n член F(n) последовательности Фибоначчи #14
Писал когда-то вычисление по модулю.
Число Фибоначчи номер N
Байт
Эксперт C
 Аватар для Байт
15050 / 9452 / 1383
Регистрация: 24.12.2010
Сообщений: 17,500
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 (которое тоже неплохо бы представить в виде длинного) исчерпает всю память вашего компа, а также всю память имеющихся у человечества запоминающих устройств (включая стиральные машины и кофеварки).
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1240 / 989 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
06.04.2013, 19:59     Вычислить n член F(n) последовательности Фибоначчи #16
93 / √5) < 264 < (φ94 / √5), если чё.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2013, 20:11     Вычислить n член F(n) последовательности Фибоначчи
Еще ссылки по теме:

C++ Вычислить сумму чисел последовательности, порядковые номера которых являются числами Фибоначчи
В последовательности Фибоначчи найти индекс члена последовательности, удовлетворяющего условию C++
C++ Вычислить n-й член последовательности
Найти k-й член последовательности Фибоначчи; верно ли, что сумма первых n членов есть чётное число? C++
C++ Найти k-й член последовательности Фибоначчи

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

Или воспользуйтесь поиском по форуму:
Байт
Эксперт C
 Аватар для Байт
15050 / 9452 / 1383
Регистрация: 24.12.2010
Сообщений: 17,500
06.04.2013, 20:11     Вычислить n член F(n) последовательности Фибоначчи #17
Цитата Сообщение от Dani Посмотреть сообщение
формула Бине же не так выглядит Там же еще вычитание было.
Вот лежит передо мной Кнут, том 1, издание 1976 г. стр.117.
Fn = 1/√5 (Фn - Ф'n)... Была впервые получена Муавром в 1718 г.
Но второй член чрезвычайно мал.
Конечно, судить о приоритетах - занятие неблагодарное, оставим его тем, для кого это хлеб насущный - историкам
Парой десятков строк ниже
Имеет место утверждение Fn = (Фn√5, округленное до ближайшего целого числа)
(курсив автора)
По поводу лишнего деления на 2, да тут я ошибся.
Округление до ближайшего целого - возможно и здесь я не точен. Ну, можно сказать так: Fn = (int)(... + 0.5)
Yandex
Объявления
06.04.2013, 20:11     Вычислить n член F(n) последовательности Фибоначчи
Ответ Создать тему
Опции темы

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