ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 76214
Темы:    [ Знакомство с циклами ]
[ Задачи с целыми числами ]
[ НОД и НОК. Алгоритм Евклида ]
Сложность: 2
Классы:
В корзину
Прислать комментарий

Условие

Написать вариант алгоритма Евклида, использующий соотношения

НОД(2a, 2b) = 2·НОД(a,b),
НОД(2a,b) = НОД(a,b)      при нечётном b,

не включающий деления с остатком, а использующий лишь деление на 2 и проверку чётности. (Число действий должно быть порядка log k для исходных данных, не превосходящих k.)

Решение

      m:= a; n:=b; d:=1;
      {НОД(a,b) = d * НОД(m,n)}
      while not ((m=0) or (n=0)) do begin
      | if (m mod 2 = 0) and (n mod 2 = 0) then begin
      | | d:= d*2; m:= m div 2; n:= n div 2;
      | end else if (m mod 2 = 0) and (n mod 2 = 1) then begin
      | | m:= m div 2;
      | end else if(m mod 2 = 1) and (n mod 2 = 0) then begin
      | | n:= n div 2;
      | end else if (m mod 2=1) and (n mod 2=1) and (m>=n) then begin
      | | m:= m-n;
      | end else if (m mod 2=1) and (n mod 2=1) and (m<=n) then begin
      | | n:= n-m;
      | end;
      end;
      {m=0 => ответ=d*n; n=0 => ответ=d*m}
Оценка числа действий: каждое второе действие делит хотя бы одно из чисел m и n пополам.

Источники и прецеденты использования

книга
Автор А.Шень
Название Программирование: теоремы и задачи
Издательство МЦНМО
Издание второе
Год издания 2004
глава
Номер 1
Название Переменные, выражения, присваивания
параграф
Номер 1
Название Задачи без массивов
задача
Номер 1.1.18

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .