ASD Ćwiczenia 10

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

Podaj przykład ciągu operacji MakeSet, Find i Union w implementacji listowej bez łączenia z wyważaniem, których łączny koszt to .

Rozwiązanie


Zadanie 2

Udowodnij, że w implementacji listowej z heurystyką łączenia z wyważaniem koszt wykonania operacji MakeSet, Find i Union, spośród których to MakeSet, wynosi .

Rozwiązanie


Zadanie 3

Udowodnij, że w implementacji drzewiastej z łączeniem według wysokości wysokość drzewa zawierającego węzłów jest mniejsza bądź równa .

Rozwiązanie


Zadanie 4

Napisz pseudokod operacji MakeSet, Union i Find w implementacji drzewiastej z łączeniem według rangi i kompresją ścieżki.

Rozwiązanie


Zadanie 5

Udowodnij Lemat 1.

Rozwiązanie


Zadanie 6

Udowodnij, że jeśli w implementacji drzewiastej z łączeniem według rangi i kompresją ścieżki najpierw wykonujemy wszystkie operacje Union, a dopiero potem wszystkie operacje Find, to zamortyzowany koszt operacji Find jest stały.

Rozwiązanie


Zadanie 7

Algorytm Kruskala znajdowania minimalnego drzewa rozpinającego w grafie z wagami na krawędziach działa następująco: krawędzie są przeglądane w kolejności od najlżejszej do najcięższej. Aktualnie rozważaną krawędź dodajemy do budowanego drzewa, o ile tylko nie powoduje to powstania cyklu. Jak efektywnie zaimplementować ten algorytm? Jaki jest jego czas działania?

Rozwiązanie


Zadanie 8

Napisz program generujący labirynt następująca metodą: Na początku każda komnata jest otoczona ścianami. W każdym kroku wybieramy losowo ścianę i usuwamy ją, jeśli komnaty po jej obu stronach nie są jeszcze połączone żadną drogą.

Rozwiązanie


Zadanie 9

Plansza do gry w Hex ma kształt rombu zbudowanego z sześciokątnych pól. Dwaj gracze wykonują na przemian ruchy polegające na dostawieniu pionka na jedno pole. Celem pierwszego gracza jest zbudowanie z białych pionków drogi łączącej lewy dolny brzeg planszy z prawym górnym, natomiast celem drugiego jest zbudowanie z czarnych pionków drogi łączącej lewy górny brzeg planszy z prawym dolnym.

HexGame.gif

Zaprojektuj algorytm, który po każdym ruchu sprawdza, czy nastąpiła wygrana któregoś z graczy.

Rozwiązanie