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

3.16M

Category:

programming

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

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

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

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

Требуется составить программу
определения наибольшего общего
делителя (НОД) двух натуральных
чисел
НОД двух натуральных чисел - это
самое большое натуральное число, на
которое они делятся нацело
Например: НОД (12, 18) = 6

3.

Алгоритм нахождения НОД
12 2
6 2
3 3
1
18 2
9 3
3 3
1
НОД (12, 18) = 2 · 3 = 6

4. Алгоритм нахождения НОД

1.
2.
3.
Разложить числа на простые
множители.
Найти общие множители.
Найти их произведение.

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

Идея алгоритма основана на двух свойствах:
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

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

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

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

НАЧАЛО
Ввод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ

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

НАЧАЛО
Цикл-пока
Ввод M и N
M N
нет
Повторяет
выполнение, пока
значения M и N не
равны друг другу
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ

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

НАЧАЛО
Вложенное
ветвление
Ввод M и N
M N
нет
Заменяет
большее из двух
значений на их
разность
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ

10. Трассировочная таблица алгоритма Евклида М=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
условие

11. Трассировочная таблица алгоритма Евклида М=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
условие

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

13. Трассировочная таблица алгоритма Евклида М=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, да

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

15. Трассировочная таблица алгоритма Евклида М=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

16. Трассировочная таблица алгоритма Евклида М=32, 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
M:=M-N
6
да
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
8
N
условие
24
24

18. Трассировочная таблица алгоритма Евклида М=32, N=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
M N
7
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
8
N
условие
24
24
8 24, да

20. Трассировочная таблица алгоритма Евклида М=32, N=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
8 24, да
7
M N
8 24, нет
8
M:=M-N
Вывод M
9
10
КОНЕЦ
11
12
13
14
8
N
условие
24
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:=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

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

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
M N
10
КОНЕЦ
11
12
13
14
8
8
N
условие
24
24
16
8 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
8 16, да
10
M N
8 16, нет
11
12
13
14
8
8
N
условие
24
24
16

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

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
N:=N-M
12
13
14
8
8
8
N
условие
24
24
16
8

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

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

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

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

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. Блок-схема алгоритма Евклида

НАЧАЛО
Ввод M и N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
Вывод M
КОНЕЦ

36. Программа на Паскале

НАЧАЛО
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
да
if m>n
then m:=m-n
else n:=n-m
M=M-N
Вывод M
КОНЕЦ
end.
end;
write (’НОД=’, m)

37. Отладка и тестирование

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

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

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

39.

НАЧАЛО
Ввод M и N
P:=M*N
M N
нет
да
нет
N:=N-M
M N
да
M:=M-N
HOK=P/M
Вывод НОК
КОНЕЦ

40. Домашнее задание

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

English Русский Rules