Ile lat mają synowie?

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:

• Dane: otrzymujemy dwie liczby całkowite - iloczyn wieku wszystkich synów oraz iloraz wieku starszego do młodszego
• Wyjście: program ma wypisać dowolną prawidłową konfiguracje, która spełnia kryteria zadania

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:

• x - wiek najmłodszego syna
• y - wiek średniego syna
• z - wiek najstarszego syna
• i - iloraz wieku najstarszego syna do najmłodszego
• s - iloczyn wieków wszystkich synów

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.

1. static long wyszukaj(long t, long n) {
2.   long s = 0;
3.   for (int i = 1; n * i * i <= t; i++) {
4.     long w = i * i * n;
5.     if (t % w == 0) {
6.       long o = t / w, r = 1, k = 1;
7.       bool error = false;
8.       List<long> dane = new List<long>();
9.       while (o != 1 && !error) {
10.         r = rozklad(o);
11.         if (k * r > n * i) {
12.           if (k > i && k < i * n) {
13.             dane.Add(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.

22.       if (k > i && k < i * n && !error) {
23.         dane.Add(k);
24.         k = 1;
25.       } else {
26.         error = true;
27.       }
28.       if (!error) {
29.         Console.Write("{0} ", i);
30.         for (int i2 = 0; i2 < dane.Count; i2++)
31.           Console.Write("{0} ", dane[i2]);
32.         Console.WriteLine("{0}", i * n);
33.         s++;
34.       }
35.     }
36.   }
37.   return s;
38. }

(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.

1. static long rozklad(long t) {
2.   for (long i = 2; i <= Math.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:

1. static void Main(string[] args) {
2.   long t = 1, n = 1;
3.   Console.WriteLine("Podaj iloczyn wieku:");
4.   t = Convert.ToInt64(Console.ReadLine());
5.   Console.WriteLine("Podaj iloraz wieku:");
6.   n = Convert.ToInt64(Console.ReadLine());
7.   Console.WriteLine("Kombinacji: {0}", wyszukaj(t, n));
8.   Console.ReadKey();
9. }

• Kod źródłowy Rozwiązanie Informatyczne