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

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

Цель урока: освоить программирование циклов с предусловием на примере Алгоритма Евклида.

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

ЕВКЛИД, древнегреческий математик. Работал в Александрии в 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

Вывод НОК

К О Н Е Ц

Домашнее задание:

§16 стр.101

Составить программу нахождения наибольшего общего делителя трех чисел, используя формулу:

НОД (A, B, C) = НОД (НОД (A, B), C).