Переменные, выражения, присваивания

1.1.7. Дано натуральное (целое неотрицательное) число а и целое положительное число d. Вычислить частное q и остаток r при делении а на d, не используя операций div и mod.

Решение. Согласно определению, $$a=q\cdot d+r$$, $$0 \le 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\cdot (n-1)$$!).

1.1.9.Последовательность Фибоначчи определяется так: $$a_0=0$$, $$a_1=1$$, $$a_k= a_{k-1} +a_{k-2}$$ при $$k\ge 2$$. Дано $$n$$, вычислить $$a_n$$.

1.1.10. Та же задача, если требуется, чтобы число операций было пропорционально $$log n$$. (Переменные должны быть целочисленными.)

Указание. Пара соседних чисел Фибоначчи получается из предыдущей умножением на матрицу

- так что задача сводится к возведению матрицы в степень $$n$$. Это можно сделать за $$Clog n$$ действий тем же способом, что и для чисел.

1.1.11. Дано натуральное n, вычислить

1.1.12. То же, если требуется, чтобы количество операций (выполненных команд присваивания) было бы порядка $$n$$ (не более $$Cn$$ для некоторой константы $$C$$ ).

Решение. Инвариант: $$sum =1/1!+\ldots+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\ge 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; 
{m = 0 или n = 0} 
if m = 0 then begin 
| k := n; 
end else begin {n = 0} 
| k := m; 
end;

1.1.14.Написать модифицированный вариант алгоритма Евклида, использующий соотношения НОД(a,b) = НОД(a mod b, b) при $$a\ge b$$, НОД(a,b) = НОД(a, b mod a) при $$b\ge a$$.

1.1.15. Даны натуральные a и b, не равные 0 одновременно. Найти d = НОД(a,b) и такие целые x и y, что $$d = a\cdot x + b\cdot 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\cdot НОК(a,b)$$.

Решение. Заметим, что величина $$m\cdot u + n\cdot v$$ не меняется в ходе выполнения алгоритма. Остается воспользоваться тем, что вначале она равна $$2ab$$ и что $$НОД (a,b) \cdot НОК (a, b) = ab$$.

1.1.18. Написать вариант алгоритма Евклида, использующий соотношения

не включающий деления с остатком, а использующий лишь деление на 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$$, что$$\begin{align*} m =ap + bq,\\ n =ar + bs. \end{align*}$$ Проблема в том, что при делении, скажем, m на 2 надо разделить p и q на 2, и они перестанут быть целыми (а станут двоично-рациональными). Двоично-рациональное число естественно хранить в виде пары $$\langle$$ числитель, показатель степени двойки в знаменателе $$\rangle$$. В итоге мы получаем d в виде комбинации a и b с двоично-рациональными коэффициентами. Иными словами, мы имеем$$2^{i}d = ax + by$$ для некоторых целых $$x,y$$ и натурального $$i$$. Что делать, если $$i > 1$$? Если x и y четны, то на 2 можно сократить. Если это не так, положение можно исправить преобразованием$$\begin{align*} x\mathbin:=x + b, \\ y\mathbin:=y - a \end{align*}$$ (оно не меняет $$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^2$$:

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;

Замечание. Можно обойтись без вычитания с помощью такой хитрости:

while not (k = n) do begin 
| k_square := k_square + k; 
| {k_square = k*k + k} 
| k := k + 1; 
| {k_square = (k-1)*(k-1)+(k-1)=k*k-k} 
| k_square := k_square + k; 
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$$ (принадлежащее $$\mathbb{Z}[i]$$ ).

(a) Проверить, является ли оно простым (в $$\mathbb{Z}[i]$$ ).

(б) Напечатать его разложение на простые (в $$\mathbb{Z}[i]$$ ) множители.

1.1.26.Разрешим применять команды write(i) лишь при $$i=0,1,\allowbreak2,\ldots,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^2 + y^2 < 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 
|  с y>=0 (при данном k) } 
| k := k + 1; 
| s := s + t; 
end; 
{k*k >= n, поэтому s = количество всех решений 
  неравенства}

Здесь ... - пока еще не написанный кусок программы, который будет таким:

l := 0; t := 0; 
{инвариант: t = число решений 
  неравенства k*k + y*y < n c 0<=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. Та же задача, но количество операций должно быть порядка $$\sqrt{n}$$. (В предыдущем решении, как можно подсчитать, порядка n операций.)

Решение. Нас интересуют точки решетки (с целыми координатами) в первом квадранте, попадающие внутрь круга радиуса $$\sqrt{n}$$. Интересующее нас множество (назовем его X ) состоит из объединения вертикальных столбцов убывающей высоты. Идея решения состоит в том, чтобы "двигаться вдоль его границы", спускаясь по верхнему его краю, как по лестнице. Координаты движущейся точки обозначим <k,l>. Введем еще одну переменную s и будем поддерживать истинность такого условия:$$\begin{quote} \rule{0pt}{0pt}<k,l> находится сразу над k-ым столбцом; \\ s - число точек в предыдущих столбцах. \end{quote}$$ Формально:

Обозначим эти условия через (И).

k := 0; l := 0; 
while <0,l> принадлежит X do begin 
| l := l + 1; 
end; 
{k = 0, l - минимальное среди тех l >= 0, 
 для которых <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 равно искомому числу}

Оценка числа действий очевидна: сначала мы движемся вверх не более чем на $$\sqrt{n}$$ шагов, а затем вниз и вправо - в каждую сторону не более чем на $$\sqrt{n}$$ шагов.

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 := 1; 
{r = (n+k+1)-ый член последовательности остатков} 
while r <> c do begin 
| r := (10 * r) mod n; 
| k := k + 1; 
end;

1.1.32.(Сообщил Ю. В. Матиясевич) Дана функция $$f:\{1\ldots N\} \to\{1\ldots N\}$$ Найти период последовательности $$1,f(1),f(f(1),\ldots $$ Количество действий должно быть пропорционально суммарной длине предпериода и периода (эта сумма может быть существенно меньше N ).

Решение. Если отбросить начальный кусок, последовательность периодична, причем все члены периода различны.

{Обозначение: f[n,1]=f(f(...f(1)...)) (n раз)} 
k:=1; a:=f(1); b:=f(f(1)); 
{a=f[k,1]; b=f[2k,1]} 
while a <> b do begin 
| k:=k+1; a:=f(a); b:=f(f(b)); 
end; 
{a=f[k,1]=f[2k,1]; f[k,1] входит в периодическую часть} 
l:=1; b:=f(a); 
{b=f[k+l,1]; f[k,1],...,f[k+l-1,1] различны} 
while a <> b do begin 
| l:=l+1; b:=f(b); 
end; 
{период равен l}

1.1.33. (Э. Дейкстра) Функция f с натуральными аргументами и значениями определена так: $$f(0) = 0$$, $$f(1)=1$$, $$f(2n) = f(n)$$, $$f(2n+1) = f(n) + f(n+1)$$. Составить программу вычисления $$f(n)$$ по заданному 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 + 1, f(k) = f(l) + f(l+1), 
 | |  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 = 0, f(n) = a * f(0) + b * f(1) = b, что и требовалось}

1.1.34. То же, если $$f(0) = 13$$, $$f(1) = 17$$, $$f(2) = 20$$, $$f(3) = 30$$, $$f(2n) = 43\,f(n) + 57\,f(n+1)$$, $$f(2n+1) = 91\,f(n) + 179\,f(n+1)$$ при $$n\ge 2$$.

Указание. Хранить коэффициенты в выражении $$f(n)$$ через три соседних числа.

1.1.35. Даны натуральные числа а и b, причем $$b>0$$. Найти частное и остаток при делении a на b, оперируя лишь с целыми числами и не используя операции div и mod, за исключением деления на 2 четных чисел; число шагов не должно превосходить $$C_1 log(a/b)+C_2$$ для некоторых констант $$C_1, C_2$$

Решение.

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}

1.2. Массивы

В следующих задачах переменные $$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]\le x[2]\le\ldots\le 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. Дан массив x: array[1..n] of integer. Найти количество различных чисел среди элементов этого массива. (Число действий должно быть порядка $$n^2$$ )

1.2.7. Та же задача, если требуется, чтобы количество действий было порядка $$n log n$$.

Указание. Смотри лекцию 4 (Сортировка)

1.2.8.Та же задача, если известно, что все элементы массива - числа от 1 до k и число действий должно быть порядка $$n+k$$.

1.2.9. (Сообщил А. Л. Брудно) Прямоугольное поле $$m\times n$$ разбито на $$mn$$ квадратных клеток. Некоторые клетки покрашены в черный цвет. Известно, что все черные клетки могут быть разбиты на несколько непересекающихся и не имеющих общих вершин черных прямоугольников. Считая, что цвета клеток даны в виде массива типа

array [1..m] of array [1..n] of boolean;

подсчитать число черных прямоугольников, о которых шла речь. Число действий должно быть порядка $$mn$$.

Решение. Число прямоугольников равно числу их левых верхних углов. Является ли клетка верхним углом, можно узнать, посмотрев на ее цвет, а также цвет верхнего и левого соседей. (Не забудьте, что их может не быть, если клетка с краю.)

1.2.10. Дан массив x[1]..x[n] целых чисел. Не используя других массивов, переставить элементы массива в обратном порядке.

Решение. Элементы x[i] и x[n+1-i] нужно поменять местами для всех i, для которых $$i<n+1-i$$, то есть$$$\w{2}\w{i} < \w{n} + \w{1}$~$\Leftrightarrow$ $\w{2}\w{i}\le \w{n}\hm\Leftrightarrow \w{i} \le \text{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[r]. Предположим, что длина левого участка (назовем его $$A$$ ) не больше длины правого (назовем его $$B$$ ). Выделим в $$B$$ начало той же длины, что и $$A$$, назовем его $$B_1$$, а остаток $$B_2$$. (Так что $$B=B_1+B_2$$, если обозначать плюсом приписывание массивов друг к другу.) Нам надо из $$A+B_1+B_2$$ получить $$B_1+B_2+A$$. Меняя местами участки $$A$$ и $$B_1$$ - они имеют одинаковую длину, и сделать это легко, - получаем $$B_1 + A + B_2$$, и осталось поменять местами $$A$$ и $$B_2$$. Тем самым мы свели дело к перестановке двух отрезков меньшей длины. Итак, получаем такую схему программы:

p := 0; q := m; r := m + n; 
{инвариант: осталось переставить x[p+1..q], x[q+1..r]} 
while (p <> q) and (q <> r) do begin 
| {оба участка непусты} 
| if (q - p) <= (r - 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+\ldots+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)$$ к многочлену $$xP(x)+c$$. Его производная в точке $$x$$ равна $$xP'(x) + P(x)$$. (Это решение обладает забавным свойством: не надо знать заранее степень многочлена. Если требовать выполнения этого условия, да еще просить вычислять только значение производной, не упоминая о самом многочлене, получается не такая уж простая задача.)

Общее утверждение о сложности вычисления производных таково:

1.2.14. (В. Баур, Ф. Штрассен) Дана программа вычисления значения некоторого многочлена $$P(x_1,\ldots,x_n)$$, содержащая только команды присваивания. Их правые части - выражения, содержащие сложение, умножение, константы, переменные $$x_1,\ldots,x_n$$ и ранее встречавшиеся (в левой части) переменные. Доказать, что существует программа того же типа, вычисляющая все $$n$$ производных $$\partial P/\partial x_1,\ldots, \partial P/\partial x_n$$, причем общее число арифметических операций не более чем в $$C$$ раз превосходит число арифметических операций в исходной программе. Константа $$C$$ не зависит от $$n$$.

Указание. Можно считать, что каждая команда - сложение двух чисел, умножение двух чисел или умножение на константу. Использовать индукцию по числу команд, применяя индуктивное предположение к программе, получающейся отбрасыванием первой команды.

1.2.15.В массивах 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 содержит коэффициент при степени 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.16. Предложенный выше алгоритм перемножения многочленов требует порядка $$n^2$$ действий для перемножения двух многочленов степени $$n$$. Придумать более эффективный (для больших $$n$$ ) алгоритм, которому достаточно порядка $$n^{log 4/log 3}$$ действий.

Указание. Представим себе, что надо перемножить два многочлена степени $$2k$$. Их можно представить в виде$$A(x)\,x^k + B(x) \quad и \quad C(x)\,x^k + D(x).$$ Произведение их равно$$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.17.Даны два возрастающих массива 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.18.Решить предыдущую задачу, если про массивы известно лишь, что $$x[1]\le\ldots\le x[k]$$ и $$y[1]\le\ldots\le y[l]$$ (возрастание заменено неубыванием).

Решение. Условие возрастания было использовано в третьей альтернативе выбора: сдвинув k1 и l1 на 1, мы тем самым уменьшали на 1 количество общих элементов в $$x[k1+1]\ldots x[k]$$ и $$x[l1+1]\ldots 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; 
| n := n + 1; 
end;

Замечание. Эта программа имеет дефект: при проверке условия$$$$ \w{(k1<k) and (x[k1+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.19. Даны два неубывающих массива x: array[1..k] of integer и y: array[1..l] of integer. Найти число различных элементов среди $$x[1],\ldots,x[k],y[1],\ldots,y[l]$$. (Число действий порядка $$k+l$$.)

1.2.20. Даны два массива $$x[1]\le\ldots\le x[k]$$ и $$y[1]\le\ldots\le y[l]$$. "Соединить" их в массив $$z[1]\le\ldots\le 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.21. Даны два массива $$x[1]\le\ldots\le x[k]$$ и $$y[1]\le\ldots\le y[l]$$. Найти их " пересечение", то есть массив $$z[1]\le\ldots\le z[m],$$ содержащий их общие элементы, причем кратность каждого элемента в массиве z равняется минимуму из его кратностей в массивах x и y. Число действий порядка $$k+l$$.

1.2.22. Даны два массива $$x[1]\le\ldots\le x[k]$$ и $$y[1]\le\ldots\le y[l]$$ и число q. Найти сумму вида $$x[i]+y[j]$$, наиболее близкую к числу q. (Число действий порядка k+l, дополнительная память - фиксированное число целых переменных, сами массивы менять не разрешается.)

Указание. Надо найти минимальное расстояние между элементами $$x[1]\le\ldots\le x[k]$$ и $$q-y[l]\le\ldots\le q-y[1]$$, что нетрудно сделать в ходе их слияния в один (воображаемый) массив.

1.2.23. (из книги Д. Гриса) Некоторое число содержится в каждом из трех целочисленных неубывающих массивов $$x[1]\le\ldots\le x[p]$$, $$y[1]\le\ldots\le y[q]$$, $$z[1]\le\ldots\le 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.24. Та же задача, только заранее не известно, существует ли общий элемент в трех неубывающих массивах и требуется это выяснить (и найти один из общих элементов, если они есть).

1.2.25. Элементами массива a[1..n] являются неубывающие массивы [1..m] целых чисел:$$\begin{multiple} \text{a: array [1..n] \text {of array} [1..m] \text {of integer};}\\ % \w{a[1][1]}\le\ldots\le\w{a[1][m]},\ldots, \w{a[n][1]}\le\ldots\le\w{a[n][m]}. \end{multiple)$$ Известно, что существует число, входящее во все массивы a[i] (существует такое x, что для всякого i из 1..n найдется j из 1..m, для которого $$a[i][j]=x$$ ). Найти одно из таких чисел х.

Решение. Введем массив $$b[1]\ldots b[n]$$, отмечающий начало "остающейся части" массивов $$a[1],\ldots,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.26. Приведенное решение предыдущей задачи требует порядка $$mn^2$$ действий. Придумать способ с числом действий порядка mn.

Указание. Придется пожертвовать симметрией и выбрать одну из строк за основную. Двигаясь по основной строке, поддерживаем такое соотношение: во всех остальных строках отмечен максимальный элемент, не превосходящий текущего элемента основной строки.

1.2.27. (Двоичный поиск) Дана последовательность $$x[1]\le\ldots\le x[n]$$ целых чисел и число a. Выяснить, содержится ли a в этой последовательности, то есть существует ли i из 1..n, для которого $$x[i]=a$$. (Количество действий порядка $$log n$$.)

Решение. (Предполагаем, что $$n>0$$.)

l := 1; r := n+1; 
{r > l, если a есть вообще, то есть и среди x[l]..x[r-1]} 
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.28. (Из книги Д. Гриса) Имеется массив x: array[1..n] of array[1..m] of integer, упорядоченный по строкам и по столбцам:$$x[i][j] \le x[i][j+1],\\ x[i][j] \le x[i+1][j],$$ и число a. Требуется выяснить, встречается ли a среди x[i][j].

Решение. Представляя себе массив x как матрицу (прямоугольник, заполненный числами), мы выберем прямоугольник, в котором только и может содержаться a, и будем его сужать. Прямоугольник этот будет содержать x[i][j] при $$1\le i\le l$$ и $$k\le j\le m$$ (допускаются пустые прямоугольники при $$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.29. (Московская олимпиада по программированию) Дан неубывающий массив положительных целых чисел $$a[1]\le a[2]\le\ldots\le a[n]$$. Найти наименьшее целое положительное число, не представимое в виде суммы нескольких элементов этого массива (каждый элемент массива может быть использован не более одного раза). Число действий порядка n.

Решение. Пусть известно, что числа, представимые в виде суммы элементов $$a[1],\ldots,a[k]$$, заполняют отрезок от 1 до некоторого N. Если $$a[k+1] > N+1$$, то $$N+1$$ и будет минимальным числом, не представимым в виде суммы элементов массива $$a[1]\ldots a[n]$$. Если же $$a[k+1]\le N+1$$, то числа, представимые в виде суммы элементов $$a[1]\ldots 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.30. (Для знакомых с основами алгебры) В целочисленном массиве $$a[1]\ldots a[n]$$ хранится перестановка чисел $$1\ldots n$$ (каждое из чисел встречается по одному разу).

(а) Определить четность перестановки. (И в (а), и в (б) количество действий порядка $$n$$.)

(б) Не используя других массивов, заменить перестановку на обратную (если до работы программы $$a[i]=j$$, то после должно быть $$a[j]=i$$ ).

Указание. (а) Четность перестановки определяется количеством циклов. Чтобы отличать уже пройденные циклы, у их элементов можно, например, менять знак. (б) Обращение производим по циклам.

1.2.31. Дан массив a[1..n] и число b. Переставить числа в массиве таким образом, чтобы слева от некоторой границы стояли числа, меньшие или равные b, а справа от границы - большие или равные b. Число действий порядка n.

Решение.

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.32. Та же задача, но требуется, чтобы сначала шли элементы, меньшие 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; 
end;

1.2.33. (Вариант предыдущей задачи, названный в книге Дейкстры задачей о голландском флаге.) В массиве длины n стоят числа 0, 1 и 2. Переставить их в порядке возрастания, если единственной разрешенной операцией (помимо чтения) над массивом является перестановка двух элементов. Число действий порядка n.

1.2.34. Дан массив a[1..n] и число $$m\le n$$. Для каждого участка из m стоящих рядом членов (таких участков, очевидно, $$n-m+1$$ ) вычислить его сумму. Общее число действий должно быть порядка n.

Решение. Переходя от участка к соседнему, мы добавляем один член, а другой вычитаем.

1.2.35. Дана квадратная таблица a[1..n][1..n] и число $$m\le n$$. Для каждого квадрата $$m\times m$$ в этой таблице вычислить сумму стоящих в нем чисел. Общее число действий порядка $$n^2$$.

Решение. Сначала для каждого горизонтального прямоугольника размером $$m\times 1$$ вычисляем сумму стоящих в нем чисел. (При сдвиге такого прямоугольника по горизонтали на 1 нужно добавить одно число и одно вычесть.) Затем, используя эти суммы, вычисляем суммы в квадратах. (При сдвиге квадрата по вертикали добавляется полоска, а другая полоска убавляется.)

1.2.36. В массиве $$a[1]\ldots a[n]$$ встречаются по одному разу все целые числа от 0 до n, кроме одного. Найти пропущенное число за время порядка n и с конечной дополнительной памятью.

Указание. Сложить все числа в массиве.

1.3.Индуктивные функции (по А. Г. Кушниренко)

Пусть M - некоторое множество. Функция f, аргументами которой являются последовательности элементов множества M, а значениями - элементы некоторого множества N, называется индуктивной, если ее значение на последовательности $$x[1]\ldots x[n]$$ можно восстановить по ее значению на последовательности $$x[1]\ldots x[n-1]$$ и по x[n], то есть если существует функция $$F\colon N\times M \to N$$, для которой$$f(\langle x[1],\ldots,x[n]\rangle) = F(\, f(\langle x[1],\ldots,x[n-1]\rangle),x[n]).$$

Например, функция sum (сумма всех членов последовательности) индуктивна, поскольку очередной член последовательности прибавляется к ее сумме:$$sum(\langle x[1],\ldots,x[n]\rangle) = sum(\langle x[1],\ldots,x[n-1]\rangle)+x[n].$$ Другой пример индуктивной функции - длина последовательности. В этом случае $$F(n,m)=n+1$$.

Напротив, среднее арифметическое не является индуктивной функцией: если мы знаем среднее арифметическое некоторой последовательности, но не знаем ее длины, то не можем предсказать, каким станет среднее арифметическое после дописывания некоторого (известного нам) числа.

Схема алгоритма вычисления индуктивной функции:

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 (\langle x[1]\ldots x[n]\rangle) = t (g(\langle x[1]\ldots x[n]\rangle))$$ при всех $$\langle x[1] \ldots x[n]\rangle$$ ). Можно доказать, что среди всех индуктивных расширений существует минимальное расширение F (минимальность означает, что для любого индуктивного расширения g значения F определяются значениями g ).

1.3.1. Указать индуктивные расширения для следующих функций:

(а) среднее арифметическое последовательности вещественных чисел;

(б) число элементов последовательности целых чисел, равных ее максимальному элементу;

(в) второй по величине элемент последовательности целых чисел (тот, который будет вторым, если переставить члены в неубывающем порядке);

(г) максимальное число идущих подряд одинаковых элементов;

(д) максимальная длина монотонного (неубывающего или невозрастающего) участка из идущих подряд элементов в последовательности целых чисел;

(е) число групп из единиц, разделенных нулями (в последовательности нулей и единиц).

Решение.

(а) $$\langle$$ сумма всех членов последовательности; длина $$\rangle$$ ;

(б) $$\langle$$ число элементов, равных максимальному; значение максимального $$\rangle$$ ;

(в) $$\langle$$ наибольший элемент последовательности; второй по величине элемент $$\rangle$$ ;

(г) $$\langle$$ максимальное число идущих подряд одинаковых элементов; число идущих подряд одинаковых элементов в конце последовательности; последний элемент последовательности $$\rangle$$ ;

(д) $$\langle$$ максимальная длина монотонного участка; максимальная длина неубывающего участка в конце последовательности; максимальная длина невозрастающего участка в конце последовательности; последний член последовательности $$\rangle$$ ;

(е) $$\langle$$ число групп из единиц, последний член $$\rangle$$.

1.3.2. (Сообщил Д. В. Варсанофьев) Даны две последовательности целых чисел $$x[1]\ldots x[n]$$ и $$y[1]\ldots 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]\ldots y[k1]$$ - подпоследовательность $$x[1]\ldots x[n1]$$, то $$y[1]\ldots y[k1-1]$$ - подпоследовательность $$x[1]\ldots x[n1-1]$$.

Вариант 2. Функция $$\langle x[1]\ldots x[n1]\rangle$$ $$\mapsto$$ [максимальное k1, для которого $$y[1]\ldots y[k1]$$ есть подпоследовательность $$x[1]\ldots x[n1]$$ ] индуктивна.

1.3.3. Даны две последовательности $$x[1]\ldots x[n]$$ и $$y[1]\ldots y[k]$$ целых чисел. Найти максимальную длину последовательности, являющейся подпоследовательностью обеих последовательностей. Количество операций порядка $$n\cdot k$$.

Решение (сообщено М. Н. Вайнцвайгом, А. М. Диментманом). Обозначим через $$f(p,q)$$ максимальную длину общей подпоследовательности последовательностей $$x[1]\ldots x[p]$$ и $$y[1]\ldots y[q]$$. Тогда$$\begin{eqnarray*} x[p]\ne y[q] \! \Rightarrow\! f(p,q) = \max\,(f(p,q\!-\!1), f(p\!-\!1,q)); \\ x[p]=y[q] \! \Rightarrow\! f(p,q) = \max\,(f(p,q\!-\!1), f(p\!-\!1,q), f(p\!-\!1,q\!-\!1)\!+\!1); \end{eqnarray*}$$ (Поскольку $$f(p-1,q-1)+1 \ge f(p,q-1), f(p-1,q)$$, во втором случае максимум трех чисел можно заменить на третье из них.) Поэтому можно заполнять таблицу значений функции f, имеющую размер $$n\cdot k$$. Можно обойтись и памятью порядка k (или n ), если индуктивно (по p ) вычислять $$\langle f(p,0),\ldots,f(p,k)\rangle$$ (как функция от p этот набор индуктивен ).

1.3.4. (из книги Д. Гриса) Дана последовательность целых чисел $$x[1],\ldots,x[n]$$. Найти максимальную длину ее возрастающей подпоследовательности (число действий порядка $$n\,log n$$ ).

Решение. Искомая функция не индуктивна, но имеет следующее индуктивное расширение: в него входят помимо максимальной длины возрастающей подпоследовательности (обозначим ее k ) также и числа $$u[1],\ldots,u[k]$$, где $$u[i]$$ - минимальный из последних членов возрастающих подпоследовательностей длины i. Очевидно, $$u[1]\le\ldots\le 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]\le 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 x[n1] <= u[s] 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^2$$. Есть и другой изящный алгоритм с квадратичным временем работы (сообщил М. В. Вьюгин): найти максимальную общую подпоследовательность исходной последовательности и отсортированной последовательности с помощью предыдущей задачи.

1.3.5. Какие изменения нужно внести в решение предыдущей задачи, если надо искать максимальную неубывающую последовательность?