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

@тым · Регистрация: 04.04.2013

Author24 — интернет-сервис помощи студентам

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

@salam · 06.04.2013, 05:36

прежде всего нужно понимать, что рекурсией они не считаются. Рекурсия для данной задачи очень медленна. Такой вариант приемлем:

C++

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 · 06.04.2013, 09:27

Сообщение от salam

прежде всего нужно понимать, что рекурсией они не считаются. Рекурсия для данной задачи очень медленна. Такой вариант приемлем:

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

@Dani · 06.04.2013, 09:57

salam, рекурсия с меморизацией и все круть. А насчет матричного метода - по моему он нужен, когда нужно вычислить число Фибоначчи по модулю, т.е. какие-нибудь огромные числа.

@salam · 06.04.2013, 16:55

Сообщение от Dani

рекурсия с меморизацией

это говнореализация обычного подсчета, который я описал, не более...

Добавлено через 1 минуту

Сообщение от MrGluck

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

внезапно...) быть может, какое-то доказательство найдется вашей гипотезе?

Байт · 06.04.2013, 17:03

C++

1	Fn = pow(sqrt(5) + 1)/2, n) / (2*sqrt(5));

@salam · 06.04.2013, 17:32

C++

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++

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 · 06.04.2013, 17:56

Байт, эта формула не годится для программирования т.к. дает неточности.
salam, и что? и что ты хочешь этим сказать? все и так знают, что итерацией работает быстрее.

@salam · 06.04.2013, 17:58

Сообщение от MrGluck

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

я хотел сказать, что эта гипотеза - говно.

Байт · 06.04.2013, 18:04

Рекурсия при вычислении чисел фибоначчи имеет исключительно учебно-демонстрационный смысл. Вроде как рекурентно определено, давайте в лоб рекурсивно считать. А с точки зрения быстродействия и памяти - вещь достаточно бессмысленная. Учитывая, что если надо только конкретное Fn, то и по памяти иттерационный метод выигрывает. (fib[46] не нужен)

Добавлено через 2 минуты

Сообщение от Dani

т.к. дает неточности.

Дает, не волнуйтесь. int Fn - округлит в нужную сторону. Может быть для первых нескольких членов... Да вы попробуйте.

@Dani · 06.04.2013, 18:17

Байт, формула Бине же не так выглядит

Там же еще вычитание было.
А насчет того что эта формула не пригодна, это всем известно.
окда. Пусть корень дает неточность в 10^(-6). При возведении этого числа в 10^6 будет неточность уже около единицы, что точно повлияет на ответ. и int не поможет)

@OhMyGodSoLong · 06.04.2013, 18:45

Сообщение от Dani

Байт, формула Бине же не так выглядит

Там же еще вычитание было.
А насчет того что эта формула не пригодна, это всем известно.
окда. Пусть корень дает неточность в 10^(-6). При возведении этого числа в 10^6 будет неточность уже около единицы, что точно повлияет на ответ. и int не поможет)

Вычитания там нет. Но формула для вычисления числа Фибоначчи действительно выглядит не так: делить надо на просто корень из пяти, а не удвоенный. Правда, это её не спасает и она начинает лажать для double начиная с 71-го числа.

@Dani · 06.04.2013, 19:09

OhMyGodSoLong, как же? http://ru.wikipedia.org/wiki/Числа_Фибоначчи

@diagon · 06.04.2013, 19:28

Писал когда-то вычисление по модулю.
Число Фибоначчи номер N

Байт · 06.04.2013, 19:48

Сообщение от Байт

C++

1	Fn = pow(sqrt(5) + 1)/2, n) / (2*sqrt(5));

Можете считать это шуткой

Добавлено через 6 минут

Сообщение от OhMyGodSoLong

начинает лажать для double начиная с 71-го числа.

Ну с 71-го числа никакая встроенная (int, long) арифметика уже не просто лажает, а дает совершенно неверные результаты. Надо переходить на длинную арифметику, да и та при достаточно большом n (которое тоже неплохо бы представить в виде длинного) исчерпает всю память вашего компа, а также всю память имеющихся у человечества запоминающих устройств (включая стиральные машины и кофеварки).

@OhMyGodSoLong · 06.04.2013, 19:59

(φ⁹³ / √5) < 2⁶⁴ < (φ⁹⁴ / √5), если чё.

Байт · 06.04.2013, 20:11

Сообщение от Dani

формула Бине же не так выглядит Там же еще вычитание было.

Вот лежит передо мной Кнут, том 1, издание 1976 г. стр.117.

Fn = 1/√5 (Фⁿ - Ф'ⁿ)... Была впервые получена Муавром в 1718 г.

Но второй член чрезвычайно мал.
Конечно, судить о приоритетах - занятие неблагодарное, оставим его тем, для кого это хлеб насущный - историкам
Парой десятков строк ниже

Имеет место утверждение Fn = (Фⁿ√5, округленное до ближайшего целого числа)

(курсив автора)
По поводу лишнего деления на 2, да тут я ошибся.
Округление до ближайшего целого - возможно и здесь я не точен. Ну, можно сказать так: Fn = (int)(... + 0.5)

@OhMyGodSoLong ~ Эврика! ~ 1256 / 1005 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	06.04.2013, 18:45	12
	Сообщение от Dani Байт, формула Бине же не так выглядит Там же еще вычитание было. А насчет того что эта формула не пригодна, это всем известно. окда. Пусть корень дает неточность в 10^(-6). При возведении этого числа в 10^6 будет неточность уже около единицы, что точно повлияет на ответ. и int не поможет) Вычитания там нет. Но формула для вычисления числа Фибоначчи действительно выглядит не так: делить надо на просто корень из пяти, а не удвоенный. Правда, это её не спасает и она начинает лажать для double начиная с 71-го числа. 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	06.04.2013, 19:28	14
	Писал когда-то вычисление по модулю. Число Фибоначчи номер N 0

@тым 0 / 0 / 0 Регистрация: 04.04.2013 Сообщений: 10
		1
	Вычислить n член F(n) последовательности Фибоначчи 04.04.2013, 16:48. Показов 11954. Ответов 16 Метки нет (Все метки) привет всем! Вычислите n-й член F(n) последовательности Фибоначчи. В этой последовательности первые два члена равны 1, а каждый последующий равен сумме двух предыдущих 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	06.04.2013, 09:27	3
	Сообщение от salam прежде всего нужно понимать, что рекурсией они не считаются. Рекурсия для данной задачи очень медленна. Такой вариант приемлем: ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема. 0

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	06.04.2013, 09:57	4
	salam, рекурсия с меморизацией и все круть. А насчет матричного метода - по моему он нужен, когда нужно вычислить число Фибоначчи по модулю, т.е. какие-нибудь огромные числа. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	06.04.2013, 16:55	5
	Сообщение от Dani рекурсия с меморизацией это говнореализация обычного подсчета, который я описал, не более... Добавлено через 1 минуту Сообщение от MrGluck ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема. внезапно...) быть может, какое-то доказательство найдется вашей гипотезе? 0

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	06.04.2013, 17:56	8
	Байт, эта формула не годится для программирования т.к. дает неточности. salam, и что? и что ты хочешь этим сказать? все и так знают, что итерацией работает быстрее. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	06.04.2013, 17:58	9
	Сообщение от MrGluck ваши суждения верны лишь если надо выполнить данную операцию более чем один раз, иначе рекурсия очень даже приемлема. я хотел сказать, что эта гипотеза - говно. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	06.04.2013, 18:04	10
	Рекурсия при вычислении чисел фибоначчи имеет исключительно учебно-демонстрационный смысл. Вроде как рекурентно определено, давайте в лоб рекурсивно считать. А с точки зрения быстродействия и памяти - вещь достаточно бессмысленная. Учитывая, что если надо только конкретное Fn, то и по памяти иттерационный метод выигрывает. (fib[46] не нужен) Добавлено через 2 минуты Сообщение от Dani т.к. дает неточности. Дает, не волнуйтесь. int Fn - округлит в нужную сторону. Может быть для первых нескольких членов... Да вы попробуйте. 0

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	06.04.2013, 18:17	11
	Байт, формула Бине же не так выглядит Там же еще вычитание было. А насчет того что эта формула не пригодна, это всем известно. окда. Пусть корень дает неточность в 10^(-6). При возведении этого числа в 10^6 будет неточность уже около единицы, что точно повлияет на ответ. и int не поможет) 0

@Dani 1405 / 647 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	06.04.2013, 19:09	13
	OhMyGodSoLong, как же? http://ru.wikipedia.org/wiki/Числа_Фибоначчи 0

@OhMyGodSoLong ~ Эврика! ~ 1256 / 1005 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	06.04.2013, 19:59	16
	(φ⁹³ / √5) < 2⁶⁴ < (φ⁹⁴ / √5), если чё. 1

	06.04.2013, 20:11

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	06.04.2013, 20:11	17
	Сообщение от Dani формула Бине же не так выглядит Там же еще вычитание было. Вот лежит передо мной Кнут, том 1, издание 1976 г. стр.117. Fn = 1/√5 (Фⁿ - Ф'ⁿ)... Была впервые получена Муавром в 1718 г. Но второй член чрезвычайно мал. Конечно, судить о приоритетах - занятие неблагодарное, оставим его тем, для кого это хлеб насущный - историкам Парой десятков строк ниже Имеет место утверждение Fn = (Фⁿ√5, округленное до ближайшего целого числа) (курсив автора) По поводу лишнего деления на 2, да тут я ошибся. Округление до ближайшего целого - возможно и здесь я не точен. Ну, можно сказать так: Fn = (int)(... + 0.5) 0