Similar presentations:
Алгоритм Евклида
1. Алгоритм Евклида
Сейдалиева З.С.Учитель информатики
2. Алгоритм Евклида
ЕВКЛИД - древнегреческий математик. Работал вАлександрии в 3 в. до н. э. Евклид оказал огромное
влияние на развитие математики. Главный труд «Начала» (состоит из 15 книг) -содержит основы
античной математики, элементарной геометрии,
теории чисел, общей теории отношений и методы
определения площадей и объемов. Евклиду
принадлежат также работы по астрономии, оптике,
теории музыки.
3. Постановка задачи:
Требуется составить программуопределения наибольшего общего
делителя (НОД) двух натуральных чисел
НОД двух натуральных чисел - это
самое большое натуральное число, на
которое они делятся нацело
Например: НОД (12, 18) = 6
4.
Алгоритм нахождения НОД12 2
6 2
3 3
1
18 2
9 3
3 3
1
НОД (12, 18) = 2 · 3 = 6
5. Алгоритм нахождения НОД
1.2.
3.
Разложить числа на простые
множители.
Найти общие множители.
Найти их произведение.
6. Алгоритм Евклида
Идея алгоритма основана на двух свойствах: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
7. Алгоритм Евклида
1.2.
3.
Если числа равны, то взять любое из
них в качестве ответа, в противном
случае продолжить выполнение
алгоритма.
Заменить большее число разностью
большего и меньшего из чисел.
Вернуться к выполнению п. 1.
8. Блок-схема алгоритма Евклида
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ
9. Структура алгоритма Евклида
НАЧАЛОЦикл-пока
Ввод M и N
M N
нет
Повторяет
выполнение, пока
значения M и N не
равны друг другу
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ
10. Структура алгоритма Евклида
НАЧАЛОВложенное
ветвление
Ввод M и N
M N
нет
Заменяет
большее из двух
значений на их
разность
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ
11. Трассировочная таблица алгоритма Евклида М=32, N=24
шагНАЧАЛО
1
2
Ввод M и N
3
M N
нет
4
5
да
нет
N:=N-M
M N
6
да
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
операция
M
N
условие
12. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
нет
4
5
да
нет
N:=N-M
M N
6
да
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
N
24
условие
13. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
нет
4
5
да
нет
N:=N-M
M N
6
да
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
N
24
условие
14. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
N:=N-M
M N
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
4
5
да
нет
шаг
6
да
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
N
условие
24
32 24, да
15. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
N:=N-M
M N
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
4
5
да
нет
шаг
6
да
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
N
условие
24
32 24, да
16. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
N:=N-M
M N
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
да
нет
шаг
6
да
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
N
условие
24
17. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
N:=N-M
M N
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
да
нет
шаг
6
да
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
N
условие
24
18. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
да
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
8
N
условие
24
24
19. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
да
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
8
N
условие
24
24
20. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
8
N
условие
24
24
8 24, да
21. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
8
N
условие
24
24
8 24, да
22. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
8
N
условие
24
24
23. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N=N-M
M N
да
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
M=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
8
N
условие
24
24
24. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
N:=N-M
9
10
КОНЕЦ
11
12
13
14
8
8
N
условие
24
24
16
25. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
N:=N-M
9
10
КОНЕЦ
11
12
13
14
8
8
N
условие
24
24
16
26. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
N:=N-M
9
M N
10
КОНЕЦ
11
12
13
14
8
8
N
условие
24
24
16
8 16, да
27. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N=N-M
M N
да
M=M-N
Вывод M
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
N:=N-M
9
M N
10
КОНЕЦ
11
12
13
14
8
8
N
условие
24
24
16
8 16, да
28. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
N:=N-M
9
M N
8 16, да
10
M N
8 16, нет
11
12
13
14
8
8
N
условие
24
24
16
29. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
N:=N-M
9
M N
8 16, да
10
M N
8 16, нет
11
12
13
14
8
8
N
условие
24
24
16
30. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
N=N-M
9
M N
8 16, да
10
M N
8 16, нет
11
N:=N-M
12
13
14
8
8
8
N
условие
24
24
16
8
31. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
N:=N-M
9
M N
8 16, да
10
M N
8 16, нет
11
N:=N-M
12
13
14
8
8
8
N
условие
24
24
16
8
32. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
N:=N-M
9
M N
8 16, да
10
M N
8 16, нет
11
N:=N-M
12
M N
13
14
8
8
8
N
условие
24
24
16
8
8 8 нет
33. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
N:=N-M
9
M N
8 16, да
10
M N
8 16, нет
11
N:=N-M
12
M N
13
14
8
8
8
N
условие
24
24
16
8
8 8 нет
34. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
N:=N-M
9
M N
8 16, да
10
M N
8 16, нет
11
N:=N-M
12
M N
13
Вывод М
14
8
8
8
N
условие
24
24
16
8
8 8 нет
8
35. Трассировочная таблица алгоритма Евклида М=32, N=24
НАЧАЛОВвод M и N
M N
нет
да
нет
N=N-M
M N
да
M=M-N
Вывод M
КОНЕЦ
шаг
операция
M
1
Ввод М
32
2
Ввод N
32
3
M N
32 24, да
4
M N
32 24, да
5
M:=M-N
6
M N
8 24, да
7
M N
8 24, нет
8
N:=N-M
9
M N
8 16, да
10
M N
8 16, нет
11
N:=N-M
12
M N
13
Вывод М
14
конец
8
8
8
N
условие
24
24
16
8
8 8 нет
8
36. Блок-схема алгоритма Евклида
НАЧАЛОВвод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ
37. Программа на Паскале
НАЧАЛОProgram Evklid;
var m, n: integer;
begin
writeln (’Введите m и n ’);
readln (m, n);
while m<>n do
begin
Ввод M и N
M N
нет
да
нет
N=N-M
M N
да
M=M-N
if m>n
then m:=m-n
else n:=n-m
Вывод M
КОНЕЦ
end;
write (’НОД=’, m)
end.
38. Отладка и тестирование
Выполнить на компьютере программу.Протестировать ее на значениях:
1) M=32, N=24;
2) M=696, N=234
39. Постановка задачи:
Составить программу нахождениянаименьшего общего кратного (НОК)
двух чисел, используя формулу:
M х N = НОД (M, N) х НОК (M, N)
40.
НАЧАЛОВвод M и N
P:=M*N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
HOK=P/M
Вывод НОК
КОНЕЦ
41. Домашнее задание
Составить программу нахождениянаибольшего общего делителя трех
чисел, используя формулу:
НОД (A, B, C) = НОД (НОД (A, B), C)