Программирование: теоремы и задачи (стр. 5 )

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) также и чис-