szukanie zaawansowane
 [ Posty: 5 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 7 lip 2017, o 11:22 
Użytkownik

Posty: 6
Lokalizacja: Polska
Witam. W podręczniku "Algorytmy i struktury danych" znalazłem następujący problem rekurencyjny:
\begin{cases} T(n)=T(\lfloor  \frac{n}{4} \rfloor)+T(\lfloor  \frac{3n}{4} \rfloor)+n \\ T(1)=1 \end{cases}.
W podręczniku tym problemy te rozwiązywano przez podstawienie n=2^{k} więc i to zadanie powinno być tak rozwiązywalne. Proszę o pomoc.
Góra
Mężczyzna Offline
PostNapisane: 7 lip 2017, o 20:59 
Gość Specjalny

Posty: 5793
Lokalizacja: Toruń
W tym przypadku sugerowałbym popatrzeć na przypadek n=4^k.
Góra
Mężczyzna Offline
PostNapisane: 7 lip 2017, o 21:07 
Użytkownik

Posty: 6
Lokalizacja: Polska
To rozumiem, ale jak uwzględnić mnożenie przez 3 w drugim wyrazie sumy?
Góra
Mężczyzna Offline
PostNapisane: 8 lip 2017, o 07:16 
Gość Specjalny

Posty: 5793
Lokalizacja: Toruń
Masz
T(4^k) = T(4^{k-1}) + T(3 \cdot 4^{k-1}) + 4^k
Góra
Mężczyzna Offline
PostNapisane: 8 lip 2017, o 08:52 
Użytkownik

Posty: 6
Lokalizacja: Polska
Po rozpisaniu tego otrzymuje:
T(4^{k})= \sum_{i=0}^{k}  {k \choose i} T(3^{i})  +k4^{k} i tu mam problem z wyrażeniami z potęgami 3.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 5 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 równanie rekurencyjne - zadanie 2  matteuszek  4
 Równanie rekurencyjne - zadanie 3  skony  1
 Równanie rekurencyjne - zadanie 4  King James  15
 Równanie rekurencyjne - zadanie 6  pokoj  1
 rownanie rekurencyjne  coldrain  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl