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


Используя алгоритм Евклида, найдите НОД для чисел 114 и 66. Сколько шагов алгоритма при этом вам пришлось выполнить?
Рейтинг: 5.0/1
Просмотров: 37 | Добавил: (09.02.2021) (Изменено: 09.02.2021)

Всего ответов: 3

Обсуждение вопроса:
Всего ответов: 3
Аватар
0

09.02.2021 оставил(а) комментарий:
Из большего нужно вычесть меньшего, т.е.

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 шагов.
Аватар
0

09.02.2021 оставил(а) комментарий:
1) числа равны? : нет, 114 > 66
найти разность большего и меньшего: 144 - 66 = 48
большее из них заменить на разность большего и меньшего чисел: 48 и 66
2) если два числа не равны, то перейти к выполнению пункта 1:
найти разность большего и меньшего: 66 - 48 = 18
большее из них заменить на разность большего и меньшего чисел: 18 и 48
3) если два числа не равны, то перейти к выполнению пункта 1:
найти разность большего и меньшего: 48-18=30
большее из них заменить на разность большего и меньшего чисел: 30 и 18
4) если два числа не равны, то перейти к выполнению пункта 1:
найти разность большего и меньшего: 30-18=12
большее из них заменить на разность большего и меньшего чисел: 12 и 18
5) если два числа не равны, то перейти к выполнению пункта 1:
найти разность большего и меньшего: 18-12=6
большее из них заменить на разность большего и меньшего чисел: 6 и 12
6) если два числа не равны, то перейти к выполнению пункта 1:
найти разность большего и меньшего: 12-6=6
большее из них заменить на разность большего и меньшего чисел: 6 и 6
если два числа равны, то за НОД принять любое из них:
НОД = 6

Пришлось выполнить 6 шагов алгоритма.
Аватар
0

09.02.2021 оставил(а) комментарий:
НОД двух чисел — это наибольший из всех их общих делителей.

Одним из простейших алгоритмов нахождения наибольшего общего делителя является Алгоритм Евклида.

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

НОД(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 шагов алгоритма пришлось выполнить.
avatar