Zadanie z trójkami pitagorejskimi #PytaniaRekrutacyjne – Special Pythagorean triplet

W związku z odświeżeniem wiedzy na temat algorytmów oraz nauką nowego języka (Rust), przedstawiam dochodzenie do rozwiązania następującego problemu:

Oryginalna treść ze strony https://projecteuler.net/:

O co chodzi w zadaniu?

Jeśli nie jesteś przyzwyczajony do tego typu zadanek, na samym początku, treść może być dla Ciebie dezorientująca. Jak to jednak jest matematyka w informatyce? Jak zazwyczaj odpowiedź brzmi to zależy. Jednak w tym konkretnym przypadku wszystkie równania mamy na tacy. Zacznijmy od przypomnienia czym był trójkąt pitagorejski:

Z definicji to taki trójkąt, którego boki są wyrażone liczbami naturalnymi, a obliczenie przeciwprostokątnej (tej określonej jako znak zapytania) wyraża się wzorem:

a^2 + b^2 = c^2 – ten wzór jest podany w zadaniu

Następnie mamy jeszcze jedną własność te 3 liczby określające boki trójkąta to tak zwane trójki pitagorejskie. Mają one następującą własność:

a < b < c

W naszym konkretnym przypadku a =2, b = 4, żeby wyliczyć przeciwprostokątną należy użyć wzoru:3^2 + 4^2 = 25, następnie pierwiastek z 25 da 5. Wstawiamy nasze liczby i sprawdzamy czy nasz trójkąt jest pitagorejski:

2 < 4 < 5 – tak, dzięki temu sprawdzeniu mamy pewność, że mamy do czynienia z trójkątem pitagorejskim

Samo zadanie polega na znalezieniu takiej trójki liczb: a + b + c, których suma da 1000. Zanim przejdziesz do następnej części, spróbuj wziąć kartkę i długopis i rozpisz sobie algorytm, który znajdzie taką trójkę.

Pierwsze rozwiązanie

Moja porada dotyczącą rozmów rekrutacyjnych podczas rozwiązywania zadań jest następująca: jeśli ciężko Ci znaleźć wyrafinowany sposób na rozwiązanie jakiegoś zadania, po prostu tego nie rób! Często rozwiązanie na początku jest bardzo prymitywne (tak jak będzie to w tym przypadku), ale zadziała i o to chodzi podczas rekrutacji, ale również w pracy. Bazując na podstawowym rozwiązaniu można rozmyślać na temat optymalizacji. Ja ciągle mam z tym problem, ale staram się oduczać takich zachowań bo wiem, że do niczego nie prowadzą.

Zacznijmy od najprostszego algorytmu do rozwiązania tego problemu:

Co tu się zadziało?
  1. Iterujemy po wszystkich możliwościach od 1 do n(1000) dla każdej zmiennej a,b oraz c.
  2. Sprawdzamy warunek czy suma potęg a oraz b jest potęgą zmiennej c.
  3. Dodatkowo sprawdzamy czy suma wszystkim 3 zmiennych a,b,c da nam liczbę n (1000).
  4. Jeśli tak dodajemy naszą trojką do hashsetu (po prostu jakiegoś kontenera).
  5. Następnie szukamy dalej. przechodząc przez 1000^3 iteracji. Nasz algorytm ma złożoność O(n^3) – ogólnie rzecz biorąc kiepsko 🙁

Optymalizacja

Zmniejszenie Ilości iteracji

Zachęcam Cię do zaimplementowania własnej wersji algorytmu w języku, który znasz. Teraz skupmy się na tym co można by usprawnić. Skorzystajmy z własności:  a < b < c oraz, że a + b + c = 1000

Musimy przemyśleć jaka może być maksymalna wartość liczby a, jeśli a wynosiłoby 500 to b = 501, a c = 502, wtedy nie zostanie spełnione równanie a + b + c = 1000

Chwila główkowania, prowadzi nas do liczby a = 332, czyli tak na prawdę 1000/3 – 1. Co w takim razie ze zmienną b? Może ją też można by zoptymalizować?, no jasne! Szukamy maksymalnego  b, więc dając np. b = 700, c musiałoby wynosić minimum 701, 700 + 701 = 1401, niestety przekracza to już liczbę 1000 nie wspominając o zmiennej a!

W takim razie b musi być maksymalnie równe 499, czyli 1000/2 -1.

Dodatkowo warto zauważyć, że jeśli a < b to możemy jako początek iteracji dla pętli b zainicjalizować jako b = a + 1, znowu będziemy do przodu o kilka iteracji.

Zredukowanie wewnętrznej pętli

Możemy dokonać jeszcze jednej optymalizacji, otóż zamiast sprawdzać za każdym razem czy suma wszystkich 3 zmiennych jest równa poszukiwanej liczbie (u nas 1000), można wyliczyć zmienną c z następującego wzoru:

a + b + c = n (1000), po przekształceniach uzyskamy:

c = n – a – b – jedno proste przekształcenie pozwala nam na zredukowanie całej pętli!

Jak teraz będzie wyglądał nasz kod?

Jest już dużo lepiej, ale czy można by coś jeszcze zrobić?

Rozwiązanie bardziej „analityczne”

Na stronie https://www.xarg.org/puzzle/project-euler/problem-9/ znalazłem ciekawe podejście do tego problemu, uzależniając się tylko od jednej pętli! Chciałbym tu rozpisać krok po kroku jakich przekształceń należy użyć aby tego dokonać. Przyznam szczerze, że sam miałem sporo problemów, w dojściu do niektórych wzorów – cóż trzeba trochę bardziej polubić matematykę 😉

Zaczynamy, naszym celem będzie takie przekształcenie wzoru, aby obliczyć zmienne a oraz b tylko iterując po zmiennej c. Wiem, może to brzmieć skomplikowanie, ale spokojnie pamiętam te lekcje matematyki, które bardziej przypominały zajęcia ze szkoły magii i czarodziejstwa…Postaram Ci się wytłumaczyć krok po kroku co się dzieje.

Na początku przekształćmy wzór:

a + b + c = n na postać a + b = n - c

w naszym arsenale mamy jeszcze wzór: a^2 + b^2 = c^2 – dodajemy do niego po obu stronach wartość 2ab Zapytasz po co? Będziemy mogli skorzystać ze wzoru skróconego mnożenia!

Wzór po dodaniu będzie wyglądał następująco:

a^2 + 2ab + b^2 = c^2 + 2ab, „zwijamy” (ze wzoru skróconego mnożenia) lewą stronę równania do postaci:

(a+b)^2=c^2+2ab

po niewielkim przekształceniu 2ab = (n-c)^2-c^2

skąd wzięło się n – c ? Zobacz kilka wzorów wyżej a + b = n – c, więc bez przeszkód możemy podstawić te wartości.

Dobra czas na odjęcie tych 2 wzorów od siebie (zabawne jest to, że odejmujemy, żeby stworzyć całkowicie nowy wzór, który przyda nam się w obliczeniach ;))
a^2 + b^2 = c^2 oraz 2ab = (n-c)^2-c^2

Po odjęciu wzór będzie wyglądał następująco:

a^2 -2ab +b^2=c^2-(n-c)^2+c^2
(a-b)^2 = c^2-n^2 + 2nc - c^2 + c^2
(a-b)^2=c^2-n^2+2nc

Do czego doszliśmy, przekształcając nasz wzór? Udało nam się poznać liczbę a oraz b uzależniając je tylko od zmiennej n (już znamy) oraz c po której iterujemy!

Jak znaleźć liczbę b bazując jedynie na zmiennych n oraz c?

Wiedząc jak obliczyć (a-b)^2 zajmijmy się obliczeniem zmiennej b, wyjdźmy od wzoru: a+b=n-c
Odejmijmy od obu stron b (pamiętaj, możesz dodać lub odjąć po obu stronach równania co tylko chcesz, to zawsze sprowadzi się do 0 ;))
Wychodzi a+b-b=n-c-b, teraz przenieśmy składnik a-b na prawą stronę. Wychodzi b=n-c-b-a+b

Co teraz? Gdzie zastosować naszą znaną informację odnośnie: (a-b)^2 Możemy zauważyć, że -a+b to po przekształceniu -(a-b), tak ujęliśmy to w nawias.

W jaki sposób z (a-b)^2 zrobić (a-b)? Wystarczy to wyrażenie spierwiastkować w efekcie dostaniemy 2 możliwości gdy (a-b) > 0 oraz (a-b) < 0 Przypominając sobie własność a<b<c wiemy, że będą nast interesować jedynie ujemne liczby (bo a musi być mniejsze od b), więc ten minus możemy wyciągnąć przed nawias. W efekcie wzór na obliczenie b będzie następujący:
b=(n-c+(a-b))/2

Czas na składnik a

Jak teraz wyliczyć a? To już całkiem proste wystarczy delikatnie przekształcić wzór: a+b+c=n do postaci: a=n-c-b i to wszystko 🙂

Sprawdzenie czy liczba jest całkowita

Żeby sprawdzić czy będziemy w stanie wyliczyć a oraz b wystarczy sprawdzić czy pierwiastek z a-b jest liczbą całkowitą, w tym przypadku mnożymy razy dwa to wyrażenie i sprawdzamy czy da liczbę podniesioną do potęgi ((a-b)^2) jeśli tak to znaczy, że liczba jest całkowita i możemy znaleźć a oraz b.

Po co nam ta cała matematyka?

I w sumie możesz myśleć, że jak zwykle przekształciliśmy parę wzorów, coś tam skróciliśmy i jak to w szkole nic z tego nie wynika, jednak zobacz jak zmieni się nasz kod:

Wisienka na torcie

Żeby jeszcze bardziej zmniejszyć ilość iteracji możemy podumać nad samą liczbą c, z własności trójkąta wynika, że a+b>c więc maksymalnie liczba c może wynosić c<n/2Z drugiej strony czy jest jakaś minimalna liczba dla której, jest sens liczenia składników a oraz b? Jasne! Jest na to kilka sposobów, można wziąć za przykład minimalne możliwe n = 12 i sprawdzić, że w tym przypadku trójka pitagorejska będzie następująca: a = 3, b = 4, c = 5, po krótkiej analizie wychodzi, że minimalne wynosi c=n/3+1.
Finalny kod wygląda następująco:

 

Podsumowanie

Udało się! Jeśli przebrnąłeś przez wszystkie obliczenia to przyjmij moje szczere gratulacje! Dopiero po kilku latach od zakończenia edukacji zaczynam dostrzegać praktyczny sens niektórych zagadnień matematycznych. W tym przypadku zmniejszyliśmy cza wykonania algorytmu algorytm o cały stopień złożoności czyniąc go liniowym, wyobraź sobie, że jest to algorytm, który wykorzystuje codziennie kilka tysięcy osób, może w jakiś programach do modelowania? Co z algorytmami używanymi przez miliony użytkowników dziennie? Nie wierz w to, że w IT wszystko jest już wymyślone – to tak dynamiczna branża, że ciągle powstają nowe podejścia do rozwiązywania codziennych problemów.

To czego się nauczyłem podczas tego zadania to kilka metod podejścia do problemu. Zestawiam je dla Ciebie w kilku punktach:

  • Kiedy dochodziłem do niektórych rozważań, warto było wykorzystać konkretne liczby i sprawdzać co się z nimi dzieje krok po kroku.
  • Pamiętaj, że możesz dodać cokolwiek do równania pod warunkiem, że dodasz to samo po obu stronach
  • Cała zabawa polega na uzależnieniu naszego wyniku od jak najmniejszej liczby danych
  • Warto zastanowić się nad zastosowaniem analitycznego podejścia do problemu od zwykłej metody typu „brute-force”, ponieważ możemy zyskać dużo wydajniejszy algorytm (świetnym przykładem może być liczba fibbonaciego, na którą istnieje wzór zamiast liczenia rekurencyjnego)

 

ZOSTAW ODPOWIEDŹ

Please enter your comment!
Please enter your name here

Loading Facebook Comments ...