Zadania do lekcji 7¶

Zadanie 701

Narysuj wykres czasu wykonywania programu “Wieże Hanoi” od liczby dysków \(n\in[1,15]\). Skorzystaj z wiadomości z lekcji 5 oraz dodatku 3. Zauważ, jak zmienia się czas przy zwiększeniu liczby dysków o \(1\). Spróbuj oszacować, jaki będzie koszt (złożoność) algorytmu.

Zadanie 702

Oryginalnie sformułowany problem “Wież Hanoi” zawierał legendę mówiącą, że w pewnej tybetańskiej świątyni jest wieża składająca się z \(64\) złotych dysków, które są przekładane przez mnichów. Kiedy uda się im przenieść całą wieżę na docelowy słup, nastąpi koniec świata. Zakładając, że mnisi przekładają jeden krążek na sekundę oszacuj, ile czasu nam pozostało. Uwaga: nie próbuj uruchamiać programu dla \(n=64\)! (nie chcemy, żeby koniec świata nastąpił już teraz, prawda?)

Zadanie 703

Częstym problemem jest znalezienie najmniejszego (największego) elementu zbioru. Stosując podejście “dziel i zwyciężaj” napisz algorytm min-max, który jednocześnie będzie znajdował najmniejszy i największy element zbioru (ich różnica to tzw. rozpiętość zbioru).

Podpowiedź: jeśli zbiór ma dwa elementy, to mniejszy jest min a większy max.

Zadanie 704

Zaimplementuj algorytm min-max z poprzedniego zadania. Spróbuj oszacować jego złożoność algorytmiczną.