Задача 76231

Темы:    [ Знакомство с циклами ] [ Задачи с целыми числами ]

Сложность: 2 Классы:

Условие

Даны натуральные числа а и b, причём b > 0. Найти частное и остаток при делении a на b, оперируя лишь с целыми числами и не используя операции div и mod, за исключением деления на 2 чётных чисел; число шагов не должно превосходить C₁log(a/b) + C₂ для некоторых констант C₁, C₂.

Решение

        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
глава
Номер	1
Название	Переменные, выражения, присваивания
параграф
Номер	1
Название	Задачи без массивов
задача
Номер	1.1.35