Нахождение наибольшего общего делителя (НОД) при помощи рекурсии
Программа принимает на вход два числа и находит наибольший общий делитель (НОД) с использованием рекурсии.
Решение задачи
- Принимаются два числа, которые сохраняются в отдельные переменные.
- Передаем оба числа в рекурсивную функцию в качестве аргумента.
- В качестве базового условия рекурсии принимаем равенство нулю второго числа (второго аргумента функции). В этом случае результатом работы функции является первое число (первый аргумент функции).
- В противном случае снова рекурсивно вызываем эту функцию и в качестве первого аргумента передаем ей второй аргумент из предыдущего вызова функции, а в качестве второго — остаток от деления первого аргумента на второй аргумент.
- Когда функция завершит свою работу, ее результатам будет первый аргумент из последнего вызова этой функции. Он и будет наибольшим общим делителем (НОД).
- Выводим результат на экран.
- Конец.
Исходный код
Ниже дан исходный код, который осуществляет нахождение наибольшего общего делителя (НОД) с использованием рекурсии. Результаты работы программы также даны ниже.
Объяснение работы программы
- Пользователь вводит два числа и они записываются в переменные a и b .
- Затем эти два числа передаются в качестве аргументов в рекурсивную функцию gcd() .
- В качестве базового условия рекурсии принимаем равенство 0 второго аргумента функции: b == 0 . В этом случае результатом работы функции будет первый аргумент a .
- В противном случае снова рекурсивно вызываем нашу функцию следующим образом: gcd(b, a % b) . То есть, в качестве первого аргумента передаем ей второй аргумент из предыдущего вызова функции ( b ), а в качестве второго —остаток от деления a на b .
- Когда функция завершит свою работу, ее результатам будет первый аргумент из последнего вызова этой функции. Он и будет наибольшим общим делителем (НОД).
- Выводим результат работы функции на экран.
Результаты работы программы
Английский для программистов
Наш телеграм канал с тестами по английскому языку для программистов. Английский это часть карьеры программиста. Поэтому полезно заняться им уже сейчас
Напишите рекурсивную функцию которая вычисляет нод двух натуральных чисел используя модифицированный
Рекурсивная:
function NOD(x,y:integer):integer;
begin
if x<>0 then NOD:=NOD(y mod x,x) else NOD:=y;
end;
var a,b:integer;
begin
write(‘a=’); readln(a);
write(‘b=’); readln(b);
writeln(‘НОД=’,NOD(a,b));
end.
Не рекурсивная:
function NOD(x,y:integer):integer;
begin
while (x<>0)and(y<>0) do
if x>y then x:=x mod y else y:=y mod x;
NOD:=x+y;
end;
var a,b:integer;
begin
write(‘a=’); readln(a);
write(‘b=’); readln(b);
writeln(‘НОД=’,NOD(a,b));
end.
Лучшие помощники
Этот сайт использует cookies. Политика Cookies Вы можете указать условия хранения и доступ к cookies в своем браузере.
Нахождение НОД (наибольшего общего делителя) с помощью рекурсивной функции
Наибольший общий делитель (НОД) чисел 3430 и 1365 – это 35. Другими словами, 35 – наибольшее число, на которое и 3430 и 1365 делятся без остатка. Чтобы убедиться в этом, разложим оба числа на простые сомножители:
и выделим пары общих сомножителей. В данном случае это пары 5 и 7. Наибольший общий делитель – это произведение совпадающих сомножителей; в данном случае это 5 * 7 = 35.
Более изящный метод поиска НОД – алгоритм Евклида. Найдем остаток от деления 3430 на 1365:
Так как этот остаток не равен нулю, повторим то же действие, подставив вместо первого числа второе, а вместо второго – остаток:
Этот остаток также не нуль, поэтому еще одно деление:
Теперь остаток – нуль, следовательно, НОД равен 35. Вот и отлично.
Следующая программа на Паскале использует метод Эвклида и рекурсию:
Если представить, что в функцию сразу подставляются числа 665 и 35, то сразу ясно, как вычисляется gcd ( 665 , 35 ) : остаток modulo будет равен нулю и функция возвратит число 35 (ветка if ). А вот при обращении gcd ( 3430 , 1365 ) modulo будет равен 700, и, следовательно, функция вызовет себя еще раз в виде gcd ( 1365 , 700 ) . Таким образом, при каждом обращении Паскаль как бы создает новую копию функции gcd :