Условие
Решить
предыдущую задачу, если требуется, чтобы число
действий (выполняемых операторов присваивания) было порядка
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 уменьшается по крайней мере вдвое.
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
1 |
|
Название |
Переменные, выражения, присваивания |
|
параграф |
|
Номер |
1 |
|
Название |
Задачи без массивов |
|
задача |
|
Номер |
1.1.4 |
