Возвести число А в натуральную степень n за как можно меньшее количество умножений

Можно, конечно, число A умножить само на себя n-1 раз, но для этого надо выполнить n-1 операцию умножения. Рассмотрим метод, требующий меньшего числа умножений (он, однако, не всегда дает минимальное число умножений).

Если n - четное, n=2m то будем вычислять Aⁿ, используя тождество A^am=(A^m)²;

если же n=2m+1, то

A^2m+1=(A^2m)*A=((A^m)²)*A.

Так(м образом, возведение A в 13 степень будет выглядеть следующим образом:

(A¹³)=((A⁶)²)*A=(((A³)²)²)*A=(((A*A*A)²)²)*A

и вычисление требует 5 операций умножения.

Используя данный метод, для возведения в степень n потребуется порядка log₂(n) операций умножения.

Программа на Паскале может выглядеть так:

var A,N: integer;function power(N: integer): integer;beginif N>1then if odd(N) {N нечетно?}then power:=SQR(power(N div 2))*A else power:=SQR(power(N div 2))else power:=Aend;beginread(A,N);writeln(power(N));

end;

Можно ту же самую идею реализовать и по другому ( далее мы приводим выдержку из книги Д.Кнута "Искусство программирования для ЭВМ", т.2, с.482):

"Запишем n в двоичной системе счисления и заменим в этой записи каждую цифру "1" парой букв SX, а каждую цифру "0" - буквой S, после чего вычеркнем крайнюю левую пару букв SX. Результат, читаемый слева направо, превращается в правило вычисления xⁿ, если букву "S" интерпретировать как операцию возведения в квадрат, а букву "X" - как операцию умножения на x. Например, если n=23, то его двоичным представлением будет 10111; строим последовательность SX S SX SX SX, удаляем из нее начальную пару SX и в итоге получаем следующее правило вычисления: S SX SX SX. Согласно этому правилу, мы должны "возвести x в квадрат, затем снова возвести в квадрат, затем умножить на x, возвести в квадрат, умножить на x, возвести в квадрат и, наконец, умножить на x"; при этом мы последовательно вычисляем x², x⁴, x⁵, x¹⁰, x¹¹, x²², x²³.

Этот "бинарный метод" легко обосновать, рассмотрев последовательность получаемых в ходе вычисления показателей: если "S" интерпретировать как операцию умножения на 2, а "X" - как операцию прибавления 1 и если начать с 1, а не с x, то наше правило дает нам в соответствии со свойствами двоичной системы счисления число n".

Приведенный метод не дает минимального числа операций умножения. Для вычисления x²³ нам, по изложенному выше методу, потребуется 7 операций умножения. В действительности их необходимо только 6:

x -> x² -> x³ -> x⁵ -> x¹⁰ -> x²⁰ -> x²³.

Задача №16

Найти максимальную по длине последовательность z, полученную вычеркиванием элементов как из x, так и из y.

Пусть x=x₁,x₂, ... ,x_m, y=y₁,y₂, ... ,y_n.

Заведем матрицу A[0..m,0..n]. Элемент A[i,j] будет длиной

максимальной общей подпоследовательности y x₁, ... ,x_i и y y₁, ..., y_j. Сначала A[i,0]=A[0,j]=0, i=0, ... ,m, j=0, ... ,n. Пусть x_i=y_j, тогда требуется увеличить длину максимальной общей подпоследовательности x₁, ... ,x_i-1 и y₁, ... ,y_j-1 на 1: A[i,j]=A[i-1,j-1]+1, если x_i=y_j. В случае, если x_i<>y_j, то, очевидно, A[i,j]=max{A[i-1,j],A[i,j-1],A[i-1,j-1]}, но так как всегда A[i-1,j-1]<=A[i,j-1], то A[i,j]=max{A[i-1,j],A[i,j-1]}. Величина A[m,n] и дает длину максимальной общей подпоследовательности. Найдем саму подпоследовательность. Пусть A[m,n]=d. Двигаясь по последней строке справа налево ищем самый левый элемент в этой строке со значением d. Двигаемся от него вверх по столбцу в поиске элемента столбца с минимальным первым индексом и значением d. Пусть это A[i,j]. Элемент A[i-1,j-1] обязан быть равен d-1, а x_i и y_i - это последние общие совпадающие элементы в x и y. Начиная от элемента A[i-1,j-1] повторяем, как было описано выше, движение влево и вверх по матрице, находим предпоследний совпадающий элемент в x и y, и т.д.

Программа:

for i:=0 to m do A[i,0]:=0;

for j:=0 to n do A[0,j]:=0; for i:=1 to m do

for j:=1 to n do

if x[i]=y[i]

then A[i,j]:=A[i-1,j-1]+1

else A[i,j]:=max(A[i-1,j],A[i,j-1]);

writeln('Длина последовательности =',A[m,n]); d:=A[m,n]; i:=m; j:=n;

while (d<>0) do begin

while A[i,j-1]=d do j:=j-1;

while A[i-1,j]=d do i:=i-1;

write('Элемент последовательности номер', d,'есть', x[i]);

i:=i-1; j:=j-1; d:=d-1;

{переход к поиску предшествующего элемента в последовательности}

end;

Задача №17

Пусть x и y - две бинарных последовательности (т.е. элементы последовательностей - нули и единицы); x и y можно рассматривать как запись в двоичной форме некоторых двух натуральных чисел.

Найти максимальное число z, двоичную запись которого можно получить вычеркиванием цифр как из x, так и из y. Ответ выдать в виде бинарной последовательности.

В последовательностях x и y избавляемся от лидирующих нулей. Если хоть одна из последовательностей стала пустой, то z=0. Иначе крайние левые цифры и в x и в y есть 1.

Запускаем на полученных последовательностях алгоритм задачи 24 (для получения максимального z необходимо, чтобы старшая цифра z была 1 и двоичная запись z имела максимальную длину), но при этом для каждого A[i,j] - длины последовательности, необходимо хранить добавочно и саму последовательность; при присвоении значения A[i,j] одновременно будем запоминать и последовательность максимальной длины. Если таких несколько, то берем из них последовательность с максимальным значением. Поэтому алгоритм задачи 23 запишется так:

Пусть S[0..m,0..n] - массив строк. В S[i,j] будет храниться подпоследовательность, длина которой A[i,j].

for i:=0 to m do A[i,0]:=0;for j:=0 to n do A[j,0]:=0;for i:=0 to m dofor j:=0 to n do S[i,j]:='';for i:=1 to m dofor j:=1 to n do beginif x[i]=y[j]then beginA[i,j]:=A[i-1,j-1]+1; S[i,j]:=S[i-1,j-1]+x[i];end;A[i,j]:=max(A[i,j],A[i-1,j],A[i,j-1]); S[i,j]:=max(S[i,j],S[i-1,j],S[i,j-1]);end;

write(A[m,n],'- длина',S[m,n]);

Попробуйте не заводить массив S[0..m,0..n], а обойтись одномерным массивом S[0..n].

Задача №18

Вокруг считающего стоит N человек, из которых выделен первый, а остальные занумерованы по часовой стрелке числами от 2 до N. Считающий, начиная с кого-то, ведет счет до M. Человек на котором остановился счет, выходит из круга. Счет продолжается со следующего человека и так до тех пор, пока не останется один человек.

Определить

a) номер оставшегося человека, если известно M и то, что счет начинался с первого человека;