W pudełku znajduje 19682 lekkich kulek oraz 1 ciężka. Kulki z wyglądu są identyczne. Ile minimalnie należy wykonać porównań, aby mieć pewność, że znajdzie się ciężką kulkę?
Zauważmy, że 19683 = 39. Algorytm poszukiwania ciężkiej kulki polega na tym, że dzielimy kulki w pudełku na 3 grupy po tyle samo kulek. Następnie porównujemy dwie dowolne grupy. W ten sposób, albo porównywane grupki będą równej wagi, więc kulka znajduje się w trzeciej grupce, albo któraś z grup będzie cięższa, więc w niej znajduje się cięższa kulka. Po dokonaniu 9 podziału i porównania będzie można wskazać, która kulka jest cięższa.
W pudełku znajduje n - 1 lekkich kulek oraz 1 ciężka. Zakładamy, że n > 1 i kulki z wyglądu są identyczne. Ile minimalnie należy wykonać porównań, aby mieć pewność, że znajdzie się ciężką kulkę?
Załóżmy, że w poprzednim przypadku kulki były w każdym kolejnym kroku podzielona na 3 grupy. W przypadku, gdyby n było potęgą 2 to w każdym kroku dzieliłoby się na dwie grupki kulek. Warto zauważyć, że jest tutaj dokonywany rozkład liczby n na czynniki pierwsze. Pozostaje teraz jedynie znaleźć odpowiedź ile minimalnie kroków potrzeba? Zakładając, że w każdym kroku uda się znaleźć cięższą grupkę w pierwszym porównaniu to odpowiedź znajdzie się po k krokach, gdzie k to liczba czynników pierwszych w rozkładzie n.
Jednak taki przypadek jest mało prawdopodobny. Z tego powodu zastanówmy się nad liczbą porównań gwarantującą znalezienie szukanej kulki. Dla n = 2 kulek wystarczy dokładnie jedno porównanie jak również dla n = 3. Przypadku dla n = 4 nie rozpatrujemy, ponieważ nie jest to liczba pierwsza i rozkład w tym przypadku polegałby na rozkład na dwa kroki i dzieleniu pozostałych kulek na dwie grupki. Sytuacja zmienia się dla n = 5: w tym przypadku należy wykonać dwa porównania, aby mieć gwarancję znalezienia cięższej grupki.
Podsumowując, aby znaleźć liczba potrzebnych porównań dla liczby pierwszej p to należy wykonać (p - 1) / 2 porównań. Przypadek dla p = 2 wyszczególniamy i wtedy potrzeba zaledwie jedno porównanie.
Algorytm rozwiązujący przedstawiony problem powinien najpierw znaleźć rozkład podanej liczby n na czynniki pierwszej, a następnie zsumować liczba potrzebnych porównań.
Funkcja wymaganePorownania() znajduje minimalną liczba porównań, która gwarantuje znalezienie cięższej kulki.
Na początku deklarowane są dwie zmienne: (2.) p - aktualna liczba pierwsza oraz (3.) ile - określa ile porównań zostało wykonanych. (4.) Dopóki liczba n jest podzielna przez jakąkolwiek liczbę: (5.) sprawdź czy aktualne p dzieli n. Jeśli tak to: (6.) dolicz ile prób zostało wykonanych oraz (7.) usuń ten czynnik z n. Na koniec każdej iteracji należy (9.) zwiększyć p.
W celu przetestowania działania funkcji można skorzystać z poniższej funkcji main(), która wczytuje ile kulek znajduje się w pudełku: