НОД и алгоритм Евклида
При рассмотрении задач, связанных с обработкой целых чисел, часто приходится сталкиваться с понятием НОД - наибольшего общего делителя чисел. Известно много алгоритмов вычисления НОД, мы рассмотрим лишь два из них.
Задача
Напишите программу, вычисляющую НОД(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)
