szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 24 lut 2016, o 10:50 
Użytkownik
Avatar użytkownika

Posty: 19
Lokalizacja: Bytom
Mam problem z takim typem zadań, byłabym wdzięczna gdyby ktoś mnie nakierował na sposób rozwiązania :)

Pokaż, że jeśli funkcja T: \NN  \rightarrow \NN  \cup \left\{ 0 \right\} spełnia warunki:
T(1) = 0, T(n) = T( \lceil \frac{n}{2} \rceil ) + 1 dla n \ge 2 to:
T(n) = \lceil {\log_2 (n)} \rceil
Góra
Mężczyzna Offline
PostNapisane: 24 lut 2016, o 11:38 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
W drugim kroku indukcyjnym załóżmy, że wzór jest prawdziwy dla wszystkich liczb mniejszych niż n i pokażmy jego prawdziwość dla n (oczywiście n>1).

Jeśli n=2k dla pewnego k całkowitego, to z uwagi na k<n wiemy, że wzór jest prawdziwy dla k, mamy zatem:
T(n)=T(2k) = T(k)+1 = \lceil {\log_2k} \rceil + \log_22=\\ = \lceil {\log_2k}  + \log_22\rceil=\lceil \log_2(2k)\rceil =\lceil \log_2n\rceil
Jeśli natomiast n=2k-1 dla pewnego k całkowitego, to z uwagi na k<n wiemy, że wzór jest prawdziwy dla k, mamy zatem:
T(n)=T(2k-1) = T(k)+1 = \ldots =\lceil \log_2 (2k)\rceil = \lceil \log_2 (2k-1)\rceil =\lceil \log_2n\rceil
(przedostatnia równość wynika z tego, że 2^l<2k-1\le 2^{l+1} wtedy i tylko wtedy gdy 2^l<2k\le 2^{l+1})

Q.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 indukcja matematyczna - pytanie  ZIELONY  2
 Coś (chyba :P) z indukcja związane  jackass  4
 indukcja  Anonymous  1
 Podzielność przez 14 - indukcja  John Til  6
 Indukcja Matematyczna [Zadanie]  Caspy  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl