убывающий массив положительных целых чисел 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}
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
