Жанр: Учеба
Программирование в теоремах и задачах
...]. Найти количество различных чисел среди
элементов этого массива.
Решение. (1 вариант)
i := 1; k := 1;
{инвариант: k - количество различных чисел среди x[1]..x[i]}
while i "" n do begin
| i := i + 1;
| if x[i] "" x[i-1] then begin
| | k := k + 1;
| end;
end;
(2 вариант) Искомое число на 1 больше количества тех чисел
i из 1..n-1, для которых x[i] "" x[i+1].
k := 1;
for i := 1 to n-1 do begin
| if x[i]"" x[i+1] then begin
| | k := k + 1;
| end;
end;
1.2.6. (Сообщил А.Л.Брудно.) Прямоугольное поле m на n разбито
на mn квадратных клеток. Некоторые клетки покрашены в черный
цвет. Известно, что все черные клетки могут быть разбиты на
несколько непересекающихся и не имеющих общих вершин черных прямоугольников.
Считая, что цвета клеток даны в виде массива типа
array [1..m] of array [1..n] of boolean;
подсчитать число черных прямоугольников, о которых шла речь.
Число действий должно быть порядка m*n.
Решение. Число прямоугольников равно числу их левых верхних
углов. Является ли клетка верхним углом, можно узнать, посмотрев
на ее цвет, а также цвет верхнего и левого соседей. (Не забудьте,
что их может не быть, если клетка с краю.)
1.2.7. Дан массив x: array [1..n] of integer. Найти количество
различных чисел среди элементов этого массива. (Число
действий должно быть порядка n*n.)
1.2.8. Та же задача, если требуется, чтобы количество
действий было порядка n* log n. (Указание. Смотри главу о сортировке.)
1.2.9. Та же задача, если известно, что все элементы массива
- числа от 1 до k и число действий должно быть порядка n+k.
1.2.10. Дан массив x [1]..x[n] целых чисел. Не используя
других массивов, переставить элементы массива в обратном порядке.
Решение. Числа x [i] и x [n+1-i] нужно поменять местами для
всех i, для которых i " n + 1 - i, т.е. 2*i " n + 1 "=" 2*i "= n
"=" i "= n div 2:
for i := 1 to n div 2 do begin
| ...обменять x [i] и x [n+1-i];
end;
1.2.11. (из книги Д.Гриса) Дан массив целых чисел
x[1]..x[m+n], рассматриваемый как соединение двух его отрезков:
начала x[1]..x[m] длины m и конца x[m+1]..x[m+n] длины n. Не используя
дополнительных массивов, переставить начало и конец.
(Число действий порядка m+n.)
Решение. (1 вариант). Перевернем (расположим в обратном порядке)
отдельно начало и конец массива, а затем перевернем весь
массив как единое целое.
(2 вариант, А.Г.Кушниренко). Рассматривая массив записанным
по кругу, видим, что требуемое действие - поворот круга. Как известно,
поворот есть композиция двух осевых симметрий.
(3 вариант). Рассмотрим более общую задачу - обмен двух
участков массива x[p+1]..x[q] и x[q+1]..x[s]. Предположим, что
длина левого участка (назовем его A) не больше длины правого
(назовем его B). Выделим в B начало той же длины, что и A, назовем
его B1, а остаток B2. (Так что B = B1 + B2, если обозначать
плюсом приписывание массивов друг к другу.) Нам надо из A + B1 +
B2 получить B1 + B2 + A. Меняя местами участки A и B1 - они имеют
одинаковую длину, и сделать это легко,- получаем B1 + A + B2,
и осталось поменять местами A и B2. Тем самым мы свели дело к
перестановке двух отрзков меньшей длины. Итак, получаем такую
схему программы:
p := 0; q := m; r := m + n;
{инвариант: осталось переставить x[p+1]..x[q], x[q+1]..x[s]}
while (p "" q) and (q "" s) do begin
| {оба участка непусты}
| if (q - p) "= (s - q) then begin
| | ..переставить x[p+1]..x[q] и x[q+1]..x[q+(q-p)]
| | pnew := q; qnew := q + (q - p);
| | p := pnew; q := qnew;
| end else begin
| | ..переставить x[q-(r-q)+1]..x[q] и x[q+1]..x[r]
| | qnew := q - (r - q); rnew := q;
| | q := qnew; r := rnew;
| end;
end;
Оценка времени работы: на очередном шаге оставшийся для обработки
участок становится короче на длину A; число действий при этом
также пропорционально длине A.
1.2.12. Коэффициенты многочлена хранятся в массиве a: array
[0..n] of integer (n - натуральное число, степень многочлена).
Вычислить значение этого многочлена в точке x (т. е. a[n]*(x в
степени n)+...+a[1]*x+a[0]).
Решение. (Описываемый алгоритм называется схемой Горнера.)
k := 0; y := a[n];
{инвариант: 0 "= k "= n,
y= a[n]*(x в степени k)+...+a[n-1]*(x в степени k-1)+...+
+ a[n-k]*(x в степени 0)}
while k""n do begin
| k := k + 1;
| y := y * x + a [n - k];
end;
1.2.13. (Для знакомых с основами анализа. Сообщил А.Г.Кушниренко.)
Дополнить алгоритм вычисления значения многочлена в
заданной точке по схеме Горнера вычислением значения его производной
в той же точке.
Решение. Добавление нового коэффициента соответствует переходу
от многочлена P(x) к многочлену P(x)*x + c. Его производная
в точке x равна P'(x)*x + P(x). (Это решение обладает забавным
свойством: не надо знать заранее степень многочлена. Если требовать
выполнения этого условия, да еще просить вычислять только
значение производной, не упоминая о самом многочлене, получается
не такая уж простая задача.)
1.2.14. В массивах
a:array [0..k] of integer и b: array [0..l] of integer
хранятся коэффициенты двух многочленов степеней k и l. Поместить
в массив c: array [0..m] of integer коэффициенты их произведения.
(Числа k, l, m - натуральные, m = k + l; элемент массива
с индексом i содержит коэффициент при x в степени i.)
Решение.
for i:=0 to m do begin
| c[i]:=0;
end;
for i:=0 to k do begin
| for j:=0 to l do begin
| | c[i+j] := c[i+j] + a[i]*b[j];
| end;
end;
1.2.15. Предложенный выше алгоритм перемножения многочленов
требует порядка n*n действий для перемножения двух многочленов
степени n. Придумать более эффективный (для больших n) алгоритм,
которому достаточно порядка (n в степени (log 4)/(log 3))
действий.
Указание. Представим себе, что надо перемножить два многочлена
степени 2k. Их можно представить в виде
A(x)*x^k + B(x) и C(x)*x^k + D(x)
(здесь x^k обозначает x в степени k). Произведение их равно
A(x)C(x)*x^{2k} + (A(x)D(x)+B(x)C(x))*x^k + B(x)D(x)
Естественный способ вычисления AC, AD+BC, BD требует четырех умножений
многочленов степени k, однако их количество можно сократить
до трех с помощью такой хитрости: вычислить AC, BD и
(A+B)(C+D), а затем заметить, что AD+BC=(A+B)(C+D)-AC-BD.
1.2.16. Даны два возрастающих массива x: array [1..k] of
integer и y: array [1..l] of integer. Найти количество общих
элементов в этих массивах (т. е. количество тех целых t, для которых
t = x[i] = y[j] для некоторых i и j). (Число действий порядка
k+l.)
Решение.
k1:=0; l1:=0; n:=0;
{инвариант: 0"=k1"=k; 0"=l1"=l; искомый ответ = n + количество
общих элементов в x[k1+1]...x[k] и y[l1+1]..y[l]}
while (k1 "" k) and (l1 "" l) do begin
| if x[k1+1] " y[l1+1] then begin
| | k1 := k1 + 1;
| end else if x[k1+1] " y[l1+1] then begin
| | l1 := l1 + 1;
| end else begin {x[k1+1] = y[l1+1]}
| | k1 := k1 + 1;
| | l1 := l1 + 1;
| | n := n + 1;
| end;
end;
{k1 = k или l1 = l, поэтому одно из множеств, упомянутых в
инварианте, пусто, а n равно искомому ответу}
Замечание. В третьей альтернативе достаточно было бы увеличивать
одну из переменных k1, l1; вторая добавлена для симметрии.
1.2.17. Решить предыдущую задачу, если известно лишь, что
x[1] "= ... "= x[k] и y[1] "= ... "= y[l] (возрастание заменено
неубыванием).
Решение. Условие возрастания было использовано в третьей
альтернативе выбора: сдвинув k1 и l1 на 1, мы тем самым уменьшали
на 1 количество общих элементов в x[k1+1]...x[k] и
x[l1+1]...x[l]. Теперь это придется делать сложнее.
end else begin {x[k1+1] = y[l1+1]}
| t := x [k1+1];
| while (k1"k) and (x[k1+1]=t) do begin
| | k1 := k1 + 1;
| end;
| while (l1"l) and (x[l1+1]=t) do begin
| | l1 := l1 + 1;
| end;
end;
Замечание. Эта программа имеет дефект: при проверке условия
(l1"l) and (x[l1+1]=t)
(или второго, аналогичного) при ложной первой скобке вторая окажется
бессмысленной (индекс выйдет за границы массива) и возникнет
ошибка. Некоторые версии паскаля, вычисляя (A and B), сначала
вычисляют A и при ложном A не вычисляют B. (Так ведет себя,
например, система Turbo Pascal, 5.0 - но не 3.0.) Тогда описанная
ошибка не возникнет.
Но если мы не хотим полагаться на такое свойство используемой
нами реализации паскаля (не предусмотренное его автором
Н.Виртом), то можно поступить так. Введем дополнительную переменную
b: boolean и напишем:
if k1 " k then b := (x[k1+1]=t) else b:=false;
{b = (k1"k) and (x[k1+1] = t}
while b do begin
| k1:=k1+1;
| if k1 " k then b := (x[k1+1]=t) else b:=false;
end;
Можно также сделать иначе:
end else begin {x[k1+1] = y[l1+1]}
| if k1 + 1 = k then begin
| | k1 := k1 + 1;
| | n := n + 1;
| end else if x[k1+1] = x [k1+2] then begin
| | k1 := k1 + 1;
| end else begin
| | k1 := k1 + 1;
| | n := n + 1;
| end;
end;
Так будет короче, хотя менее симметрично.
Наконец, можно увеличить размер массива в его описании,
включив в него фиктивные элементы.
1.2.18. Даны два неубывающих массива x: array [1..k] of
integer и y: array [1..l] of integer. Найти число различных элементов
среди x[1],...,x[k], y[1],...,y[l]. (Число действий порядка
k+l.)
1.2.19. Даны два массива x[1] "= ... "= x[k] и y[1] "= ...
"= y[l]. "Соединить" их в массив z[1] "= ... "= z[m] (m = k+l;
каждый элемент должен входить в массив z столько раз, сколько
раз он входит в общей сложности в массивы x и y). Число действий
порядка m.
Решение.
k1 := 0; l1 := 0;
{инвариант: ответ получится, если к z[1]..z[k1+l1] приписать
справа соединение массивов x[k1+1]..x[k] и y[l1+1]..y[l]}
while (k1 "" k) or (l1 "" l) do begin
| if k1 = k then begin
| | {l1 " l}
| | l1 := l1 + 1;
| | z[k1+l1] := y[l1];
| end else if l1 = l then begin
| | {k1 " k}
| | k1 := k1 + 1;
| | z[k1+l1] := x[k1];
| end else if x[k1+1] "= y[l1+1] then begin
| | k1 := k1 + 1;
| | z[k1+l1] := x[k1];
| end else if x[k1+1] "= y[l1+1] then begin
| | l1 := l1 + 1;
| | z[k1+l1] := y[l1];
| end else begin
| | { такого не бывает }
| end;
end;
{k1 = k, l1 = l, массивы соединены}
Этот процесс можно пояснить так. Пусть у нас есть две стопки
карточек, отсортированных по алфавиту. Мы соединяем их в одну
стопку, выбирая каждый раз ту из верхних карточек обеих стопок,
которая идет раньше в алфавитном порядке.
1.2.20. Даны два массива x[1] "= ... "= x[k] и y[1] "= ...
"= y[l]. Найти их "пересечение", т.е. массив z[1] "= ... "=
z[m], содержащий их общие элементы, причем кратность каждого
элемента в массиве z равняется минимуму из его кратностей в массивах
x и y. Число действий порядка k+l.
1.2.21. Даны два массива x[1]"=..."=x[k] и y[1]"=..."=y[l]
и число q. Найти сумму вида x[i]+y[j], наиболее близкую к числу
q. (Число действий порядка k+l, дополнительная память - фиксированное
число целых переменных, сами массивы менять не разрешается.)
Указание. Надо найти минимальное расстояние между элементами
x[1]"=..."=x[k] и q-y[l]"=.."=q-y[1], что нетрудно сделать в
ходе их слияния в один (воображаемый) массив.
1.2.22. (из книги Д.Гриса) Некоторое число содержится в
каждом из трех целочисленных неубывающих массивов x[1] "= ... "=
x[p], y[1] "= ... "= y[q], z[1] "= ... "= z[r]. Найти одно из
таких чисел. Число действий должно быть порядка p + q + r.
Решение.
p1:=1; q1=1; r1:=1;
{инвариант: x[p1]..x[p], y[q1]..y[q], z[r1]..z[r]
содержат общий элемент }
while not ((x[p1]=y[q1]) and (y[q1]=z[r1])) do begin
| if x[p1]"y[q1] then begin
| | p1:=p1+1;
| end else if y[q1]"z[r1] then begin
| | q1:=q1+1;
| end else if z[r1]"x[p1] then begin
| | r1:=r1+1;
| end else begin
| | { так не бывает }
| end;
end;
{x[p1] = y[q1] = z[r1]}
writeln (x[p1]);
1.2.23. Та же задача, только заранее не известно, существует
ли общий элемент в трех неубывающих массивах и требуется это
выяснить (и найти один из общих элементов, если они есть).
1.2.24. Элементами массива a[1..n] являются неубывающие
массивы [1..m] целых чисел (a: array [1..n] of array [1..m] of
integer; a[1][1] "= ... "= a[1][m], ..., a[n][1] "= ... "=
a[n][m]). Известно, что существует число, входящее во все массивы
a[i] (существует такое х, что для всякого i из [1..n]
найдётся j из [1..m], для которого a[i][j]=x). Найти одно из таких
чисел х.
Решение. Введем массив b[1]..b[n], отмечающий начало "остающейся
части" массивов a[1]..a[n].
for k:=1 to n do begin
| b[k]:=1;
end;
eq := true;
for k := 2 to n do begin
| eq := eq and (a[1][b[1]] = a[k][b[k]]);
end;
{инвариант: оставшиеся части пересекаются, т.е. существует
такое х, что для всякого i из [1..n] найдётся j из [1..m],
не меньшее b[i], для которого a[i][j] = х; eq "=" первые
элементы оставшихся частей равны}
while not eq do begin
| s := 1; k := 1;
| {a[s][b[s]] - минимальное среди a[1][b[1]]..a[k][b[k]]}
| while k "" n do begin
| | k := k + 1;
| | if a[k][b[k]] " a[s][b[s]] then begin
| | | s := k;
| | end;
| end;
| {a[s][b[s]] - минимальное среди a[1][b[1]]..a[n][b[n]]}
| b [s] := b [s] + 1;
| for k := 2 to n do begin
| | eq := eq and (a[1][b[1]] = a[k][b[k]]);
| end;
end;
writeln (a[1][b[1]]);
1.2.25. Приведенное решение предыдущей задачи требует порядка
m*n*n действий. Придумать способ с числом действий порядка
m*n.
Указание. Придется пожертвовать симметрией и выбрать одну
из строк за основную. Двигаясь по основной строке, поддерживаем
такое соотношение: во всех остальных строках отмечен максимальный
элемент, не превосходящий текущего элемента основной
строки.
1.2.26. (Двоичный поиск) Дана последовательность x[1] "=
... "= x[n] целых чисел и число a. Выяснить, содержится ли a в
этой последовательности, т. е. существует ли i из 1..n, для которого
x[i]=a. (Количество действий порядка log n.)
Решение. (Предполагаем, что n " 0.)
l := 1; r := n+1;
{если a есть вообще, то есть и среди x[l]..x[r-1], r " l}
while r - l "" 1 do begin
| m := l + (r-l) div 2 ;
| {l " m " r }
| if x[m] "= a then begin
| | l := m;
| end else begin {x[m] " a}
| | r := m;
| end;
end;
(Обратите внимание, что и в случае x[m] = a инвариант не нарушается.)
Каждый раз r-l уменьшается примерно вдвое, откуда и вытекает
требуемая оценка числа действий.
Замечание.
l + (r-l) div 2 = (2l + (r-l)) div 2 = (r+l) div 2.
1.2.27. (Из книги Д.Гриса) Дан массив x: array [1..n] of
array [1..m] of integer, упорядоченный по "строкам" и по
"столбцам":
x[i][j] "= x[i+1][j],
x[i][j] "= x[i][j+1]
и число a. Требуется выяснить, встречается ли a среди x[i][j].
Решение. Представляя себе массив a как матрицу (прямоугольник,
заполненный числами), мы выберем прямоугольник, в котором
только и может содержаться a, и будем его сужать. Прямоугольник
этот будет содержать x[i][j] при 1"=i"=l и k"=j"=m.
1 k m
-----------------------------------
1| |***********|
| |***********|
| |***********|
l| |***********|
|---------------------------------|
| |
n| |
-----------------------------------
(допускаются пустые прямоугольники при l = 0 и k = m+1).
l:=n; k:=1;
{l"=0, k"=m+1, если a есть, то в описанном прямоугольнике}
while (l " 0) and (k " m+1) and (x[l][k] "" a) do begin
| if x[l][k] " a then begin
| | k := k + 1; {левый столбец не содержит a, удаляем его}
| end else begin {x[l][k] " a}
| | l := l - 1; {нижняя строка не содержит a, удаляем ее}
| end;
end;
{x[l][k] = a или прямоугольник пуст }
answer:= (l " 0) and (k " m+1) ;
Замечание. Здесь та же ошибка: x[l][k] может оказаться неопределенным.
(Её исправление предоставляется читателю.)
1.2.28. (Московская олимпиада по программированию) Дан неубывающий
массив положительных целых чисел a[1] "= a[2] "=..."=
a[n]. Найти наименьшее целое положительное число, не представимое
в виде суммы нескольких элементов этого массива (каждый элемент
массива может быть использован не более одного раза). Число
действий порядка n.
Решение. Пусть известно, что числа, представимые в виде
суммы элементов a[1],...,a[k], заполняют отрезок от 1 до некоторого
N. Если a[k+1] " N+1, то N+1 и будет минимальным числом, не
представимым в виде суммы элементов массива a[1]..a[n]. Если же
a[k+1] "= N+1, то числа, представимые в виде суммы элементов
a[1]..a[k+1], заполняют отрезок от 1 до N+a[k+1].
k := 0; N := 0;
{инвариант: числа, представимые в виде суммы элементов массива
a[1]..a[k], заполняют отрезок 1..N}
while (k "" n) and (a[k+1] "= N+1) do begin
| N := N + a[k+1];
| k := k + 1;
end;
{(k = n) или (a[k+1] " N+1); в обоих случаях ответ N+1}
writeln (N+1);
(Снова тот же дефект: в условии цикла при ложном первом условии
второе не определено.)
1.2.29. (Для знакомых с основами алгебры) В целочисленном
массиве a[1]..a[n] хранится перестановка чисел 1..n (каждое из
чисел встречается по одному разу).
(а) Определить четность перестановки. (И в (а), и в (б) количество
действий порядка n.)
(б) Не используя других массивов, заменить перестановку на
обратную (если до работы программы a[i]=j, то после должно быть
a[j]=i).
Указание. (а) Четность перестановки определяется количеством
циклов. Чтобы отличать уже пройденные циклы, у их элементов
можно, например, менять знак. (б) Обращение производим по
циклам.
1.2.30. Дан массив a[1..n] и число b. Переставить числа в
массиве таким образом, чтобы слева от некоторой границы стояли
числа, меньшие или равные b, а справа от границы - большие или
равные b.
Решение.
l:=0; r:=n;
{инвариант: a[1]..a[l]"=b; a[r+1]..a[n]"=b}
while l "" r do begin
| if a[l+1] "= b then begin
| | l:=l+1;
| end else if a[r] "=b then begin
| | r:=r-1;
| end else begin {a[l+1]"b; a[r]"b}
| | поменять a[l+1] и a[r]
| | l:=l+1; r:+r-1;
| end;
end;
1.2.31. Та же задача, но требуется, чтобы сначала шли элементы,
меньшие b, затем равные b, а лишь затем большие b.
Решение. Теперь потребуются три границы: до первой будут
идти элементы, меньшие b, от первой до второй - равные b, затем
неизвестно какие до третьей, а после третьей - большие b. (Более
симметричное решение использовало бы четыре границы, но вряд ли
игра стоит свеч.) В качестве очередного рассматриваемого элемента
берем элемент справа от средней границы.
l:=0; m:=0; r:=n;
{инвариант: a[1..l]"b; a[l+1..m]=b; a[r+1]..a[n]"b}
while m "" r do begin
| if a[m+1]=b then begin
| | m:=m+1;
| end else if a[m+1]"b then begin
| | обменять a[m+1] и a[r]
| | r:=r-1;
| end else begin {a[m+1]"b}
| | обменять a[m+1] и a[l+1]
| | l:=l+1; m:=m+1;
end;
1.2.32. (вариант предыдущей задачи, названный в книге
Дейкстры задачей о голландском флаге) В массиве стоят числа 0, 1
и 2. Переставить их в порядке возрастания, если единственной
разрешенной операцией (помимо чтения) над массивом является перестановка
двух элементов.
1.2.33. Дан массив a[1]..a[n] и число m"=n. Для каждой
группы из m стоящих рядом членов (таких групп, очевидно, n-m+1)
вычислить ее сумму. Общее число действий должно быть порядка n.
Решение. Переходя от группы к соседней, мы добавляем один
член, а другой вычитаем.
1.2.34. Дана квадратная таблица a[1..n][1..n] и число m"=n.
Для каждого квадрата размера m на m в этой таблице вычислить
сумму стоящих в нем чисел. Общее число действий должно быть порядка
n*n.
Решение. Сначала для каждого горизонтального прямоугольника
размером n на 1 вычисляем сумму стоящих в нем чисел. (При сдвиге
такого прямоугольника по горизонтали на 1 нужно добавить одно
число и одно вычесть.) Затем, используя эти суммы, вычисляем
суммы в квадратах. (При сдвиге квадрата по вертикали добавляется
полоска, а другая полоска убавляется.)
1.3. Индуктивные функции (по А.Г.Кушниренко).
Пусть M - некоторое множество. Функция f, аргументами которой
являются последовательности элементов множества M, а значениями
- элементы некоторого множества N, называется индуктивной,
если ее значение на последовательности x[1]..x[n] можно восстановить
по ее значению на последовательности x[1]..x[n-1] и по
x[n], т. е. если существует функция F из N*M (множество пар
"n,m", где n - элемент множества N, а m - элемент множества M) в
N, для которой
f("x[1],...,x[n]") = F (f ("x[1],...,x[n-1]"), x[n]).
Схема алгоритма вычисления индуктивной функции:
k := 0; f := f0;
{инвариант: f - значение функции на "x[1],...,x[k]"}
while k"" n do begin
| k := k + 1;
| f := F (f, x[k]);
end;
Здесь f0 - значение функции на пустой последовательности
(последовательности длины 0). Если функция f определена только
на непустых последовательностях, то первая строка заменяется на
"k := 1; f := f ("x[1]");".
Индуктивные расширения.
Если функция f не является индуктивной, полезно искать ее
индуктивное расширение - такую индуктивную функцию g, значения
которой определяют значения f (это значит, что существует такая
функция t, что f ("x[1]...x[n]") = t (g ("x[1]...x[n]")) при
всех "x[1]...x[n]"). Можно доказать, что среди всех индуктивных
расширений существует минимальное расширение F (минимальность
означает, что для любого индуктивного расширения g значения F
определяются значениями g).
1.3.1. Указать индуктивные расширения для следующих
функций:
а) среднее арифметическое последовательности вещественных
чисел;
б) число элементов последовательности целых чисел, равных ее
максимальному элементу;
в) второй по величине элемент последовательности целых чисел
(тот, который будет вторым, если переставить члены в неубывающем
порядке);
г) максимальное число идущих подряд одинаковых элементов;
д) максимальная длина монотонного (неубывающего или невозрастающего)
участка из идущих подряд элементов в последовательности
целых чисел;
е) число групп из единиц, разделенных нулями (в последовательности
нулей и единиц).
Решение.
а) "сумма всех членов последовательности; длина";
б) "число элементов, равных максимальному; значение макси-
мального";
в) "наибольший элемент последовательности; второй по величине
элемент";
г) "максимальное число идущих подряд одинаковых элементов; чис-
ло идущих подряд одинаковых элементов в конце последова-
тельности; последний элемент последовательности";
д) "максимальная длина монотонного участка; максимальная длина
неубывающего участка в конце последовательности; макси-
мальная длина невозрастающего участка в конце последова-
тельности; последний член последовательности";
е) "число групп из единиц, последний член".
1.3.2. (Сообщил Д.Варсонофьев.) Даны две последовательности
x[1]..x[n] и y[1]..y[k] целых чисел. Выяснить, является ли вторая
последовательность подпоследовательностью первой, т. е. можно
ли из первой вычеркнуть некоторые члены так, чтобы осталась
вторая. Число действий порядка n+k.
Решение. (1 вариант) Будем сводить задачу к задаче
меньшего размера.
n1:=n;
k1:=k;
{инвариант: искомый ответ "=" возможность из x[1]..x[n1] по-
лучить y[1]..y[k1] }
while (n1 " 0) and (k1 " 0) do begin
| if x[n1] = y[k1] then begin
| | n1 := n1 - 1;
| | k1 := k1 - 1;
| end else begin
| | n1 := n1 - 1;
| end;
end;
{n1 = 0 или k1 = 0; если k1 = 0, то ответ - да, если k1 "" 0
(и n1 = 0), то ответ - нет}
answer := (k1 = 0);
Мы использовали то, что если x[n1] = y[k1] и y[1]..y[k1] -
подпоследовательность x[1]..x[n1], то y[1]..y[k1-1] - подпоследовательность
x[1]..x[n1-1].
(2 вариант) Функция x[1]..x[n1] |-" (максимальное k1, для
которого y[1]..y[k1] есть подпоследовательность x[1]..x[n1]) индуктивна.
1.3.3. Даны две последовательности x[1]..x[n] и y[1]..y[k]
целых чисел. Найти максимальную длину последовательности, являющейся
подпоследовательностью обеих последовательностей. Количество
операций порядка n*k.
Решение (сообщено М.Н.Вайнцвайгом, А.М.Диментманом). Обозначим
через f(n1,k1) максимальную длину общей подпоследовательности
последовательностей x[1]..x[n1] и y[1]..y[k1]. Тогда
x[n1] "" y[k1] =" f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1));
x[n1] = y[k1] =" f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1),
f(n1-1,k1-1)+1 );
(Поскольку f(n1-1,k1-1)+1 "= f(n1,k1-1), f(n1-1,k1), во втором
случае максимум трех чисел можно заменить на третье из них.)
Поэтому можно заполнять таблицу значений функции f, имеющую
размер n*k. Можно обойтись и памятью порядка k (или n), если индуктивно
(по n1) выписать "f(n1,0), ..., f(n1,k)" (как функция
от n1 этот набор индуктивен).
1.3.4 (из книги Д.Гриса) Дана последовательность целых чисел
x[1],..., x[n]. Найти максимальную длину ее возрастающей
подпоследовательности (число действий порядка n*log(n)).
Решение. Искомая функция не индуктивна, но имеет следующее
индуктивное расширение: в него входит помимо максимальной длины
возрастающей подпоследовательности (обозначим ее k) также и числа
u[1],...,u[k], где u[i] = (минимальный из последних членов
возрастающих подпоследовательностей длины i). Очевидно, u[1] "=
... "= u[k]. При добавлении нового члена x значения u и k корректируются.
n1 := 1; k := 1; u[1] := x[1];
{инвариант: k и u соответствуют данному выше описанию}
while n1 "" n do begin
| n1 := n1 + 1;
| ...
| {i - наибольшее из тех чисел отрезка 1..k, для кото-
| рых u[i] " x[n1]; если таких нет, то i=0 }
| if i = k then
...Закладка в соц.сетях
