Strona główna » Algorytmy » Artykuły » Ciężka Kulka

Ciężka Kulka

Zadanie

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ę?

Odpowiedź

Minimalnie potrzeba 9 porównań.

Wyjaśnienie

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.

Uogólniony przypadek

Zadanie

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ę?

Wyjaśnienie

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.

Implementacja

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

Funkcja wymaganePorownania() znajduje minimalną liczba porównań, która gwarantuje znalezienie cięższej kulki.

  1. int wymaganePorownania(int n) {
  2.   int p = 2;
  3.   int ile = 0;
  4.   while (n > 1) {
  5.     while (n % p == 0) {
  6.       ile += p / 2;
  7.       n /= p;
  8.     }
  9.     p++;
  10.   }
  11.   return ile;
  12. }

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.

Testowanie funkcji

W celu przetestowania działania funkcji można skorzystać z poniższej funkcji main(), która wczytuje ile kulek znajduje się w pudełku:

  1. int main() {
  2.   int n;
  3.   cin >> n;
  4.   cout << "Sukces zawsze po: " << wymaganePorownania(n);
  5.   cout << endl;
  6.   system("pause");
  7.   return 0;
  8. }