24 января. Информатика. 8в, 8г классы

 

24 января. Информатика. 8в, 8г классы

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

Для освоения материала сегодняшнего урока вам понадобится знание циклов и ветвлений.

Сегодня мы рассмотрим три алгоритма на нахождение наибольшего общего делителя двух целых чисел, два из которых непосредственно связывают с именем Евклида.
Наибольший общий делитель (НОД) двух чисел a и b — наибольшее целое число, которое делит их оба.
Пример: НОД(25, 5) = 5; НОД(12, 18) = 6.

Переборный алгоритм
Начинаем перебор с d — наименьшего из двух чисел. Это первый, очевидный кандидат на роль их наибольшего общего делителя. А затем, пока d не делит оба числа, уменьшаем его на единицу. Как только такое деление будет обеспечено, останавливаем уменьшение d.

  1. var
  2.  a, b, d: integer;
  3. begin
  4.  write('Введите два числа: ');
  5.  readln(a, b);
  6.  if a
  7.  {так как мы используем цикл с постусловием,
  8.  необходимо минимальное значение увеличить на один,
  9.  иначе цикл repeat,в силу своих конструктивных особенностей,
  10.  не учтет это минимальное число
  11.  и не сделает его кандидатом в НОД. Например, 5 и 25.}
  12.  repeat d := d - 1
  13.  until (a mod d = 0) and (b mod d = 0);
  14.  write('NOD = ', d)
  15. end.

Обратимся к этой программе, например, с числами 30 и 18. Тогда на пути к ответу(числу 6) ей придется перебрать числа: 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6.


Алгоритм Евклида «с вычитанием»

Пусть a и b — целые числа, тогда верны следующие утверждения:

1.      Все общие делители пары a и b являются также общими делителями пары a — b, b;

2.      И наоборот, все общие делители пары a — b и b являются также общими делителями пары a и b;

3.      НОД(A,  B) = НОД(A — B, B) , если A > B;

4.      НОД(A, 0) = A.

Вкратце алгоритм Евклида «с вычитанием» будет таким: Вычитаем из большего числа меньшее и заменяем большее на разность до тех пор, пока одно из чисел не обратится в нуль. Тогда оставшееся ненулевое число — наибольший общий делитель.

Пример. Пусть а = 82 и b = 60. НОД(82, 60) = НОД(22, 60) = НОД(22, 38) = НОД(22, 16) = НОД(6, 16) = НОД(6, 10) = НОД(6, 4) = НОД(2, 4) = НОД(2, 2) = НОД(2, 0) = 2.

На предпоследнем шаге алгоритма, перед появлением 0, оба числа равны, иначе не мог возникнуть 0. Поэтому мы будем извлекать НОД именно в этот момент.

пример:

  1. var
  2.  a, b: integer;
  3. begin
  4.  write('a = ');
  5.  readln(a);
  6.  write('b = ');
  7.  readln(b);
  8.  while a b do
  9.    if a > b then
  10.      a := a - b
  11.    else
  12.      b := b - a;
  13.  writeln('NOD = ', a);
  14. end.

Алгоритм Евклида с «делением»

Пусть a и b — целые числа, а r — остаток от деления a на b. Тогда НОД(a, b) = НОД(b, r).

Эта формула также позволяет свести вычисление наибольшего общего делителя одной пары чисел к вычислению наибольшего обшего делителя другой пары чисел.

Пример. НОД(82, 60) = НОД(22, 60) = НОД(22, 16) = НОД(6, 16) = НОД(6, 4) = НОД(2, 4) = НОД(0, 2) = 2.

  1. var
  2.  a, b: integer;
  3. begin
  4.  write('a = ');
  5.  readln(a);
  6.  write('b = ');
  7.  readln(b);
  8.  while (a 0) and (b 0) do
  9.    if a >= b
  10.    then
  11.      a := a mod b
  12.    else
  13.      b := b mod a;
  14.  write(a + b)
  15. end.
Вам помогут:

Учебник: «Информатика, 8 класс», К.Ю.Поляков, параграф 20

Презентация: Алгоритм Эвклида.ppt

Cайт: http://learnpascal.ru/algoritmy/algoritm-evklida-1.html#more-1355

Вложенное задание выбираете по уровню и присылаете мне на электронную почту: или в соц. сетях

*
 
....