Информатика: Опишите процесс записи алгоритма, который находит наибольший общий делитель (НОД) двух чисел
Описание в словах: Для нахождения наибольшего общего делителя (НОД) двух чисел следует выполнить следующие шаги:
1. Создайте две таблицы с двумя столбцами и назовите их «Х» и «У».
2. В первый столбец «Х» запишите первое заданное число, а во второй столбец «У» запишите второе число.
3. Если числа различны, замените большее из них на разницу между ними и запишите новое значение в тот же столбец.
4. Повторяйте этот процесс до тех пор, пока числа в столбцах «Х» и «У» не станут равными.
5. Полученное значение в столбце «Х» является наибольшим общим делителем (НОД) заданных чисел.
Графическая схема:
--------------------- | Х | Y | --------------------- | X1 = | Y1 = | | X2 = | Y2 = | | X3 = | Y3 = | | . | . | | . | . | ---------------------
Запись по шагам:
1. Создаем таблицу с двумя столбцами и называем их «Х» и «У».
2. В первый столбец «Х» записываем первое заданное число, во второй столбец «У» записываем второе число.
3. Если числа различны, заменяем большее из них на разницу между ними и записываем новое значение в тот же столбец.
4. Повторяем шаг 3 до тех пор, пока числа в столбцах «Х» и «У» не станут равными.
5. После того, как числа стали равными, значение в столбце «Х» берем в качестве наибольшего общего делителя (НОД) заданных чисел.
Пример использования:
Х1 = 24, Y1 = 36
= 36, Y2 = 24
= 12, Y3 = 24
Х4 = 12, Y4 = 12
НОД = 12
Совет:
Для понимания и запоминания данного алгоритма, полезно разобрать несколько примеров на бумаге, проведя вычисления вручную. Также можно применять данный алгоритм для нахождения НОД других чисел и проверять его работоспособность.
Задание:
Найдите НОД для чисел:
Х = 72, Y = 48