PPt4Web Хостинг презентаций

Главная / Физика / Алгоритм Евклида
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

Чтобы скачать данную презентацию, порекомендуйте, пожалуйста, её своим друзьям в любой соц. сети.

После чего скачивание начнётся автоматически!

Кнопки:

Презентация на тему: Алгоритм Евклида


Скачать эту презентацию

Презентация на тему: Алгоритм Евклида


Скачать эту презентацию



№ слайда 1 Алгоритм Евклида Составила: Антонова Е.П.2009г.
Описание слайда:

Алгоритм Евклида Составила: Антонова Е.П.2009г.

№ слайда 2 Постановка ЗадачиРассмотрим следующую задачу: требуется составить программу опре
Описание слайда:

Постановка ЗадачиРассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.Вспомним математику. Наибольший общий делитель двух натуральных чисел — это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:НОД(12,18) = 6.Обозначим исходные данные как М и N. Постановка задачи выглядит следующим образом:Дано: М, N Найти: НОД(М,N).

№ слайда 3 РешениеНе существует формулы для нахождения НОД двух чисел. Но зато достаточно д
Описание слайда:

РешениеНе существует формулы для нахождения НОД двух чисел. Но зато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида.

№ слайда 4 Идея алгоритмаИдея этого алгоритма основана на том свойстве, что если M>N, тоНОД
Описание слайда:

Идея алгоритмаИдея этого алгоритма основана на том свойстве, что если M>N, тоНОД(М,N) = НОД(М - N,N).Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа.

№ слайда 5 ДоказательствоПусть К — общий делитель М и. N (M>N). Это значит, что М = тК, N =
Описание слайда:

ДоказательствоПусть К — общий делитель М и. N (M>N). Это значит, что М = тК, N = пК, где т, п — натуральные числа, причем т>п. Тогда М - N = К(т - п), откуда следует, что К — делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности M-N, в том числе и наибольший общий делитель. Отсюда:НОД(М,N) = НОД(М - N,N).Второе очевидное свойство:НОД(М,М) = М.

№ слайда 6 Алгоритм Евклидаесли числа равны, то взять любое из них в качестве ответа, в про
Описание слайда:

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

№ слайда 7 Блок-схема алгоритма Евклида
Описание слайда:

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

№ слайда 8 Задание для практики:Напишите программу, реализующую алгоритм Евклида для нахожд
Описание слайда:

Задание для практики:Напишите программу, реализующую алгоритм Евклида для нахождения наибольшего общего делителя для двух натуральных чисел

№ слайда 9 Программа на языке ПаскальProgram Evklid; var М, N : integer; beginwriteln('Введ
Описание слайда:

Программа на языке ПаскальProgram Evklid; var М, N : integer; beginwriteln('Введите M и N'); readln(M,N); while MN do beginif M>N then M:=M-N else N:=N-Mend;write('HOD=',M) end.

Скачать эту презентацию


Презентации по предмету
Презентации из категории
Лучшее на fresher.ru