Обработка информации и алгоритмы
Ответ на вопрос №3
Используя алгоритм Евклида, найти НОД для чисел 114 и 66. Сколько шагов алгоритма мне пришлось выполнить?
Алгоритм Евкалида - известный способ вычисления НОД (наибольшего общего делителя) двух натуральных чисел, который описывается так:
- Если числа не равны, то большее из них заменить на разность большего и меньшего из чисел.
- Если два числа равны, то за НОД принять любое из них, иначе перейти к выполнению пункта 1.
При решении данной задачи мы должны пользоваться 1-ым решением, так как нам даны числа 114 и 66.
Шаг 1. 114-66=48
Шаг 2. 66-48=18
Шаг 3. 48-18=30
Шаг 4. 30-18=12
Шаг 5. 18-12=6
Шаг 6. 12-6=6
Ответ: Наибольшим общим делителем чисел 114 и 66 является делитель 6.
Для решения алгоритма мне пришлось выполнить 6 шагов.
