Решение. Теперь потребуются три границы: до первой будут
идти элементы, меньшие b, от первой до второй - равные b, затем
неизвестно какие до третьей, а после третьей - большие b. (Более
симметричное решение использовало бы четыре границы, но вряд ли
игра стоит свеч.) В качестве очередного рассматриваемого элемен-
та берем элемент справа от средней границы.
l:=0; m:=0; r:=n;
{инвариант: a[1..l]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], где n - элемент множества N, а m - элемент множества M) в
N, для которой
f() = F (f (), x[n]).
Схема алгоритма вычисления индуктивной функции:
k := 0; f := f0;
{инвариант: f - значение функции на }
while k<> n do begin
| k := k + 1;
| f := F (f, x[k]);
end;
Здесь f0 - значение функции на пустой последовательности
(последовательности длины 0). Если функция f определена только
на непустых последовательностях, то первая строка заменяется на
"k := 1; f := f ();".
Индуктивные расширения.
Если функция f не является индуктивной, полезно искать ее
индуктивное расширение - такую индуктивную функцию g, значения
которой определяют значения f (это значит, что существует такая
функция t, что f () = t (g ()) при
всех ). Можно доказать, что среди всех индуктивных
расширений существует минимальное расширение 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) выписать (как функция
от 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 begin
| | k := k + 1;
| | u[k+1] := x[n1];
| end else begin {i < k, u[i] < x[n1] <= u[i+1] }
| | u[i+1] := x[n1];
| end;
end;
Фрагмент ... использует идею двоичного поиска; в инвариан-
те условно полагаем u[0] равным минус бесконечности, а u[k+1]
- плюс бесконечности; наша цель: u[i] < x[n1] <= u[i+1].
i:=0; j:=k+1;
{u[i] < x[n1] <= u[j], j > i}
while (j - i) <> 1 do begin
| s := i + (j-i) div 2; {i < s < j}
| if u[s] >= x[n1] then begin
| | j := s;
| end else begin {u[s] < x[n1]}
| | i := s;
| end;
end;
{u[i] < x[n1] <= u[j], j-i = 1}
Замечание. Более простое (но не минимальное) индуктивное
расширение получится, если для каждого i хранить максимальную
длину возрастающей подпоследовательности, оканчивающейся на
x[i]. Это расширение приводит к алгоритму с числом действий по-
рядка n*n.
1.3.5. Какие изменения нужно внести в решение предыдущей
задачи, если надо искать максимальную неубывающую последова-
тельность?
Глава 2. Порождение комбинаторных объектов.
Здесь собраны задачи, в которых требуется получить один за
другим все элементы некоторого множества.
2.1. Размещения с повторениями.
2.1.1. Напечатать все последовательности длины k из чисел
1..n.
Решение. Будем печатать их в лексикографическом порядке
(последовательность a предшествует последовательности b, если
для некоторого s их начальные отрезки длины s равны, а (s+1)-ый
член последовательности a меньше). Первой будет последова-
тельность <1, 1, ..., 1>, последней - последовательность . Будем хранить последнюю напечатанную последовательность
в массиве x[1]...x[k].
...x[1]...x[k] положить равным 1
...напечатать x
...last[1]...last[k] положить равным n
while x <> last do begin
| ...x := следующая за x последовательность
| ...напечатать x
end;
Опишем, как можно перейти от x к следующей последова-
тельности. Согласно определению, у следующей последовательности
первые s членов должны быть такими же, а (s+1)-ый - больше. Это
возможно, если x[s+1] было меньше n. Среди таких s нужно выбрать
наибольшее (иначе полученная последовательность не будет непос-
редственно следующей). Соответствующее x[s+1] нужно увеличить на
1. Итак, надо, двигаясь с конца последовательности, найти самый
правый член, меньший n (он найдется, так как по предположению
x<>last), увеличить его на 1, а идущие за ним члены положить
равными 1.
p:=k;
while not (x[p] < n) do begin
| p := p-1;
end;
{x[p] < n, x[p+1] =...= x[k] = n}
x[p] := x[p] + 1;
for i := p+1 to k do begin
| x[i]:=1;
end;
Замечание. Если членами последовательности считать числа не
от 1 до n, а от 0 до n-1, то переход к следующему соответствует
прибавлению 1 в n-ичной системе счисления.
2.1.2. В предложенном алгоритме используется сравнение двух
массивов x <> last. Устранить его, добавив булевскую переменную
l и включив в инвариант соотношение l <=> последовательность x -
последняя.
2.1.3. Напечатать все подмножества множества {1...k}.
Решение. Подмножества находятся во взаимно однозначном со-
ответствии с последовательностями нулей и единиц длины k.
2.1.4. Напечатать все последовательности из k положительных
целых чисел, у которых i-ый член не превосходит i.
2.2. Перестановки.
2.2.1. Напечатать все перестановки чисел 1..n (то есть пос-
ледовательности длины n, в которые каждое из чисел 1..n входит
по одному разу).
Решение. Перестановки будем хранить в массиве x[1],...,
x[n] и печатать в лексикографическом порядке. (Первой при этом
будет перестановка <1 2...n>, последней - .) Для сос-
тавления алгоритма перехода к следующей перестановке зададимся
вопросом: в каком случае k-ый член перестановки можно увеличить,
не меняя предыдущих? Ответ: если он меньше какого-либо из следу-
ющих членов (членов с номерами больше k). Мы должны найти на-
