Strona główna » Po Godzinach » Zagadki » Ile lat mają synowie?
?
 

Ile lat mają synowie?

https://mattomatti.com/a00

Treść zadania

Zadanie jest z pozoru proste, ale na zwykłej kartce bardzo czasochłonne:

Matematyk ma trzech synów i musimy określić ich wiek znając iloczyn wieku wszystkich dzieci oraz ilorazu wieku starszego do młodszego.

Przykładowo jeśli iloczyn wszystkich dzieci będzie miał 189 i iloraz wyniesie 3 to jest tylko jedna prawidłowo kombinacja liczb i synowie mają wtedy: 3, 7 i 9 lat.

Specyfikacja wygląda tak:

Oczywiście dla bardziej ambitnych proponuje napisanie algorytmu, który sprawdzałby ile jest łącznie kombinacji spełniających kryteria zadania.

Rozwiązanie matematyczne

Przyjmijmy następujące zmienne:

Otrzymujemy, że , gdzie . Na tej podstawie można stwierdzić, że ostateczna funkcja jest postaci

Wiadomo, że . Szukam w takim razie takiego x, który jest dzielnikiem Najprostszym sposobem jest dokonać rozkładu . Wybieramy wszystkie zduplikowane liczby z rozkładu i w ten sposób uzyskujemy wiek najmłodszego. Wiek średniego możemy uzyskać na dwa sposoby: ze wzoru lub obliczając iloczyn liczb niezduplikowanych w rozkładzie

Rozwiązując tym sposobem przykład zadania otrzymujemy, że s = 189, i = 3. Wyznaczamy wzór funkcji: Rozkładamy 63 na czynniki pierwsze: {3, 3, 7}. Odczytujemy, że najmłodszy ma 3 lata, średni 7. Wiek najstarszego najprościej wyliczyć ze wzoru. W tym przypadku otrzymamy 9.

Rozwiązanie informatyczne

Zamieszczone rozwiązanie informatyczne stara się wyznaczyć wszystkie możliwe rozwiązania zadania. Używana jest tu metoda nieco lepsza od brute force. Program wykonuje wszystko dokładnie tak jak zostało wyjaśnione w rozwiązaniu matematycznym.

Kod źródłowy

Do wyszukiwania rozwiązań służy funkcja wyszukaj(), która przyjmuje dwa argumenty: t - iloczyn wieku wszystkich chłopców oraz n - iloraz wieku najstarszego do najmłodszego.

C++
C#
  1. long long wyszukaj(long long t, long long n) {
  2.   long long s = 0;
  3.   for (int i = 1; n*i*i <= t; i++) {
  4.     long long w = i*i*n;
  5.     if (t % w == 0) {
  6.       long long o = t / w, r = 1, k = 1;
  7.       bool error = false;
  8.       vector < long long > dane;
  9.       while (o != 1 && !error) {
  10.         r = rozklad(o);
  11.         if (k*r > n*i) {
  12.           if (k > i && k < i*n) {
  13.             dane.push_back(k);
  14.             k = 1;
  15.           } else {
  16.             error = true;
  17.           }
  18.         }
  19.         k *= r;
  20.         o /= r;
  21.       }

(2.) Początkowo łączna liczba kombinacji wynosi 0. (3.) Stwierdzamy, że wiek najmłodszego oznacza zmienna i. Wiadomo, że wtedy kwadrat zmiennej pomnożony przez n musi być mniejszy, równy t. Dla każdej liczby spełniającej ten warunek: (4.) wyliczamy wartość w (tj. iloczyn najmłodszego i najstarszego z braci). Jeśli (5.) iloczyn t jest podzielny przez w to: (6. - 21.) można przejść do wyszukania wszystkich możliwych rozkładów.

C++
C#
  1.       if (k > i && k < i*n && !error) {
  2.         dane.push_back(k);
  3.         k = 1;
  4.       } else {
  5.         error = true;
  6.       }
  7.       if (!error) {
  8.         cout << i << " ";
  9.         for (size_t i2 = 0; i2 < dane.size(); i2++)
  10.           cout << dane[i2] << " ";
  11.         cout << i*n << endl;
  12.         s++;
  13.       }
  14.     }
  15.   }
  16.   return s;
  17. }

(22.) Jeśli znaleziona wartość k mieści się w przedziale wieku braci to (23. - 24.) dodajemy kombinację. W przeciwnym razie (26.) zgłaszamy, że rozwiązanie jest niepoprawne. (28. - 34.) Jeśli rozwiązanie jest poprawne to wypisujemy oraz (33.) zwiększamy liczbę znalezionych rozwiązań. Na koniec (37.) zwracamy wartość zmiennej s.

Rozkład liczby

W celu znalezienia rozkładu liczby funkcja wyszukaj() korzysta z funkcji rozklad(), której działanie polega na znalezieniu najmniejszego dzielnika liczby t.

C++
C#
  1. long long rozklad(long long t) {
  2.   for (long long i = 2; i <= sqrt(t); i++) {
  3.     if (t%i == 0)
  4.       return i;
  5.   }
  6.   return t;
  7. }

Testowanie funkcji

W celu przetestowania działania napisanej funkcji wyszukaj() można skorzystać z poniższego kodu:

C++
C#
  1. int main() {
  2.   long long t = 1, n = 1;
  3.   cout << "Podaj iloczyn wieku:" << endl;
  4.   cin >> t;
  5.   cout << "Podaj iloraz wieku:" << endl;
  6.   cin >> n;
  7.   cout << "Kombinacji: " << wyszukaj(t, n) << endl;
  8.   system("PAUSE");
  9.   return 0;
  10. }