logowanie

matematyka » forum » studia » zadanie

Inne, zadanie nr 4734

ostatnie wiadomości  |  regulamin  |  latex

AutorZadanie / 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: 8085
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: 8085
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: 8085
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





© 2017 Mariusz Śliwiński      o serwisie | kontakt online: 52 drukuj