Question

100 баллов! Ввести с клавиатуры два натуральных числа и сравнить количество шагов цикла для вычисления их НОД с помощью обычного и модифицированного алгоритмов Евклида. Python

Answer 1

Ответ:

a, b = map(int, input("Введите два числа: \n").split())

a1,b1 = a,b

o = 0

while a1 != b1:

   if a1 > b1:

       a1 = a1 - b1

   else:

       b1 = b1 - a1  

   o += 1

a2,b2 = a,b

m = 0

while a2 != 0 and b2 != 0:

   if a2 > b2:

       a2 = a2 % b2

   else:

       b2 = b2 % a2  

   m += 1

print(f"НОД ({a},{b}) = {a1}")

print(f"Обычный: {o}")

print(f"Модифицированный: {m}")

Объяснение:

Вводим 2 числа (в строку через пробел)

Вычисляем НОД с помощью обычного алгоритма Евклида и считаем количество шагов цикла

Вычисляем НОД с помощью модифицированного алгоритма Евклида и считаем количество шагов цикла

Выводим результат

Answer 2

Для сравнения количества шагов цикла для вычисления НОД (Наибольшего Общего Делителя) с помощью обычного и модифицированного алгоритмов Евклида в Python, вы можете использовать следующий код:

pythonCopy code
def euclidean_gcd(a, b):
    steps = 0
    while b:
        a, b = b, a % b
        steps += 1
    return a, steps

def modified_euclidean_gcd(a, b):
    steps = 0
    while b:
        q = a // b
        a, b = b, a - q * b
        steps += 1
    return a, steps

try:
    num1 = int(input("Введите первое натуральное число: "))
    num2 = int(input("Введите второе натуральное число: "))

    if num1 <= 0 or num2 <= 0:
        print("Пожалуйста, введите натуральные числа.")
    else:
        gcd1, steps1 = euclidean_gcd(num1, num2)
        gcd2, steps2 = modified_euclidean_gcd(num1, num2)

        print(f"Обычный алгоритм Евклида: НОД = {gcd1}, количество шагов = {steps1}")
        print(f"Модифицированный алгоритм Евклида: НОД = {gcd2}, количество шагов = {steps2}")

except ValueError:
    print("Пожалуйста, введите корректные натуральные числа.")

Этот код сначала запрашивает у пользователя два натуральных числа, затем вычисляет НОД с использованием обычного и модифицированного алгоритмов Евклида и выводит результаты, включая количество шагов для каждого алгоритма.