\(\displaystyle{ T(n)=\begin{cases} 1, \ n=1\\2T(n-1)+1, \ n \ge 2 \end{cases}}\)
\(\displaystyle{ n=2^k}\)
Rozwiązałam:
\(\displaystyle{ T(2^k)=2T(2^k-1)+1=}\)
\(\displaystyle{ = 2(2T(2^k-2)+1)+1=}\)
\(\displaystyle{ =2(2(2T(2^k-3)+1)+1)+1=}\)
\(\displaystyle{ =2^3T(2^k-3)+4+2+1=}\)
\(\displaystyle{ =2^kT(2^k-k)+2^{k-1}+2^{k-2}+...+2+1=}\)
No i utknęłam, nie wiem, co zrobić z \(\displaystyle{ T(2^k-k)}\)
Równanie rekurencyjne
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
Równanie rekurencyjne
A dlaczego zaczynasz od \(\displaystyle{ T(2^k)}\), a nie po prostu od \(\displaystyle{ T(k)}\)? Życie się uprości, bo dojdziesz do \(\displaystyle{ T(1)}\) po \(\displaystyle{ (k-1)}\) krokach.
-
- Użytkownik
- Posty: 141
- Rejestracja: 24 paź 2011, o 19:14
- Płeć: Kobieta
- Lokalizacja: Miasto
- Podziękował: 74 razy
Równanie rekurencyjne
Rzeczywiście, jeśli zaczniemy od T(k), to jest łatwiej obliczyć. Spróbowałam i mi wyszło:
\(\displaystyle{ =k \cdot T(k-k)+(k-1)+(k-2)+...+2+1=}\)
No i mamy \(\displaystyle{ T(k-k)=T(0)}\) Nic z tym nie możemy zrobić. Skoro mamy w równaniu \(\displaystyle{ T(1)=1}\).
\(\displaystyle{ =k \cdot T(k-k)+(k-1)+(k-2)+...+2+1=}\)
No i mamy \(\displaystyle{ T(k-k)=T(0)}\) Nic z tym nie możemy zrobić. Skoro mamy w równaniu \(\displaystyle{ T(1)=1}\).
- yorgin
- Użytkownik
- Posty: 12762
- Rejestracja: 14 paź 2006, o 12:09
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 17 razy
- Pomógł: 3440 razy
Równanie rekurencyjne
Ponieważ wykonałaś \(\displaystyle{ k}\) kroków, a powinnaś zatrzymać się na \(\displaystyle{ (k-1)}\) krokach. Lub ewentualnie przyjąć, że \(\displaystyle{ T(l)=0, l<1}\) (co czasem się robi).