помогите разобраться в задачке. Пожалуйста.
program fibonachi;
uses crt;
var i:byte;
function fib(ind:byte):longint;
begin
case ind of
0:fib:=1;
1:fib:=2;
else fib:=fib(ind-2)+fib(ind-1)
end
end;
Begin
clrscr; textcolor(15);
for i:=0 to 10 do
writeln(i,': ',fib(i));
readln
end.
кто-нибудь может нарисовать стек?
а то я чё-то не понимаю…
26 мая 2008 в 16:00
Стек можно нарисовать как любой путь от вершины дерева вызова до текущей подрограммы…
26 мая 2008 в 16:00
а "текущей подпрограммой" может быть люой вызов, не обязательно листовой (завершающий)
26 мая 2008 в 7:04
дак у меня тема была рекурсия….
26 мая 2008 в 0:04
> и обяснить мне нужно стеково…
Долго думал, что может означать данная фраза – так и не понял
Вам уже сказали, что решение данной задачи через рекурсию КРАЙНЕ не оптимально.
Я бы решал обычным циклом + очередь из двух элементов
25 мая 2008 в 22:03
ну вот сама задачка
//i020.radikal.ru/0805/82/22632b9fd8e4.jpg
и обяснить мне нужно стеково…
25 мая 2008 в 21:05
Действительно оптимальнее использовать ДП (динамическое программирование), когда запоминаем и повтороно используем решение fib[i].
Наверно надо нарисовать не стек, а дерево вызова, т.к. в противном случае потребовалось бы текущее значение переменной ind, чтобы путь от корня дерева до текущего решения образовал стек вызовов.
А рисуется просто с помощью той же рекурсии =)
Если n = 0 или n=1рисуем лист:
……… fib(0 или 1 )
иначе:
………… fib(n)
……… /…….. \
…… fib(n-2) fib(n-1)
25 мая 2008 в 20:04
Ну и? Все ясно, очевидно, и жуть как не оптимально. Вопрос в чем?