Нахождение НОД (наибольшего общего делителя) с помощью рекурсивной функции

Задача

Вычислить НОД с помощью рекурсии.

Решение

 

Наибольший общий делитель (НОД) чисел 3430 и 1365 – это 35. Другими словами, 35 – наибольшее число, на которое и 3430 и 1365 делятся без остатка. Чтобы убедиться в этом, разложим оба числа на простые сомножители:

3430 = 2 * 5 * 7 * 7 * 7
1365 = 3 * 5 * 7 * 13

и выделим пары общих сомножителей. В данном случае это пары 5 и 7. Наибольший общий делитель – это произведение совпадающих сомножителей; в данном случае это 5 * 7 = 35.

Более изящный метод поиска НОД – алгоритм Евклида. Найдем остаток от деления 3430 на 1365:

3430 mod 1365 = 700

Так как этот остаток не равен нулю, повторим то же действие, подставив вместо первого числа второе, а вместо второго – остаток:

1365 mod 700 = 665

Этот остаток также не нуль, поэтому еще одно деление:

700 mod 665 = 35

И еще одно:

665 mod 35 = 0

Теперь остаток – нуль, следовательно, НОД равен 35. Вот и отлично.

Следующая программа на Паскале использует метод Эвклида и рекурсию:

Программа на языке Паскаль: 

 

var a, b, answer: integer;
 
function gcd(m, n: integer): integer;
    var modulo: integer;
    begin
        modulo := m mod n;
        if modulo = 0 then
            gcd := n
        else
            gcd := gcd (n, modulo)
    end;
 
begin
    write('Enter two numbers: ');
    readln(a, b);
 
    answer := gcd(a, b);
    writeln('Greatest common divisor: ', answer);
 
readln
end.

 

Примечания: 

Если представить, что в функцию сразу подставляются числа 665 и 35, то сразу ясно, как вычисляется gcd(665, 35): остаток modulo будет равен нулю и функция возвратит число 35 (ветка if). А вот при обращении gcd(3430, 1365) modulo будет равен 700, и, следовательно, функция вызовет себя еще раз в виде gcd(1365, 700). Таким образом, при каждом обращении Паскаль как бы создает новую копию функции gcd:

Алгоритм вычисления НОД с помощью рекурсии

 

  1. Из основной ветки программы вызывается функция gcd. Результат работы данной функции в дальнейшем будет присвоен переменной answer.
  2. В функции gcd вычисляется остаток от деления чисел 3430 и 1365. Поскольку он не равен нулю, то осуществляется повторный вызов функции, но уже с числами 1365 и 700 (700 – это остаток от первого деления).
  3. При третьем вызове функции передаются числа 700 и 665.
  4. При четвертом – 665 и 35. Здесь остаток равен 0. Следовательно, результатом работы функции является число 35 (gcd = 35).
  5. Результат четвертого вызова возвращается в третий.
  6. Третий – во второй.
  7. Второй – в первый.
  8. Первый – в основную ветку программы и присваивается переменной answer.

 

Тема

Процедуры, функции, рекурсии

Уровень

Сложные задачи

Комментарии

Нужно ещё проверить,какое число больше другого.Чтобы первым поставить.

В вашей программе всё верно.Только без проверки рекурсия на один шаг длиннее будет.

Добавить комментарий

CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.
CAPTCHA на основе изображений
Введите символы, которые показаны на картинке.