Algorytm Euklidesa z odejmowaniem - schemat blokowy

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.

1. krok: niech a=16 i b=56;
2. krok: 56 jest większe od 16, to b=b-a=56-16=40, bez zmian a=16;
3. krok: 40 jest większe od 16, to b=b-a=40-16=24, bez zmian a=16,
4. krok: 24 jest większe od 16, to b=b-a=24-16=8, bez zmian a=16,
5. krok: 16 jest większe od 8, to a=a-b=16-8=8, bez zmian b=8,
6. 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.

W pierwszej kolejności zgodnie z schematem pobierzmy zmienne całkowite:

a = int(input("Podaj liczbę a: "))
b = int(input("Podaj liczbę b: "))

Kolejnym krokiem będzie określenie warunku, który pozwoli nam sprawdzić, czy liczby a i b są sobie różne. Wykonamy to za pomocą pętli while, gdzie != to operator różności:

while (a!=b):

Teraz dodajmy warunki, które sprawdzą czy a, czy b jest większe, a następnie wykona odpowiednie odejmowanie:

     if (a>b):
           a=a-b
     else:
           b=b-a

Pamiętaj o odpowiedniej tabulacji, aby interpreter prawidłowo rozłożył zadania na przypisane im warunki. Pozostaje nam jeszcze wyświetlenie wyniku. Gdy osiągniemy a=b. wychodzimy z pętli while i wykonujemy print

print (a)

Cały kod wygląda następująco:

a = int(input("Podaj liczbę a: ")) 
b = int(input("Podaj liczbę b: "))
while (a!=b):
     if (a>b):
           a=a-b
     else:
           b=b-a
print (a)

Dział: informatyka - python