UWB Informatyka - Nieoficjalne Forum Studentów

zad 7 zestaw 1 domino
liczy się jako ciąg fibanaciego

fib(0)=0
fib(1)=1

żeby uzyskać n-ty wyraz to fib(n) = f(n-1) + f(n-2) dla n=>2        [czyli juz mamy utworzony wzór rekurencyjny ]

czyli np dla fib(2) to bedzie f(2-1)+f(2-2)= f(1)+f(0) = 1+0 = 1

żeby uzyskać na 5 wyraz ciągu to albo liczymy po kolei ( 2,3,4 i w końcu 5 ) albo liczymy od razy fib(5) korzystając ze wzorku czyli:

f(5)= f(5-1) + f(5-2) = f(4) + f(3) = jako że nie mamy 4 i 3 rozbijamy go dalej ze wzoru f(4-1) + f(4-2) + f(3-1) + f(3-2) = f(3)+f(2)+f(2)+f(1)=  i tak samo dalej f(3-1) + f(3-2) + 2*[f(2-1)+f(2-2)] + f(1) = f(2) +f(1) +2*[f(1)+f(0)] +f(1)=  f(2-1)+f(2-2)+f(1) +2*[f(1)+f(0)] +f(1)= f(1)+f(0)+f(1) +2*[f(1)+f(0)] +f(1)= podstawienie jest już łatwe 1+0+1+2*(1+0)+1= 5

fib(5)=5
                                                                                                                         

                                                                                                                             []

Ostatnio edytowany przez Darrjus (2009-09-23 11:22:13)