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

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

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

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

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

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

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

Найти k-й член последовательности Фибоначчи - C++
Последовательность Фибоначчи образуется так: первый и второй члены последовательности равны 1, каждый следующий равен сумме двух предыдущих...

Вычислите n-й член F(n) последовательности Фибоначчи - C++
Вычислите n-й член F(n) последовательности Фибоначчи. В этой последовательности первые два члена равны 1, а каждый последующий равен сумме...

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

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

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

16
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
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Эксперт С++
7418 / 4533 / 673
Регистрация: 29.11.2010
Сообщений: 12,287
06.04.2013, 09:27 #3
Цитата Сообщение от salam Посмотреть сообщение
прежде всего нужно понимать, что рекурсией они не считаются. Рекурсия для данной задачи очень медленна. Такой вариант приемлем:
ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 09:57 #4
salam, рекурсия с меморизацией и все круть. А насчет матричного метода - по моему он нужен, когда нужно вычислить число Фибоначчи по модулю, т.е. какие-нибудь огромные числа.
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
06.04.2013, 16:55 #5
Цитата Сообщение от Dani Посмотреть сообщение
рекурсия с меморизацией
это говнореализация обычного подсчета, который я описал, не более...

Добавлено через 1 минуту
Цитата Сообщение от MrGluck Посмотреть сообщение
ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема.
внезапно...) быть может, какое-то доказательство найдется вашей гипотезе?
0
Байт
Эксперт C
16324 / 10600 / 1587
Регистрация: 24.12.2010
Сообщений: 20,207
06.04.2013, 17:03 #6
C++
1
Fn = pow(sqrt(5) + 1)/2, n) / (2*sqrt(5));
1
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
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 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 17:56 #8
Байт, эта формула не годится для программирования т.к. дает неточности.
salam, и что? и что ты хочешь этим сказать? все и так знают, что итерацией работает быстрее.
0
salam
165 / 146 / 14
Регистрация: 10.07.2012
Сообщений: 738
06.04.2013, 17:58 #9
Цитата Сообщение от MrGluck Посмотреть сообщение
ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема.
я хотел сказать, что эта гипотеза - говно.
0
Байт
Эксперт C
16324 / 10600 / 1587
Регистрация: 24.12.2010
Сообщений: 20,207
06.04.2013, 18:04 #10
Рекурсия при вычислении чисел фибоначчи имеет исключительно учебно-демонстрационный смысл. Вроде как рекурентно определено, давайте в лоб рекурсивно считать. А с точки зрения быстродействия и памяти - вещь достаточно бессмысленная. Учитывая, что если надо только конкретное Fn, то и по памяти иттерационный метод выигрывает. (fib[46] не нужен)

Добавлено через 2 минуты
Цитата Сообщение от Dani Посмотреть сообщение
т.к. дает неточности.
Дает, не волнуйтесь. int Fn - округлит в нужную сторону. Может быть для первых нескольких членов... Да вы попробуйте.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 18:17 #11
Байт, формула Бине же не так выглядит Там же еще вычитание было.
А насчет того что эта формула не пригодна, это всем известно.
окда. Пусть корень дает неточность в 10^(-6). При возведении этого числа в 10^6 будет неточность уже около единицы, что точно повлияет на ответ. и int не поможет)
0
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
06.04.2013, 18:45 #12
Цитата Сообщение от Dani Посмотреть сообщение
Байт, формула Бине же не так выглядит Там же еще вычитание было.
А насчет того что эта формула не пригодна, это всем известно.
окда. Пусть корень дает неточность в 10^(-6). При возведении этого числа в 10^6 будет неточность уже около единицы, что точно повлияет на ответ. и int не поможет)
Вычитания там нет. Но формула для вычисления числа Фибоначчи действительно выглядит не так: делить надо на просто корень из пяти, а не удвоенный. Правда, это её не спасает и она начинает лажать для double начиная с 71-го числа.
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
06.04.2013, 19:09 #13
OhMyGodSoLong, как же? http://ru.wikipedia.org/wiki/Числа_Фибоначчи
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.04.2013, 19:28 #14
Писал когда-то вычисление по модулю.
Число Фибоначчи номер N
0
Байт
Эксперт C
16324 / 10600 / 1587
Регистрация: 24.12.2010
Сообщений: 20,207
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
06.04.2013, 19:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2013, 19:48
Привет! Вот еще темы с ответами:

Поменять местами наибольший член последовательности и член с номером m - C++
Помогите в 4 пункте меню сделать вывод на консоль, в файл и защиту если сразу выбрать 4 пункт. #include &lt;stdio.h&gt; #include...

Вычислить и вывести номер первого элемента последовательности Фибоначчи > 1000. - C++
Вычислить и вывести номер первого элемента последовательности Фибоначчи &gt; 1000.(Числа фибоначи : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

Вычислить сумму чисел последовательности, порядковые номера которых являются числами Фибоначчи - C++
Задана последовательность N вещественных чисел. Вычислить сумму чисел, порядковые номера которых являются: a) числами Фибоначчи. ...

Вычислить сумму чисел последовательности, порядковые номера которых являются числами Фибоначчи - C++
Вычислить сумму чисел последовательности, порядковые номера которых являются числами Фибоначчи программа подчеркивает n в строке float...


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

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

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