Dzisiaj będziecie tworzyć program, który oblicza NWD – największy wspólny dzielnik dwóch liczb.

Największy wspólny dzielnik to największa liczba, która dzieli obie podane liczby bez reszty.

Przykład:
Dla liczb 12 i 18 największym wspólnym dzielnikiem jest 6.

Będziecie programować algorytm Euklidesa – jeden z najstarszych i najbardziej znanych algorytmów matematycznych. Zrealizujecie go w Baltie 8K na dwa sposoby i porównacie ich działanie.

Podczas tej lekcji:

• użyjecie zmiennych,
• zastosujecie instrukcję warunkową IF / ELSE,
• stworzycie pętlę,
• porównacie dwa różne sposoby rozwiązania tego samego problemu.

Algorytm Euklidesa – wersja z odejmowaniem

W tej wersji będziecie:

• porównywać dwie liczby,
• odejmować mniejszą od większej,
• powtarzać czynność tak długo, aż liczby będą równe.

Gdy liczby staną się równe — ta wspólna wartość jest NWD.

Lista kroków

1. Zacznij program.
2. Wprowadź pierwszą liczbę i zapisz ją w zmiennej a.
3. Wprowadź drugą liczbę i zapisz ją w zmiennej b.
4. Dopóki a ≠ b, wykonuj kroki 5–6.
5. Jeżeli a > b, to przypisz:
     a ← a − b
6. W przeciwnym razie przypisz:
     b ← b − a
7. Gdy liczby będą równe, wyprowadź wynik:
     NWD = a
8. Zakończ program.

Ta wersja jest bardzo prosta i dobrze pokazuje działanie instrukcji warunkowej.

Algorytm Euklidesa – wersja z dzieleniem

W tej wersji zamiast wielokrotnego odejmowania użyjecie reszty z dzielenia.

Ta metoda działa szybciej, szczególnie przy dużych liczbach.

Lista kroków

1. Zacznij program.
2. Wprowadź pierwszą liczbę i zapisz ją w zmiennej a.
3. Wprowadź drugą liczbę i zapisz ją w zmiennej b.
4. Dopóki b ≠ 0, wykonuj kroki 5–7.
5. Zapisz wartość b do zmiennej pomocniczej, np. dzielnik.
6. Przypisz zmiennej b resztę z dzielenia a przez b.
7. Przypisz zmiennej a wartość zmiennej dzielnik.
8. Gdy b = 0, wyprowadź wynik:
     NWD = a
9. Zakończ program.

Podsumowanie

Ten sam problem można rozwiązać na dwa różne sposoby.

Wersja z odejmowaniem:

• jest łatwiejsza do zrozumienia,
• może wykonywać więcej powtórzeń.

Wersja z dzieleniem:

• działa szybciej,
• wykonuje mniej kroków,
• jest bardziej efektywna dla dużych liczb.

Na koniec zastanówcie się:

Czy prostszy algorytm zawsze oznacza lepszy?

Która wersja była prostsza do zaprogramowania?

Która działała szybciej?