Задача 76200
|
|
 |
Условие
Решить предыдущую задачу, если требуется, чтобы число
действий (выполняемых операторов присваивания) было порядка
log n (то есть не превосходило бы
C log n для
некоторой константы C;
log n — это степень,
в которую нужно возвести 2, чтобы получить
n).
Решение
Внесём некоторые изменения во второе из предложенных решений предыдущей задачи:
k := n; b := 1; c:=a;
{a в степени n = b * (c в степени k)}
while k <> 0 do begin
| if k mod 2 = 0 then begin
| | k:= k div 2;
| | c:= c*c;
| end else begin
| | k := k - 1;
| | b := b * c;
| end;
end;
Каждый второй раз (не реже) будет выполняться первый
вариант оператора выбора (если k нечётно, то после
вычитания единицы становится чётным), так что за два цикла
величина k уменьшается по крайней мере вдвое.
