Обработка информации и алгоритмы

Вопрос 3. Используя алгоритм Евклида, найдите НОД для чисел 114 и 66. Сколько шагов алгоритма при этом вам пришлось выполнить?

Алгоритм Евклида

НОД двух чисел — это наибольший из всех их общих делителей.

Одним из простейших алгоритмов нахождения наибольшего общего делителя является Алгоритм Евклида. Выделяют два способа реализации алгоритма: методом деления и методом вычитания. Но в данном задании мы будем использовать только способ вычитания.

Алгоритм Евклида вычитанием

Найти НОД двух целых чисел немного проще используя операцию вычитания. Для этого потребуется следовать такому условию: если A=B, то НОД найден и он равен одному из чисел, иначе необходимо большее из двух чисел заменить разностью его и меньшего.

Блок-схема Алгоритма Евклида вычитанием:

А теперь составим с данными числами таблицу для алгоритма вычитанием.

Начальные данные	114	66
Шаг 1	48	66
Шаг 2	48	18
Шаг 3	30	18
Шаг 4	12	18
Шаг 5	12	6
Шаг 6	6	0

НОД(114, 66) =НОД(6, 6) = 6

1)114 - 66 = 48

2)66 - 48=18

3)48-18=30

4)30-18=12

5)18-12=6

6)12-6=6

Итого: 6 шагов алгоритма  пришлось выполнить.