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

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать Алгоритм Евклида Составила: Антонова Е.П. 2009г.. Презентация содержит 9 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

Программа на языке Паскаль Program Evklid; var М, 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('HOD=',M) end.