[Algorytmy] Algorytm rekurencyjny - wartość dla argumentu

fart411
Użytkownik
Użytkownik
Posty: 135
Rejestracja: 5 lut 2011, o 09:10
Płeć: Mężczyzna
Lokalizacja: xaswq
Podziękował: 60 razy

[Algorytmy] Algorytm rekurencyjny - wartość dla argumentu

Post autor: fart411 »

Rozważmy następujący algorytm rekurencyjny:

Kod: Zaznacz cały

ZROB-TO-SAM(n)
if n < 1
then return 0
else return ZROB-TO-SAM(n-2)*(n+1)
Jaką wartość zwróci instrukcja ZROB-TO-SAM(12)? Odpowiedź uzasadnić. Uwaga: wszystkie zmienne są liczbami całkowitymi.

Czy może mi ktoś w miarę dokładnie wytłumaczyć to zadanie, ew. podać link, w którym takie algorytmy rekurencyjny byłyby rozpisane?
Ostatnio zmieniony 21 maja 2013, o 14:34 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
arcan
Użytkownik
Użytkownik
Posty: 106
Rejestracja: 17 gru 2012, o 23:56
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 7 razy
Pomógł: 31 razy

[Algorytmy] Algorytm rekurencyjny - wartość dla argumentu

Post autor: arcan »

Sprobuje wytłumaczyć:
załóżmy że funkcja zrob-to-sam(n) to to samo co x(n).
\(\displaystyle{ x(0)=x(-1)=x(-2)=...=x(- \infty )=0}\)
bo jest wartunek, że dla n<1 wartość x(n) to 0.
Teraz rozpatrz sytuacje gdy \(\displaystyle{ n>=1}\)
Wtedy:
\(\displaystyle{ x(1)=x(-1) \cdot x(2)}\)
\(\displaystyle{ x(-1)=0}\), więc \(\displaystyle{ x(1)}\)też się równa zero, bo cokolwiek pomnożone razy 0 daje nam 0.
To samo będzie z \(\displaystyle{ x(2)=x(0) \cdot x(3)}\)
\(\displaystyle{ x(3)=x(1) \cdot x(4)}\)
tutaj widze zależność liniową i wszystkie wartości tej funkcji wynosza zero
więc \(\displaystyle{ x(12)=0.}\)
ODPOWIEDZ