Поделиться
Задача по программированию Найти наибольший общий делитель двух натуральных чисел.docx
Формулировка. Даны два натуральных числа. Найти их наибольший общий делитель.
Примечание: наибольшим общим делителем (сокращенно пишут НОД) двух натуральных чисел 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.
Решение. Конечно, при решении мы не будем выписывать делители и выбирать нужный. В принципе, ее можно было бы решить как задачу 14, начав цикл с наименьшего из двух заданных чисел (так как оно тоже может быть НОД, например, НОД(12, 4) = 4). Но мы воспользуемся так называемым алгоритмом Евклида нахождения НОД, который выведен с помощью математических методов. В самом простейшем случае для заданных чисел m и n он выглядит так:
1) Если m неравно n, перейти к шагу 2, в противном случае вывести m и закончить алгоритм;
2) Если m > n, заменить m на m – n, в противном случае заменить n на n – m;
3) Перейти на шаг 1
Как видим, в шаге 2 большее из двух текущих чисел заменяется разностью большего и меньшего.
Приведем пример для чисел 12 и 8:
a. Так как 12 > 8, заменим 12 на 12 – 8 = 4;
b. Так как 8 > 4, заменим 8 на 8 – 4 = 4;
c. 4 = 4, конец.
Не проводя каких-либо рассуждений над алгоритмом и не доказывая его корректности, переведем его описание в более близкую для языка Pascal форму:
Алгоритм на естественном языке:
1) Ввод m и n;
2) Запуск цикла с предусловием m < > n. В цикле:
1. Если m > n, то переменной m присвоить m – n, иначе переменной n присвоить n – m;
3) Вывод m:
Код:
|
1. program GreatestCommonDiv; 2. 3. var 4. m, n: word; 5. 6. begin 7. readln(m, n); 8. while m <> n do begin 9. if m > n then begin 10. m := m - n 11. end 12. else begin 13. n := n - m 14. end 15. end; 16. writeln(m) 17. end. |
Скачано с www.znanio.ru
Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
