Практическая информатика

НОД и алгоритм Евклида


При рассмотрении задач, связанных с обработкой целых чисел, часто приходится сталкиваться с понятием НОД - наибольшего общего делителя чисел. Известно много алгоритмов вычисления НОД, мы рассмотрим лишь два из них.

Задача

Напишите программу, вычисляющую НОД(a,b) - наибольший общий делитель двух введенных с клавиатуры неотрицательных целых чисел a и b, не равных нулю одновременно.

Вариант 1

Определим максимум из этих чисел и, последовательно уменьшая его, будем искать число, на которое делятся и a и b. Программа обязательно завершит свою работу, так как в самом неудачном случае, когда эти числа взаимно просты, k станет равно 1, а на 1 делятся все числа, следовательно выполнение цикла прекратится.

print "Введите первое число: "; a = gets.to_i print "Введите второе число: "; b = gets.to_i

k = a >= b ? a : b # теперь k - максимум until (a % k == 0) and (b % k == 0) k -= 1 end print "НОД(#{a},#{b}) = #{k}\n"

Вариант 2 - алгоритм Евклида

Алгоритм Евклида основан на следующих свойствах НОД: для всех a и b, больших или равных 0, выполнены равенства

НОД(a, b) = НОД(a - b, b)= НОД(a, b - a); НОД(a, 0) = НОД(0, a) = a

Ниже приведен текст программы, реализующей алгоритм Евклида.

print "Введите первое число: "; a = gets.to_i print "Введите второе число: "; b = gets.to_i m, n = a, b while !((m == 0) || (n == 0)) if m >= n m = m - n else n = n - m end end

k = m == 0 ? n : m print "НОД(#{a},#{b}) = #{k}\n"

Пример 1.9.

(html, txt)



Содержание раздела