Zadania – PK (2022)
Piotr Potiopa
(zestaw nr 8)
Zadanie
Opracuj algorytm wyszukiwania oparty na Ternary Search, który znajdzie wskazany
element w zbiorze liczb. Program ma działać w następujący sposób:
1.
program przy uruchomieniu z parametrem „-random”
powinien wygenerować n losowych
unikalnych liczb (liczby od 0 do 1 000 000), które będą zapisane w pliku random.txt.
(liczba
n podawana jest na wejściu programu
w zakresie od 0 do 100 000)
2.
Po uruchomieniu programu bez parametru „-random”
program powinien zaczytać plik random.txt,
gdzie zapisane są liczby losowe i zapytać o liczbę którą ma wyszukać.
3.
Następnie przeszukać zbiór wczytanych z pliku
liczb i wypisać na ekran pozycję liczby (indeks kolejności) którą szuka.
4.
Program powinien dodatkowo pokazywać czas
wykonania operacji wyszukiwania (po wczytaniu danych, czyli sama operacja
wyszukiwania). Proszę też o zapisanie czasu wyszukiwania dla liczby n = 100 000.
Uwaga: jeśli algorytm wymaga
posortowanych liczb trzeba to obsłużyć już na etapie generowania liczb do pliku
random.txt.
Przydatne
linki:
https://en.wikipedia.org/wiki/Ternary_search