|
Вопрос # 5 493/ вопрос открыт / |
|
Здравствуйте, уважаемые эксперты!
Помогите написать прогу для вычисления чисел фибоначчи рекурсивным способом
 |
Вопрос задал: Aristotel (статус: Посетитель)
Вопрос отправлен: 11 июля 2011, 12:43
Состояние вопроса: открыт, ответов: 1.
|
Ответ #1. Отвечает эксперт: Вадим К
Здравствуйте, Aristotel!
function fib(n:integer):integer;
begin
if (n = 1) or (n = 2) then result := 1
else result := fib(n - 1) + fib(n-2);
end;
на форму ставим edit1 для ввода, и label для вывода результата. И конечно кнопку, по которой будет производится расчет. Обработчик клика будет такой
Label1.caption := Intttostr(fib(strtoint(edit1.text)));
 |
Ответ отправил: Вадим К (статус: Академик)
Время отправки: 11 июля 2011, 12:48
Оценка за ответ: 5
Комментарий к оценке: А вот этот кусок писать где?
|
Мини-форум вопроса
Всего сообщений: 31; последнее сообщение — 11 июля 2011, 15:36; участников в обсуждении: 4.
Страницы: [« Предыдущая] [1] [2]
|
|
Aristotel (статус: Посетитель), 11 июля 2011, 13:24 [#21]:
Ну вот а то когда я не менял-всё работало-так что всё в порядке-менять не нужно))
|
|
Gooddy (статус: 3-ий класс), 11 июля 2011, 13:32 [#22]:
function fib( n: Int64 ): Int64;
var
a1, a2: Int64;
i: Integer;
begin
a1 := 0;
a2 := 1;
Result := a1 + a2;
for i:=3 to n do
begin
a1 := a2;
a2 := Result;
Result := a1 + a2;
end;
end;
Вот неплохой вариант итерационного метода. Под условия задачи не подходит но вычисляет быстрее. Особенно большие числа.
Вычисляет до 80-ого числа фибоначи за доли секунды. После 80-ого будет переполнение.
Чисти код! Чисти код! Чисти код!
|
|
|
Вадим К (статус: Академик), 11 июля 2011, 13:32 [#23]:
Можно написать рекурсией, но сделать код очень быстрым, просто жуть как быстрым.
Обычной рекурсией для числа 60 и больше будет считаться очень долго. А мы делаем так
заводим глобальный массив
const max_n = 200;
var f[1..max_n] of int64; // до 200, что бы наверняка. кому не нравится - могут переписать под динамический массив или увеличить-уменьшить диапазон.
в formCreate вписываем код
f[1] := 1;
f[2] := 1;
for i := 3 to 200 do
f[i] := 0;
сама процедура рассчета теперь будет быстрой.
function fib(n:integer):integer;
begin
if (n < max_n) and (f[n] = 0) then begin
result := fib(n - 1) + fib(n-2);
f[n] := rusult;
end
else if (n < max_n) and (f[n] <> 0) then
result := f[n]
else
result := fib(n - 1) + fib(n-2);
end;
Такой код до 200 будет считать очень быстро, а дальше - там разрядной сетки может не хватить
Пишу на глаз, вроде ошибок не сделал.
Почему такой код будет очень быстрым? просто он не считает дважды одно и тоже число, а "кеширует".
Галочка "подтверждения прочтения" - вселенское зло.
|
|
min@y™ (статус: Доктор наук), 11 июля 2011, 13:32 [#24]:
Из-за такой ерунды такой флейм! Интересно...
Делаю лабы и курсачи по Delphi и Turbo Pascal. За ПИВО! Пишите в личку, а лучше в аську. А ещё лучше - звоните в скайп!
|
|
|
Aristotel (статус: Посетитель), 11 июля 2011, 13:41 [#25]:
Всем спасибо но мне и прошлая программа подошла.
Удачи и до новых вопросов))
|
|
|
Gooddy (статус: 3-ий класс), 11 июля 2011, 13:47 [#26]:
Вадим К: итерационный метод в любом случае быстрей. Рекурсия выигрывает в понятности и связанности, но не в скорости.
Чисти код! Чисти код! Чисти код!
|
|
|
Вадим К (статус: Академик), 11 июля 2011, 13:49 [#27]:
в данной задаче - да, рекурсия будет медленной. Но рекурсию нужно тоже уметь готовить
Галочка "подтверждения прочтения" - вселенское зло.
|
|
|
Gooddy (статус: 3-ий класс), 11 июля 2011, 13:57 [#28]:
И число высчитывается не 2 раза кстати.
Например для 5-го числа
7-ое - 1 раз
6-ое - 2 раза
5-ое - 3 раза
4-ое - 5 раз
3-е - 8 раз
2-ое и 3-е задаются статически и не вычисляются. Но вызовы процедуры для их получения происходят. Причём так:
2-ое - 13 раз.
1-ое - 8 раз.
1-ое вызывается реже, потому что оно используется лишь для расчёта 3-ки, а тогда как остальные числа используются для двух более старших.
Чисти код! Чисти код! Чисти код!
|
|
|
Gooddy (статус: 3-ий класс), 11 июля 2011, 13:58 [#29]:
Так что для чисел фибоначи лучше использовать итерацию. А рекурсия хороша для факториала. Коротко и быстро.
Чисти код! Чисти код! Чисти код!
|
|
|
Вадим К (статус: Академик), 11 июля 2011, 14:14 [#30]:
Мой код рекурсии (последний приведенный) слишком медленнее итерационного метода?
Галочка "подтверждения прочтения" - вселенское зло.
|
|
|
Gooddy (статус: 3-ий класс), 11 июля 2011, 15:36 [#31]:
Не слишком. Но для понимания сложнее, чем итерационный и тем более чем рекурсия без примочек.
Чисти код! Чисти код! Чисти код!
|
12 июля 2011, 12:18: Вопрос перемещён из тематического раздела Delphi » Общие вопросы по программированию в раздел Лабораторный практикум » Delphi модератором Ерёмин А.А.
Страницы: [« Предыдущая] [1] [2]
Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.
|
