- Zmodyfikuj algorytm min_max2 tak, by zwracał pozycję elementu
najmniejszego i pozycję elementu największego, a nie ich wartości. Sformułuj
niezmiennik pętli i uzasadnij, poprawność tego algorytmu ze względu na warunek
końcowy ("i £n)(e[min]
£e[i]
£ e[max]) w dowolnej strukturze danych
wyposażonej w liniowy porządek £.
- Napisz algorytm wyszukiwania minimum i maksimum wykorzystujący
następującą metodę:
- Krok1: dla każdej pary kolejnych elementów ciągu ustawiam element mniejszy na pozycji nieparzystej,
a element większy na pozycji parzystej.
- Krok 2: szukam elementu najmniejszego na pozycjach nieparzystych.
- Krok 3: szukam elementu największego na pozycjach parzystych.
(a) Uzasadnij poprawność i zbadaj koszt tego algorytmu.
(b) Zaproponuj implementację tego algorytmu, zakładając, że elementy ciągu są umieszczone w tablicy.
Uwaga. Nie należy zakładać, że liczba elementów jest parzysta.
- Zrealizuj algorytm z poprzedniego zadania na listach jedno lub
dwukierunkowych.
- Zmodyfikuj algorytm min_max5 tak by działał poprawnie, również dla n
nieparzystych.
- Zmodyfikuj algorytm turniej tak by działał poprawnie dla dowolnych ciągów
(bez założenia, że n jest potęgą dwójki). Przeanalizuj działanie tego
algorytmu dla ciągu 2,1,4,3,6,5,8,7,9,10.
- Przeanalizuj działanie algorytmu Partition dla ciągu
15,16,18,12,5,3,6,7,10. Ile dokładnie porównań zostanie wykonanych? Jaki jest
koszt algorytmu mierzony liczbą wykonanych operacji swap?
- Zaproponuj iteracyjną wersję algorytmu Hoare znajdywanie k-tego co do
wielkości elementu ciągu.
- Zaproponuj algorytm tłumaczenia liczby naturalnej zapisanej w systemie
dziesiętnym na dowolny inny system. Podaj specyfikację i uzasadnij poprawność
podanego algorytmu.