szukanie zaawansowane
 [ Posty: 21 ]  Przejdź na stronę 1, 2  Następna strona
Autor Wiadomość
Kobieta Offline
PostNapisane: 9 gru 2016, o 00:24 
Użytkownik
Avatar użytkownika

Posty: 2784
Metodą iteracyjną rozwiązać:
T(n)= \begin{cases} 1, \ n=1 \\ 2T(\frac{n}{2})+n, \ n>1 \end{cases}

Zrobiłąm na razie tyle: T(n)=2T(\frac{n}{2})+n=n+2(2t(\frac{n}{4})+\frac{n}{2})=2n+4T(\frac{n}{8})+\frac{n}{4})=3n+8T(\frac{n}{8})=
= 3n+8(2T(\frac{n}{16})+\frac{n}{8})=
= 4n+16T(\frac{n}{16})=4n+16(2T(\frac{n}{32})+\frac{n}{16})=5n+32T(\frac{n}{32})
Góra
Mężczyzna Offline
PostNapisane: 9 gru 2016, o 00:25 
Użytkownik

Posty: 15237
Lokalizacja: Bydgoszcz
Wzorek jest do luftu. Potrafisz powiedzieć ile to jest T(3) ?
Góra
Mężczyzna Offline
PostNapisane: 9 gru 2016, o 00:27 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Ależ fajny wzorek:

Kliknij tu:

https://www.matematyka.pl/413512.htm
Góra
Kobieta Offline
PostNapisane: 9 gru 2016, o 00:44 
Użytkownik
Avatar użytkownika

Posty: 2784
a4karo, T(2)=2T(1)+2=4, \ T(4)=2T(2)+4=12

Dam radę policzyć tylko wyrazy, które mają indeksy w postaci potęgi dwójek.

Czy to znaczy, że ciąg jest źle zdefiniowany i nie ma takiego ciągu?
Góra
Mężczyzna Offline
PostNapisane: 9 gru 2016, o 00:46 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Pobaw się nim tak jak ja i go rozciąg sobie
Góra
Kobieta Offline
PostNapisane: 9 gru 2016, o 00:49 
Użytkownik
Avatar użytkownika

Posty: 2784
Dobrze, pobawię się ;)

Ale czy można stwierdzić, że nie da się przeprowadzić tutaj sensownej iteracji, która doprowadzi do rozwiązania?
Góra
Mężczyzna Offline
PostNapisane: 9 gru 2016, o 00:54 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
tak jak to zrobiłem w linku z przymrużeniem oka...


Najpierw pobaw się z ciągiem:

x_{1}=1

x_{n+1}=2x_{n}+2^n

Znajdź wzór jawny


Wyszło mi:

x_{n}=2^{n-1}n


Teraz: robię takie kwiprokwo:

przypuszczam , że:

x_{n+1}=T(2^n)=2^n(n+1)

2^n=x

n= \frac{\ln x}{\ln 2}

Dalej sobie brnę w to bagno i obstaję przy tym, że:

potem z powrotem podstawiam:

x:=n

T(n)=n \frac{\ln n}{\ln 2}+n

a teraz:

T(2n)=2n \frac{\ln 2n}{\ln 2}+2n

A teraz sprawdzam, czy:

(1)T(2n)=2T(n)+2n - czyli wyjściowe nasze

I o dziwo dla:

T(n)=n \frac{\ln n}{\ln 2}+n

Wzór (1) jest spełniony i działa (sprawdzałem osobiście)

W ten nietypowy sposób poszerzyliśmy wzór z dziedziny potęg dwójki na wszystkie eny a nawet ixy...

czyli ostatecznie:

T(n)=n \frac{\ln n}{\ln 2}+n , n \in N

lub:

T(x)=x \frac{\ln x}{\ln 2}+x , x \in R , x>0

Teraz możesz liczyć nie tylko dla potęg dwójki ale i dla wszystkich liczb dodatnich...

Troszkę więcej roboty niż w tym wzorku z linku ponieważ musiałem tworzyć funkcje tworzące
dla wyznaczenia wzoru jawnego...

Tak do końca nie musicie brać tego na poważnie...
Góra
Mężczyzna Offline
PostNapisane: 26 gru 2016, o 02:15 
Użytkownik
Avatar użytkownika

Posty: 6622
Lokalizacja: 53°02'N 18°35'E
Analizę sortowania przez scalanie przeprowadzasz ?
Góra
Mężczyzna Offline
PostNapisane: 26 gru 2016, o 16:30 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Cytuj:
Analizę sortowania przez scalanie przeprowadzasz ?


A teraz proszę przetłumacz mi to na nasze, ja człowiek bardzo prosto myślący nie dla mnie takie indygacje...
Góra
Mężczyzna Offline
PostNapisane: 26 gru 2016, o 18:48 
Użytkownik
Avatar użytkownika

Posty: 6622
Lokalizacja: 53°02'N 18°35'E
Sortowanie przez scalanie ma takie równanie rekurencyjne
Średni przypadek sortowania szybkiego też ma podobną rekurencję
Góra
Mężczyzna Offline
PostNapisane: 26 gru 2016, o 19:02 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
O i widzisz pierwsze słyszę coś takiego.

to równanie Poszukującej było określone na dziedzinie będącej potęgami dwójki ja po prostu na beszczelnego dziedzinę rozszerzyłem na wszystkie...
Teraz na ten temat poczytałem to masz rację , ja osobiście nie znałem tego algorytmu , ja po prostu tu i tam dokonałem radosnej twórczości.
Góra
Mężczyzna Offline
PostNapisane: 26 gru 2016, o 23:29 
Użytkownik
Avatar użytkownika

Posty: 6622
Lokalizacja: 53°02'N 18°35'E
Nie pisałeś nigdy sortowań w jakimś języku programowania jak Pascal czy C
Dla tablic Cormen podaje łatwe do przepisania pseudokody
(Algorithms unlocked, Introduction to Algorithms)

Sortowanie przez scalanie jest dobrym wyborem dla list albo plików
natomiast dla tablic tylko wtedy gdy zależy nam na szybkim algorytmie zachowującym
oryginalną kolejność powtarzających się kluczy
Jeżeli nie zależy nam na kolejności powtarzających się kluczy to dla tablic lepszym wyborem będzie sortowanie stogowe ze względu na to że działa w miejscu a standardowa wersja sortowania przez scalanie wymaga dodatkowej pamięci
I am not crazy about quicksort because it may slow down
Góra
Mężczyzna Offline
PostNapisane: 27 gru 2016, o 05:17 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
No jasne pisałem za pomocą sortowania bąbelkowego w C++
Góra
Mężczyzna Offline
PostNapisane: 27 gru 2016, o 14:12 
Użytkownik
Avatar użytkownika

Posty: 6622
Lokalizacja: 53°02'N 18°35'E
arek1357, co powiesz na takie równanie rekurencyjne

T\left( n\right) =\begin{cases} 1 \qquad n=1\\ T\left(  \frac{n}{k} \right)+T\left(n- \frac{n}{k} \right) + n \qquad n>1 \end{cases}

k\in\left(1,n\right\rangle
Góra
Mężczyzna Offline
PostNapisane: 27 gru 2016, o 14:17 
Użytkownik
Avatar użytkownika

Posty: 3273
Lokalizacja: blisko
Hmmm ciekawe ale chyba tam w drugim brakuje znaku =
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 21 ]  Przejdź na stronę 1, 2  Następna strona


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rozwiązanie rekurencji metodą czynnika sumacyjnego  el ZAX  2
 Rozwiąż rekurencję - zadanie 7  Lucjan  3
 metoda znajdowania dróg  pumbosza  0
 Metoda podwójnego przeliczania  contact  0
 Cztery zadanka - rekurencje (4/4)  swpr  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl