МОЗИ 4 семестр / Лабораторная 3 / MOZI_LAB3

# Алгоритм Евклида и бинарный алгоритм Евклида


def evklid_algoritm(a, b):
while a != 0 and b != 0:
if a >= b:
a %= b
else:
b %= a
return a or b


def evlkid_bin_algoritm(a, b):
k = 1

if a == b:
return (a)

# Пока а и б не равны нулю выполняется цикл
while (a != 0) and (b != 0):

# Если а и б четные
while (a % 2 == 0) and (b % 2 == 0):
a /= 2
b /= 2
k *= 2
# Если а четное то a/2, если б четное то b/2
while a % 2 == 0:
a /= 2
while b % 2 == 0:
b /= 2
# Если оба числа нечетные, то а-б или б-а
if a >= b:
a -= b
else:
b -= a

return b * k


print("Введите номер необходимого алгоритма")
print("1 - Алгоритм Евклида (НОД)")
print("2 - Бинарный алгоритм Евклида (НОД)")
vibor = int(input())

if vibor == 1:
print("\nВыбран обычный алгоритм")
a = int(input("Введите число a:"))
b = int(input("Введите число b:"))
print(evklid_algoritm(a, b))
elif vibor == 2:
print("\nВыбран бинарный алгоритм")
a = int(input("Введите число a:"))
b = int(input("Введите число b:"))
c = evlkid_bin_algoritm(a, b)
if c != 'Error':
print(c)

else:
print("\nВведен некорректный номер алгоритма")