równania rekurencyjne

Nie znajdujac podpowiedzi ani na google ani na zadnej ze stron 4programmers, chcialbym poprosic Wam o pomoc przy równaniach rekurencyjnych. Nasz wykladowca ma niesamowita zdolnosc aby nawet najlatwiejsze rzeczy tak zakrecic ze nic sie z tego nie rozumie a co dopiero to.. Kto jest na silach, prosze niech pisze.Ja nie mam pojecia jak sie za to zabrac;

<font size="3">Rozwiaz (w sensie asympotycznym) nastepujace rownanie rekurencyjne

T(n) = T([n/2]) + n

[n/2] - oznacza czesc calkowita z dzielenia n przez 2</span>

prosze o pomoc, musze opracowac schemat blokowy i zrealizowac zagadnienie w pascalu, tak nakazal wykładowca :(</b>

przy zalozeniu ze T(1) = 1

to ma byc równanie rekurencyjne, ktore nie sprawdza pokolei liczb az dojdzie do n tylko te liczby ktore trzeba, kiedyds na matematyce mielismy to tlumaczone mniej wiecej tak, ze:

T(1)=1;
T(n)=2*[n/2] //tu tez chodzi o czesc calkowita

program pyta jakie n podac

wpisalismy ze 73

n=73

T(73)=2T[73/2]=2T(36)
T(36)=2T[32/2]=2T(18)
T(18)=2T[18/2]=2T(9)
T(9)=2T[9/2]=2T(4)
T(4)=2T[4/2]=2T(2)
T(2)=2T[2/2]=2T(1)

znalezlismy wartosc poczatkowa

T(1)=1 wiec sie cofamy kolejno..

T(1)=1
T(2)=2
T(4)=4
T(9)=8
T(18)=16
T(36)=32
T(73)=64

program wyswietla wynik: 64

dla mnie to jest kosmicznie trudne zadanie bo nie wiem jak zrobic aby nie bralo wszystkich pokolei wlasnie tylko aby sie cofalo

da sie to jakos zrealizowac??

:(

No to na tym samym przykładzie będzie to:

n=73

T(73)=2*T[73/2]+73=2*T(36)+73
T(36)=2*T[36/2]+32=2*T(18)+36
T(18)=2*T[18/2]+18=2*T(9)+18
T(9)=2*T[9/2]+9=2*T(4)+9
T(4)=2*T[4/2]+4=2*T(2)+4
T(2)=2*T[2/2]+2=2*T(1)+2

T(1)=1
T(2)=4
T(4)=12
T(9)=33
T(18)=84
T(36)=204
T(73)=481

Po rozwinęciu tego wzoru otrzymujemy takiego cudaka:

T(73)=2*T(36)+73
T(73)=2*(2*T(18)+36)+73
T(73)=2*(2*(2*T(9)+18)+36)+73
T(73)=2*(2*(2*(2*T(4)+9)+18)+36)+73
T(73)=2*(2*(2*(2*(2*T(2)+4)+9)+18)+36)+73
T(73)=2*(2*(2*(2*(2*(2*T(1)+2)+4)+9)+18)+36)+73
>T(73)=2*(2*(2*(2*(2*(2*1+2)+4)+9)+18)+36)+73<

Jak widzisz za T(n) wstawiamy jej wzór, co pozwala nam na obliczenie wartości.

Sama funkcja liczaca T jest powiedzmy banalna:

1 - określamy warunek stopu n=1 to zwraca 1, dla porządku dla n<1 powinno zwracać najlepiej -1 jako błąd wykonania, bo parametr nie pasuje.
2 - określamy wejście w rekurencję, czyli wzór T=2*T[n/2]+n.
3 - piszemy funkcję :)

Edytka:

No dobra, masz tę funkcyjkę:

function T(n:integer):integer;
begin
 if n<1 then {warunek stopu z bledem}
  begin
   T:=-1;
   exit;
  end;
 if n=1 then {warunek stopu - najnizszy poziom rekurencji}
  begin
   T:=1;
   exit;
  end;
 T:=2*T(n shr 1)+n; {jesli nie stanal powyzej to schodzi o poziom nizej w rekurencji (rozwija wzor, tak jak to pokazalem powyzej)}
end;

Schemat blokowy już zrób sobie sam :>

Edytka2:

n shr 1 odpowiada n div 2 tyle że się szybciej wykona.
Takie zboczenie :|

Czy DIV czy SHR, sprawdź, bo to nawyk przestarzały, ważniejsze używać liczb bez znaku.

jeżeli T(1)=1 to mnie wychodzi, że T(73) = 143
T(73)=T(36)+73
T(36)=T(18)+36
T(18)=T(9)+18
T(9)=T(4)+9
T(4)=T(2)+4
T(2)=T(1)+2=1+3=3
T(4)=3+4=7
T(9)=7+9=16
T(18)=16+18=34
T(36)=34+36=70
T(73)=70+73=143

http://www.research.att.com/~njas/sequences/A005187

A faktycznie, tam było T(n)=T[n/2]+n a nie T(n)=2*T[n/2]+n...

No to wystarczy wyrzucić 2*

Mój błąd.

nie radze sobie z reszta zadan... jak porownuje to co maja inni na pierwszym roku studiow a co mamy my na programowaniu, jest roznica i to spora :( poziom 3 roku..

jestem w stanie zaplacic za pomoc lub zaoferowac hosting na swoim serwerze

http://www.zlecenia.przez.net/oferta,6440,programowanie-zadania-nawet-4zl-za-jedno

kto pomoze studentowi?

t:= n;
repeat
    n:= n div 2;
    t:= t + n
until n = 0;

jesli ktos bedzie zainteresowany pomoca oferuje darmowa reklame gwarantowane tysiac unikalbych wejsc dziennie na stronie lub roczny hosting http://www.cheap-web-host.net/ lub skrypty PHP http://www.lolekserwer.com [od powstania strony dawna nie aktualizowane] lub kaske

n->oo T(n)=2n