торого 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}
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)).
Решение. Искомая функция не индуктивна, но имеет следующее
индуктивное расширение: в него входит помимо максимальной длины
