Алгоритм Евклида презентация

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

Алгоритм Евклида ЕВКЛИД - древнегреческий математик. Работал в Александрии в 3 в. до н. э. Евклид оказал огромное влияние на развитие математики. Главный труд - «Начала» (состоит из 15 книг) -содержит основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и методы определения площадей и объемов. Евклиду принадлежат также работы по астрономии, оптике, теории музыки.

Постановка задачи: Требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел

12 2 18 2 6 2 9 3 3 3 3 3 1 1

Алгоритм нахождения НОД Разложить числа на простые множители. Найти общие множители. Найти их произведение.

Алгоритм Евклида Идея алгоритма основана на двух свойствах: 1. Если M>N, то НОД (M, N) = НОД (M-N, N) 2. НОД (M, M) = M НОД (12, 18) = НОД (12, 18-12) = НОД (12, 6) = = НОД (12-6, 6) = НОД (6, 6) = 6

Алгоритм Евклида Если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма. Заменить большее число разностью большего и меньшего из чисел. Вернуться к выполнению п. 1.

Блок-схема алгоритма Евклида

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

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

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Трассировочная таблица алгоритма Евклида М=32, N=24

Блок-схема алгоритма Евклида

Программа на Паскале Program Evklid; var m, n: integer; begin writeln (’Введите m и n ’); readln (m, n); while m<>n do begin if m>n then m:=m-n else n:=n-m end; write (’НОД=’, m) end.

Отладка и тестирование Выполнить на компьютере программу. Протестировать ее на значениях: 1) M=32, N=24; 2) M=696, N=234

Постановка задачи: Составить программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу: M х N = НОД (M, N) х НОК (M, N)

Домашнее задание Составить программу нахождения наибольшего общего делителя трех чисел, используя формулу: НОД (A, B, C) = НОД (НОД (A, B), C)