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

Июль 28, 2022

Главная
Информатика
Алгоритм Евклида

Содержание

2. Алгоритм Евклида ЕВКЛИД - древнегреческий математик. Работал в Александрии в 3 в. до н. э. Евклид
3. Постановка задачи: Требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел НОД двух натуральных
4. 12 2 18 2 6 2 9 3 3 3 3 3 1 1 НОД (12,
5. Алгоритм нахождения НОД Разложить числа на простые множители. Найти общие множители. Найти их произведение.
6. Алгоритм Евклида Идея алгоритма основана на двух свойствах: 1. Если M>N, то НОД (M, N) =
7. Алгоритм Евклида Если числа равны, то взять любое из них в качестве ответа, в противном случае
8. Блок-схема алгоритма Евклида Н А Ч А Л О Ввод M и N M ≠ N
9. Структура алгоритма Евклида Н А Ч А Л О Ввод M и N M ≠ N
10. Структура алгоритма Евклида Н А Ч А Л О Ввод M и N M ≠ N
11. Трассировочная таблица алгоритма Евклида М=32, N=24
12. Трассировочная таблица алгоритма Евклида М=32, N=24
13. Трассировочная таблица алгоритма Евклида М=32, N=24
14. Трассировочная таблица алгоритма Евклида М=32, N=24
15. Трассировочная таблица алгоритма Евклида М=32, N=24
16. Трассировочная таблица алгоритма Евклида М=32, N=24
17. Трассировочная таблица алгоритма Евклида М=32, N=24
18. Трассировочная таблица алгоритма Евклида М=32, N=24
19. Трассировочная таблица алгоритма Евклида М=32, N=24
20. Трассировочная таблица алгоритма Евклида М=32, N=24
21. Трассировочная таблица алгоритма Евклида М=32, N=24
22. Трассировочная таблица алгоритма Евклида М=32, N=24
23. Трассировочная таблица алгоритма Евклида М=32, N=24
24. Трассировочная таблица алгоритма Евклида М=32, N=24
25. Трассировочная таблица алгоритма Евклида М=32, N=24
26. Трассировочная таблица алгоритма Евклида М=32, N=24
27. Трассировочная таблица алгоритма Евклида М=32, N=24
28. Трассировочная таблица алгоритма Евклида М=32, N=24
29. Трассировочная таблица алгоритма Евклида М=32, N=24
30. Трассировочная таблица алгоритма Евклида М=32, N=24
31. Трассировочная таблица алгоритма Евклида М=32, N=24
32. Трассировочная таблица алгоритма Евклида М=32, N=24
33. Трассировочная таблица алгоритма Евклида М=32, N=24
34. Трассировочная таблица алгоритма Евклида М=32, N=24
35. Трассировочная таблица алгоритма Евклида М=32, N=24
36. Блок-схема алгоритма Евклида Н А Ч А Л О Ввод M и N M ≠ N
37. Программа на Паскале Program Evklid; var m, n: integer; begin writeln (’Введите m и n ’);
38. Отладка и тестирование Выполнить на компьютере программу. Протестировать ее на значениях: 1) M=32, N=24; 2) M=696,
39. Постановка задачи: Составить программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу: M х N
40. Н А Ч А Л О Ввод M и N M ≠ N N:=N-M M:=M-N M
42. Скачать презентацию

Слайд 2

Алгоритм Евклида
ЕВКЛИД - древнегреческий математик. Работал в Александрии в 3

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

Слайд 3

Постановка задачи:
Требуется составить программу определения наибольшего общего делителя (НОД) двух

натуральных чисел

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

Слайд 4

12 2 18 2
6 2 9 3

3 3 3 3
1 1

НОД (12, 18) = 2 · 3 = 6

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

Слайд 5

Алгоритм нахождения НОД
Разложить числа на простые множители.
Найти общие множители.
Найти их произведение.

Слайд 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.

Слайд 8