Inne, zadanie nr 4734

Autor	Zadanie / Rozwiązanie
makaron1 postów: 60	2016-06-20 14:50:27 Do 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+21+2^2)+3^2+2(0+21+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