Программирование цикла. Алгоритм Евклида.
Цель урока: освоить программирование циклов с предусловием на примере Алгоритма Евклида.
Алгоритм Евклида
ЕВКЛИД, древнегреческий математик. Работал в Александрии в 3 в. до н. э. Главный труд «Начала» (15 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода определения площадей и объемов, включавшего элементы теории пределов, оказал огромное влияние на развитие математики. Работы по астрономии, оптике, теории музыки.
Постановка задачи:
- Требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел
НОД двух натуральных чисел- это
самое большое натуральное число,
на которое они делятся нацело.
НАПРИМЕР: НОД(12,18)=6
НОД
Постановка задачи:
- Дано: M и N
- Найти: НОД( M , N )
АЛГОРИТМ ЕВКЛИДА:
то ответ любое из них
иначе перейти к 2)
2) Заменить большее число разностью
большего и меньшего из чисел
3) Вернуться к 1)
НОД
Блок-схема алгоритма Евклида
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
M=M-N
N=N-M
Вывод M
К О Н Е Ц
Структура алгоритма Евклида
Н А Ч А Л О
Цикл-пока
Повторяет выполнение, пока значения M и N не равны друг другу
Ввод M и N
нет
M N
да
нет
да
M N
M=M-N
N=N-M
Вывод M
К О Н Е Ц
Структура алгоритма Евклида
Н А Ч А Л О
Вложенное ветвление
Заменяет большее из двух значений на их разность
Ввод M и N
нет
M N
да
нет
да
M N
M=M-N
N=N-M
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
M
2
N
3
4
условие
5
6
7
8
9
10
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
Ввод М
M
2
N
Ввод N
3
32
32
4
условие
24
5
6
7
8
9
10
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
да
нет
M N
M=M-N
N=N-M
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
Ввод М
M
Ввод N
N
3
32
32
условие
4
24
5
6
7
8
9
10
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
да
нет
M N
M=M-N
N=N-M
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
M
Ввод М
N
Ввод N
32
3
условие
4
M N
32
24
5
6
7
32 24 , да
8
9
10
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
M=M-N
N=N-M
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
M
Ввод М
N
Ввод N
32
3
условие
4
M N
32
24
5
6
7
32 24 , да
8
9
10
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
M=M-N
N=N-M
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
Ввод М
M
2
Ввод N
N
3
32
4
M N
32
условие
M N
24
5
6
32 24 , да
7
8
32 24, да
9
10
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
Ввод М
M
2
Ввод N
N
3
32
4
M N
32
условие
M N
24
5
6
32 24 , да
7
8
32 24, да
9
10
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
M
2
Ввод М
Ввод N
N
3
32
4
M N
условие
32
24
M N
5
6
M=M-N
8
7
32 24 , да
8
24
32 24, да
9
10
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
M
2
Ввод М
Ввод N
N
3
32
4
M N
условие
32
24
M N
5
6
M=M-N
8
7
32 24 , да
8
24
32 24, да
9
10
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
M
Ввод М
Ввод N
N
3
32
условие
4
M N
32
M N
24
5
M=M-N
6
M N
8
7
32 24 , да
32 24, да
8
24
9
10
8 24 , да
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
M
Ввод М
Ввод N
N
3
32
условие
4
M N
32
M N
24
5
M=M-N
6
M N
8
7
32 24 , да
32 24, да
8
24
9
10
8 24 , да
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
Ввод М
M
N
Ввод N
32
3
4
условие
M N
32
M N
24
5
6
M=M-N
M N
7
8
32 24 , да
32 24, да
8
M N
24
9
8 24 , да
10
11
8 24 , нет
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
Ввод М
M
N
Ввод N
32
3
4
условие
M N
32
M N
24
5
6
M=M-N
M N
7
8
32 24 , да
32 24, да
8
M N
24
9
8 24 , да
10
11
8 24 , нет
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
Ввод М
M
Ввод N
N
32
3
условие
M N
4
32
24
M N
5
M=M-N
6
M N
8
7
32 24 , да
32 24, да
24
8
M N
N=N-M
9
8
10
8 24 , да
16
8 24 , нет
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
Ввод М
M
Ввод N
N
32
3
условие
M N
4
32
24
M N
5
M=M-N
6
M N
8
7
32 24 , да
32 24, да
24
8
M N
N=N-M
9
8
10
8 24 , да
16
8 24 , нет
11
12
13
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
M
2
Ввод М
Ввод N
N
3
32
M N
32
условие
4
M N
24
5
M=M-N
6
M N
8
32 24 , да
7
M N
8
24
32 24, да
N=N-M
9
8
M N
10
8 24 , да
16
11
8 24 , нет
12
13
8 16, да
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
M
2
Ввод М
Ввод N
N
3
32
M N
32
условие
4
M N
24
5
M=M-N
6
M N
8
32 24 , да
7
M N
8
24
32 24, да
N=N-M
9
8
M N
10
8 24 , да
16
11
8 24 , нет
12
13
8 16, да
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
Ввод М
M
Ввод N
N
3
32
условие
4
M N
32
24
M N
5
M=M-N
6
M N
7
32 24 , да
8
8
M N
24
32 24, да
N=N-M
9
8
8 24 , да
M N
10
M N
16
11
8 24 , нет
12
8 16, да
13
8 16, нет
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
Ввод М
M
Ввод N
N
3
32
условие
4
M N
32
24
M N
5
M=M-N
6
M N
7
32 24 , да
8
8
M N
24
32 24, да
N=N-M
9
8
8 24 , да
M N
10
M N
16
11
8 24 , нет
12
8 16, да
13
8 16, нет
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
Ввод М
M
N
Ввод N
3
32
M N
4
условие
32
24
M N
5
6
M=M-N
M N
32 24 , да
7
8
8
24
M N
32 24, да
N=N-M
9
M N
8 24 , да
10
8
M N
16
8 24 , нет
11
N=N-M
12
8 16, да
8
13
8 16, нет
8
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
Ввод М
M
N
Ввод N
3
32
M N
4
условие
32
24
M N
5
6
M=M-N
M N
32 24 , да
7
8
8
24
M N
32 24, да
N=N-M
9
M N
8 24 , да
10
8
M N
16
8 24 , нет
11
N=N-M
12
8 16, да
8
13
8 16, нет
8
14
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
Ввод М
M
Ввод N
N
3
32
4
M N
32
условие
M N
24
5
6
M=M-N
M N
8
7
32 24 , да
8
M N
32 24, да
24
N=N-M
9
8
M N
10
8 24 , да
16
M N
8 24 , нет
11
N=N-M
12
M N
8
13
8 16, да
8 16, нет
8
14
8 8 нет
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
Ввод М
M
Ввод N
N
3
32
4
M N
32
условие
M N
24
5
6
M=M-N
M N
8
7
32 24 , да
8
M N
32 24, да
24
N=N-M
9
8
M N
10
8 24 , да
16
M N
8 24 , нет
11
N=N-M
12
M N
8
13
8 16, да
8 16, нет
8
14
8 8 нет
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
Ввод М
2
M
N
Ввод N
32
3
M N
4
условие
32
24
M N
5
6
M=M-N
M N
7
32 24 , да
8
32 24, да
8
M N
24
N=N-M
9
8 24 , да
10
M N
8
M N
16
11
8 24 , нет
12
N=N-M
M N
8
13
8 16, да
14
8 16, нет
8
Вывод М
8
8 8 нет
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Трассировочная таблица алгоритма Евклида М=32, N=24
шаг
операция
1
2
Ввод М
M
Ввод N
N
32
3
M N
4
условие
32
24
M N
5
M=M-N
6
M N
32 24 , да
7
8
M N
32 24, да
24
8
N=N-M
9
10
M N
8
8 24 , да
16
M N
8 24 , нет
11
N=N-M
12
M N
13
8
8 16, да
Вывод М
14
8 16, нет
8
конец
8
8 8 нет
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Блок-схема алгоритма Евклида
Н А Ч А Л О
Ввод M и N
нет
M N
да
нет
да
M N
M=M-N
N=N-M
Вывод M
К О Н Е Ц
n then m:=m-n else n:=n-m If mn then m:=m-n else n:=n-m If mn then m:=m-n else n:=n-m If mn then m:=m-n else n:=n-m If mn then m:=m-n else n:=n-m end; write (‘ НОД= ‘,m); end; write (‘ НОД= ‘,m); end; write (‘ НОД= ‘,m); end. Н А Ч А Л О Ввод M и N нет M N да да нет M N N=N-M M=M-N Вывод M К О Н Е Ц " width="640"
Программа на Паскале
Program Evklid;
var m,n:integer;
Begin
writeln(‘ Введите m и n’);
readln (m,n);
while mn do
begin
- writeln(‘ Введите m и n’); readln (m,n); while mn do begin
- writeln(‘ Введите m и n’); readln (m,n); while mn do begin
If mn
then m:=m-n
else n:=n-m
- If mn then m:=m-n else n:=n-m
- If mn then m:=m-n else n:=n-m
- If mn then m:=m-n else n:=n-m
- If mn then m:=m-n else n:=n-m
end;
write (‘ НОД= ‘,m);
- end; write (‘ НОД= ‘,m);
- end; write (‘ НОД= ‘,m);
end.
Н А Ч А Л О
Ввод M и N
нет
M N
да
да
нет
M N
N=N-M
M=M-N
Вывод M
К О Н Е Ц
Отладка и тестирование задачи на ПК:
- Выполнить на ПК программу. Протестировать ее на значениях
1) M = 32
N =24
2) M = 696
N =234
Постановка задачи:
- Составить программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:
А х В=НОД(А,В) х НОК (А,В)
Н А Ч А Л О
Ввод M и N
P=M*N
нет
M N
да
нет
да
M N
M=M-N
N=N-M
HOK=P/M
Вывод НОК
К О Н Е Ц
Источники материала:
«Информатика и ИКТ- 9» учебник И.Г.Семакин. Л.А. Залогова. С.В. Русаков. Л.В. Шестакова, М: Бином, 2012 г.