ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 76231
УсловиеДаны натуральные числа а и b, причём
b > 0.
Найти частное и остаток при делении a на b,
оперируя лишь с целыми числами и не используя операции
div и mod, за исключением деления на 2 чётных
чисел; число шагов не должно превосходить
C1log(a/b) + C2 для некоторых констант C1, C2.
Решениеb1 := b; while b1 <= a do begin | b1 := b1 * 2; end; {b1 > a, b1 = b * (некоторая степень 2)} q:=0; r:=a; {инвариант: q, r - частное и остаток при делении a на b1, b1 = b * (некоторая степень 2)} while b1 <> b do begin | b1 := b1 div 2 ; q := q * 2; | { a = b1 * q + r, 0 <= r, r < 2 * b1} | if r >= b1 then begin | | r := r - b1; | | q := q + 1; | end; end; {q, r - частное и остаток при делении a на b} Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |
Проект осуществляется при поддержке