[Algorytmy] Dziel i zwyciężaj - pseudokod

kirk1994
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 23 lut 2015, o 23:14
Płeć: Mężczyzna
Lokalizacja: Polska

[Algorytmy] Dziel i zwyciężaj - pseudokod

Post autor: kirk1994 »

Załózmy, ze dany jest posortowany ciag róznych liczb całkowitych w tablicy
T[1, . . . , n]. Podaj algorytm (w pseudokodzie), działajacy w czasie \(\displaystyle{ O \left( \lg n \right)}\) i oparty na metodzie
„dziel i zwyciezaj”, który sprawdza, czy istnieje indeks równy elementowi, czyli taki
indeks \(\displaystyle{ 1 < i < n}\), ze T[i] = i. Algorytm powinien zaczynac sie nastepujaco:

Kod: Zaznacz cały

Indeks(T[1, . . . , n])
1 . . .
Przykłady: Dla tablicy T = [−7, 0, 2, 4, 7] odpowiedz brzmi TAK, gdyz T[4] = 4. Dla tablicy
[2, 3, 4, 5] odpowiedz brzmi NIE.
Uzasadnij, dlaczego czas jego działania jest \(\displaystyle{ O \left( \lg n \right)}\).

Nie mam pojęcia jak się do tego zabrać, ktoś potrafi pomóc ?
Ostatnio zmieniony 24 lut 2015, o 07:31 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Gouranga
Użytkownik
Użytkownik
Posty: 1565
Rejestracja: 16 maja 2013, o 17:56
Płeć: Mężczyzna
Lokalizacja: Trójmiasto
Podziękował: 11 razy
Pomógł: 243 razy

[Algorytmy] Dziel i zwyciężaj - pseudokod

Post autor: Gouranga »

Ponieważ liczby są posortowane sprawdź środkowy element (przy parzystych trzeba obrać założenie np. pierwszy z dwóch środkowych)
Dla tej tablicy:
T = [-7,0,2,4,7]
sprawdź T[3]
widzimy, że liczba jest mniejsza niż indeks bo T[3] = 2
W tym przypadku liczby mogą "dogonić" indeksy tylko w prawo od tego miejsca oczywiście tylko przy założeniu, że liczby się nie powtarzają.
Sprawdźmy teraz środkowy element z prawej połowy tablicy. Prawą połową jest T' = [4,7] o indeksach 4,5
Przyjęliśmy, że przy parzystej sprawdzamy ten z lewej więc T[4]=4 odpowiedź TAK

Dla tablicy:
T = [2,3,4,5]
Sprawdzamy środkowy: T[2] = 3
Liczba jest większa od indeksu,sprawdzamy lewą stronę T[1] = 2
Znów liczba większa niż indeks, sprawdzamy lewą stronę. Lewa strona jest pusta, odpowiedź NIE

Uzasadnienie dlaczego \(\displaystyle{ \log n}\):
Stosujemy metodę przeszukiwania Binary Search, która opiera się o drzewa binarne a wysokość drzewa binarnego o \(\displaystyle{ n}\) węzłach jest równa \(\displaystyle{ \log n}\)
Ostatnio zmieniony 24 lut 2015, o 07:31 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
ODPOWIEDZ