Spróbujmy napisać program, który policzy NWD (największy wspólny dzielnik) za pomocą algorytmu Euklidesa z odejmowaniem.
Aby to zrobić, zapoznajmy się z schematem działania. Dla przykładu policzymy NWD dla 16 i 56. Nasze zadanie będzie polegało na odejmowaniu od liczby większej liczbę mniejszą, tak długo, aż otrzymamy dokładnie te same wartości obu liczb.
- krok: niech a=16 i b=56;
- krok: 56 jest większe od 16, to b=b-a=56-16=40, bez zmian a=16;
- krok: 40 jest większe od 16, to b=b-a=40-16=24, bez zmian a=16,
- krok: 24 jest większe od 16, to b=b-a=24-16=8, bez zmian a=16,
- krok: 16 jest większe od 8, to a=a-b=16-8=8, bez zmian b=8,
- krok: a=b, czyli NWD(16,56)=a=b=8
Poniższe kroki możemy zapisać w postaci schematu blokowego:
Powyższy algorytm jest algorytmem iteracyjnym.
Czytaj dalej"Algorytm Euklidesa z odejmowaniem - schemat blokowy"