Strona główna » Algorytmy » Teoria Liczb » Trójki Pitagorejskie
 

Trójki Pitagorejskie

https://mattomatti.com/a82

Definicja

Trójki Pitagorejskie są to takie trzy liczby całkowite, dodatnie a, b, c, które spełniają warunek . Trójka takich liczb jest też czasem nazywana liczbami Pitagorejskimi.

Przykład

Najpopularniejszą trójką Pitagorejską jest trójka (3, 4, 5). Innym przykładem trójki jest (7, 24, 25).

Implementacja

Czy poprawna trójka

Funkcja czyPoprawnaTrojka() ma za zadanie określić czy podana trójka liczb jest prawidłową trójką Pitagorejską. Najprostszą jej implementacją będzie porównanie lewej i prawej strony równania:

  1. bool czyPitagorejskie(int a, int b, int c) {
  2.   return (a * a + b * b == c * c);
  3. }

Szukaj trójki

Jednak zdecydowanie częściej nie padnie pytanie czy trójka w podanej kolejności jest trójką Pitagorejską. Lepszy pomysłem jest napisanie funkcji, która dla dowolnej trójki liczb stwierdzi czy istnieje takie ich ustawienie, że spełnią warunek. W tym przypadku warto zauważyć, że liczba po prawej stronie musi być liczbą największą z podanej trójki.

  1. bool czyIstniejeTrojka(int a, int b, int c) {
  2.   if (c > b && c > a)
  3.     return czyPitagorejskie(a, b, c);
  4.   return czyIstniejeTrojka(b, c, a);
  5. }

(1.) Nagłówek funkcji jest identyczny jak w przypadku funkcji czyPitagorejskie(). (2.) Jeśli liczba c jest większa od a i b to (3.) wystarczy podać wynik funkcji czyPitagorejskie() z argumentami w tej samej kolejności. Jednak jeśli nie to (4.) zmień kolejność liczb w trójce przesuwają liczby w lewo. W ten sposób przy kolejnym wywołaniu liczbą c jest kolejna wartość, która może okazać się tą największą. Przy takim rozwiązaniu funkcja zostanie wywołana maksymalnie trzy razy.

Znajdź trzecią liczbę

Kolejną przydatną funkcją może okazać się algorytm, który będzie wyszukiwał trzecią liczbę na podstawie znajomości dwóch pozostałych liczb. Tutaj zadanie polega na tym, że należy wyliczyć sumę podanych liczb, a następnie sprawdzić czy suma jest kwadratem jakieś liczby całkowitej. Drugą możliwością jest, że jedna z podanych liczb jest sumą kwadratów drugiej znanej liczby oraz liczby szukanej. W przypadku niepowodzenia znalezienia liczby zwróconą wartości powinno być 0.

  1. int znajdzTrojke(int a1, int a2) {
  2.   double c = sqrt( a1 * a1 + a2 * a2 );
  3.   if (c == int(c))
  4.     return c;
  5.   double b = sqrt(abs(a1 * a1 - a2 * a2));
  6.   if (b == int(b))
  7.     return b;
  8.   return 0;
  9. }

(1.) Na podstawie dwóch liczb należy zwrócić trzecią liczbę, która pozwoli tak ustawić podane liczby, aby były trójką Pitagorejską. Jednak jeśli nie ma takiej szansy to powinno zostać zwrócone 0. (2.) Wylicz pierwiastek suma dwóch podanych argumentów. (3.) Jeśli nie maja części dziesiętnej to (4.) zwróć wyliczoną wartość. Jednak jeśli nie to (4.) przypuść, że jeden z podanych argumentów stoi po prawej stronie równania. Wylicz pierwiastek wartości absolutnej różnicy dwóch argumentów czyli np. wartość a lub b w równaniu. Ponownie (5.) jeśli nie ma części dziesiętnej to (6.) zwracana jest wyliczona wartość. (7.) Jeśli w obu przypadkach nie została zwrócona żadna wartość to do podanych liczby nie da rady dołączyć trzeciej, aby powstała trójka Pitagorejska. Zgodnie z założeniami zwracane jest 0.

Liczby pierwotne

Warto zauważyć, że jeśli liczby (a, b, c) są trójką Pitagorejską to liczby (da, db, dc) też będzie trójką Pitagorejską. W celu sprawdzenia czy przekazana trójka jest trójką pierwotną należy sprawdzić czy największym wspólnym dzielnikiem liczb a, b i c jest 1.

  1. bool czyPierwotna(int a, int b, int c) {
  2.   return nwd(nwd(a, b), c) == 1;
  3. }

Testowanie funkcji

W celu wypisania wszystkich trójek Pitagorejskich, których pierwsza liczba jest z zakresu [3, 10] wystarczy taka funkcja main():

  1. int main () {
  2.   for (int i = 3; i < 10; i++) {
  3.     for (int j = i; j < 1000; j++) {
  4.       int c = znajdzTrojke(i, j);
  5.       if (i <= j && j <= c && c != 0) {
  6.         cout << i << ", " << j << ", " << c << endl;
  7.         continue;
  8.       }
  9.     }
  10.   }
  12.   system("pause");
  13.   return 0;
  14. }

Zadania

Zadanie 1

Napisz iteracyjną wersją funkcji czyIstniejeTrojka(), która dla podanych argumentów a, b, c, która sprawdzi czy istnieje takie ich podstawienie do równania Pitagorasa, że będzie można je uznać za trójkę Pitagorejską. Funkcja powinna zwrócić prawdę dla (3, 4, 5), (3, 5, 4) oraz dla każdej pozostałej permutacji.

Zadanie 2

Napisz funkcję wypiszTrojkiPitagorejskie(), która wypisze na ekran wszystkie trójki w identyczny sposób jak funkcja main() testująca działanie funkcji. Tym razem należy dodatkowo dopisać koło trójki PIERWOTNA jeśli faktycznie taką właściwość posiada.

Przykładowo dla przekazanego argumentu 10 program powinien wypisać:

  1. 3, 4, 5 PIERWOTNA
  2. 5, 12, 13 PIERWOTNA
  3. 6, 8, 10
  4. 7, 24, 25 PIERWOTNA
  5. 8, 15, 17 PIERWOTNA
  6. 9, 12, 15
  7. 9, 40, 41 PIERWOTNA