Proszę o pomoc w zrozumieniu następujących przykładów, bo mam problem z ich częściowym zrozumieniem. Kilka rzeczy nie jest dla mnie jeszcze jasne i wierzę że z waszą pomocą to się zmieni.
Polecenie do zadania: Rozwiąż następujące równania rekurencyjne.
a)
\(\displaystyle{ T(0)=1}\) , \(\displaystyle{ T(n)=3T(n-1)+1}\)
\(\displaystyle{ T(n)=3T(n-1)+1=T(n)=3(3T(n-2)+1)+1=3^2 T(n-2)+2=3^2(3T(n-3)+1)+2=... 3^k T(n-k)+k ...=3^n T(0)+n= 3^n*1+n=3^n+n}\)
b)
\(\displaystyle{ T(1)=1}\) , \(\displaystyle{ T(n)=T( \frac{n}{2} )+n}\)
Niech \(\displaystyle{ 2^m=n}\)
\(\displaystyle{ T(2^m)=T(2^{m-1})+2^m}\)
Niech \(\displaystyle{ T(2^m)=S(m)}\)
\(\displaystyle{ S(m)=S(m-1)+2^m=S(m-2)+2^m+2^m=S(m-2)2*2^m=S(m-3)+2^m+2*2^m=S(m-3)+3*2^m=...S(m-k)+k*2^m=...S(0)+m*2^m=1+m*2^m=1+log _{2}m*n=1+m log _{2}n}\)
c)
\(\displaystyle{ T(n)=T (\sqrt{n})+1}\)
Niech \(\displaystyle{ 2^m=n}\)
\(\displaystyle{ T(2^m)=T (2^{ \frac{m}{2}} )+1}\)
Niech \(\displaystyle{ S(m)=T(2^m)}\)
\(\displaystyle{ S(m)=S( \frac{m}{2})+1}\)
Niech \(\displaystyle{ m=2 ^{p}}\)
\(\displaystyle{ S(2 ^{p})=S(2 ^{p-1})+1}\)
Niech \(\displaystyle{ V(p)=S(2^p)}\)
\(\displaystyle{ V(p)=V(p-1)+1=V(p-2)+2=V(p-3)+3=V(0)+p=p+a=log _{2}m+a=log_{2}(log_{2}n)+a}\)
Moje pytania
a)
Skąd się to wzieło \(\displaystyle{ 3^n T(0)+n= 3^n*1+n=3^n+n}\) ? Bo wcześniej za każde n powstawia się \(\displaystyle{ 3T(n-1)+1}\). Chociaż nie wiem po co. Te \(\displaystyle{ T(0)=1}\) ma na to podstawianie wpływ? Coś by zmieniło gdyby było np. \(\displaystyle{ T(1)=2}\), lub \(\displaystyle{ T(1)=1}\)?
b)
Nie wiem po co się podstawia \(\displaystyle{ 2^m=n}\), a potem \(\displaystyle{ T(2^m)=S(m)}\)?
To nie wiem skąd się wzięło \(\displaystyle{ S(0)+m*2^m=1+m*2^m=1+log _{2}m*n=1+m log _{2}n}\)
c) Tradycyjnie po co te podstawiania są S(m), V(p)? Samemu się to wymyśla? I nie wiem skąd to \(\displaystyle{ V(0)+p=p+a=log _{2}m+a=log_{2}(log_{2}n)+a}\) i te logarytmy kosmiczne?
I kulminacyjne pytanie. O co chodzi w tej całej rekurencji? Co tu wyznaczamy?
Rekurencja - problem ze zrozumieniem
-
- Użytkownik
- Posty: 4094
- Rejestracja: 10 lut 2008, o 15:31
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 12 razy
- Pomógł: 805 razy
Rekurencja - problem ze zrozumieniem
Nie sądzisz, że to raczej powinno być Twoje pierwsze pytanie? Jeśli rozwiązujesz zadanie, a nie wiesz, na czym ono polega, to powinieneś spodziewać się wątpliwości co do wielu rzeczy.Goenitz pisze:I kulminacyjne pytanie. O co chodzi w tej całej rekurencji? Co tu wyznaczamy?
Mamy wzory, w których wartość funkcji dla \(\displaystyle{ n}\) określona jest wartością funkcji w innym punkcie (np. dla \(\displaystyle{ n-1}\) w podpunkcie a). Chcąc obliczyć wartość funkcji dla \(\displaystyle{ n}\), musisz znać wartośc funkcji dla \(\displaystyle{ n-1}\), a żeby znać tę wartośc, musisz znać wartość funkcji dla \(\displaystyle{ n-2}\) itd. Trochę to kłopotliwe. zadanie polega na znalezieniu wzoru funkcji w postaci zwartej (który zależy tylko od \(\displaystyle{ n}\), czyli: masz wzór, podstawiasz \(\displaystyle{ n}\), masz wynik).
Znamy tylko wartość \(\displaystyle{ T(0)}\). Chcąc nie chcąc, żeby wyliczyć wartość \(\displaystyle{ T}\) dla danego \(\displaystyle{ n}\), musimy korzystać tak długo z zależności rekurencyjnej, aż dojdziemy do \(\displaystyle{ T(0)}\), np.:Goenitz pisze:Skąd się to wzieło \(\displaystyle{ 3^n T(0)+n= 3^n*1+n=3^n+n}\) ? Bo wcześniej za każde n powstawia się \(\displaystyle{ 3T(n-1)+1}\). Chociaż nie wiem po co. Te \(\displaystyle{ T(0)=1}\) ma na to podstawianie wpływ? Coś by zmieniło gdyby było np. \(\displaystyle{ T(1)=2}\), lub \(\displaystyle{ T(1)=1}\)?
\(\displaystyle{ T(3)=3T(2)+1=3(3T(1)+1)+1=3(3(3T(0)+1)+1)+1=3(3(3\cdot 1+1)+1)+1}\)
W tym rozwiązaniu zauważono po prostu, że jak k razy skorzystamy z zależności rekurencyjnej, to otrzymamy \(\displaystyle{ T(n)=3^kT(n-k)+k}\). Dalej zauważono, ze żeby dojść do \(\displaystyle{ T(0)}\) trzeba z tej zależności skorzystać \(\displaystyle{ n}\) razy, i sprawdzili, co wtedy otrzymujemy (a otrzymujemy \(\displaystyle{ 3^nT(n-n)+n}\). Stąd \(\displaystyle{ T(n)=3^nT(0)+n}\).
-
- Użytkownik
- Posty: 23
- Rejestracja: 13 paź 2010, o 16:44
- Płeć: Mężczyzna
- Lokalizacja: C:\Program Files
- Podziękował: 8 razy
Rekurencja - problem ze zrozumieniem
Wydaje mi się, że zarówno przykład a jak i b są źle obliczone.
a) \(\displaystyle{ T(n)=3T(n-1)+1=T(n)=3(3T(n-2)+1)+1=3^2 T(n-2)+2 ...}\)
Powinno być: \(\displaystyle{ T(n)=3(3T(n-2)+1)+1=3^2 T(n-2)+4}\) itd.
a nie \(\displaystyle{ T(n)=3(3T(n-2)+1)+1=3^2 T(n-2)+2}\) itd.
Jedynka nie jest tutaj mnożona przez 3.
b) \(\displaystyle{ S(m)=S(m-1)+2^m=S(m-2)+2^m+2^m=S(m-2)2*2^m ...}\)
Powinno być: \(\displaystyle{ S(m)=S(m-1)+2^m=S(m-2)+2^{m-1}+2^m}\) itd.
a nie \(\displaystyle{ S(m)=S(m-1)+2^m=S(m-2)+2^m+2^m}\) itd.
Tutaj z kolei argumentem jest \(\displaystyle{ m-1}\), więc powinno być \(\displaystyle{ 2^{m-1}}\) itd.
a) \(\displaystyle{ T(n)=3T(n-1)+1=T(n)=3(3T(n-2)+1)+1=3^2 T(n-2)+2 ...}\)
Powinno być: \(\displaystyle{ T(n)=3(3T(n-2)+1)+1=3^2 T(n-2)+4}\) itd.
a nie \(\displaystyle{ T(n)=3(3T(n-2)+1)+1=3^2 T(n-2)+2}\) itd.
Jedynka nie jest tutaj mnożona przez 3.
b) \(\displaystyle{ S(m)=S(m-1)+2^m=S(m-2)+2^m+2^m=S(m-2)2*2^m ...}\)
Powinno być: \(\displaystyle{ S(m)=S(m-1)+2^m=S(m-2)+2^{m-1}+2^m}\) itd.
a nie \(\displaystyle{ S(m)=S(m-1)+2^m=S(m-2)+2^m+2^m}\) itd.
Tutaj z kolei argumentem jest \(\displaystyle{ m-1}\), więc powinno być \(\displaystyle{ 2^{m-1}}\) itd.
-
- Użytkownik
- Posty: 32
- Rejestracja: 19 sie 2010, o 23:09
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 10 razy
Rekurencja - problem ze zrozumieniem
Crizz dzięki za informacje.
bigmen
Jak w przykładzie a) może być tam 4? 1+1=2.
A w przykładzie b skąd m-1 w potędze?
bigmen
Jak w przykładzie a) może być tam 4? 1+1=2.
A w przykładzie b skąd m-1 w potędze?