Задача 1.
Вычислить значение суммы
S = 1/1! + 1/2! + ... + 1/k!
Задача 2.
Написать программу определения количества шестизначных
'счастливых' билетов, у которых сумма первых 3 десятичных цифр
равна сумме 3 последних десятичных цифр.
Задача 3.
Написать программу определения количества 2*N -значных биле-
тов, у которых сумма первых N десятичных цифр равна сумме N
последних десятичных цифр; при этом N -произвольное натуральное
число.
Задача 4.
Фишка может двигаться по полю длины N только вперед. Длина
хода фишки не более K. Найти число различных путей, по которым
фишка может пройти поле от начала до конца.
Пример. N=3, K=2
Возможные пути:
1,1,1
1,2
2,1
Ответ: 3.
Задача 5.
Покупатель имеет купюры достоинством A(1), ...,A(n), а прода-
вец - B(1), .. ,B(m). Необходимо найти максимальную стоимость то-
вара Р, которую покупатель не может купить, потому что нет возмож-
ности точно рассчитаться за этот товар с продавцом, хотя денег на
покупку этого товара достаточно.
Задача 6.
Задан массив М [1:N] натуральных чисел, упорядоченный по неу-
быванию, т.е.: M[1]<=M[2]<=...<=M[N].
Найти первое натуральное число, не представимое суммой ника-
ких элементов этого массива, при этом сумма может состоять и из
одного слагаемого, но каждый элемент массива может входить в нее
только один раз.
Задача 7.
У покупателя есть n монет достоинством H(1),..., H(n). У про-
давца есть m монет достоинством B(1),...,B(l). Может ли купить по-
купатель вещь стоимости S так, чтобы у продавца нашлась точная
сдача (если она необходима).
Задача 8.
Задан массив М [1:N] натуральных чисел, упорядоченный по неу-
быванию, т.е.: M[1]<=M[2]<=...<=M[N].
Написать алгоритм выплаты заданной суммы S минимальным коли-
чеством купюp достоинством M(1), ..., M(N).
Задача 9.
По матрице A(N,N) построить матрицу B(N,N). Элемент B(I,J)
равен максимальному из элементов матрицы А принадлежащем части,
ограниченной справа диагоналями, проходящими через A(I,J).
┌──────────────────────┐
│****** . │
│******* . │
│******** │
│****** . │
│**** . │
│** . │
│ . │
│ . │
│ . │
└──────────────────────┘
Задача 10.
Вводится матрица a(m,n) из 0 и 1. Найти в ней квадратную под-
матрицу из одних единиц максимального размера.
Задача 11.
Вводится матрица a(m,n) из 0 и 1. Найти в ней прямоугольную под-
матрицу из одних единиц максимального размера (т.е. с максимальным
произведением высоты на длину).
Переформулировка задачи 11.
Фермер хочет построить на своей земле как можно больший по
площади сарай. Но на его участке есть деревья и хозяйственные
постройки, которые он не хочет никуда переносить. Для простоты
представим ферму сеткой размера MxN. Каждое из деревьев и построек
размещается в одном или нескольких узлах сетки. Прямоугольный са-
рай не должен ни с чем соприкасаться (т.е. в соседних с ним узлах
сетки не может ничего быть).
Найти максимально возможную площадь сарая и где он может раз-
мещаться.
Задача 12.
Дан массив A[N,M]. Необходимо найти максимальную сумму элементов
прямоугольного подмассива по всем возможным прямоугольным подмасси-
вам.
Задача 13.
Задана матрица натуральных чисел A(n,m). За каждый проход че-
рез клетку (i,j) взымается штраф A(i,j). Необходимо минимизировать
штраф и
а) Пройти из какой-либо клетки 1-ой строки в n-ую строчку, при
этом из текущей клетки можно перейти
1) в любую из 3-х соседних, стоящих в стpоке с номеpом на
1-цу большем;
2) в любую из 8 соседних клеток;
б) Реализовать пункт a) для перехода из клетки (1,1) в (n,m).
Задача 14.
Дан выпуклый n-угольник, n=>3, своим обходом по контуру. Раз-
бить его на треугольники (n-3)-мя диагоналями, непересекающимися
кроме как по концам, таким образом чтобы
а) Cумма их длин была минимальной;
б) Максимальная из диагоналей имела наименьшую длину.
Задача 15.
Задано число А и два вектора b[1..n] и c[1..n].
Найти множество I, являющееся подмножеством множества {1,...,n},
такое, что
SUM C <=А, a SUM B является максимальной из всех
i из I i i из I i возможных
Задача 16.
Пусть x=(a1,a2,...,am) и y=(b1,b2,...,bn) - две заданных строки
символов.
Определим d(x,y) как минимальное число вставок, удалений и за-
мен символа, которое необходимо для преобразования x в y.
Например: d(ptslddf,tsgldds)=3
удаление p вставка g замена f
ptslddf---------->tslddf--------->tsglddf-------->tsgldds
Для заданных x и y найти d(x,y).
Задача 17.
Вводится три неотрицательных числа d, i, c и две строки X и
Y. Найти преобразование строки X в Y минимальной стоимости. До-
пустимы следующие три операции:
удалить любой символ из X (стоимость операции d);
вставить любой символ в X (стоимость операции i);
заменить символ в X на произвольный (стоимость операции e).
Задача 18.
Даны две строки x и y. Строка x состоит из нулей и единиц,
строка y из символов A и B. Можно ли строку x преобразовать в
строку y по следующему правилу: цифра 0 преобразуется в непустую
последовательность букв A, а цифра 1 - либо в непустую последова-
тельность букв A, либо в непустую последовательность букв B?
Задача 19.
Пусть известно, что для перемножения матрицы размера n*m на
матрицу размера m*k требуется n*m*k операций. Необходимо опреде-
лить, какое минимальное число операций потребуется для перемноже-
ния n матриц А1,...Аn, заданных своими размерами n(i)*m(i). При
этом можно перемножать любые две рядом стоящие матрицы, в резуль-
тате чего получается матрица нужного размера.
Замечание:
n(i) - число строк в матрице Ai
m(i) - число столбцов в матрице Ai
n(i)=m(i)+1.
Задача 20.
а) Из последовательности, состоящей из N чисел, вычеркнуть ми-
нимальное количество элементов так, чтобы оставшиеся образовали
строго возрастающую последовательность.
б) Из заданной числовой последовательности A[1..N] вычеркнуть
минимальное число элементов так, чтобы в оставшейся подпоследова-
тельности каждый последующий элемент был больше предыдущего кроме,
быть может, одной пары соседних элементов ( одного "разрыва" возрас-
тающей подпоследовательности).
Например: A=(1,2,3,2,4,3,4,6);
Искомая подпоследовательность (1,2,3,2,3,4,6)
Разрыв подчеркнут. ---
б) Из заданной числовой последовательности A[1..N] вычеркнуть
минимальное число элементов так, чтобы в оставшейся подпоследова-
тельности каждый последующий элемент был больше предыдущего кроме,
быть может, m пар соседних элементов ( возрастающая подпоследова-
тельность с m "разрывами").
Задача 21.
В заданной последовательности целых чисел найти максимально
длинную подпоследовательность чисел такую, что каждый последующий
элемент подпоследовательности делился нацело на предыдущий.
Задача 22.
Возвести число А в натуральную степень n за как можно меньшее
количество умножений.
Задача 23.
Заданы z и y - две последовательности. Можно ли получить
последовательность z вычеркиванием элементов из y.
Задача 24.
Найти максимальную по длине последовательность z, полученную
вычеркиванием элементов как из x, так и из y.
Задача 25.
Пусть x и y - две бинарных последовательности (т.е. элементы
последовательностей - нули и единицы); x и y можно рассматривать
как запись в двоичной форме некоторых двух натуральных чисел.
Найти максимальное число z, двоичную запись которого можно
получить вычеркиванием цифр как из x, так и из y. Ответ выдать в
виде бинарной последовательности.
Задача 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;
Задача 2.
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 во вложенных циклах будет проверяться 10^6 раз,
поэтому будем говорить, что сложность этого алгоритма 10^6.
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;
Сложность алгоритма 10^5.
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; { удваиваем сумму }
Сложность этого алгоритма 10^3.
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.
Задача 3.
Задача имеет очевидное решение, которое состоит в генерации
всех 2*n-разрядных чисел и проверке их на требуемое свойство. Од-
нако общее количество таких чисел равно 10^(2*n) и поэтому при 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-разрядных чисел равно
P=S(n,0)*S(n,0)+S(n,1)*S(n,1)+...+S(n,9*n)*S(n,9*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). Следовательно,
S(k+1,i) = S(k,i-0)+S(k,i-1)+...+ S(k,i-m).
Задача 4.
Очевидное решение задачи предполагает разложение числа 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.
Задача 5.
Если покупатель отдаст все свои купюры продавцу, то понятно,
что для решения исходной задачи размер минимальной сдачи, которую
продавец не может вернуть, используя любые имеющиеся теперь у него
купюры 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.
Задача 6.
Решается аналогично задаче 5.
Задача 7.
Если S>H(1)+...+H(n), то сумму выплатить нельзя.
Если покупатель отдаст все свои купюры продавцу, то понятно,
что для решения исходной задачи надо определить, может ли продавец
вернуть сумму 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 элементов.
Задача 8.
Решается аналогично задаче 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']).
Задача 9.
Очевидное решение задачи состоит в использовании некоторой
процедуры, которая по заданным координатам (номеру строки i и но-
меру столбца j) элемента определяет максимальное значение элемен-
тов, расположенных в нужной части матрицы A.
Однако нетрудно заметить, что для элементов первого столбца
матрицы В справедливо соотношение B[i,1]=A[i,1], i=1,...N. Вы-
числение же других столбцов можно проводить следующим образом:
B[i,j]=max(A[i,j], B[i-1,j-1], B[i,j-1], B[i+1,j-1]).
При этом необходимо учитывать, что индексы элементов должны
находится в пределах границ массива.
Задача 10.
В элемент 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);
Задача 11.
Пусть верхний левый угол матрицы имеет индекс (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!
Задача 12.
Комбинируем идеи пунктов 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
MaxEndingHere:=0;
for k:=1 to i do
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;
Задача 13.
Для решения пункта 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 можно воспользоваться алгоритмом
Дейкстры нахождения минимального пути в графе из главы 'Гра-
фы'.
Задача 14.
а) Обозначим вершины 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)=min max {d(p,p+k),S(p,i),S(i,k)},
i
где 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).
Задача 15.
Будем считать, что вектор С определяет веса элементов, а век-
тор В - стоимость.
Обозначим через 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.
Задача 16.
Для x=a(1)...a(m) и y=b(1)...b(n), a(i) и b(i) символы,
1<=i<=m, 1<=j<=n, d(x,y) можно вычислить, применяя метод динами-
ческого программирования.
Определим массив d[0..m,0..n], элементы которого
d[i,j] = d(a(1)...a(i), b(1)...b(j)), 0<=i<=m,0<=j<=n,
так что
d[0,j]=j;
d[i,0]=i;
очевидным образом получаем
d[i,j]=min{d[i-1,j]+1,d[i,j-1]+1,d[i-1,j-1]+Pij}
где 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};
Задача 17.
Делается аналогично задаче 16.
Задача 18.
Пусть строка 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 шагов:
A A A A B B A A Если после N шагов в позиции (N,M)
┌───────────────┐ стоит x, то строки можно преобразовы-
0 │x x x x │ вать друг в друга.
0 │ x x x │
1 │ x x x x │
1 │ x x x x x│
0 │ x x│
└───────────────┘
Замечание: Можно обойтись и одномерным массивом. В самом де-
ле, при заполнении следующей строки мы обращаемся только к элемен-
там предыдущей строки, к каждому - по одному разу.
Алгоритм (без учета замечания) может быть следующим:
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('Нельзя преобразовать');
Напишите программу, использующую одномерный массив.
Задача 19.
Определим через 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;
кц
Задача 20.
а). Пусть К(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.
Задача 21.
Для решения задачи элементы массива удобно упорядочить по
абсолютной величине (в порядке неубывания). Если в массиве есть
элементы, равные 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).
Задача 22.
Можно, конечно, число A умножить само на себя n-1 раз, но
для этого надо выполнить n-1 операцию умножения. Рассмотрим метод,
требующий меньшего числа умножений (он, однако, не всегда дает ми-
нимальное число умножений).
Если n - четное, n=2m то будем вычислять A^n, используя тож-
дество
A^2m=(A^m)^2;
если же n=2m+1, то
A^(2m+1)=(A^2m)*A=((A^m)^2)*A.
Так(м образом, возведение A в 13 степень будет выглядеть сле-
дующим образом:
(A^13)=((A^6)^2)*A=(((A^3)^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. Результат, чи-
таемый слева направо, превращается в правило вычисления x**n, если
букву "S" интерпретировать как операцию возведения в квадрат, а
букву "X" - как операцию умножения на x. Например, если n=23, то
его двоичным представлением будет 10111; строим последовательность
SX S SX SX SX, удаляем из нее начальную пару SX и в итоге получаем
следующее правило вычисления: S SX SX SX. Согласно этому правилу,
мы должны "возвести x в квадрат, затем снова возвести в квадрат,
затем умножить на x, возвести в квадрат, умножить на x, возвести в
квадрат и, наконец, умножить на x"; при этом мы последовательно
вычисляем x**2, x**4, x**5, x**10, x**11, x**22, x**23.
Этот "бинарный метод" легко обосновать, рассмотрев последо-
вательность получаемых в ходе вычисления показателей: если "S"
интерпретировать как операцию умножения на 2, а "X" - как операцию
прибавления 1 и если начать с 1, а не с x, то наше правило дает
нам в соответствии со свойствами двоичной системы счисления число
n".
Приведенный метод не дает минимального числа операций умно-
жения. Для вычисления x**23 нам, по изложенному выше методу, пот-
ребуется 7 операций умножения. В действительности их необходимо
только 6:
x -> x**2 -> x**3 -> x**5 -> x**10 -> x**20 -> x**23.
Алгоритм нахождения минимального числа операций (кроме пол-
ного перебора) сейчас неизвестен (см. там же у Д.Кнута).
Задача 23.
Пусть 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 получить нель-
зя.
Задача 24.
Пусть x=x1,x2, ... ,xm, y=y1,y2, ... ,yn.
Заведем матрицу 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, ... ,x[i-1] и y1, ... ,y[j-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;
Задача 25.
В последовательностях 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].