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

Содержание

• 
  Слайд 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 MN do begin if M>N then M:=M-N else N:=N-M end; write('HOD=',M) end.