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

Евклида;  ♦ описание алгоритма Евклида блок-схемой;  ♦ программа на AЯ и на Паскале.

двух натуральных чисел.
Вспомним математику. Наибольший общий делитель двух натуральных чисел — это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:
НOД(12, 18) = 6.
Обозначим исходные данные как М и N. Постановка задачи выглядит следующим образом:
Дано: М, N Найти: НОД(M, N).
В данном случае какой-то дополнительной математической формализации не требуется. Сама постановка задачи носит формальный математический характер. Не существует формулы для вычисления НОД(М, N) по значениям М и N. Но зато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида.

N) = НОД(М – N, N).
Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.
Легко доказать это свойство. Пусть К — общий делитель М и N (М > N). Это значит, что М = mК, N = nК, где m,n — натуральные числа, причем m > n. Тогда М - N = К(m - n), откуда следует, что К — делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности М - N в том числе и наибольший общий делитель.
Второе очевидное свойство:
НОД(М, М) = М.

взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма; 2) затенить большее число разностью большего и меньшего из чисел; 3) вернуться к выполнению п. 1.
Рассмотрим этот алгоритм на примере М=32, N=24:

Получили: НОД(32, 24) = НОД(8, 8) = 8, что верно.

пока значения М и N не равны друг другу. В ветвлении большее из двух значений заменяется на их разность.

и N не равны друг другу. В ветвлении большее из двух значений заменяется на их разность.

§ 40