Напишите программу которая получает с клавиатуры два натуральных числа и находит их нод

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

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

Решение задачи

1. Принимаются два числа, которые сохраняются в отдельные переменные.
2. Передаем оба числа в рекурсивную функцию в качестве аргумента.
3. В качестве базового условия рекурсии принимаем равенство нулю второго числа (второго аргумента функции). В этом случае результатом работы функции является первое число (первый аргумент функции).
4. В противном случае снова рекурсивно вызываем эту функцию и в качестве первого аргумента передаем ей второй аргумент из предыдущего вызова функции, а в качестве второго — остаток от деления первого аргумента на второй аргумент.
5. Когда функция завершит свою работу, ее результатам будет первый аргумент из последнего вызова этой функции. Он и будет наибольшим общим делителем (НОД).
6. Выводим результат на экран.
7. Конец.

Исходный код

Ниже дан исходный код, который осуществляет нахождение наибольшего общего делителя (НОД) с использованием рекурсии. Результаты работы программы также даны ниже.

Объяснение работы программы

1. Пользователь вводит два числа и они записываются в переменные a и b .
2. Затем эти два числа передаются в качестве аргументов в рекурсивную функцию gcd() .
3. В качестве базового условия рекурсии принимаем равенство 0 второго аргумента функции: b == 0 . В этом случае результатом работы функции будет первый аргумент a .
4. В противном случае снова рекурсивно вызываем нашу функцию следующим образом: gcd(b, a % b) . То есть, в качестве первого аргумента передаем ей второй аргумент из предыдущего вызова функции ( b ), а в качестве второго —остаток от деления a на b .
5. Когда функция завершит свою работу, ее результатам будет первый аргумент из последнего вызова этой функции. Он и будет наибольшим общим делителем (НОД).
6. Выводим результат работы функции на экран.

Результаты работы программы

Английский для программистов

Наш телеграм канал с тестами по английскому языку для программистов. Английский это часть карьеры программиста. Поэтому полезно заняться им уже сейчас

Найти наибольший общий делитель двух натуральных чисел

Формулировка. Даны два натуральных числа. Найти их наибольший общий делитель.

Примечание: наибольшим общим делителем (сокращенно пишут НОД) двух натуральных чисел m и n называется наибольший из их общих делителей. Обозначение: НОД(m, n).

Примечание 2: общим делителем двух натуральных чисел называется натуральное число, на которое натуральное число, которое является делителем обоих этих чисел.

Например, найдем НОД(12, 8):

Выпишем все делители числа 12: 1, 2, 3, 4, 6, 12;

Выпишем все делители числа 8: 1, 2, 4, 8;

Выпишем все общие делители чисел 12 и 8: 1, 2, 4. Из них наибольшее число – 4. Это и есть НОД чисел 12 и 8.

Решение. Конечно, при решении мы не будем выписывать делители и выбирать нужный. В принципе, ее можно было бы решить как задачу 15, начав цикл с наименьшего из двух заданных чисел (так как оно тоже может быть НОД, например, НОД(12, 4) = 4). Но мы воспользуемся так называемым алгоритмом Евклида нахождения НОД, который выведен с помощью математических методов. В самом простейшем случае для заданных чисел m и n он выглядит так:

1) Если m неравно n, перейти к шагу 2, в противном случае вывести m и закончить алгоритм;

2) Если m > n, заменить m на m – n, в противном случае заменить n на n – m;

Как видим, в шаге 2 большее из двух текущих чисел заменяется разностью большего и меньшего.

Приведем пример для чисел 12 и 8:

1. Так как 12 > 8, заменим 12 на 12 – 8 = 4;
2. Так как 8 > 4, заменим 8 на 8 – 4 = 4;
3. 4 = 4, конец.

Не проводя каких-либо рассуждений над алгоритмом и не доказывая его корректности, переведем его описание в более близкую для языка Pascal форму:

Алгоритм на естественном языке:

1) Ввод m и n;

2) Запуск цикла с предусловием m < > n. В цикле:

Почему не выполняется программа (нахождение НОД с помощью алгоритма Евклида)?

Задача:
Ввести с клавиатуры два натуральных числа и найти их НОД с помощью алгоритма Евклида.

После запуска программы просит ввести числа и все. Сама программа не выполняется. Что не так?

• Вопрос задан более года назад
• 440 просмотров

• Facebook
• Вконтакте
• Twitter

while a!=0 and b!=0:
цикл работает, пока a и b не равны нулю. Вы изначально задаете их не равными нулю, в цикле никак не модифицируете их, он бесконечно работает