Pytanie dotyczy rozpoznania celu algorytmu zapisanego jako lista kroków. W praktyce w zadaniach szkolnych i egzaminacyjnych taki zapis najczęściej odpowiada algorytmowi Euklidesa (w wersji z dzieleniem z resztą albo w wersji z odejmowaniem), czyli klasycznej procedurze do wyznaczania największego wspólnego podzielnika (NWD) liczb a i b.
Dlaczego poprawne jest "obliczenia największego wspólnego podzielnika liczb a i b."? NWD ma własność, że nie zmienia się przy zastąpieniu pary (a, b) parą (b, a mod b) lub przy wielokrotnym odejmowaniu mniejszej liczby od większej. Powtarzanie takich kroków aż do uzyskania reszty 0 (albo aż wartości się zrównają) prowadzi do wyniku, którym jest NWD.
- Odpowiedź "sprawdzenia, czy liczby a i b są liczbami pierwszymi." jest błędna, bo test pierwszości wymaga badania dzielników (np. do pierwiastka z liczby) lub metod probabilistycznych; nie jest to procedura nastawiona na wspólny dzielnik dwóch liczb.
- Odpowiedź "obliczenia najmniejszej wspólnej wielokrotności liczb a i b." jest myląca, bo NWW zwykle wyznacza się przez zależność z NWD (NWW = |a·b|/NWD) albo przez rozkład na czynniki pierwsze. Sama procedura typowa dla Euklidesa daje bezpośrednio NWD, a nie NWW.
- Odpowiedź "sprawdzenia, która z liczb a i b jest większa." jest zbyt prosta względem typowych algorytmów krokowych: do porównania wystarcza jeden warunek. Algorytm iteracyjny z wieloma krokami ma zwykle cel obliczeniowy (tu: NWD), a nie jednorazowe wskazanie większej liczby.
Wskazówka egzaminacyjna: gdy widzisz w krokach operacje typu "reszta z dzielenia", "zamień (a, b)", "powtarzaj aż b = 0" lub "odejmuj mniejszą od większej aż do równości", skojarz to z NWD i algorytmem Euklidesa.
