Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Задача № 22. Найти наибольший общий делитель двух натуральных чиселФормулировка. Даны два натуральных числа. Найти их наибольший общий делитель. Примечание: наибольшим общим делителем (сокращенно пишут НОД) двух натуральных чисел 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: Код:
|