Решения: Рекуррентные соотношения и динамическое программирование
Решение задачи 1.
Можно, конечно, каждый раз вычислять очередное p!, затем 1/p!, и полученное слагаемое добавлять к сумме. Но обратим внимание на следующее очевидное равенство:
1/(p+1)! = (1/p!)/(p+1),
и программа вычисления запишется следующим образом
S:=1; p:=1; {S = p = 1/1!}
for i:=2 to k do
begin
p:=p/i;
S:=S+p;
end;
1) Самое простое - это перебрать все возможные комбинации шести цифр и подсчитать число "счастливых" билетов.
Count:=0; {количество "счастливых" билетов}
for a1:=0 to 9 do
for a2:=0 to 9 do
for a3:=0 to 9 do
for a4:=0 to 9 do
for a5:=0 to 9 do
for a6:=0 to 9 do
if a1+a2+a3=a4+a5+a6
then Count:=Count+1;
Условие if во вложенных циклах будет проверяться 106 раз, поэтому будем говорить, что сложность этого алгоритма 106.
2) Обратим внимание на то, что в "счастливом" билете последняя цифра a6 однозначно определяется первыми пятью:
a6=(a1+a2+a3)-(a4+a5).
Если 0<=a6<=9, то билет "счастливый", иначе - нет. Таким образом, мы можем убрать шестой вложенный цикл:
Count:=0;
for a1:=0 to 9 do
for a2:=0 to 9 do
for a3:=0 to 9 do
for a4:=0 to 9 do
for a5:=0 to 9 do
begin
a6:=(a1+a2+a3)-(a4+a5);
if (a6>=0) and (a6<=9)
then Count:=Count+1;
end;
Сложность алгоритма 105.
3) Если комбинаций a1 a2 a3 первых трех цифр с суммой T=a1+a2+a3 насчитывается C[T], то всего "счастливых" билетов с суммой половины T=a1+a2+a3=a4+a5+a6 будет C[T]*C[T]. Всех возможных сумм T-28 (от 0=0+0+0 до 27=9+9+9). Подсчитаем C[i], i=0, ..., 28, затем найдем интересующее нас количество "счастливых" билетов
C[0]2 + C[1]2 + ... + C[27]2.
Заметим, что "счастливых" билетов с суммой T столько же, сколько и с суммой 27-T. Действительно, если билет a1 a2 a3 a4 a5 a6 с суммой T - "счастливый", то таковым же является и билет (999999 - a1 a2 a3 a4 a5 a6) с суммой 27-T. Поэтому число билетов можно вычислять и по формуле
2*(C[0]2+ ... +C[13]2),
т.е.рассматривать только суммы T от 0 до 13.
var C:array[0..13] of longint;
Count:=0;
for T:=0 to 13 do C[T]:=0;
for a1:=0 to 9 do {перебираем все}
for a2:=0 to 9 do {возможные a1 a2 a3}
for a3:=0 to 9 do
begin
T:=a1+a2+a3;
C[T]:=C[T]+1 {нашли еще один билет}
end; {с суммой T}
for T:=0 to 13 do {считаем число билетов} Count:=Count+C[T]*C[T];
Count:=Count*2; {удваиваем сумму}
Сложность этого алгоритма 103.
4) В пункте 3 мы перебирали комбинации цифр и искали количество комбинаций с суммами C[T]. Сейчас мы пойдем от суммы T, и по ней будем определять, какое количество комбинаций a1 a2 a3 ее имеет.
Итак T=a1+a2+a3.
Минимальное значение, которое может принимать a1, - это MAX{0,T-18}. Член T-18 появляется из следующих соображений: пусть a2=a3=9, тогда a1=T-18, но a1 не может быть меньше 0. Максимальное значение a1=MIN{9,T} (так как a2 и a3 неотрицательны, то a1<=T и одновременно a1<=9).
Для цифры a2 аналогично получаем, что она лежит в пределах от max{0,T-a1-9} до min{9,T-a1}.
Цифра a3 по T, a1 и a2 определяется однозначно.
Получаем, что комбинаций a1 a2 a3 с суммой T и с первой цифрой a1 столько же, сколько возможных цифр a2, а именно
min{9,T-a1}-max{0,T-a1-9}+1.
Как и в пункте 3 мы можем рассматривать диапазон сумм T от 0 до 13.
Count:=0;
for T:=0 to 13 do
begin
CT:=0;
for a1:=max(0,T-18) to min(9,T) do CT:=CT+min(9,T-a1)-max(0,T-a1-9)+1;
Count:=Count+CT*CT
end;
Count:=Count*2;
Сложность этого алгоритма (т.е. количество выполнений операций присваивания внутри двух вложенных циклов) не превышает 140.
Задача имеет очевидное решение, которое состоит в генерации всех 2*n-разрядных чисел и проверке их на требуемое свойство. Однако общее количество таких чисел равно 102n и поэтому при n>3 практически очень трудно получить результат на ЭВМ. Следовательно необходимо разработать алгоритм, не требующий генерации чисел.
Определим через S(k,i) количество k-разрядных чисел, сумма цифр которых равна i. Например, S(2,3)=4, так как существует 4 двуразрядных числа (03,12,21,30), сумма цифр которых равна 3. Легко заметить, что S(1,i)=1 при i<10 и S(1,i)=0 при i>9. Предположим теперь, что мы сумели вычислить значения величин S(n,i) для всех i от 0 до 9*n, т.е. мы знаем, сколько существует n-разрядных чисел с суммой цифр, равной 0,1,...,9*n (максимальное число цифр в n-разрядном числе). Тогда нетрудно убедиться, что общее количество 'счастливых' 2*n-разрядных чисел равно
Действительно, каждое 'счастливое' 2*n-разрядное число может быть получено склейкой двух произвольных n-разрядных чисел с одинаковой суммой цифр.
Таким образом, необходимо уметь вычислять значения величин S(k,i) для всех k<=n,i<=9*k. Определим способ вычисления S(k+1,i) через значения величин S(k,j), j<=i. Понятно, что любое k+1-разрядное число может быть получено из k-разрядного добавлением еще одного разряда (цифры). Следовательно
S(k+1,i) = S(k,i-ц1)+S(k,i-ц2)+...,
где ц1,ц2,... - возможные добавленные цифры. Ясно, что это 0,1,...,m где m=min(9,i). Следовательно,
Очевидное решение задачи предполагает разложение числа N на всевозможные суммы таким образом, чтобы каждое слагаемое в сумме не превосходило k. Очевидно, что таких разложений очень много, особенно если учитывать, порядок слагаемых в разложении существенен, так как он соответствует различной последовательности ходов фишки.
Обозначим через S(i) количество различных путей, по которым фишка может пройти поле от начала до позиции с номером i. Предположим теперь, что для любого j от 1 до i известны значения величин S(j). Задача состоит в определении правила вычисления значения S(i+1), используя значения известных величин. Легко заметить, что в позицию с номером i+1 фишка может попасть из позиций i, i-1,...,i-k. Следовательно,
S(i+1)=S(i)+S(i-1)+...+S(i-k).
Таким образом, вычисляя последовательно значения величин S(1), S(2),..., S(N) по описанному выше правилу, получаем значение S(N), которое и указывает общее количество различных путей, по которым фишка может пройти поле от начала до позиции с номером N.
Если покупатель отдаст все свои купюры продавцу, то понятно, что для решения исходной задачи размер минимальной сдачи, которую продавец не может вернуть, используя любые имеющиеся теперь у него купюры C[i] (его и покупателя). Для этого удобно отсортировать купюры согласно их достоинства в порядке неубывания.
Предположим, что продавец может вернуть любую сдачу от 1 до S, используя только меньшие i купюр. Для следующей (i+1)-ой купюры достоинства C[i+1] возможны 2 ситуации.
1. C[i+1]<S+2. Тогда понятно, что продавец может вернуть любую сдачу от 1 до C[i+1]+S, т.к. любая из этих сумм представима либо первыми i купюрами, либо (i+1)-ой купюрой вместе с некоторыми из первых i купюр.
2. C[i+1]>S+1. Тогда понятно, что продавец не может вернуть сдачу S+1.
Опишем процедуру вычисления S.
S:=0;
i:=1;
пока (i<=N) и (C[i]<=S+1)
нц
S:=S+C[i];
i:=i+1
кц
Если значение S не меньше суммарного количества денег покупателя, то покупатель может купить товар любой доступной ему стоимости, точно рассчитавшись за покупку. Иначе P=A[1]+...+A[N]-S.
Если покупатель отдаст все свои купюры продавцу, то понятно, что для решения исходной задачи надо определить, может ли продавец вернуть сумму H(1)+...+H(n)+B(1)+...+B(l)-S, используя любые имеющиеся теперь у него купюры M[i] (его и покупателя). Для этого удобно отсортировать купюры согласно их достоинства в порядке неубывания.
Пусть P=M[1]+M[2]+ ... +M[n+l].
Решим чуть более общую задачу: найдем все непредставимые данными купюрами суммы на промежутке от 0 до P.
Заведем массив A[0 .. P] натуральных чисел. Элемент A[i]=1, если мы можем выплатить сумму i (т.е. существует набор купюр суммарного достоинства i), и A[i]=0 иначе.
Будем строить всевозможные суммы, используя последовательно 0,1,2,...,N купюр.
Очевидно, что сумма из ноля купюр - это ноль, поэтому сначала A[0]=1.
Предположим, что мы нашли всевозможные суммы, которые можно составить, используя не более (k-1) - ой купюры M[1], ..., M[K-1]. Добавим еще одну купюру M[k].
Теперь мы можем выплатить следующие суммы:
1) Все суммы, которые можно было составить с помощью купюр M[1], ... , M[K-1].
2) Все суммы, которые можно было составить с помощью купюр M[1], ... , M[K-1], увеличенные на M[K].
Расстановка новых пометок в массиве A может выглядеть следующим образом:
for i:=P-M[K] downto 0 do
if A[i]=1
then A[i+M[K]]:=1;
Мы проходим по массиву справа налево для того, чтобы не использовать повторно впервые образованную на данном шаге сумму.
После выполнения n+l шагов алгоритм заканчивает работу.
Если известно, что H(1)+...+H(n)+B(1)+...+B(l)-S не превосходит некоторой константы D, то тогда массив A имеет смысл брать не из P, а из D элементов.
Решается аналогично задаче 7. При этом достаточно завести массивы
var A, KOL, PredSum, B: array [0..P] of byte;
Назначение массива A - как и в предыдущей задаче. Массив В служит для временного хранения предыдущих сумм. Элементы KOL[i] и PredSum[i] указывают соответственно минимальное количество элементов, участвующих в получении суммы со значением i и предыдущую сумму, из которой была получена добавлением одного слагаемого сумма i. Формирование этих массивов осуществляется параллельно с заполнением массива А. Сначала
A[0]=1, A[i]=0 для всех i>0,
KOL[0]=0, KOL[i]=254, для всех i>0,
(считаем, что если KOL[i]=254, то сумму i набрать нельзя),
PredSum[i]=0 для всех i>0;
for i:=1 to N do {цикл по всем купюрам}
begin
for j:=M[i] to P
{цикл по всем возможным суммам с участием купюры M[i]}
if (A[j-M[i]]<>0) and{если можно набрать сумму j-M[i]}
(KOL[j]>KOL[j-M[i]]+1)
{и добавлением купюры M[i] мы получаем сумму
j из меньшего количества купюр}
then begin
KOL[j]:=KOL[j-M[i]]+1 {то запоминаем это новое количество и
в B[j] заносим новую}
B[j]:=j-M[i];{информацию о предыдущей сумме}
A[j]:=1;{и помечаем, что сумму j набрать можно} end
else B[i]:=PredSum[j]; {иначе дублируем старую информацию}
for j:=M[i] to P do {Дублируем информацию из B}
PredSum[j]:=B[j]; {в PredSum}
end;
Почему мы не можем непосредственно записывать новую информацию о предыдущей сумме в массив PredSum? Обратите внимание, что массивы A и KOL дублируют друг друга. Напишите тот же фрагмент программы, объединив функции массивов A и KOL в одном массиве A. После завершения работы предыдущего фрагмента если A[S]=1, то сумму S набрать можно с помощью KOL[S] купюр. Предыдущая сумма (до добавления последней купюры) была S'= PredSum[S], следовательно последняя купюра есть S-PredSum[S]. Аналогично выписываем купюры, требуемые для представления суммы S' (используя PredSum[S']).
Очевидное решение задачи состоит в использовании некоторой процедуры, которая по заданным координатам (номеру строки i и номеру столбца j) элемента определяет максимальное значение элементов, расположенных в нужной части матрицы A.
Однако нетрудно заметить, что для элементов первого столбца матрицы В справедливо соотношение B[i,1]=A[i,1], i=1,...N. Вычисление же других столбцов можно проводить следующим образом:
В элемент a[i,j] матрицы будем заносить длину максимальной стороны квадрата из единиц, у которого элемент (i,j) есть верхний левый угол (очевидно, что если a[i,j]=0, то квадрат построить нельзя).
Матрицу A будем просматривать по строкам справа налево, снизу вверх.
Предположим, что текущий просматриваемый элемент a[i,j] (все элементы, лежащие в строках с номерами больше i, равно как и все элементы строки i правее a[i,j] считаются уже к этому моменту просмотренными).
Если элемент a[i,j]=0, то его значение остается нулевым. Если же a[i,j]=1, то для того, чтобы найти максимальный размер квадрата из единиц, у которого (i,j) - верхний левый угол, проанализируем уже просмотренные элементы a[i,j+1], a[i+1,j+1], a[i+1,j] - соответственно длины сторон максимальных квадратов с левым углом справа, по диагонали вниз и просто вниз от данного элемента. Квадрат с верхним левым углом (i,j) может протянуться вправо на больше чем на a[i+1,j]+1, вниз - не больше чем на a[i,j+1]+1 и по диагонали не больше чем на a[i+1,j+1]+1. Следовательно, максимальная сторона квадрата есть
a[i,j]=min{a[i,j+1],a[i+1,j],a[i+1,j+1]}+1.
Программа:
MaxDim:=0; {текущая максимальная длина стороны}
for i:=n-1 downto 1 do
for j:=m-1 downto 1 do
if a[i,j]<>0
then begin
a[i,j]:=min(a[i,j+1],a[i+1,j+1],a[i+1,j])+1;
if a[i,j]>MaxDim
then a[i,j]:=MaxDim
end;
writeln('максимальная длина стороны= ',MaxDim);
Пусть верхний левый угол матрицы имеет индекс (1,1).
Будем для каждой строки i формировать вектор p[1..M] такой, что p[j] есть число последовательных единичных элементов в столбце j, начиная с элемента (i,j) и выше его. Таким образом, если p[j]=0, то A[i,j]=0, а если p[j]=u>0, то
A[i,j]=A[i,j+1]= ... =A[i,j-u+1]=1,
а элемент A[i,j-u] нулевой (если, конечно, такой элемент есть в матрице, т.е. если j-u>0).
Тогда площадь (сумма элементов) единичного прямоугольника S_i(L,R) с нижними правым и левым углами в элементах (i,R) и (i,L) соответственно есть площадь основания (R-L+1) умноженная на высоту этого прямоугольника
h(L,R)=минимальное p[i] по всем j, изменяющимся от L до R.
Для каждой строки i надо найти максимум величины S_i(L,R) при 1<=L<=R<=M, а максимум по всем строкам и даст искомую величину.
Очевидно, что для первой строки
p[j]=A[1,j].
Если мы знаем вектор l для строки i, то мы можем вычислить его для строки (i+1) по следующей формуле
if A[i+1,j]=0 then p[j]:=0
else p[j]:=p[j]+1;
Более коротко это же можно записать и так: p[j]:=(p[j]+1)*A[i+1,j];
Будем рассматривать вектор p, соответствующий строке i, и для каждого индекса j, 1<=j<=M, определим максимальный размер единичного прямоугольника с высотой p(j), располагающегося в столбцах с номерами от L(j) до R(j), L(j)<=j<=R(j), нижняя граница которого строка i. Очевидно, что L(j) есть увеличенный на единицу индекс первого меньшего чем p[j] элемента вектора p при просмотре p от j-го элемента влево, или L(j)=1, если такого меньшего элемента нет. Аналогично, R(j) есть уменьшенный на 1 индекс первого меньшего чем p[j] элемента вектора p при просмотре p от j-го элемента вправо, или R(j)=M, если такого элемента нет.
Как быстро вычислить L(j) и R(j)? Используя алгоритм 8 Главы "Структуры данных" мы можем найти все L и R за два прохода по вектору p:
Будем заполнять массив R. Вектор p просматриваем слева направо. Организуем стек для позиций элементов. Для каждого текущего p[j] будем выталкивать из стека все позиции, на которых стоят элементы большие текущего, и заносить в соответствующие этим позициям места массива R число (j-1). Замет позицию текущего элемента j поместить в стек. После просмотра всех элементов в стеке будут стоять индексы позиций массива R, в которые необходимо занести число M.
var Stack: array [0..M] of byte;
...
S[0]:=0; {стек пуст, S[0] есть указатель на последнюю
помещенную в стек позицию}
for j:=1 to M do
begin
while p[j]<p[S[S[0]]] do
{S[0] - это индекс последней занятой позиции в стеке,
на которой находится число S[S[0]] - индекс элемента массива p,
а сам этот элемент - это p[S[S[0]]]}
begin
R[S[S[0]]]:=j-1; {для элемента массива p с индексом
S[S[0]] нашли координату правой стенки}
S[0]:=S[0]-1;{убрать элемент из стека}
end;
S[0]:=S[0]+1;{индекс - в стек}
S[S[0]]:=j;
end;
for j:=1 to S[0] do R[S[S[0]]]:=M;
Для заполнения массива L необходимо проделать те же самые операции, но вектор p будет просматриваться справа налево:
...
S[0]:=0; {стек пуст, S[0] есть указатель на последнюю
помещенную в стек позицию}
for j:=M downto 1 do
begin
while p[j]<p[S[S[0]]] do
begin
L[S[S[0]]]:=j+1; {для элемента массива p с индексом
S[S[0]] нашли координату левой стенки}
S[0]:=S[0]-1;{убрать элемент из стека}
end;
S[0]:=S[0]+1;{индекс - в стек}
S[S[0]]:=j;
end;
for j:=1 to S[0] do L[S[S[0]]]:=1;
Последнее, что остается сделать - это за один проход вычислить максимум по всем j выражения
p[j]*(R[j]-L[j]+1).
Этот максимум есть размер максимального единичного прямоугольника с нижней гранью в строке i.
Максимум по всем i и даст решение.
Сложность алгоритма O(N*M), т.е. количество операции линейно зависит от числа элементов матрицы A!
Комбинируем идеи пунктов a) и c) задачи 16 (глава "Сортировки и последовательности"). Пусть элемент C[i,j] массива C есть следующая сумма
C[i,j]=A[1,j]+ ... +A[i,j].
Переменная MaxSoFar имеет то же самое назначение, что и раньше,MaxFndingHere есть максимальное значение суммы элементов прямоугольной подматрицы с правым нижним углом (i,j) и высоты k.
MaxSoFar:=A[1,1];
for i:=1 to M do begin
for k:=1 to i do begin MaxEndingHere:=0;
for j:=1 to N do begin
{смотрим, что произойдет с максимальным значением
суммы элементов прямоугольной подматрицы с правым
нижним углом (i-1,j) и высоты k при приписывании к
этой подматрице очередного i-го столбца с суммой C[i,j]-C[i-k,j]}
MaxEndingHere:=max(MaxEndingHere+C[i,j]-C[i-k,j], C[i,j]-C[i-k,j]);
MaxSoFar:=max(MaxSoFar, MaxEndingHere);
end
end;
Для решения пункта 1 задачи достаточно воспользоваться
тем фактом, что для определения минимальной величины штрафа, взимаемого за проход в клетку i-той строки достаточно знать минимальные величины штрафа, взимаемого за проход в клетки (i-1)-той строки, которые являются соседними рассматриваемой клетке. Поэтому алгоритм решения пункта 1 следующий:
для i от 1 до n
Штраф[i,1]:=A[i,1] для i от 2 до n
для j от 1 до m
нц
Штраф[i,j]:=Штраф[i-1,j]+A[i,j];
если j>1 и Штраф[i,j] < Штраф[i-1,j-1]+A[i,j];
то Штраф[i,j]:=Штраф[i-1,j-1]+A[i,j];
если j<m и Штраф[i,j] < Штраф[i-1,j+1]+A[i,j];
то Штраф[i,j]:=Штраф[i-1,j+1]+A[i,j];
кц
Для решения пункта 2 можно воспользоваться алгоритмом Дейкстры нахождения минимального пути в графе из главы 'Графы'.
а) Обозначим вершины N-угольника x(0), ..., x(N-1) в порядке обхода по контуру. В дальнейшем будем считать, что если у нас в выкладках встречается вершина с индексом k, то это то же, что и вершина с номером k mod N (остаток от деления k на N).
Рассмотрим выпуклый L-угольник, вершинами которого являются L
последовательных вершин данного N-угольника, начиная с x(p) и до x(p+L-1) (в порядке обхода по контуру). У этого L-угольника будем считать, что отрезок (x(p),x(p+L-1)) - это его диагональ. Сумму диагоналей этой фигуры обозначим S(p,p+L-1).
Очевидно, что по условию задачи:
S(p,p)=0; S(p,p+1)=0 (у точки и отрезка нет диагоналей),
S(p,p+2)=d(p,p+2)
(тут d(p,p+2) - длина отрезка (x(p),x(p+2))).
Предположим, что мы знаем S(p,p+L-1) для всех p=0, ...,N-1 и L=1,...k.
Найдем S(p,p+k).
Мы знаем, что диагонали разбивают k+1 угольник на треугольники, и что (x(p),x(p+k)) - диагональ, т.е. одна из сторон какого-то треугольника. Итак, мы зафиксировали две вершины треугольника x(p) и x(p+k). Третьей вершиной может быть либо x(p+1), либо x(p+2),..., либо x(p+k-1). Если мы считаем, что третья вершина это x(i), то сумма диагоналей будет
d(p,p+k) + S(p,i) + S(i,k). (1)
Тут мы уже знаем S(p,i) и S(i,k) - они, по предположению, были вычислены на предыдущих шагах. d(p,p+k) - это расстояние между вершинами x(p) и x(p+k), его мы тоже можем вычислить.
Так как нас интересует минимальная сумма триангуляции (разбиения на треугольники), то мы ищем выражение (1) с минимальным значением
S(p,p+k)=d(p,p+k)+ min{S(p,i)+S(i,k)} (2) i
при i=p+1,p+2,...,k-1.
Находим S(p,p+k) для каждого p=0,...,N-1.
Минимум S(p,p+N-2) по p=0,...,N-1, и даст искомую триангуляцию (действительно, S(p,p+N-2) есть стоимость разбивки фигуры после проведения N-3 диагоналей).
б) Алгоритм остается тем же, за исключением того, что вместо формулы (2) надо использовать следующую:
S(p,p+k)={d(p,p+k),S(p,i),S(i,k)},
где S(p,p+k) - длина максимальной диагонали в фигуре с вершинами x(p), x(p+1), ...,x(p+k) (отрезок (x(p),x(p+k)) считается диагональю). Мы берем минимум по всем возможным разбивкам фигуры, а стоимость разбивки определяется как максимум из длины диагонали d(p,p+k) и длин максимальных диагоналей S(p,i) и S(i,k).
Будем считать, что вектор С определяет веса элементов, а вектор В - стоимость.
Обозначим через F[k,y] величину наибольшей суммарной стоимости элементов с номерами не большими k, суммарный вес которых не превышает y. Покажем, как можно вычислить значение F[k+1,y], используя величины с меньшими значениями индексов.
Понятно, что величина F[k+1,y] может соответствовать множеству элементов, которое содержит или не содержит элемент k+1. Если множество не содержит элемент k+1, то F[k+1,y]=F[k,y]. Иначе F[k+1,y]=B[k+1]+F[k,y-С[k+1]], т.е. максимальная суммарная стоимость есть стоимость k+1 элемента плюс максимальная стоимость элементов с номерами не большими k, суммарный вес которых не превышает величины y-С[k+1].
Таким образом, мы имеем рекуррентную формулу вычисления величин
F[k+1,y]=max(F[k,y],B[k+1]+F[k,y-С[k+1]]).
Вычисляя последовательно элементы матрицы F, учитывая при этом, что F[0,y]=0 для любого y, и F[j,0] для любого j, получим значение F[N,A], которая является значением максимально возможной стоимости.
Для выяснения номеров элементов, вошедших в множество, достаточно, начав с элемента с индексами [i,y] (которые вначале равны N и A соответственно),сравнить его со значением F[i-1,y]. Если значения равны, то i элемент не входит в множество, а процесс повторяется для элемента с индексами [i-1,y]. В случае неравенства элементов элемент i входит в множество, а процесс повторяется для элемента с индексами [i-1,y-C[i]]. Процесс выполняется для всех i от N до1.
где Pij=1 если a(i)<>b(i) и Pij=0 иначе (в правой части приведенного выше выражения первому элементу в min соответствует операция удаления из строки a(1)...a(i-1)a(i) последнего элемента a(i), после чего за d[i-1,j] операцию строка a(1)...a(i-1) преобразуется в строку b(1)...b(j), второму элементу - операция вставки символа b(j) в конец строки b(1)...b(j-1), полученной за d[i,j-1] операцию из строки a(1)...a(i), а третьему - контекстная замена ai на bj, замена осуществляется в случае ai<>bj (тогда Pij=1) и не происходит при совпадении ai и bj).
Получаем необходимое d(x,y)=d[m,n].
Алгоритм может быть записан так:
for i:=1 to m do
d[i,0]:=i;
for j:=1 to n do d[0,j]:=j;
for i:=1 to m do for j:=1 to n do
d[i,j]=min{d[i-1,j]+1,d[i,j-1]+1,d[i-1,j-1]+Pij};
Пусть строка S1 состоит из цифр 0 и 1 и имеет длину N, а строка S2 (из символов A и B) - длину M.
Заведем матрицу А размера N на M, при этом строки матрицы помечаются i-ой цифрой строки S1, а j-й столбец - j-м символом строки S2.
Возьмем в качестве примера S1='00110', S2='AAAABBAA'.
Первая цифра строки S1 (цифра 0) может быть преобразована в одну из последовательностей букв 'A','AA','AAA','AAAA', являющиеся префиксами строки S2. Заносим символ 'x' в те столбцы первой строки, буквы-пометки которых соответствуют последним буквам возможных последовательностей. Таким образом, помечаются элементы A[1,1], A[1,2], A[1,3] и A[1,4].
Шаг алгоритма: будем преобразовывать очередную цифру S1[i], которой соответствует строка i.
Находим 'x' в предыдущей строке при просмотре ее слева направо (этому столбцу соответствует последняя буква в какой-то из непустых последовательностей букв, порожденных на предыдущем шаге). Если текущую цифру можно преобразовать в последовательность букв, помечающих следующие за данным столбцы, то в этих столбцах в данной строке ставим 'x'.
Далее от места над последней помеченной ячейкой ищем в предыдущей строке 'x' и, когда находим, повторяем указанные выше операции.
Эти действия проводим далее для i=2,...,N.
Вид матрицы после N шагов:
Замечание: Можно обойтись и одномерным массивом. В самом деле, при заполнении следующей строки мы обращаемся только к элементам предыдущей строки, к каждому - по одному разу.
Алгоритм (без учета замечания) может быть следующим:
for i:=1 to N do
for j:=1 to M do
A[i,j]:=' '; {инициализация}
if S1[1]=0
then element:='A' {0 преобразуется в A}
else element:=S2[1]; {1 - в A или в B}
i:=1;
while (i<=M) and (S2[i]=element) do begin {первый шаг}
A[1,i]:='x';
i:=i+1
end;
for i:=2 to N do begin
j:=2;
while j<M do begin {просмотр строки i}
if A[i-1,j-1]='x'
then begin
if S1[i]=0
then element:='A'
else element:=S2[j];
if S2[j]=element
then
while (j<=M) and (S2[j]=element) do begin
A[i,j]:='x';
j:=j+1;
end {end for while}
else j:=j+1
end {end for then}
else j:=j+1
end {end for while}
end; {end for for}
if A[N,M]='x'
then writeln('Можно преобразовать') else writeln('Нельзя преобразовать');</P></DIR>
Определим через F[i,j] минимальное число операций, которое требуется для перемножения группы матриц с номерами от i до j включительно. Ясно, что F[i,i]=0. Перемножение матриц в такой группе может производиться различными способами, а именно, производить сначала перемножение наилучшим способом группы от i до k, затем от k+1 до j, наконец перемножить получившиеся матрицы. Понятно, что k может быть величиной от i до j-1. Учитывая требование получить наилучший результат, величина F[i,j] определяется как
F[i,j]=max(F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j]),
где k может быть величиной от i до j-1, n[i], n[k+1], m[j] определяют размеры матриц, получившихся при перемножении в группах.
для i от 1 до N выполнять
F[i,i]:=0;
дляl от 1 до N-1 выполнять
для i от 1 до N-l выполнять
нц
Kol:=бесконечность;
j:=i+l;
для k от i до j-1 выполнять
если Kol > F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j]
то Kol:=F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j];
все
F[i,j]:=Kol;
кц
а). Пусть К(L,i) обозначает множество возрастающих подпоследовательностей длины L, которые составлены из элементов с номерами от 1 до i-1. Понятно, что их может быть очень много. Однако их число можно существенно сократить, воспользовавшись следующим фактом: из двух цепочек длины L более перспективной будет цепочка, у которой величина последнегоэлемента меньше, так как ее может продолжить большее числоэлементов. Пусть S(L,i) - это именно такая самая перспективная цепочка длины Lс минимальным по величине последним элементом, а S(i) – это множество всех цепочек S(L,i) со всевозможными L. Понятно, что в S(i) содержится не более i-1 цепочек (с длинами 1,...,i-1). Пусть мы знаем S(i).
Для того, чтобы определить, какие цепочки может продолжать i-й элемент,достаточно знать последние элементы перспективных цепочек.
Для этого удобно завести массив адресов АДР последних элементов перспективных цепочек длины 1,2,...,n. При этом легко понять, что последний элемент перспективной цепочки длины s не превышает последнего элемента перспективной цепочки длины s+1. Следовательно, для очередного i-го элемента достаточно найти только максимальную длину перспективной цепочки, для которой он будет последним. Понятно, что это будет цепочка максимальной длины, последний элемент которой меньше текущего элемента. Учитывая упорядоченность последних элементов перспективных цепочек, поиск можно сделать дихотомией. При присоединении i-го элемента к какой-нибудь цепочке длины p ее длина увеличивается на 1, a ее последним элементом становится элбмент i. При этом множество S(i+1) совпадает с S(i) за исключением одной цепочки
S(p+1,i+1) = S(p,i) сцепленная с i-ым элементом.
Для хранения цепочек удобно хранить для каждого элемента номер элемента, который ему предшествует в цепочке.
Другое решение этой задачи:
Заведем 3 массива длины N: в массиве A[1..N] помещаются самичисла последовательности. Элемент B[i] имеет значение длины максимальной возрастающей подпоследовательности, завершающейся элементом A[i], а величина C[i] есть индекс предшествующего элементу A[i] элемента вэтой максимальной последовательности (A[i]=0 есть такого элемента нет).
Если N=1, то A[1] и есть искомая подпоследовательность. При этом B[1]=1, C[1]=0. Предположим, что мы заполнили массивы A,B и C от начала до элемента M-1. Попытаемся обработать элемент A[M]. Просматривая массив A от 1 до M-1-го элемента мы ищем такое A[k], что одновременно
1) A[k]<A[M],
2) B[k] максимально.
Очевидно, что для того, чтобы получить максимальную по длине подпоследовательность, заканчивающуюся A[M], этот элемент надо приписать к подпоследовательности с последним элементом A[K]. Получаем, что B[M]=B[K]+1, C[M]=K.
Пусть мы обработали все N элементов массива A. Находим максимальный элемент массива B, пусть это будет B[K]. По построению это длина максимальной подпоследовательности.
Выписываем эту подпоследовательность: полагаем j:=k; печатаем элемент A[j]; так как предшествующий в последовательности элемент имеет индекс C[j], то делаем присваивание j:=C[j], распечатываем этот элемент и т.д., до тех пор, пока j не станет 0 (т.е. мы дошли до начала последовательности).
Запись алгоритма:
for i:=2 to N do B[i]:=0;
C[1]:=0; B[1]:=1; Max:=1; IndexMax:=1;
for i:=2 to N do
for j:=1 to i-1 do
if (A[j]<A[i]) AND (B[i]<B[j]+1)
then begin
C[i]:=j;
B[i]:=B[j]+1;
if B[i]>Max
then begin Max:=B[i]
IndexMax:=i
end;
while IndexMax<>0 do begin
writeln(A[Index-Max]);
IndexMax:=C[IndexMax]
end;
В программе в переменной Max хранится максимальная найденная до сих пор длина подпоследовательности, в IndexMax находится индекс последнего элемента этой подпоследовательности.
Структура данных, каждый элемент которой (в данном случае A[i]) содержит ссылку (в этой задаче C[i]) на предыдущий элемент (или, если требуется, на последующий элемент) называется однонаправленным списком. Если у элемента есть ссылка как на предыдущий, так и на последующий за ним элемент, то список двунаправленный (его можно реализовать, используя не один массив для индексов, а два).
б). Частный случай пункта в).
в). Заведем матрицу С[0..m+1,1..n]. В ней i-тая строка будет хранить информацию о последовательностях с i-1 разрывами; j-ый элемент в этой строке есть длина самой длинной подпоследовательности элементов "хвоста" массива А ( от j-го элемента до n-го), начинающейся в j-ой позиции и с не более чем i-1 разрывом.
Правило заполнения матрицы:
Заполним нулевую строку нулями (чтобы можно было заполнить первую строку по общему алгоритму).
Для каждого номера строки i от 1 до m+1 выполнить следующие действия:
Для j-го элемента массива A (j изменяется от n до 1) находим максимальную по длине подпоследовательность, которую можно присоединить к этому элементу так, чтобы получить подпоследовательность максимальной длины с не более чем i-1 разрывом. Для этого мы:
1) ищем элемент A[k] последовательности A, больший A[j], стоящий в массиве A правее j-го элемента и с максимальным С[i,k];
2) затем просматриваем элементы i-1 -ой строки матрицы С, начиная с j+1 -го и до конца, и находим C[i-1,s] - максимальный из них;
3) сравниваем C[i-1,s] с С[i,k]. Больший из них (обозначим его C[row,col]), увеличенный на 1, запоминаем в C[i,j]. Это и будет длина максимальной подпоследовательности, начинающейся в позиции j, с не более чем i-1 разрывом.
4) Запоминаем индексы row и col элемента массива C, предшествующего C[i,j], в ячейках X[i,j] и Y[i,j] соответственно.
После окончания цикла максимальный элемент m+1 -ой строки матрицы C и есть максимальная длина возрастающей подпоследовательности с m разрывами. Выписать всю подпоследовательность можно следующим образом: для каждого элемента подпоследовательности в массивах X и Y хранится информация о предшественнике. Мы, начиная с максимального элемента m+1 -ой строки матрицы C, восстанавливаем всю подпоследовательность.
Обоснование алгоритма:
Пусть мы знаем C[i-1,j] для всех j от 1 до n и для некоторого i, а также C[i,k] для k от j+1 до n. Мы хотим вычислить C[i,j].
Для j-го элемента массива А существует максимальная по длине подпоследовательность с не более чем i-1 -им разрывом, начинающаяся с A[j]. Второй элемент (обозначим его A[k]) этой максимальной подпоследовательности (если он, конечно, есть) может быть
1) больше, чем A[j]. Тогда мы находим его среди элементов, обладающих следующими свойствами:
а) k>j,
б) C[i,k] максимальный (т.е. мы присоединяем к A[j] максимальную по длине подпоследовательность с не более чем i-1 разрывом, формируя подпоследовательность опять не более чем с i-1 разрывом);
2) меньше или равный, чем A[j]. Тогда мы ищем его среди элементов, обладающих следующими свойствами:
а) k>j;
б) C[i-1,k] максимальный (т.е. мы присоединяем максимальную подпоследовательность с не более чем i-2 -мя разрывами, формируя подпоследовательность с не более чем i-1 разрывом).
Полученная подпоследовательность получается максимальной длины, так как длина подпоследовательности, начиная с A[k], максимальная.
Упоминавшиеся выше индексы row и col, которые запоминаются в X[i,j] и Y[i,j] соответственно, обозначают
col - индекс следующего за A[j] элемента в максимальной по длине подпоследовательности, начинающейся в позиции j и имеющей не более i-1 разрыва;
row-1 - максимальное количество разрывов в подпоследовательности, начинающейся в A[col].
{Программа написана Д.Медведевым и А.Гавриловым}
const max=100; {максимальная длина массива A}
var
sw,l,i,j,k,n,m,maxind,swind:integer;
c:array [0..max,1..max] of integer;
x,y:array [1..max,1..max] of integer;
a,b:array [1..max] of integer;
begin
Write('Введите N:');
readln(n);
Writeln('Введите последовательность');
for i:=1 to n do
read(a[i]);
readln;
Write('Введите количество разрывов подпоследовательности:');
readln(m);
fillchar(c,sizeof(c),0); {зануление с, x и y} fillchar(x,sizeof(x),0);
fillchar(y,sizeof(y),0);
for i:=1 to m+1 do
for j:=n downto 1 do
begin
c[i,j]:=1;
for k:=j+1 to n do
if (a[k]>a[j]) and (c[i,k]>=c[i,j]) then
begin
c[i,j]:=c[i,k]+1;
x[i,j]:=k;
y[i,j]:=i;
end;
for k:=j+1 to n do
if c[i-1,k]>=c[i,j] then
begin
c[i,j]:=c[i-1,k]+1;
x[i,j]:=k;
y[i,j]:=i-1;
end;
end;
maxind:=1;
for i:=1 to n do
if c[m+1,i]>c[m+1,maxind] then
maxind:=i;
l:=c[m+1,maxind];
j:=maxind;i:=m+1;k:=1;
while (c[i,j]<>1) do
begin
b[k]:=j; {в массив b выписываем индексы элементов} inc(k);
{максимальной по длине подпоследователь}
sw:=x[i,j]; {ности в прямом порядке}
i:=y[i,j];
j:=sw;
end;
b[k]:=j;
for i:=1 to k do write(a[b[i]],' ');
writeln;
writeln('Длина=',l);
end.
Для решения задачи элементы массива удобно упорядочить по абсолютной величине (в порядке неубывания). Если в массиве есть элементы, равные 0, то один из них и будет последним элементом искомой последовательности, поэтому их можно игнорировать. Пусть К(i) обозначает максимальное количество элементов, которое может находится в некоторой последовательности с требуемым свойством, последним элементом которой является i-й элемент.
Понятно, что наименьшему по абсолютной величине элементу ничего не может предшествовать ни один элемент, поэтому К(р)=0, где р - индекс первого ненулевого элемента.
Для каждого следующего элемента с номером j, j=р+1,...,N, необходимо определить максимальное количество элементов, которое может предшествовать рассматриваемому элементу, с учетом требуемого свойства. Понятно, что это количество есть максимум из величин К(р1), К(р2),..., К(рm), где элементы с номерами p1,p2,...,pm, р<=p1<p2<...<pm<j являются делителями элемента с номером j. Поэтому мы имеем рекуррентную формулу для вычисления К(j):
К(j) = мах (К(p1),К(p2),...,К(pm)).
Значение К(N), вычисленное по описанному выше правилу, и определяет максимальное количество элементов, которое может находится в некоторой последовательности с требуемым свойством (без учета возможного нуля в конце последовательности).
Для того, чтобы установить, какие элементы образуют максимальную последовательность, достаточно для каждого номера j помнить тот номер из p1,p2,...,pm, на котором достигается максимум для чисел К(p1),К(p2),...,К(pm). Эти номера можно определять параллельно с вычислением значения К(j) в некотором массиве, например ПРЕДОК. Используя эту информацию, легко определить номера элементов последовательности, проходя от элемента i с максимальным значением К(i) к элементу, который ему предшествует (ПРЕДОК(i)), до тех пор, пока не придем к первому элементу f последовательности (ПРЕДОК(f)=0).
Можно, конечно, число A умножить само на себя n-1 раз, но для этого надо выполнить n-1 операцию умножения. Рассмотрим метод, требующий меньшего числа умножений (он, однако, не всегда дает минимальное число умножений).
Если n - четное, n=2m то будем вычислять An, используя тождество Aam=(Am)2;
если же n=2m+1, то
A2m+1=(A2m)*A=((Am)2)*A.
Так(м образом, возведение A в 13 степень будет выглядеть следующим образом:
(A13)=((A6)2)*A=(((A3)2)2)*A=(((A*A*A)2)2)*A
и вычисление требует 5 операций умножения.
Используя данный метод, для возведения в степень n потребуется порядка log2(n) операций умножения.
Программа на Паскале может выглядеть так:
var A,N: integer;
function power(N: integer): integer;
begin
if N>1
then if odd(N) {N нечетно?}
then power:=SQR(power(N div 2))*A else power:=SQR(power(N div 2))
else power:=A
end;
begin
read(A,N);
writeln(power(N));
end;
Можно ту же самую идею реализовать и по другому ( далее мы приводим выдержку из книги Д.Кнута "Искусство программирования для ЭВМ", т.2, с.482):
"Запишем n в двоичной системе счисления и заменим в этой записи каждую цифру "1" парой букв SX, а каждую цифру "0" - буквой S, после чего вычеркнем крайнюю левую пару букв SX. Результат, читаемый слева направо, превращается в правило вычисления xn, если букву "S" интерпретировать как операцию возведения в квадрат, а букву "X" - как операцию умножения на x. Например, если n=23, то его двоичным представлением будет 10111; строим последовательность SX S SX SX SX, удаляем из нее начальную пару SX и в итоге получаем следующее правило вычисления: S SX SX SX. Согласно этому правилу, мы должны "возвести x в квадрат, затем снова возвести в квадрат, затем умножить на x, возвести в квадрат, умножить на x, возвести в квадрат и, наконец, умножить на x"; при этом мы последовательно вычисляем x2, x4, x5, x10, x11, x22, x23.
Этот "бинарный метод" легко обосновать, рассмотрев последовательность получаемых в ходе вычисления показателей: если "S" интерпретировать как операцию умножения на 2, а "X" - как операцию прибавления 1 и если начать с 1, а не с x, то наше правило дает нам в соответствии со свойствами двоичной системы счисления число n".
Приведенный метод не дает минимального числа операций умножения. Для вычисления x23 нам, по изложенному выше методу, потребуется 7 операций умножения. В действительности их необходимо только 6:
x -> x2 -> x3 -> x5 -> x10 -> x20 -> x23.
Алгоритм нахождения минимального числа операций (кроме полного перебора) сейчас неизвестен (см. там же у Д.Кнута).
Пусть z есть массив из N элементов, y - из M. Положим i=1 и j=1. Берем элемент z[i] и ищем минимальное k, k>=j, k<=M, такое что y[k]=z[i] (мы находим очередной совпадающий символ в строках z и y). Полагаем i=i+1 и j=k+1. Повторяем поиск элемента z[i] в оставшемся куске последовательности y. Условия окончания поиска:
a) Если i стало больше N (т.е. все элементы массива z являются подпоследовательностью элементов y), - и тогда z можно получить вычеркиванием элементов из y.
б) Если в оставшимся куске последовательности y не найдено элемента, совпадающего с очередным z[i], то z из y получить нельзя.
Заведем матрицу A[0..m,0..n]. Элемент A[i,j] будет длиной
максимальной общей подпоследовательности y x1, ... ,xi и y y1, ..., yj. Сначала A[i,0]=A[0,j]=0, i=0, ... ,m, j=0, ... ,n.
Пусть xi=yj, тогда требуется увеличить длину максимальной общей подпоследовательности x1, ... ,xi-1 и y1, ... ,yj-1 на 1: A[i,j]=A[i-1,j-1]+1, если xi=yj.
В случае, если xi<>yj, то, очевидно,
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, а xi и yi - это последние общие совпадающие элементы в 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;
В последовательностях 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 do
for j:=0 to n do S[i,j]:='';
for i:=1 to m do
for j:=1 to n do begin
if x[i]=y[j]
then begin
A[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].
{d(p,p+k),S(p,i),S(i,k)},