Zadania – PK (2022)

Piotr Potiopa (zestaw nr 2)


Zadanie

Opracuj algorytm wyszukiwania oparty na Fibonacci 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 0000), 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/Fibonacci_search_technique