Возвести число а в натуральную степень 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 и то, что счет начинался с первого человека;

b) номер человека c которого начинался счет, если известно M и номер оставшегося человека L.

 

Для решения этой задачи используем структуру данных 'список'. Каждый элемент списка указывает на следующий за ним элемент (другими словами - хранит информацию о расположении следующего элемента).

a). Заведем массив A из N ячеек - по числу людей в круге. В каждую из ячеек A[i] занесем номер стоящего следующим за i-ым человека. Первоначально A[i]=i+1, i=1,...,.N-1, A[N]=1. Начиная счет от текущего человека (человека с номером IndTek, с самого сначала IndTek=1) будем делать ход - отсчитывать M ячеек, двигаясь по кругу в поисках человека, который должен выйти из круга. С учетом определения массива A это будет выглядеть следующим образом:

{IndTek - это номер человека, с которого начинается счет} for i:=1 to M-1 do {Отсчитываем M человек, начиная с IndTek} begin IndPred:=IndTek; {в IndPred сохраняем номер текущего человека в круге} IndTek:=A[IndTek]; {и вычисляем номер следующего за ним} end;

После выполнения этого цикла в переменной IndTek будет номер человека, на котором остановился счет (т.е. номер человека, который покинул круг), а в переменной IndPred - номер предшествующего ему человека в круге.

Удалим человека с номером IndTek. Для этого мы просто изменим ссылку A[IndPred] у предшествующего ему человека так, чтобы он указывал не на IndTek, а на следующего за IndTek, т.е. на A[IndTek], и новый отсчет M-того человека начнем со следующего за удаленным:

A[IndPred]:=A[IndTek]; IndTek:=A[IndTek];{Новый номер начального человека}

Все вышеописанные операции мы будем повторять до тех пор, пока в круге не останется одного единственного человека, т.е. до тех пор, пока A[IndTek] не станет равным IndTek, что означает, что следующим за человеком с номером IndTek является он сам.

Полностью весь фрагмент программы будет выглядеть так:

{Инициализация массива A}<P>for i:=1 to N-1 doA[i]:=i+1;A[N]:=1;{IndTek - это номер человека, с которого начинается счет}IndTek:=1;while A[IndTek] <> IndTek dobeginfor i:=1 to M-1 do {Отсчитываем M человек, начиная с IndTek}beginIndPred:=IndTek; {в IndPred сохраняем номер текущего человека в круге}IndTek:=A[IndTek]; {и вычисляем номер следующего за ним}end;A[IndPred]:=A[IndTek];IndTek:=A[IndTek]; {Новый номер начального человека}end;

writeln('Номер последнего оставшегося человека ',IndTek);

Решения пункта b).

Будем считать, что человек с номером N+i - это то же самое, что и человек с номером i.

Предположим, что как и в пункте a), что мы начали счет с первого человека, выбрасывали из круга M-того, и последний оставшийся в круге человек имеет номер K. Очевидно, что если бы мы начали счет со второго человека, то последний оставшийся в круге человек имел бы номер K+1,..., если с j-го, то K+j-1.

Если номер оставшегося человека L, то из равенства L=K+j-1 определяем номер j первого человека (если j<=0, то заменим j на j+N, считая как и раньше, что человек с номером N+j - это то же самое, что и человек с номером j).

Задача №19

Задана полоска длиной 2^k клеток и шириной в одну клетку. Полоску сгибают пополам так, чтобы правая половинка оказалась под левой. Сгибание продолжают до тех пор, пока сверху находится больше одной клетки. Необходимо пронумеровать клетки таким образом, чтобы после окончания сгибания полосы номера клеток в получившейся колонке были расположены в порядке 1,2,3,4,...,2^k.

 

Будем моделировать сложение полоски, затем пронумеруем получившуюся колонку клеток числами от 1 до 2ⁿ, после чего распечатаем числа, приписанные первой, второй,..., 2ⁿ-ой клетке исходной полоски.

Сначала создаем двусвязный список, состоящий из 2^k элементов. Поле next будет указывать на элемент находящийся под данным, а поле last - на элемент находящийся над данным. Для верхнего элемента last=0, а для нижнего next=n+1, где n-общее число элементов. Вначале длина верхней полоски равняется n элементов, после первого сгибания их она станет n/2, после второго - n/4, и т.д. Пусть в данный момент длина верхней полоски есть cn элементов. Значит нам необходимо cn/2 правых элементов опустить под cn/2 левых. Для этого запустим цикл, который будет менять i от 1 до cn/2 и на каждом шаге помещать (cn-i+1)-ю колонку элементов под i-ю, при этом порядок элементов в (cn-i+1)-ой колонке меняется на противоположный. После каждого сгибания cn уменьшается вдвое. Так продолжаем до тех пор пока cn>1.

Программа

{$A-,B-,D-,E+,F-,I-,L-,N-,O-,R-,S-,V-}{$M 65520,0,655360}uses crt;constmaxk = 13; {Максимальное значение для k}typeinput = recordlast,next,new: word;end;vark,i,j,n,cn,half: word;m: array[1..1 shl maxk] of input;Procedure concat(a,b: word);var i,j,nj: word;begini:=a;while m[i].next<>n+1 do i:=m[i].next;j:=b; while m[j].next<>n+1 do j:=m[j].next;while j<>0 dobeginnj:=m[j].last; m[i].next:=j; m[j].last:=i; i:=j; j:=nj;end;m[i].next:=n+1;end;beginWrite('Enter k...');readln(k);n:=1 shl k; {Определение длины полоски}for i:=1 to n do{Начальные значения}with m[i] dobeginlast:=0;next:=n+1;new:=0;end;cn:=n;while cn>1 do {Сгибание полоски}beginhalf:=cn div 2;for i:=1 to half do concat(i,cn-i+1);cn:=half;end;j:=1;for i:=1 to n do {Нумерация клеток}beginm[j].new:=i; j:=m[j].next;end;for i:=1 to n do write(m[i].new:5);writeln;

end.

Попробуйте найти формулу и написать программу, которая без моделирования складывания полоски по номеру клетки выдавала бы ее номер.

Задача №20

Квадрат разбит на 4^k равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной (правая половина подкладывается под левую) и горизонтальной (нижняя половина подкладывается под верхнюю) оси симметрии до тех пор, пока все клетки не будут расположены друг под другом. Требуется занумеровать клетки исходного квадрата таким образом, чтобы в результате выполнения операций перегиба номера клеток, расположенных друг под другом, образовали числовую последовательность 1,2,3,...,4^k, начиная с верхней клетки.

 

Решение этой задачи аналогично решению предыдущей задачи со сгибанием полоски с той лишь разницей, что тут будет поочередно производится два сгибания: сначала правая половина под левую, а затем нижнюю под верхнюю

{$A-,B-,D-,E+,F-,G-,I+,L-,N-,O-,R-,S-,V-,X-}{$M 16384,0,655360}uses crt;constmaxk = 6;typeinput = recordlast1,last2,next1,next2,new: word;end;vark,i,j,i1,i2,j1,j2,nj1,nj2,n,n1,cn,half: word;m: array[1..1 shl maxk,1..1 shl maxk] of input;Procedure concat(a,b,c,d: word);var i1,i2,j1,j2,nj1,nj2: word;begini1:=a; i2:=b;while (m[i1,i2].next1<>n+1) and (m[i1,i2].next2<>n+1) dobegini1:=m[i1,i2].next1; i2:=m[i1,i2].next2;end;j1:=c; j2:=d;while (m[j1,j2].next1<>n+1) and (m[j1,j2].next2<>n+1) dobeginj1:=m[j1,j2].next1; j2:=m[j1,j2].next2;end;while j1<>0 dobeginnj2:=m[j1,j2].last2; nj1:=m[j1,j2].last1;m[i1,i2].next1:=j1; m[i1,i2].next2:=j2;m[j1,j2].last1:=i1; m[j1,j2].last2:=i2;i1:=j1; i2:=j2; j1:=nj1; j2:=nj2;end;m[i1,i2].next1:=n+1; m[i1,i2].next2:=n+1;end;beginWrite('Введите k...');readln(k);n:=1 shl k; {Определение числа клеток в одной строке или столбце}n1:=n*n; {Определение числа клеток в матрице}for i:=1 to n dofor j:=1 to n do with m[i,j] do beginlast1:=0; next1:=n+1;last2:=0; next2:=n+1;new:=0;end;cn:=n;while cn>1 do {сгибание матрицы}beginhalf:=cn div 2;for i:=1 to half do {сгиб по вертикали}for j:=1 to cn do concat(j,i,j,cn-i+1);for i:=1 to half do {сгиб по горизонтали}for j:=1 to half do concat(i,j,cn-i+1,j);cn:=half;end;j1:=1;j2:=1;for i:=1 to n1 do {Назначение клеткам новые номера}beginm[j1,j2].new:=i;nj1:=m[j1,j2].next1; nj2:=m[j1,j2].next2;j1:=nj1; j2:=nj2;end;for i:=1 to n do {Вывод результатов}beginfor j:=1 to n do write(m[i,j].new:8);writeln;end;end.

Задача №21

Имеется n черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая под низ стопки, третья- на стол, четвертая - под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.

 

Проще всего взять и промоделировать раскладку карточек: берем стопку из n черных и белых карточек и начинаем расклад как говорится в задаче - первая на стол, вторая под низ, третья на стол, и т.д. при этом первой выложенной карточке приписывается белый цвет, а каждой последующей - цвет, не совпадающий с цветом предыдущей карточки. Повторяет так, пока не найдем раскраску всех n карточек.

Для этой задачи возьмем такую структуру данных как список. У списка есть начало и конец, и каждый элемент его указывает на следующий за ним элемент. Будем считать, что у последнего элемента списка указатель на следующий за ним равен 0. Список можно представлять массивом. Например, если в списке 4 элемента, то массив будет выглядеть так:

т.е. за первым элементом находится A[1]=2 элемент,..., за 4-ым - A[4]=0 (т.к. 4-ый элемент списка последний).

Пусть у нас есть указатель на начальный элемент списка и на последний (BEG и FIN соответственно). В списке n элементов.

Рассмотрим процедуру удаления элемента из начала списка (это соответствует переносу карточки на стол):

BEG:=A[BEG]; {теперь новый первый элемент списка - второй элемент старого списка}

Рассмотрим операторы перестановки элемента из начала списка в конец (это соответствует перемещению карточки сверху стопки под низ ее):

A[FIN]:=BEG; {следующей за последним элементом - бывший первый}FIN:=BEG; {меняем ссылку на последний элемент}BEG:=A[BEG] {новый первый элемент}A[FIN]:=0 {корректировка ссылки у последнего элемента}Фрагмент программы будет выглядеть так:for i:=1 to N-1 do A[i]:=i+1;A[N]:=0; {установка ссылок в списке}BEG:=1; FIN:=N;COLOR:=1; {белый цвет = 1, черный = 0}while A[BEG]<>0 do {пока первый элемент не является} {одновременно и последним}beginBEFORE:=BEG; {сохраняем индекс начала списка}BEG:=A[BEG]; {удаляем первый элемент из списка}A[BEFORE]:=COLOR; {раскрашиваем удаленный элемент} {в нужный цвет}COLOR:=1-COLOR; {меняем цвет}A[FIN]:=BEG; {переставляем элемент из}FIN:=BEG; {начала списка в конец}BEG:=A[BEG];A[FIN]:=0end;A[BEG]:=COLOR; {раскрашиваем последний элемент}{списка}for i:=1 to N do {распечатка цветов}if A[i]=0then writeln('элемент',i,' - черный')else writeln('элемент',i,' - белый');

Задача №22

Фоpма тела задана матpицей А pазмеpности M x N. Элементы матpицы - натуpальные числа. Элемент А (i,j) соответствует высоте гоpизонтальной квадpатной площадки pазмеpа 1 x 1 относительно нижнего основания.Нижнее основание фоpмы горизонтально.