(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) 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] первые
элементы оставшихся частей равны}
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, для ко-
