Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Числа Фибоначчи и рекурсия

Sonia © (2007-11-25 20:33:00)
Всем привет!
Подскажите, пожалуйста, можно ли реализовать рекурсивно нахождение опрееленного числа (например, первое больше 1000) из ряда Фибоначчи?
f0=f1=1; fn=fn-1 + fn-2, при n>=2
Если можно, то как тогда в процессе выполнения рекурсии узнать предыдущие 2 числа?

Sonia (2007-11-26 14:03:00) [1]

> DrPass © (26.11.07 00:28) [15]

Спасибо!!! Я примерно так и представляла, только думала обойтись без промежуточных 2-х предыдущих членов :)
Вопрос можно считать закрытым.

@!!ex (2007-11-26 05:43:00) [2]
> Ты видимо решил меня доконать...обидеть еще дальше... Пойми
> ты, если человек не очень хорошо знает рекурсию, не значит,
> что он не разбирается в программировании!!!

фига се...
Сорри. правда не хотел!

> Чего ты не понял? условие поиска члена ряда не по номеру
> члена, а по самому члену (большему 1000 в данном случае)
> .

Тоесть надо найти номер члена, у которого значение равно заданному? ;)

> Уже учла пожелания, но все равно интересно, возможно ли
> такое...

Возможно.

DrPass (2007-11-26 00:28:00) [3]

> Уже учла пожелания, но все равно интересно, возможно ли
> такое...

Ну, возможно конечно. Что мешает крутить рекурсию в другую сторону, по пути цикла? Я бы решил как-нибудь так:
function Fibonachi(prev1, prev2, limit:integer):integer; var n: integer begin n:= prev1 + prev2; if n > limit then Result:= n else Result:= Fibonachi(prev2, n, limit); end;

Стартовать так: Fibonachi(1, 1, 1000)
Решение надуманное, конечно. Но решение ведь

Sonia (2007-11-26 00:04:00) [4]

> Сорри. Не хотел обидеть. Просто было ощущение, что ты более
> менее разбираешься в порграммирование.

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

> Вот теперб вопроса реально не понял...

Чего ты не понял? условие поиска члена ряда не по номеру члена, а по самому члену (большему 1000 в данном случае).

> Надо решать через цикл

Уже учла пожелания, но все равно интересно, возможно ли такое...

@!!ex (2007-11-25 22:07:00) [5]
> А по сему:
> 1) как вы думаете, задавала бы я вопросы, если бы хорошо
> знала рекурсию?

Сорри. Не хотел обидеть. Просто было ощущение, что ты более менее разбираешься в порграммирование. А тут вдруг выясняется, что ты не знаешь рекурсию. :(

> Я уже не новичек на форуме и стараюсь задавать вопросы грамотно,
> поэтому, не обижайте меня, пожалуйста.

А я и не говорил что плохо спрошено. Это вообще было DrPass'у, который считает, что мой вариант неправильный.
На что я и ответил, да не правильный, но на вопрос отвечает.

> Если использовать номер члена ряда, то все просто, а вот
> как найти первый член, больший 1000, не зная его номера...я
> в замешательстве...

Вот теперб вопроса реально не понял...

> Я знаю, что решается. Но с промежуточными переменными (?
> ). А как по вашему будет красивее?

В отличии от математики, где красивое решение - обычно самое рациональное, в программировании все наоборот в 99,(9)% случаев.
Надо решать через цикл. А еще желательно хранить массив с уже расчитанными элементами.
Тогда первый расчет для 1000 будет долгим, зато второй - мгновенным.

P.S.
Кстати, рекурсия загнется на больших числах.

Sonia (2007-11-25 22:04:00) [6]

> DrPass © (25.11.07 21:58) [11]

Спасибо! Я все учту и запомню. Однако теперь уже чисто ради интереса надо понять, как сделать это рекурсией :) Так что вопрос остается в силе

DrPass (2007-11-25 21:58:00) [7]

> И как книжки пишут, рекурсией красивее

Может быть, и красивее, не спорю. Красота - субъективное понятие.
Но что при использовании цикла
а) алгоритм будет работать в несколько раз быстрее
б) алгоритм будет использовать всего несколько десятков байт памяти независимо от N, в то время как рекурсия будет жрать совершенно дикие N * <несколько десятков байт памяти>
- это неопровержимый факт.

Sonia (2007-11-25 21:43:00) [8]

> это пример, а не образец

Я понимаю, что пример, и не говорю ему следовать :)
Однако вопрос стоит четко.

Правильный_Вася (2007-11-25 21:37:00) [9]

> как книжки пишут, рекурсией красивее

это пример, а не образец

Sonia (2007-11-25 21:32:00) [10]

> Кстати, действительно решается банальным циклом, а не рекурсией

Я знаю, что решается. Но с промежуточными переменными (?). А как по вашему будет красивее?
ЗЫ факториал, тоже можно циклом сделать, а можно рекурсией :) И как книжки пишут, рекурсией красивее

Sonia (2007-11-25 21:30:00) [11]
Меня несколько обидел ваш ответ:

> Видимо ты плохо понимаешь рекурсию, раз такие вопросы задаешь.

А по сему:
1) как вы думаете, задавала бы я вопросы, если бы хорошо знала рекурсию?

> Как спрошено, так и отвечено. ;)

2) Спросила я нормально:

нахождение определенного числа (например, первое больше 1000) из ряда Фибоначчи?

Я уже не новичек на форуме и стараюсь задавать вопросы грамотно, поэтому, не обижайте меня, пожалуйста.

По теме:

@!!ex © (25.11.07 20:42) [3]

Если использовать номер члена ряда, то все просто, а вот как найти первый член, больший 1000, не зная его номера...я в замешательстве...

DrPass (2007-11-25 21:28:00) [12]

> @!!ex © (25.11.07 20:58) [5]

Дык ведь...

> можно ли реализовать рекурсивно нахождение опрееленного
> числа (например, первое больше 1000) из ряда Фибоначчи?

Кстати, действительно решается банальным циклом, а не рекурсией

@!!ex (2007-11-25 20:58:00) [13]
> [4] DrPass © (25.11.07 20:43)

Как спрошено, так и отвечено. ;)
Я бы это вообще без рексурсии решал.

DrPass (2007-11-25 20:43:00) [14]

> @!!ex © (25.11.07 20:39) [1]

Ну и найди со своей рекурсивной функцией первое число больше 1000 (n ведь неизвестно!), раз такой умный
:)

@!!ex (2007-11-25 20:42:00) [15]
Лучше всетаки dword, а не integer.
Чтобы какой нить умник не привел к переполнению call стэка вызовом с отричательным числом.
function Fibonachi(n:dword):dword; begin if (n=0) or (n=1) then Result:=1 else Result:=Fibonachi(n-1)+Fibonachi(n-2); end;

@!!ex (2007-11-25 20:40:00) [16]
function Fibonachi(n:integer):integer; begin if (n=0) or (n=1) then Result:=1 else Result:=Fibonachi(n-1)+Fibonachi(n-2); end;

@!!ex (2007-11-25 20:39:00) [17]
> [0] Sonia © (25.11.07 20:33)

Видимо ты плохо понимаешь рекурсию, раз такие вопросы задаешь..

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »