Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.93/15: Рейтинг темы: голосов - 15, средняя оценка - 4.93
тым
0 / 0 / 0
Регистрация: 04.04.2013
Сообщений: 10
1

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

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

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

Вычислить определённый член последовательности Фибоначчи
Последовательность Фибоначчи определяется так: F(0) = 0, F(1) = 1, …, F(n) =...

Найти k-й член последовательности Фибоначчи
Последовательность Фибоначчи образуется так: первый и второй члены...

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

Найти k-й член последовательности Фибоначчи; верно ли, что сумма первых n членов есть чётное число?
Дано натуральное число n,n>=3. 1)Найти k-й член последовательности Фибоначчи....

Дано число A. Написать программу, которая выводит первый член последовательности Фибоначчи, который превосходит A
Немножко лень выполнять лабы про программированию...

16
salam
176 / 157 / 29
Регистрация: 10.07.2012
Сообщений: 769
06.04.2013, 05:36 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];
Однако стоит понимать, что все равно можно вычислить небольшое количество чисел.
Есть еще более быстрый метод -матричный. Почитайте, если интересно.
0
MrGluck
Модератор
Эксперт CЭксперт С++
8105 / 4956 / 1436
Регистрация: 29.11.2010
Сообщений: 13,451
06.04.2013, 09:27 3
Цитата Сообщение от salam Посмотреть сообщение
прежде всего нужно понимать, что рекурсией они не считаются. Рекурсия для данной задачи очень медленна. Такой вариант приемлем:
ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема.
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 09:57 4
salam, рекурсия с меморизацией и все круть. А насчет матричного метода - по моему он нужен, когда нужно вычислить число Фибоначчи по модулю, т.е. какие-нибудь огромные числа.
0
salam
176 / 157 / 29
Регистрация: 10.07.2012
Сообщений: 769
06.04.2013, 16:55 5
Цитата Сообщение от Dani Посмотреть сообщение
рекурсия с меморизацией
это говнореализация обычного подсчета, который я описал, не более...

Добавлено через 1 минуту
Цитата Сообщение от MrGluck Посмотреть сообщение
ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема.
внезапно...) быть может, какое-то доказательство найдется вашей гипотезе?
0
Байт
Эксперт C
19212 / 12338 / 2604
Регистрация: 24.12.2010
Сообщений: 25,376
06.04.2013, 17:03 6
C++
1
Fn = pow(sqrt(5) + 1)/2, n) / (2*sqrt(5));
1
salam
176 / 157 / 29
Регистрация: 10.07.2012
Сообщений: 769
06.04.2013, 17:32 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.
1
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 17:56 8
Байт, эта формула не годится для программирования т.к. дает неточности.
salam, и что? и что ты хочешь этим сказать? все и так знают, что итерацией работает быстрее.
0
salam
176 / 157 / 29
Регистрация: 10.07.2012
Сообщений: 769
06.04.2013, 17:58 9
Цитата Сообщение от MrGluck Посмотреть сообщение
ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема.
я хотел сказать, что эта гипотеза - говно.
0
Байт
Эксперт C
19212 / 12338 / 2604
Регистрация: 24.12.2010
Сообщений: 25,376
06.04.2013, 18:04 10
Рекурсия при вычислении чисел фибоначчи имеет исключительно учебно-демонстрационный смысл. Вроде как рекурентно определено, давайте в лоб рекурсивно считать. А с точки зрения быстродействия и памяти - вещь достаточно бессмысленная. Учитывая, что если надо только конкретное Fn, то и по памяти иттерационный метод выигрывает. (fib[46] не нужен)

Добавлено через 2 минуты
Цитата Сообщение от Dani Посмотреть сообщение
т.к. дает неточности.
Дает, не волнуйтесь. int Fn - округлит в нужную сторону. Может быть для первых нескольких членов... Да вы попробуйте.
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 18:17 11
Байт, формула Бине же не так выглядит Там же еще вычитание было.
А насчет того что эта формула не пригодна, это всем известно.
окда. Пусть корень дает неточность в 10^(-6). При возведении этого числа в 10^6 будет неточность уже около единицы, что точно повлияет на ответ. и int не поможет)
0
OhMyGodSoLong
~ Эврика! ~
1247 / 996 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
06.04.2013, 18:45 12
Цитата Сообщение от Dani Посмотреть сообщение
Байт, формула Бине же не так выглядит Там же еще вычитание было.
А насчет того что эта формула не пригодна, это всем известно.
окда. Пусть корень дает неточность в 10^(-6). При возведении этого числа в 10^6 будет неточность уже около единицы, что точно повлияет на ответ. и int не поможет)
Вычитания там нет. Но формула для вычисления числа Фибоначчи действительно выглядит не так: делить надо на просто корень из пяти, а не удвоенный. Правда, это её не спасает и она начинает лажать для double начиная с 71-го числа.
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 19:09 13
OhMyGodSoLong, как же? http://ru.wikipedia.org/wiki/Числа_Фибоначчи
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.04.2013, 19:28 14
Писал когда-то вычисление по модулю.
Число Фибоначчи номер N
0
Байт
Эксперт C
19212 / 12338 / 2604
Регистрация: 24.12.2010
Сообщений: 25,376
06.04.2013, 19:48 15
Цитата Сообщение от Байт Посмотреть сообщение
C++
1
Fn = pow(sqrt(5) + 1)/2, n) / (2*sqrt(5));
Можете считать это шуткой

Добавлено через 6 минут
Цитата Сообщение от OhMyGodSoLong Посмотреть сообщение
начинает лажать для double начиная с 71-го числа.
Ну с 71-го числа никакая встроенная (int, long) арифметика уже не просто лажает, а дает совершенно неверные результаты. Надо переходить на длинную арифметику, да и та при достаточно большом n (которое тоже неплохо бы представить в виде длинного) исчерпает всю память вашего компа, а также всю память имеющихся у человечества запоминающих устройств (включая стиральные машины и кофеварки).
0
OhMyGodSoLong
~ Эврика! ~
1247 / 996 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
06.04.2013, 19:59 16
93 / √5) < 264 < (φ94 / √5), если чё.
1
Байт
Эксперт C
19212 / 12338 / 2604
Регистрация: 24.12.2010
Сообщений: 25,376
06.04.2013, 20:11 17
Цитата Сообщение от Dani Посмотреть сообщение
формула Бине же не так выглядит Там же еще вычитание было.
Вот лежит передо мной Кнут, том 1, издание 1976 г. стр.117.
Fn = 1/√5 (Фn - Ф'n)... Была впервые получена Муавром в 1718 г.
Но второй член чрезвычайно мал.
Конечно, судить о приоритетах - занятие неблагодарное, оставим его тем, для кого это хлеб насущный - историкам
Парой десятков строк ниже
Имеет место утверждение Fn = (Фn√5, округленное до ближайшего целого числа)
(курсив автора)
По поводу лишнего деления на 2, да тут я ошибся.
Округление до ближайшего целого - возможно и здесь я не точен. Ну, можно сказать так: Fn = (int)(... + 0.5)
0
06.04.2013, 20:11
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2013, 20:11

Вычислить n-й член последовательности
Помогите решить задачу, пожалуйста. Пусть а0= 1; аk = k*аk-1 + 1 / k, k =...

В последовательности а1,...,a30 поменять местами наибольший член и член с номером m.
Даны натуральное число m, действительные числа а1,..,a30 (числа попарно...

Поменять местами наибольший член последовательности и член с номером m
Помогите в 4 пункте меню сделать вывод на консоль, в файл и защиту если сразу...


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

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Опции темы

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