Algorytm Euklidesa - wersja rozszerzona

Wstęp

• Algorytm Euklidesa służy do znajdowania największego wspólnego dzielnika (NWD) dwóch liczb naturalnych w sposób optymalny.
• Wersja rozszerzona algorytmu pozwala rozwiązać równania diofantyczne: (x \cdot a + y \cdot b = \text{NWD}(a, b)) dla całkowitych (x) i (y).

Podstawy algorytmu Euklidesa

• Rekurencyjna definicja NWD:
  • NWD(a, b) = NWD(b, a mod b), jeśli b ≠ 0
  • NWD(a, b) = a, jeśli b = 0
• Przykład obliczania NWD dla 23 i 13:
  • 23 % 13 = 10
  • 13 % 10 = 3
  • 10 % 3 = 1
  • 3 % 1 = 0
  • NWD(23, 13) = 1

Algorytm Euklidesa - wersja rozszerzona

• Rozwiązuje równania diofantyczne postaci (x \cdot a + y \cdot b = \text{NWD}(a, b)).
• Używany w problemach takich jak problem przelewania wody.
  • Przykład z wiaderkami: 23 litry i 13 litrów, uzyskanie 1 litra jest możliwe, bo 1 jest NWD(23, 13).

Rozwiązywanie równania diofantycznego

• Proces:
  • Zapisz reszty z dzielenia poszczególnych kroków algorytmu Euklidesa.
  • Wyrażaj reszty w postacich równania z 23 i 13.
  • Przekształcaj krok po kroku zaczynając od ostatnich równań.
  • Wyprowadź docelowe wartości (x) i (y).

Implementacja algorytmu

• Algorytm można zaimplementować rekurencyjnie lub jako funkcję procedurę.
• Wyjścia z rekurencji zwracają pary (x, y) do obliczeń w poprzednich krokach.

Przykład implementacji

• Rekurencyjna funkcja obliczająca NWD i zwracająca wartości (x, y).
• Funkcja nie zwraca bezpośrednio wartości, ale używa zmiennych globalnych do przechowywania wyników.

Podsumowanie

• Algorytm Euklidesa w wersji rozszerzonej jest użyteczny w rozwiązywaniu równań diofantycznych i problemów z rzeczywistego świata.
• Algorytm ten, mimo że trudny do pełnego zrozumienia, jest cennym narzędziem matematycznym.

Dodatkowe informacje

• Algorytm pojawił się na maturze z matematyki w roku 2015 w arkuszu rozszerzonym.
• Znajomość działania algorytmu jest ważniejsza niż jego pełne zrozumienie teoretyczne.