Презентация, доклад по информатикеАлгоритм Евклида(9 класс)

Дано: А, В Найти: НОД(А,В)

1. Постановка задачи.

3. Построение алгоритма.

Алгоритм Евклида основан на двух свойствах:
1) если А>B, то НОД(А,В) = НОД(А-В,В)
2) если А=B, то НОД(А,А) = А

Для ручного счета алгоритм Евклида выглядит следующим образом:
1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма
2) заменить большее число разностью большего и меньшего из чисел
3) вернуться к выполнению п.1