1.1.1. Даны две целые переменные a, b. Составить фрагмент программы, после исполнения которого значения переменных поменялись бы местами (новое значение a равно старому значению b и наоборот).
Решение. Введем дополнительную целую переменную t.
t := a;
a := b;
b := t;
Попытка обойтись без дополнительной переменной, написав
a := b;
b := a;
не приводит к цели (безвозвратно утрачивается начальное значение переменной a).
1.1.2. Решить предыдущую задачу, не используя дополнительных переменных (и предполагая, что значениями целых переменных могут быть произвольные целые числа).
Решение. (Начальные значения a и b обозначим a0, b0.)
a := a + b; {a = a0 + b0, b = b0}
b := a - b; {a = a0 + b0, b = a0}
a := a - b; {a = b0, b = a0}
1.1.3. Дано целое число а и натуральное (целое неотрицательное) число n. Вычислить а в степени n. Другими словами, необходимо составить программу, при исполнении которой значения
переменных а и n не меняются, а значение некоторой другой переменной (например, b) становится равным а в степени n. (При этом разрешается использовать и другие переменные.)
Решение. Введем целую переменную k, которая меняется от 0 до n, причем поддерживается такое свойство: b = (a в степениk).
k := 0; b := 1;
{b = a в степени k}
while k <> n do begin
| k := k + 1;
| b := b * a;
end;
Другое решение той же задачи:
k := n; b := 1;
{a в степени n = b * (a в степени k)}
while k <> 0 do begin
| k := k - 1;
| b := b * a;
end;
1.1.4. Решить предыдущую задачу, если требуется, чтобы число действий (выполняемых операторов присваивания) было порядка log n (то есть не превосходило бы C*log n для некоторой константы C; log n - это степень, в которую нужно возвести 2, чтобы получить n).
Решение. Внесем некоторые изменения во второе из предложенных решений предыдущей задачи:
k := n; b := 1; c:=a;
{a в степени n = b * (c в степени k)}
while k <> 0 do begin
| if k mod 2 = 0 then begin
| | k:= k div 2;
| | c:= c*c;
| end else begin
| | k := k - 1;
| | b := b * c;
| end;
end;
Каждый второй раз (не реже) будет выполняться первый вариант оператора выбора (если k нечетно, то после вычитания единицы становится четным), так что за два цикла величина k уменьшается по крайней мере вдвое.
1.1.5. Даны натуральные числа а, b. Вычислить произведение а*b, используя в программе лишь операции +, -, =, <>.
Решение.
var a, b, c, k : integer;
k := 0; c := 0;
{инвариант: c = a * k}
while k <> b do begin
| k := k + 1;
| c := c + a;
end;
{c = a * k и k = b, следовательно, c = a * b}
1.1.6. Даны натуральные числа а и b. Вычислить их сумму а+b. Использовать операторы присваивания лишь вида
<переменная1> := <переменная2>,
<переменная> := <число>,
<переменная1> := <переменная2> + 1.
Решение.
...
{инвариант: c = a + k}
...
1.1.7. Дано натуральное (целое неотрицательное) число а и целое положительное число d. Вычислить частное q и остаток r при делении а на d, не используя операций div и mod.
Решение. Согласно определению, a = q * d + r, 0 <= r < d.
{a >= 0; d > 0}
r := a; q := 0;
{инвариант: a = q * d + r, 0 <= r}
while not (r < d) do begin
| {r >= d}
| r := r - d; {r >= 0}
| q := q + 1;
end;
1.1.8. Дано натуральное n, вычислить n!(0!=1, n! = n * (n-1)!).
1.1.9. Последовательность Фибоначчи определяется так:
a(0)=
Дано n, вычислить a(n).
1.1.10. Та же задача, если требуется, чтобы число операций было пропорционально log n. (Переменные должны быть целочисленными.)
Указание. Пара соседних чисел Фибоначчи получается из предыдущей умножением на матрицу
|1 1|
|1 0|
так что задача сводится к возведению матрицы в степень n. Это можно сделать за C*log n действий тем же способом, что и для чисел.
1.1.11. Дано натуральное n, вычислить 1/0!+1/1!+...+1/n!.
1.1.12. То же, если требуется, чтобы количество операций (выполненных команд присваивания) было бы не более C*n для некоторой константы С.
Решение. Инвариант: sum = 1/1! +...+ 1/k!, last = 1/k! (важно не вычислять заново каждый раз k!).
1.1.13. Даны два натуральных числа a и b, не равные нулю одновременно. Вычислить НОД (a,b) - наибольший общий делитель а и b.
Решение (1 вариант).
if a > b then begin
| k := a;
end else begin
| k := b;
end;
{k = max (a,b)}
{инвариант: никакое число, большее k, не является об-
щим делителем}
while not (((a mod k)=0) and ((b mod k)=0)) do begin
| k := k - 1;
end;
{k - общий делитель, большие - нет}
(2 вариант - алгоритм Евклида). Будем считать , что НОД
(0,0) = 0. Тогда НОД (a,b) = НОД (a-b,b) = НОД (a,b-a); НОД
(a,0) = НОД (0,a) = a для всех a,b>=0.
m := a; n := b;
{инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 }
while not ((m=0) or (n=0)) do begin
| if m >= n then begin
| | m := m - n;
| end else begin
| | n := n - m;
| end;
end;
if m = 0 then begin
| k := n;
end else begin
| k := m;
end;
1.1.14. Написать модифицированный вариант алгоритма Евклида, использующий соотношения НОД (a, b) = НОД (a mod b, b) при a >= b, НОД (a, b) = НОД (a, b mod a) при b >= a.
1.1.15. Даны натуральные а и b, не равные 0 одновременно. Найти d = НОД (a,b) и такие целые x и y, что d = a*x + b*y.
Решение. Добавим в алгоритм Евклида переменные p, q, r, s и впишем в инвариант условия m = p*a + q*b; n = r*a + s*b.
m:=a; n:=b; p := 1; q := 0; r := 0; s := 1;
{инвариант: НОД (a,b) = НОД (m,n); m,n >= 0
m = p*a + q*b; n = r*a + s*b.}
while not ((m=0) or (n=0)) do begin
| if m >= n then begin
| | m := m - n; p := p - r; q := q - s;
| end else begin
| | n := n - m; r := r - p; s := s - q;
| end;
end;
if m = 0 then begin
| k :=n; x := r; y := s;
end else begin
| k := m; x := p; y := q;
end;
1.1.16. Решить предыдущую задачу, используя в алгоритме Евклида деление с остатком.
1.1.17. (Э.Дейкстра). Добавим в алгоритм Евклида дополнительные переменные u, v, z:
m := a; n := b; u := b; v := a;
{инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 }
while not ((m=0) or (n=0)) do begin
| if m >= n then begin
| | m := m - n; v := v + u;
| end else begin
| | n := n - m; u := u + v;
| end;
end;
if m = 0 then begin
| z:= v;
end else begin {n=0}
| z:= u;
end;
Доказать, что после исполнения алгоритма z равно удвоенному наименьшему общему кратному чисел a, b: z = 2 * НОК (a,b).
Решение. Заметим, что величина m*u + n*v не меняется в ходе выполнения алгоритма. Остается воспользоваться тем, что вначале она равна 2*a*b и что НОД (a, b) * НОК (a, b) = a*b.
1.1.18. Написать вариант алгоритма Евклида, использующий соотношения
НОД(2*a, 2*b) = 2*НОД(a,b)
НОД(2*a, b) = НОД(a,b) при нечетном b, не включающий деления с остатком, а использующий лишь деление на 2 и проверку четности. (Число действий должно быть порядка log k
для исходных данных, не превосходящих k.)
Решение.
m:= a; n:=b; d:=1;
{НОД(a,b) = d * НОД(m,n)}
while not ((m=0) or (n=0)) do begin
| if (m mod 2 = 0) and (n mod 2 = 0) then begin
| | d:= d*2; m:= m div 2; n:= n div 2;
| end else if (m mod 2 = 0) and (n mod 2 = 1) then begin
| | m:= m div 2;
| end else if (m mod 2 = 1) and (n mod 2 = 0) then begin
| | n:= n div 2;
| end else if (m mod 2=1) and (n mod 2=1) and (m>=n)then begin
| | m:= m-n;
| end else if (m mod 2=1) and (n mod 2=1) and (m<=n)then begin
| | n:= n-m;
| end;
end;
{m=0 => ответ=d*n; n=0 => ответ=d*m}
Оценка числа действий: каждое второе действие делит хотя бы одно из чисел m и n пополам.
1.1.19. Дополнить алгоритм предыдущей задачи поиском x и y,для которых ax+by=НОД(a,b).
Решение. (Идея сообщена Д.Звонкиным) Прежде всего заметим,что одновременое деление a и b пополам не меняет искомых x и y.Поэтому можно считать, что с самого начала одно из чисел a и b
нечетно. (Это свойство будет сохраняться и далее.)
Теперь попытаемся, как и раньше, хранить такие числа p,q,r,s, что
m = ap + bq
n = ar + bs
Проблема в том, что при делении, скажем, m на 2 надо разделить p и q на 2, и они перестанут быть целыми (а станут двоично-рациональными). Двоично-рациональное число естественно хранить в виде пары (числитель, показатель степени двойки в знаменателе). В итоге мы получаем d в виде комбинации a и b с двоично-рациональными коэффициентами. Иными словами, мы имеем
(2 в степени i)* d = ax + by
для некоторых целых x,y и натурального i. Что делать, если i > 1? Если x и y чётны, то на 2 можно сократить. Если это не так,положение можно исправить преобразованием
x := x + b
y := y - a
(оно не меняет ax+by). Убедимся в этом. Напомним, что мы считаем, что одно из чисел a и b нечётно. Пусть это будет a. Если при этом y чётно, то и x должно быть чётным (иначе ax+by будет нечётным). А при нечётном y вычитание из него нёчетного a делает y чётным.
1.1.20. Составить программу, печатающую квадраты всех натуральных чисел от 0 до заданного натурального n.
Решение.
k:=0;
writeln (k*k);
{инвариант: k<=n, напечатаны все
квадраты до k включительно}
while not (k=n) do begin
| k:=k+1;
| writeln (k*k);
end;
1.1.21. Та же задача, но разрешается использовать из арифметических операций лишь сложение и вычитание, причем общее число действий должно быть порядка n.
Решение. Введем переменную k_square (square - квадрат),связанную с k соотношением
k_square = k*k:
k := 0; k_square := 0;
writeln (k_square);
while not (k = n) do begin
| k := k + 1;
| {k_square = (k-1) * (k-1) = k*k - 2*k + 1}
| k_square := k_square + k + k - 1;
| writeln (k_square);
end;
1.1.22. Составить программу, печатающую разложение на простые множители заданного натурального числа n > 0 (другими словами, требуется печатать только простые числа и произведение напечатанных чисел должно быть равно n; если n = 1, печатать ничего не надо).
Решение (1 вариант).
k := n;
{инвариант: произведение напечатанных чисел и k равно
n, напечатаны только простые числа}
while not (k = 1) do begin
| l := 2;
| {инвариант: k не имеет делителей в интервале (1,l)}
| while k mod l <> 0 do begin
| | l := l + 1;
| end;
| {l - наименьший делитель k, больший 1, следовательно,
| простой}
| writeln (l);
| k:=k div l;
end;
(2 вариант).
k := n; l := 2;
{произведение k и напечатанных чисел равно n; напеча-
танные числа просты; k не имеет делителей, меньших l}
while not (k = 1) do begin
| if k mod l = 0 then begin
| | {k делится на l и не имеет делителей,
| | меньших l, значит, l просто}
| | k := k div l;
| | writeln (l);
| end else begin
| | { k не делится на l }
| | l := l + 1;
| end;
end;
1.1.23. Составить программу решения предыдущей задачи, использующую тот факт, что составное число имеет делитель, не превосходящий квадратного корня из этого числа.
Решение. Во втором варианте решения вместо l:=l+1 можно написать
if l*l > k then begin
| l:=k;
end else begin
| l:=l+1;
end;
1.1.24. Проверить, является ли заданное натуральное число n > 1 простым.
1.1.25. (Для знакомых с основами алгебры). Дано целое гауссово число n + mi (принадлежащее Z[i]). (a) Проверить, является ли оно простым (в Z[i]); (б) напечатать его разложение на простые (в Z[i]) множители.
1.1.26. Разрешим использовать команды write (i) лишь при i = 0,1,2,...,9. Составить программу, печатающую десятичную запись заданного натурального числа n > 0. (Случай n = 0 явился
бы некоторым исключением, так как обычно нули в начале числа не печатаются, а для n = 0 - печатаются.)
Решение.
base:=1;
{base - степень 10, не превосходящая n}
while 10 * base <= n do begin
| base:= base * 10;
end;
{base - максимальная степень 10, не превосходящая n}
k:=n;
{инвариант: осталось напечатать k с тем же числом
знаков, что в base; base = 100..00}
while base <> 1 do begin
| write(k div base);
| k:= k mod base;
| base:= base div 10;
end;
{base=1; осталось напечатать однозначное число k}
write(k);
(Типичная ошибка при решении этой задачи: неправильно обрабатываются числа с нулями посередине. Приведенный инвариант допускает случай, когда k < base; в этом случае печатание k начинается
со старших нулей.)
1.1.27. То же самое, но надо напечатать десятичную запись в обратном порядке. (Для n = 173 надо напечатать 371.)
Решение.
k:= n;
{инвариант: осталось напечатать k в обратном порядке}
while k <> 0 do begin
| write (k mod 10);
| k:= k div 10;
end;
1.1.28. Дано натуральное n. Подсчитать количество решений неравенства x*x + y*y < n в натуральных (неотрицательных целых)числах, не используя действий с вещественными числами.
Решение.
k := 0; s := 0;
{инвариант: s = количество решений неравенства
x*x + y*y < n c x < k}
while k*k < n do begin
| ...
| {t = число решений неравенства k*k + y*y < n
| (при данном k) }
| k := k + 1;
| s := s + t;
end;
{k*k >= n, поэтому s = количество всех решений неравенства}
Здесь ... - пока еще не написанный кусок программы, который будет таким:
l := 0; t := 0;
{инвариант: t = число решений
неравенства k*k + y*y < n c y < l }
while k*k + l*l < n do begin
| l := l + 1;
| t := t + 1;
end;
{k*k + l*l >= n, поэтому t = число всех решений неравенства k*k + y*y < n}
1.1.29. Та же задача, но количество операций должно быть порядка (n в степени 1/2). (В предыдущем решении, как можно подсчитать, порядка n операций.)
Решение. Нас интересуют точки решетки (с целыми координата-
* ми) в первом квадранте, попадающие внутрь круга
* * * радиуса (n в степени 1/2). Интересующее нас
* * * * множество (назовем его X) состоит из объедине-
* * * * ния вертикальных столбцов убывающей высоты.
* * * * * Идея решения состоит в том, чтобы "двигаться вдоль его границы", спускаясь по верхнему его краю, как по лестнице. Координаты движущейся точки обозначим <k,l>. Введем
еще одну переменную s и будем поддерживать истинность такого условия:
<k,l> находится сразу над k-ым столбцом;
s - число точек в предыдущих столбцах.
Формально:
l - минимальное среди тех l >= 0, для которых <k,l> не принад лежит X;
s - число пар натуральных x, y, для которых x < k и <x,y> принадлежит X.
Обозначим эти условия через (И).
k := 0; l := 0;
while "<0,l> принадлежит X" do begin
| l := l + 1;
end;
{k =
для которых <k,l> не принадлежит X }
s := 0;
{инвариант: И}
while not (l = 0) do begin
| s := s + l;
| {s - число точек в столбцах до k-го включительно}
| k := k + 1;
| {точка <k,l> лежит вне X, но, возможно, ее надо сдвинуть
| вниз, чтобы восстановить И }
| while (l <> 0) and ("<k, l-1> не принадлежит X") do begin
| | l := l - 1;
| end;
end;
{И, l = 0, поэтому k-ый столбец и все следующие пусты, а s равно искомому числу}
Оценка числа действий очевидна: сначала мы движемся вверх не более чем на (n в степени 1/2) шагов, а затем вниз и вправо – в каждую сторону не более чем на (n в степени 1/2) шагов.
1.1.30. Даны натуральные числа n и k, n > 1. Напечатать k десятичных знаков числа 1/n. (При наличии двух десятичных разложений выбирается то из них, которое не содержит девятки в периоде.) Программа должна использовать только целые переменные.
Решение. Сдвинув в десятичной записи числа 1/n запятую на k мест вправо, получим число (10 в степени k)/n. Нам надо напечатать его целую часть, т. е. разделить (10 в степени k) на n на-
цело. Стандартный способ требует использования больших по величине чисел, которые могут выйти за границы диапазона представимых чисел. Поэтому мы сделаем иначе (следуя обычному методу "деления уголком") и будем хранить "остаток" r:
l := 0; r := 1;
{инв.: напечатано l разрядов 1/n, осталось напечатать
k - l разрядов дроби r/n}
while l <> k do begin
| write ( (10 * r) div n);
| r := (10 * r) mod n;
| l := l + 1;
end;
1.1.31. Дано натуральное число n > 1. Определить длину периода десятичной записи дроби 1/n.
Решение. Период дроби равен периоду в последовательности остатков (докажите это; в частности, надо доказать, что он не может быть меньше). Кроме того, в этой последовательности все периодически повторяющиеся все члены различны, а предпериод имеет длину не более n. Поэтому достаточно найти (n+1)-ый член последовательности остатков и затем минимальное k, при котором(n+1+k)-ый член совпадает с (n+1)-ым.
l := 0; r := 1;
{инвариант: r/n = результат отбрасывания l знаков в 1/n}
while l <> n+1 do begin
| r := (10 * r) mod n;
| l := l + 1;
end;
c := r;
{c = (n+1)-ый член последовательности остатков}
r := (10 * r) mod n;
k := 0;
{r = (n+k+1)-ый член последовательности остатков}
while r <> c do begin
| r := (10 * r) mod n;
| k := k + 1;
end;
1.1.32 (Э. Дейкстра). Функция f с натуральными аргументами и значениями определена так: f(0) =
по заданному n, требующую порядка log n операций.
Решение.
k := n; a := 1; b := 0;
{инвариант: 0 <= k, f (n) = a * f(k) + b * f (k+1)}
while k <> 0 do begin
| if k mod 2 = 0 then begin
| | l := k div 2;
| | {k = 2l, f(k) = f(l), f (k+1) = f (2l+1) = f(l) + f(l+1),
| | f (n) = a*f(k) + b*f(k+1) = (a+b)*f(l) + b*f(l+1)}
| | a := a + b; k := l;
| end else begin
| | l := k div 2;
| | {k = 2l +
| | f(k+1) = f(2l+2) = f(l+1),
| | f(n) = a*f(k) + b*f(k+1) = a*f(l) + (a+b)*f(l+1)}
| | b := a + b; k := l;
| end;
end;
{k =
1.1.33. То же, если f(0) =
Указание. Хранить коэффициенты в выражении f(n) через три соседних числа.
1.1.34. Даны натуральные числа а и b, причем b > 0. Найти частное и остаток при делении а на b, оперируя лишь с целыми числами и не используя операции div и mod, за исключением деления на 2 четных чисел; число шагов не должно превосходить C1*log(a/b) + C2 для некоторых констант C1, C2.
Решение.
b1 := b;
while b1 <= a do begin
| b1 := b1 * 2;
end;
{b1 > a, b1 = b * (некоторая степень 2)}
q:=0; r:=a;
{инвариант: q, r - частное и остаток при делении a на b1,
b1 = b * (некоторая степень 2)}
while b1 <> b do begin
| b1 := b1 div 2 ; q := q * 2;
| { a = b1 * q + r, 0 <= r, r < 2 * b1}
| if r >= b1 then begin
| | r := r - b1;
| | q := q + 1;
| end;
end;
{q, r - частное и остаток при делении a на b}
В следующих задачах переменные x, y, z предполагаются описанными как array [1..n] of integer (n - некоторое натуральное число, большее 0), если иное не оговорено явно.
1.2.1. Заполнить массив x нулями. (Это означает, что нужно составить фрагмент программы, после выполнения которого все значения x[1]..x[n] равнялись бы нулю, независимо от начального
значения переменной x.)
Решение.
i := 0;
{инвариант: первые i значений x[1]..x[i] равны 0}
while i <> n do begin
| i := i + 1;
| {x[1]..x[i-1] = 0}
| x[i] := 0;
end;
1.2.2. Подсчитать количество нулей в массиве x. (Составить фрагмент программы, не меняющий значения x, после исполнения которого значение некоторой целой переменной k равнялось бы числу
нулей среди компонент массива x.)
Решение.
...
{инвариант: k= число нулей среди x[1]...x[i] }
...
1.2.3. Не используя оператора присваивания для массивов,составить фрагмент программы, эквивалентный оператору x:=y.
Решение.
i := 0;
{инвариант: значение y не изменилось, x[l] = y[l] при l <= i}
while i <> n do begin
| i := i + 1;
| x[i] := y[i];
end;
1.2.4. Найти максимум из x[1]..x[n].
Решение.
i := 1; max := x[1];
{инвариант: max = максимум из x[1]..x[i]}
while i <> n do begin
| i := i + 1;
| {max = максимум из x[1]..x[i-1]}
| if x[i] > max then begin
| | max := x[i];
| end;
end;
1.2.5. Дан массив x: array [1..n] of integer, причём x[1]<= x[2] <= ... <= x[n]. Найти количество различных чисел среди элементов этого массива.
Решение. (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 нужно добавить одно
число и одно вычесть.) Затем, используя эти суммы, вычисляем суммы в квадратах. (При сдвиге квадрата по вертикали добавляется полоска, а другая полоска убавляется.)
Пусть 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 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. Какие изменения нужно внести в решение предыдущей задачи, если надо искать максимальную неубывающую последовательность?