NWD (największy wspólny dzielnik) dwóch liczb dodatnich to największa liczba całkowita, która dzieli je obie bez reszty. Kluczowe w zadaniach z uzupełnianiem schematu algorytmu jest rozpoznanie poprawnej iteracji i poprawnego warunku zakończenia.
Najczęściej w takich pytaniach chodzi o algorytm Euklidesa w jednym z dwóch równoważnych wariantów:
- Wariant z resztą (modulo): powtarzaj, dopóki druga liczba nie będzie równa 0; w kroku podstawienia ustaw (a, b) = (b, a mod b). Wynik to ostatnia niezerowa wartość.
- Wariant z odejmowaniem: powtarzaj, dopóki a ≠ b; odejmuj mniejszą liczbę od większej. Gdy a = b, ta wartość jest NWD.
Dlaczego wskazany wariant jest poprawny? Ponieważ zawiera elementy konieczne dla algorytmu NWD:
- pętlę, która gwarantuje wielokrotne wykonywanie kroków aż do osiągnięcia warunku stopu,
- warunek stopu zgodny z teorią (0 w wariancie modulo albo równość w wariancie odejmowania),
- aktualizację zmiennych, która zachowuje NWD (inwariant: NWD(a, b) nie zmienia się po przejściu do (b, a mod b) ani po odjęciu mniejszej od większej).
Typowe błędne uzupełnienia schematu (co reprezentują odpowiedzi niepoprawne) to m.in.:
- zły warunek zakończenia (np. przerwanie za wcześnie, zanim jedna z wartości osiągnie 0 albo zanim wartości się zrównają),
- nieprawidłowe podstawienie (np. nadpisanie a przed obliczeniem reszty, co psuje kolejny krok),
- operacja, która nie zachowuje NWD (np. przypadkowe dzielenie, zamiana na średnią, błędne odejmowanie bez rozróżnienia większej i mniejszej liczby).
W przygotowaniu do egzaminu warto umieć rozpoznać, że poprawny schemat NWD zawsze sprowadza problem do coraz mniejszych liczb, a jednocześnie nie "gubi" wspólnego dzielnika. To pozwala szybko ocenić, czy wstawione bloki tworzą logiczną, skończoną procedurę.
