Массивы

В следующих задачах переменные ${\hbox{\tt x}},{\hbox{\tt y}},{\hbox{\tt z}}$ предполагаются описанными как array[1..n] of integer (где n -- некоторое натуральное число, большее 0), если иное не оговорено явно.

$\scriptstyle{\blacktriangleright}$ 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;`

$\scriptstyle{\blacktriangleright}$ 1.2.2. Подсчитать количество нулей в массиве x. (Составить фрагмент программы, не меняющий значения x, после исполнения которого значение некоторой целой переменной k равнялось бы числу нулей среди компонент массива x.)

Решение:

          ...
          {инвариант: k = число нулей среди x[1]...x[i] }
          ...  `

$\scriptstyle{\blacktriangleright}$ 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;`

$\scriptstyle{\blacktriangleright}$ 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;`

$\scriptstyle{\blacktriangleright}$ 1.2.5. Дан массив x: array[1..n] of integer, причем ${\hbox{\tt x[1]}}\leqslant{\hbox{\tt x[2]}}\leqslant\ldots\leqslant{\hbox{\tt 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;`

$\scriptstyle{\blacktriangleright}$ 1.2.6 (Сообщил А.Л. Брудно.) Прямоугольное поле ${\hbox{\tt m}}\times{\hbox{\tt n}}$ разбито на ${\hbox{\tt mn}}$ квадратных клеток. Некоторые клетки покрашены в черный цвет. Известно, что все черные клетки могут быть разбиты на несколько непересекающихся и не имеющих общих вершин черных прямоугольников. Считая, что цвета клеток даны в виде массива типа $\begin{displaymath} {\hbox{\tt array [1..m] of array [1..n] of boolean;}}\end{displaymath}$ подсчитать число черных прямоугольников, о которых шла речь. Число действий должно быть порядка ${\hbox{\tt mn}}$ .

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

$\scriptstyle{\blacktriangleright}$ 1.2.7. Дан массив x: array[1..n] of integer. Найти количество различных чисел среди элементов этого массива. (Число действий должно быть порядка ${\hbox{\tt n}}^2$ .) $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 1.2.8. Та же задача, если требуется, чтобы количество действий было порядка ${\hbox{\tt n}}\,\log{\hbox{\tt n}}$ .

[Указание. Смотри главу 4 (Сортировка)] $\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 1.2.9. Та же задача, если известно, что все элементы массива -- числа от 1 до k и число действий должно быть порядка ${\hbox{\tt n}}+{\hbox{\tt k}}$ . $\scriptstyle\blacktriangleleft$

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

Решение. Числа x[i] и x[n+1-i] нужно поменять местами для всех i, для которых ${\hbox{\tt i}}<{\hbox{\tt n}}+{\hbox{\tt 1}}-{\hbox{\tt i}}$ ,то есть ${\hbox{\tt 2}}{\hbox{\tt i}} < {\hbox{\tt n}} + {\hbox{\tt 1}}$ $\Leftrightarrow$ ${\hbox{\tt 2}}{\hbox{\tt i}}\leqslant{\hbox{\tt n}}$ $\Leftrightarrow$ ${\hbox{\tt i}} \leqslant{\hbox{\tt n div 2}}$ :

  for i := 1 to n div 2 do begin
  | ...обменять x [i] и x [n+1-i];
  end;`

$\scriptstyle{\blacktriangleright}$ 1.2.11 (из книги Д. Гриса). Дан массив целых чисел
x[1]..x[m+n], рассматриваемый как соединение двух его отрезков: начала x[1]..x[m] длины m и конца x[m+1]..x[m+n] длины n. Не используя дополнительных массивов, переставить начало и конец. (Число действий порядка ${\hbox{\tt m}}+{\hbox{\tt n}}$ .)

Решение:

Вариант 1. Перевернем (расположим в обратном порядке) отдельно начало и конец массива, а затем перевернем весь массив как единое целое.

Вариант 2, А.Г. Кушниренко. Рассматривая массив записанным по кругу, видим, что требуемое действие -- поворот круга. Как известно, поворот есть композиция двух осевых симметрий.

Вариант 3. Рассмотрим более общую задачу -- обмен двух участков массива x[p+1]..x[q] и x[q+1]..x[r]. Предположим, что длина левого участка (назовем его A ) не больше длины правого (назовем его B ). Выделим в B начало той же длины, что и A , назовем его B₁ , а остаток B₂ . (Так что B=B₁+B₂ , если обозначать плюсом приписывание массивов друг к другу.) Нам надо из A+B₁+B₂ получить B₁+B₂+A . Меняя местами участки A и B₁ -- они имеют одинаковую длину, и сделать это легко,-- получаем B₁ + A + B₂ , и осталось поменять местами A и B₂ . Тем самым мы свели дело к перестановке двух отрезков меньшей длины. Итак, получаем такую схему программы:

 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 . $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 1.2.12. Коэффициенты многочлена лежат в массиве $\begin{displaymath} {\hbox{\tt a:\ array[0..n]}}\ {\hbox{\tt of}}\ {\hbox{\tt integer}} \end{displaymath}$ (n -- натуральное число, степень многочлена). Вычислить значение этого многочлена в точке x, то есть ${\hbox{\tt a[n]}}\,{\hbox{\tt x}}^{\hbox{\tt n}}+\ldots+{\hbox{\tt a[1]}}\,{\hbox{\tt x}}+{\hbox{\tt 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;`

$\scriptstyle{\blacktriangleright}$ 1.2.13. (Для знакомых с основами анализа. Сообщил А.Г. Кушниренко) Дополнить алгоритм вычисления значения многочлена в заданной точке по схеме Горнера вычислением значения его производной в той же точке.

Решение. Добавление нового коэффициента соответствует переходу от многочлена P(x) к многочлену xP(x)+c . Его производная в точке x равна xP'(x) + P(x) . (Это решение обладает забавным свойством: не надо знать заранее степень многочлена. Если требовать выполнения этого условия, да еще просить вычислять только значение производной, не упоминая о самом многочлене, получается не такая уж простая задача.) $\scriptstyle\blacktriangleleft$

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

$\scriptstyle{\blacktriangleright}$ 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 . (В. Баур, Ф. Штрассен)

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

$\scriptstyle{\blacktriangleright}$ 1.2.15. В массивах $\begin{displaymath} {\hbox{\tt a:\ array[0..k]}}\ {\hbox{\tt of}}\ {\hbox{\tt in... ...x{\tt b:\ array[0..l]}}\ {\hbox{\tt of}}\ {\hbox{\tt integer}} \end{displaymath}$ хранятся коэффициенты двух многочленов степеней k и l. Поместить в массив c: array[0..m] of integer коэффициенты их произведения. (Числа ${\hbox{\tt k}},{\hbox{\tt l}},{\hbox{\tt m}}$ -- натуральные, ${\hbox{\tt m}}={\hbox{\tt k}}+{\hbox{\tt 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;`

$\scriptstyle{\blacktriangleright}$ 1.2.16. Предложенный выше алгоритм перемножения многочленов требует порядка n² действий для перемножения двух многочленов степени n . Придумать более эффективный (для больших n ) алгоритм, которому достаточно порядка $n^{\log 4/\log 3}$ действий.

[Указание. Представим себе, что надо перемножить два многочлена степени 2k . Их можно представить в виде $\begin{displaymath} A(x)\,x^k + B(x) \quad {\hbox{\tt и}} \quad C(x)\,x^k + D(x)\end{displaymath}$ Произведение их равно $\begin{displaymath} A(x)C(x)\,x^{2k} + (A(x)D(x)+B(x)C(x))\,x^k + B(x)D(x).\end{displaymath}$ Естественный способ вычисления AC , AD+BC , BD требует четырех умножений многочленов степени k , однако их количество можно сократить до трех с помощью такой хитрости: вычислить AC , BD и (A+B)(C+D) , а затем заметить, что AD+BC=(A+B)(C+D)-AC-BD .] $\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 1.2.17. Даны два возрастающих массива x: array[1..k] of integer и y: array[1..l] of integer. Найти количество общих элементов в этих массивах, то есть количество тех целых t, для которых ${\hbox{\tt t}} = {\hbox{\tt x[i]}} = {\hbox{\tt y[j]}}$ для некоторых i и j. (Число действий порядка ${\hbox{\tt k}}+{\hbox{\tt 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; вторая добавлена для симметрии.

$\scriptstyle{\blacktriangleright}$ 1.2.18. Решить предыдущую задачу, если известно лишь, что ${\hbox{\tt x[1]}}\leqslant\ldots\leqslant{\hbox{\tt x[k]}}$ и ${\hbox{\tt y[1]}}\leqslant\ldots\leqslant{\hbox{\tt y[l]}}$ (возрастание заменено неубыванием).

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

Замечание. Эта программа имеет дефект: при проверке условия $\begin{displaymath} {\hbox{\tt (l1<l) and (x[l1+1]=t)}}\end{displaymath}$ (или второго, аналогичного) при ложной первой скобке вторая окажется бессмысленной (индекс выйдет за границы массива) и возникнет ошибка. Некоторые версии паскаля, вычисляя 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;

Так будет короче, хотя менее симметрично.

Наконец, можно увеличить размер массива в его описании, включив в него фиктивные элементы.

$\scriptstyle{\blacktriangleright}$ 1.2.19. Даны два неубывающих массива x: array[1..k] of integer и y: array[1..l] of integer. Найти число различных элементов среди ${\hbox{\tt x[1]}},\ldots,{\hbox{\tt x[k]}},{\hbox{\tt y[1]}},\ldots,{\hbox{\tt y[l]}}$ . (Число действий порядка ${\hbox{\tt k}}+{\hbox{\tt l}}$ .) $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 1.2.20. Даны два массива ${\hbox{\tt x[1]}}\leqslant\ldots\leqslant{\hbox{\tt x[k]}}$ и ${\hbox{\tt y[1]}}\leqslant\ldots\leqslant{\hbox{\tt y[l]}}$ . << Соединить>> их в массив ${\hbox{\tt z[1]}}\leqslant\ldots\leqslant{\hbox{\tt z[m]}}$ ( ${\hbox{\tt m}}={\hbox{\tt k}}+{\hbox{\tt 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]