Question

Запишите алгоритм Евклида. Найти наибольший общий делитель (НОД) двух целых положительных чисел.

Answer 1

 function nod( a, b: longint): longint;

 begin

  while (a <> 0) and (b <> 0) do

    if a >= b then

      a:= a mod b

    else

      b:= b mod a;

  nod:= a + b;

 end;

Answer 2

Алгоритм Евклида находит наибольший общий делитель (НОД) двух целых положительных чисел. Вот его шаги:

1. Начните с двух заданных чисел, которые мы обозначим как "a" и "b", где a >= b. Если a < b, поменяйте значения a и b.

2. Разделите a на b и найдите остаток. Запишите его как "r".

3. Если r равно нулю, то b является НОДом двух исходных чисел, и алгоритм завершается.

4. Если r не равно нулю, замените a на b, b на r и вернитесь к шагу 2.

5. Повторяйте шаги 2-4 до тех пор, пока не будет найден НОД.

В итоге, когда алгоритм завершается, значение b будет являться НОДом исходных чисел.

Вот пример алгоритма Евклида на языке Python:

pythonCopy code
def euclidean_algorithm(a, b):
    if a < b:
        a, b = b, a
    
    while b != 0:
        r = a % b
        a, b = b, r
    
    return a

# Пример использования:
num1 = 48
num2 = 18

gcd = euclidean_algorithm(num1, num2)
print("Наибольший общий делитель чисел", num1, "и", num2, ":", gcd)

В данном примере результатом будет "Наибольший общий делитель чисел 48 и 18: 6".