А. шень Издание шестое, дополненное Москва

• Название: А. шень Издание шестое, дополненное Москва
• Дата: 17.09.2022
• Размер: 1.62 Mb.
• Имя файла: shen-progbook.pdf
• Тип: Книга; #681926
• страница: 2 из 19

2id = ax + by для некоторых целых x, y и натурального i. Что делать, если i > 1?
Если x и y чётны, то на 2 можно сократить. Если это не так, положение можно исправить преобразованием x := x + b,
y := y − a
(оно не меняет ax + by). Убедимся в этом. Напомним, что мы считаем,
что одно из чисел a и b нечётно. Пусть это будет a. Если при этом

1.1. Задачи без массивов
15
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, печатать ничего не надо).

16 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. Задачи без массивов
17 1.1.24. Проверьте, является ли заданное натуральное число n > 1
простым.

1.1.25. (Для знакомых с основами алгебры) Дано целое гауссово число n + m𝑖 (принадлежащее Z[𝑖]).
(a) Проверьте, является ли оно простым (в Z[𝑖]).
(б) Напечатайте его разложение на простые (в Z[𝑖]) множители. 
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 в обратном порядке}

18 1. Переменные, выражения, присваивания 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<=ywhile 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. (В предыдущем решении, как можно подсчитать, порядка n опера- ций.)
Решение. Нас интересуют точки решётки (с целыми координата- ми) в первом квадранте, попадающие внутрь круга радиуса
√
n. Ин- тересующее нас множество (назовём его X) состоит из объединения

1.1. Задачи без массивов
19
вертикальных столбцов убывающей высоты.
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
∙
Идея решения состоит в том, чтобы «двигаться вдоль его границы»,
спускаясь по верхнему его краю, как по лестнице. Координаты движу- щейся точки обозначим . Введём ещё одну переменную s и будем поддерживать истинность такого условия:
находится сразу над k-м столбцом;
s | число точек в предыдущих столбцах.
Формально:
∙
l | минимальное среди тех l > 0, для которых не принад- лежит X;
∙
s | число пар натуральных x, y, для которых x < k и при- надлежит X.
Обозначим эти условия через (И).
k := 0; l := 0;
while <0,l> принадлежит X do begin l := l + 1;
end;
{k = 0, l - минимальное среди тех l >= 0,
для которых не принадлежит X}
s := 0;
{инвариант: И}
while not (l = 0) do begin s := s + l;
{s - число точек в столбцах до k-го включительно}
k := k + 1;
{точка лежит вне X, но, возможно, её надо сдвинуть вниз, чтобы восстановить И}
while (l <> 0) and ( не принадлежит X) do begin l := l - 1;
end;
end;
{И, l = 0, поэтому k-ый столбец и все следующие пусты, а s равно искомому числу}

20 1. Переменные, выражения, присваивания
Оценка числа действий очевидна: сначала мы движемся вверх не более чем на
√
n шагов, а затем вниз и вправо | в каждую сторону не более чем на
√
n шагов.

1.1.30. Даны натуральные числа n и k, n > 1. Напечатайте k деся- тичных знаков числа 1/n. (При наличии двух десятичных разложений выбирается то из них, которое не содержит девятки в периоде.) Про- грамма должна использовать только целые переменные.
Решение. Сдвинув в десятичной записи числа 1/n запятую на k мест вправо, получим число 10k/n. Нам надо напечатать его целую часть,
то есть разделить 10k на 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;

1.1. Задачи без массивов
21
{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 . . . N} →
→ {
1 . . . N}. Найдите период последовательности 1, f(1), f(f(1)), . . .
Количество действий должно быть пропорционально суммарной дли- не предпериода и периода (эта сумма может быть существенно мень- ше 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;

22 1. Переменные, выражения, присваивания
{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 > 2.
[Указание. Храните коэффициенты в выражении f(n) через три со- седних числа.]

1.1.35. Даны натуральные числа а и b, причём b > 0. Найдите част- ное и остаток при делении a на b, оперируя лишь с целыми числами и не используя операции div и mod, за исключением деления на 2 чёт- ных чисел; число шагов не должно превосходить 𝐶
1
log(a/b) + 𝐶
2
для некоторых констант 𝐶
1
, 𝐶
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. Массивы
23 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].

24 1. Переменные, выражения, присваивания
Решение.
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] 6 x[2] 6 . . . 6 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. Массивы
25 1.2.8. Та же задача, если известно, что все элементы массива |
числа от 1 до k и число действий должно быть порядка n + k.

1.2.9. (Сообщил А. Л. Брудно) Прямоугольное поле m × 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, то есть 2i < n + 1 ⇔ 2i 6 n ⇔
⇔
i 6 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]. Предположим, что длина левого участка (назовём его 𝐴) не больше длины правого (назовём

26 1. Переменные, выражения, присваивания его 𝐵). Выделим в 𝐵 начало той же длины, что и 𝐴, назовём его 𝐵
1
,
а остаток 𝐵
2
. (Так что 𝐵 = 𝐵
1
+ 𝐵
2
, если обозначать плюсом припи- сывание массивов друг к другу.) Нам надо из 𝐴 + 𝐵
1
+ 𝐵
2
получить
𝐵
1
+ 𝐵
2
+ 𝐴. Меняя местами участки 𝐴 и 𝐵
1
| они имеют одинаковую длину, и сделать это легко, | получаем 𝐵
1
+ 𝐴 + 𝐵
2
, и осталось поме- нять местами 𝐴 и 𝐵
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;
Оценка времени работы: на очередном шаге оставшийся для обработки участок становится короче на длину 𝐴; число действий при этом также пропорционально длине 𝐴.

1.2.12. Коэффициенты многочлена лежат в массиве a: array[0..n]
of integer (n | натуральное число, степень многочлена). Вычислите значение этого многочлена в точке x, то есть a[n] xn + . . . + 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. (Для знакомых с основами анализа; сообщил А. Г. Кушни- ренко) Дополните алгоритм вычисления значения многочлена в задан-

1.2. Массивы
27
ной точке по схеме Горнера вычислением значения его производной в той же точке.
Решение. Добавление нового коэффициента соответствует переходу от многочлена 𝑃 (𝑥) к многочлену 𝑥𝑃 (𝑥) + 𝑐. Его производная в точ- ке 𝑥 равна 𝑥𝑃
′
(𝑥) + 𝑃 (𝑥). (Это решение обладает забавным свойством:
не надо знать заранее степень многочлена. Если требовать выполнения этого условия, да ещё просить вычислять только значение производ- ной, не упоминая о самом многочлене, получается не такая уж простая задача.)

Общее утверждение о сложности вычисления производных таково:
1.2.14. (В. Баур, Ф. Штрассен) Дана программа вычисления значе- ния некоторого многочлена 𝑃 (𝑥
1
, . . . , 𝑥
𝑛
), содержащая только команды присваивания. Их правые части | выражения, содержащие сложение,
умножение, константы, переменные 𝑥
1
, . . . , 𝑥
𝑛
и ранее встречавшиеся
(в левой части) переменные. Докажите, что существует программа то- го же типа, вычисляющая все 𝑛 производных 𝜕𝑃/𝜕𝑥
1
, . . . , 𝜕𝑃/𝜕𝑥
𝑛
, при- чём общее число арифметических операций не более чем в 𝐶 раз пре- восходит число арифметических операций в исходной программе. Кон- станта 𝐶 не зависит от 𝑛.
[Указание. Можно считать, что каждая команда | сложение двух чисел, умножение двух чисел или умножение на константу. Используй- те индукцию по числу команд, применяя индуктивное предположение к программе, получающейся отбрасыванием первой команды.]

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;


28 1. Переменные, выражения, присваивания
1.2.16. Предложенный выше алгоритм перемножения многочленов требует порядка 𝑛
2
действий для перемножения двух многочленов сте- пени 𝑛. Придумайте более эффективный (для больших 𝑛) алгоритм,
которому достаточно порядка 𝑛
log 4/ log 3
действий.
[Указание. Представим себе, что надо перемножить два многочлена степени 2𝑘. Их можно представить в виде
𝐴(𝑥) 𝑥
𝑘
+ 𝐵(𝑥) и 𝐶(𝑥) 𝑥
𝑘
+ 𝐷(𝑥).
Произведение их равно
𝐴(𝑥)𝐶(𝑥) 𝑥
2𝑘
+ (𝐴(𝑥)𝐷(𝑥) + 𝐵(𝑥)𝐶(𝑥)) 𝑥
𝑘
+ 𝐵(𝑥)𝐷(𝑥).
Естественный способ вычисления 𝐴𝐶, 𝐴𝐷 + 𝐵𝐶, 𝐵𝐷 требует четы- рёх умножений многочленов степени 𝑘, однако их количество можно сократить до трёх с помощью такой хитрости: вычислить 𝐴𝐶, 𝐵𝐷
и (𝐴 + 𝐵)(𝐶 + 𝐷), а затем заметить, что 𝐴𝐷 + 𝐵𝐶 = (𝐴 + 𝐵)(𝐶 + 𝐷) −
−
𝐴𝐶 − 𝐵𝐷.]

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 равно искомому ответу}


1.2. Массивы
29
Замечание. В третьей альтернативе достаточно было бы увеличи- вать одну из переменных k1, l1; вторая добавлена для симметрии.
1.2.18. Решите предыдущую задачу, если про массивы известно лишь, что x[1] 6 . . . 6 x[k] и y[1] 6 . . . 6 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 (k1end;
while (l1end;
n := n + 1;
end;

Замечание. Эта программа имеет дефект: при проверке условия
(k1(или второго, аналогичного) при ложной первой скобке вторая окажет- ся бессмысленной (индекс выйдет за границы массива) и возникнет ошибка. Некоторые версии паскаля, вычисляя 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 = (k1while b do begin k1:=k1+1;
if k1 < k then b := (x[k1+1]=t) else b:=false;
end;

30 1. Переменные, выражения, присваивания
Можно также сделать иначе:
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], . . . , x[k], y[1], . . . , y[l]. (Число действий порядка k + l.)

1.2.20. Даны два массива x[1] 6 . . . 6 x[k] и y[1] 6 . . . 6 y[l]. «Со- едините» их в массив z[1] 6 . . . 6 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

1.2. Массивы
31
l1 := l1 + 1;
z[k1+l1] := y[l1];
end else begin
{ такого не бывает }
end;
end;
{k1 = k, l1 = l, массивы соединены}

Этот процесс можно пояснить так. Пусть у нас есть две стопки кар- точек, отсортированных по алфавиту. Мы соединяем их в одну стоп- ку, выбирая каждый раз ту из верхних карточек обеих стопок, которая идёт раньше в алфавитном порядке. Если в одной стопке карточки кон- чились, берём их из другой стопки.
1.2.21. Даны два массива x[1] 6 . . . 6 x[k] и y[1] 6 . . . 6 y[l]. Най- дите их «пересечение», то есть массив z[1] 6 . . . 6 z[m], содержащий их общие элементы, причём кратность каждого элемента в массиве z рав- няется минимуму из его кратностей в массивах x и y. Число действий порядка k + l.

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

1.2.23. (Из книги Д. Гриса) Некоторое число содержится в каж- дом из трёх целочисленных неубывающих массивов x[1] 6 . . . 6 x[p],
y[1] 6 . . . 6 y[q], z[1] 6 . . . 6 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]end else if y[q1]end else if z[r1]

32 1. Переменные, выражения, присваивания 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] целых чисел:
a: array [1..n] of array [1..m] of integer;
a[1][1] 6 . . . 6 a[1][m], . . . , a[n][1] 6 . . . 6 a[n][m].
Известно, что существует число, входящее во все массивы a[i] (су- ществует такое x, что для всякого 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;

1.2. Массивы
33
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]6. . .6x[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.

34 1. Переменные, выражения, присваивания
В этой задаче существенно, что массив упорядочен | поиск в неупо- рядоченном массиве требует времени, пропорционального длине масси- ва. (Чтобы убедиться, что какого-то числа нет в массиве, надо просмо- треть все его элементы.)
1.2.28. (Из книги Д. Гриса) Имеется массив x: array[1..n] of array[1..m] of integer, упорядоченный по строкам и по столбцам:
x[i][j] 6 x[i][j+1],
x[i][j] 6 x[i+1][j],
и число a. Требуется выяснить, встречается ли a среди x[i][j].
Решение. Представляя себе массив x как матрицу (прямоугольник,
заполненный числами), мы выберем прямоугольник, в котором только и может содержаться a, и будем его сужать. Прямоугольник этот будет содержать x[i][j] при 1 6 i 6 l и k 6 j 6 m n
l
1 1
k 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. Массивы
35 1.2.29. (Московская олимпиада по программированию) Дан неубы- вающий массив положительных целых чисел a[1] 6 a[2] 6 . . . 6 a[n].
Найдите наименьшее целое положительное число, не представимое в ви- де суммы нескольких элементов этого массива (каждый элемент мас- сива может быть использован не более одного раза). Число действий порядка n.
Решение. Пусть известно, что числа, представимые в виде суммы элементов a[1], . . . , a[k], заполняют отрезок от 1 до некоторого N. Ес- ли a[k+1] > N+1, то N+1 и будет минимальным числом, не представимым в виде суммы элементов массива a[1] . . . a[n]. Если же a[k+1] 6 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.30. (Для знакомых с основами алгебры) В целочисленном мас- сиве a[1] . . . a[n] хранится перестановка чисел 1 . . . n (каждое из чисел встречается по одному разу).
(а) Определите чётность перестановки. (И в (а), и в (б) количество действий порядка 𝑛.)
(б) Не используя других массивов, замените перестановку на обрат- ную (если до работы программы a[i] = j, то после должно быть a[j] =
= i).
[Указание. (а) Чётность перестановки определяется количеством ци- клов. Чтобы отличать уже пройденные циклы, у их элементов можно,
например, менять знак. (б) Обращение производим по циклам.]

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

36 1. Переменные, выражения, присваивания
Решение.
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]..поменять 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}
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]..обменять a[m+1] и a[l+1]
l:=l+1; m:=m+1;
end;
end;

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


1.2. Массивы
37 1.2.34. Дан массив a[1..n] и число m 6 n. Для каждого участка из m стоящих рядом членов (таких участков, очевидно, n − m + 1) вычи- слите его сумму. Общее число действий должно быть порядка n.
Решение. Переходя от участка к соседнему, мы добавляем один член, а другой вычитаем.

В этом решении ключевую роль играет возможность вычитания |
скажем, если бы надо было вычислять не сумму, а максимум, то так действовать было нельзя. Тем не менее это тоже возможно, как пока- зывает следующая задача (сообщил А. Г. Коган):
1.2.35. Дан массив a[1..n] и число m 6 n. Для каждого участка из m стоящих рядом членов (таких участков, очевидно, n − m + 1) вычисли- те максимум значений на этом участке. Общее число действий должно быть порядка n.
Решение. Разобьём массив на блоки по m элементов, и для каждого элемента вычислим максимум элементов, стоящих в том же блоке слева от него, а также максимум элементов, стоящих в том же блоке спра- ва от него (включая сам этот элемент). Это можно сделать, пройдя по каждому блоку слева направо, а также справа налево. Осталось заме- тить, что каждый участок длины 𝑚 либо совпадает с одним из блоков,
либо разбивается границей блока на две части, для каждой из которых максимум мы уже вычислили.

Такой способ годится для любой ассоциативной операции (а не то- лько для максимума).
1.2.36. Дана квадратная таблица a[1..n][1..n] и число m 6 n. Для каждого квадрата m × m в этой таблице вычислите сумму стоящих в нём чисел. Общее число действий порядка n
2
Решение. Сначала для каждого горизонтального прямоугольника размером m × 1 вычисляем сумму стоящих в нём чисел. (При сдвиге такого прямоугольника по горизонтали на 1 нужно добавить одно чи- сло и одно вычесть.) Затем, используя эти суммы, вычисляем суммы в квадратах. (При сдвиге квадрата по вертикали добавляется полоска,
а другая полоска убавляется.)