zastanawiałem się, czy możliwe jest poznanie ile razy funkcja Fibonacciego została wywołana dla każdego n z przedziału 1…N., gdzie N - podaje użytkownik
nie wiem czy dość dokładnie pokazałem o co mi chodzi, ale tłumaczyć tego rozwlekle nie chce, bo jeszcze gorzej zagmatwam :lol:
Wystarczy powiedzieć czy chcesz to wyliczyć analitycznie czy też żeby program pokazał.
Liczba wywołań też będzie tworzyła pewien ciąg:
n < 2: 0
n = 2: 2
n > 2: 2 + suma dwóch poprzednich
z wyjściem na konsolę, o ile dobrze zinterpretowałem
bardzo fajne, ale to rozwikłałem. Przykładowo dla n=10 mam 177 wywołań, ale jest to ogólna liczba wszystkich wywołań… a jak policzyć ile wywołań było dla każdego węzła… bo o to tutaj chodzi
tj. ile razy wywołała się dla
10, dla 9, dla 8 itd…, pewnie chodzi tutaj o włączenia gdzieś w kod czegoś na kształt
licznik++
który będzie pokazywał wynik, jak rekurencja wróci do danego poziomu i wszystko w oddzielnym wyniku
Nadal nie powiedziałeś chcesz policzyć matematycznie czy programowo.
Programowo - jest bardzo prosto.
czyli, źle Cię zrozumiałem
chce to policzyć programowo
Tzn. chodzi Ci o to, że wywołując fib(10) ile razy wywołane zostało fib(10), fib(9), fib(8)…, fib(1)? Jeśli o to Ci chodzi, to liczba wywołań fib(N), …, fib(1) tworzy właśnie ciąg Fibonacciego. Np. dla fib(10):
10 => 1
9 => 1
8 => 2
7 => 3
6 => 5
5 => 8
4 => 13
3 => 21
2 => 34
1 => 55
0 => 34
Suma tych liczb to właśnie 177, jak powiedziałeś. Nie wiem tylko, czy o to Ci chodzi.
tak, dokładnie o to mi chodziło
– Dodane Wt paź 19, 2010 11:26 am –
nie mam tylko za bardzo koncepcji jak to rozwiązać
ale chyba najlepsza byłaby tablica ?
– Dodane Wt paź 19, 2010 12:01 pm –
FUNCTION Fib_Rec (
N : IN Integer)
RETURN Integer IS
BEGIN
Steps_Rec := Steps_Rec + 1;
Steps_Level(N) := Steps_Level(N) + 1;
IF N = 0 THEN
RETURN 0;
ELSIF N = 1 THEN
RETURN 1;
ELSE
RETURN Fib_Rec(N - 2) + Fib_Rec(N - 1);
END IF;
END Fib_Rec;
gdzie Steps_Level jest wskaźnikiem do tablicy o rozmiarze adekwatnym do podanego N