Программирование цикла. Алгоритм Евклида.

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

3.37M

Category:

programming

Программирование цикла. Алгоритм Евклида

1. Программирование цикла. Алгоритм Евклида.

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

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

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

Дано: M и N
Найти: НОД(M,N)
АЛГОРИТМ ЕВКЛИДА:
НОД
1) Если два числа равны,
то ответ любое из них
иначе перейти к 2)
2) Заменить большее число разностью
большего и меньшего из чисел
3) Вернуться к 1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

НАЧАЛО
Ввод M и N
M N
нет
да
нет
N=N-M
M N
да
M=M-N
Вывод M
КОНЕЦ
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.

34. Отладка и тестирование задачи на ПК:

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

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

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

36.

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

English Русский Rules