Inne, zadanie nr 4734
ostatnie wiadomo艣ci | regulamin | latex
| Autor | Zadanie / Rozwi膮zanie |
makaron1 post贸w: 60 |  2016-06-20 14:50:27Do obliczania wartosci funkcji$ f: N_{0} \rightarrow N_{0}, f_{n}= \left\{\begin{matrix} n ,n<2 \\ f(n-2) + 2f(n-1) + n^{2} , n\ge2 \end{matrix}\right. $ dysponujemy funkcja rekurencyjna oparta wprost na definicji. Ile razy bedzie ona wo艂ana do obliczenia f(2) podczas wywo艂ania do obliczenia f(5)? Mo偶e kto艣 wyt艂umaczyc jak co艣 takiego si臋 robi krok po kroku? |
janusz78 post贸w: 820 | 2016-06-20 16:21:34 a) $ f(2)= f_{2}= f(0) + 2f(1)+2^2 = 0 + 2\cdot 1+ 4 = 6$ - trzy razy odwo艂ywali艣my si臋 do wzoru funkcji - pierwszy raz do obliczenia $ f(2)$, drugi raz do obliczenia $ f(0)$, trzeci raz do obliczenia $ f(1).$ b) Podobnie. |
makaron1 post贸w: 60 | 2016-06-20 16:31:13 Rozumiem, 偶e te wywo艂ania to ilo艣膰 oblicze艅 we wzorze ? Bo s膮 3 obliczenia jakby? w b) wynik to 36 i r贸wnie偶 3 razy si臋 odwo艂ujemy, tak ? |
makaron1 post贸w: 60 | 2016-06-20 16:57:44 W odpowiedziach mam tylko napisane, 偶e odwo艂ujemy si臋 3 razy. |
tumor post贸w: 8070 | 2016-06-20 18:23:08 $ f(5)=f(3)+2f(4)+5^2=$ do tego miejsca 2 razy (poza pierwszym wywo艂aniem f(5)) $f(1)+2f(2)+3^2+2(f(2)+2f(3)+4^2)+5^2=$ tu jeszcze 4 razy $1+2(f(0)+2f(1)+2^2)+3^2+2(f(0)+2f(1)+2^2+2(f(1)+2f(2)+3^2)+4^2)+5^2=$ jeszcze 6 razy $1+2(0+2*1+2^2)+3^2+2(0+2*1+2^2+2(1+2(f(0)+2f(1)+2^2)+3^2)+4^2)+5^2=$ jeszcze dwa razy $1+2*6+9+2(6+2(1+12+9)+16)+25=22+2(22+44)+25$ |
makaron1 post贸w: 60 | 2016-06-20 18:38:01 Kompletnie ju偶 nie wiem jak to dzia艂膮, w odpowiedziach mam napisane 偶e zosta艂o 3 razy wywo艂ane a przy tym jakie艣 drzewo kt贸re mi to udowadnia niby. |
tumor post贸w: 8070 | 2016-06-20 18:56:46 Aha, chodzi o czytanie polecenia ze zrozumieniem. Nie pytano ile razy b臋dzie ona wywo艂ana (bardzo du偶o), tylko ile razy b臋dzie wywo艂ana z argumentem 2. Rzeczywi艣cie wywo艂anie f(2) w czasie oblicze艅 zwi膮zanych z f(5) jest trzykrotne. (w mojej rozpisce te偶 wida膰, gdzie) |
makaron1 post贸w: 60 | 2016-06-20 19:01:35 No widz臋 w艂asnie teraz, dzi臋ki wielkie za odpowiedz! |
makaron1 post贸w: 60 | 2016-06-20 19:07:47 Mam jeszcze jedno pytanie, czy na to d艂ugie dzia艂anie jest jaki艣 og贸lny wz贸r ? Opr贸cz tego, 偶e 1 wers to ze wzoru z polecenia |
tumor post贸w: 8070 | 2016-06-20 19:28:07 Wz贸r rekurencyjny, kt贸ry masz w poleceniu, m贸wi, 偶e dla n=0 lub n=1 znamy warto艣膰 od razu (to po prostu n), natomiast je艣li potrzebujemy obliczy膰 f(n) dla wi臋kszego n, to musimy obliczy膰 $f(n-2)+2f(n-1)+n^2$ Za ka偶dym razem, gdy si臋 pojawia艂o f(1) lub f(0) to w nast臋pnym kroku pisa艂em po prostu 1 lub 0. Gdy jednak pojawia艂o si臋 f(2) lub f(3) lub f(4), to rozpisywa艂em zgodnie ze wzorem. Na tym polega rekurencja liczenie czego艣 dla wi臋kszego argumentu wymaga wywo艂ania dla argument贸w mniejszych. ---- Ten przyk艂ad pokazuje pewne wady rekurencji. Mamy tu du偶o wywo艂a艅 funkcji (pomy艣l, jak obci膮偶a艂oby pami臋膰 wywo艂anie f(100), a co dopiero f(500) czy wi臋ksze liczby, nie m贸wi膮c o f(1000000), a ponadto pewne fragmenty obliczane s膮 wielokrotnie. Dlatego spytano o ilo艣膰 powt贸rze艅 obliczenia f(2). Dla argumentu 5 ju偶 trzykrotnie musieli艣my liczy膰 f(2), za ka偶dym razem te same dodawania i mno偶enia, to dalsza strata zasob贸w. B臋dziesz jeszcze mo偶e mie膰 co艣 o programowaniu dynamicznym, to techniki przy艣pieszaj膮ce dzia艂anie program贸w przez pami臋tanie wynik贸w ju偶 uzyskanych. Zalet膮 rekurencji jest za to prostota programowania. Banalny kod, prosty przepis, kt贸ry szybki komputer mniej wi臋cej szybko zastosuje (ale dla cz艂owieka to droga m臋cz膮ca, wiele wiele ma艂ych oblicze艅). |
| strony: 1 2 | |
Prawo do pisania przys艂uguje tylko zalogowanym u偶ytkownikom. Zaloguj si臋 lub zarejestruj