1.2. Массивы

  •  
    •  
      •  
        • (а) Определить четность перестановки. (И в (а), и в (б) количество действий порядка n.)
        • (б) Не используя других массивов, заменить перестановку на обратную (если до работы программы a[i]=j, то после должно быть a[j]=i).
    • В следующих задачах переменные x, y, z предполагаются описанными как array [1..n] of integer (n - некоторое натуральное число, большее 0), если иное не оговорено явно.

      1.2.1. Заполнить массив x нулями. (Это означает, что нужно составить фрагмент программы, после выполнения которого все значения x[1]..x[n] равнялись бы нулю, независимо от начального значения переменной x.)

      Решение.
      i := 0;
      {инвариант: первые i значений x[1]..x[i] равны 0}
      while i <> n do begin
      | i := i + 1;
      | {x[1]..x[i-1] = 0}
      | x[i] := 0;
      end;

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

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

      1.2.3. Не используя оператора присваивания для массивов, составить фрагмент программы, эквивалентный оператору x:=y.

      Решение.
      i := 0;
      {инвариант: значение y не изменилось, x[l] = y[l] при l <= i}
      while i <> n do begin
      | i := i + 1;
      | x[i] := y[i];
      end;

      1.2.4. Найти максимум из x[1]..x[n].

      Решение.
      i := 1; max := x[1];
      {инвариант: max = максимум из x[1]..x[i]}
      while i <> n do begin
      | i := i + 1;
      | {max = максимум из x[1]..x[i-1]}
      | if x[i] > max then begin
      | | max := x[i];
      | end;
      end;

      1.2.5. Дан массив x: array [1..n] of integer, причём x[1] <= x[2] <= ... <= x[n]. Найти количество различных чисел среди элементов этого массива.

      Решение (вариант 1).
      i := 1; k := 1;
      {инвариант: k - количество различных чисел среди x[1]..x[i]}
      while i <> n do begin
      | i := i + 1;
      | if x[i] <> x[i-1] then begin
      | | k := k + 1;
      | end;
      end;

      (вариант 2) Искомое число на 1 больше количества тех чисел i из 1..n-1, для которых x[i] <> x[i+1].
      k := 1;
      for i := 1 to n-1 do begin
      | if x[i]<> x[i+1] then begin
      | | k := k + 1;
      | end;
      end;

      1.2.6. (Сообщил А.Л.Брудно.) Прямоугольное поле m на n разбито на mn квадратных клеток. Некоторые клетки покрашены в черный цвет. Известно, что все черные клетки могут быть разбиты на несколько непересекающихся и не имеющих общих вершин черных прямоугольников. Считая, что цвета клеток даны в виде массива типа
      array [1..m] of array [1..n] of boolean;

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

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

      1.2.7. Дан массив x: array [1..n] of integer. Найти количество различных чисел среди элементов этого массива. (Число действий должно быть порядка n*n.)

      1.2.8. Та же задача, если требуется, чтобы количество действий было порядка n* log n. (Указание. Смотри главу о сортировке.)

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

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

      Решение. Числа x [i] и x [n+1-i] нужно поменять местами для всех i, для которых i < n + 1 - i, т.е. 2*i < n + 1 <=> 2*i <= n <=> i <= n div 2:
      for i := 1 to n div 2 do begin
      | ...обменять x [i] и x [n+1-i];
      end;

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

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

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

      (вариант 3) Рассмотрим более общую задачу - обмен двух участков массива x[p+1]..x[q] и x[q+1]..x[r]. Предположим, что длина левого участка (назовем его 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[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)+...+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. Дана программа вычисления значения некоторого многочлена P(x[1],...,x[n]), содержащая только команды присваивания. Их правые части - выражения, содержащие сложение, умножение, константы, переменные x[1]...x[n] и ранее встречавшиеся (в левой части) переменные. Доказать, что существует программа того же типа, вычисляющая все n производных многочлена P по переменным x[1]...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 содержит коэффициент при 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.16. Предложенный выше алгоритм перемножения многочленов требует порядка 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.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] <= ... <= x[k] и y[1] <= ... <<k) and (x[k1+1]=t) do begin
      | | k1 := k1 + 1;
      | end;
      | while (l1><k) and (x[k1+1]=t)

      (или второго, аналогичного) при ложной первой скобке вторая окажется бессмысленной (индекс выйдет за границы массива) и возникнет ошибка. Некоторые версии паскаля, вычисляя (A and B), сначала вычисляют A и при ложном A не вычисляют B. (Так ведет себя, например, система Turbo Pascal, 5.0 - но не 3.0.) Тогда описанная ошибка не возникнет.

      Но если мы не хотим полагаться на такое свойство используемой нами реализации паскаля (не предусмотренное его автором Н.Виртом), то можно поступить так. Введем дополнительную переменную b: boolean и напишем:
      if k1 ><k) and (x[k1+1] = t)}
      while b do begin
      | k1:=k1+1;
      | if k1 >= 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 (k1l) and (x[l1+1]=t) do begin
      | | l1 := l1 + 1;
      | end;
      | n := n + 1;
      end;

      Замечание. Эта программа имеет дефект: при проверке условия
      (k1 k then b := (x[k1+1]=t) else b:=false;
      {b = (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],...,x[k], y[1],...,y[l]. (Число действий порядка k+l.)

      1.2.20. Даны два массива x[1] <= ... <= x[k] и y[1] <= ... <= y[l]. "Соединить" их в массив z[1] <= ... <= z[m] (m = k+l; каждый элемент должен входить в массив z столько раз, сколько раз он входит в общей сложности в массивы x и y). Число действий порядка m.

      Решение.
      k1 := 0; l1 := 0;
      {инвариант: ответ получится, если к z[1]..z[k1+l1] приписать
      справа соединение массивов x[k1+1]..x[k] и y[l1+1]..y[l]}
      while (k1 <> k) or (l1 <> l) do begin
      | if k1 = k then begin
      | | {l1 < l}
      | | l1 := l1 + 1;
      | | z[k1+l1] := y[l1];
      | end else if l1 = l then begin
      | | {k1 < k}
      | | k1 := k1 + 1;
      | | z[k1+l1] := x[k1];
      | end else if x[k1+1] <= y[l1+1] then begin
      | | k1 := k1 + 1;
      | | z[k1+l1] := x[k1];
      | end else if x[k1+1] >= y[l1+1] then begin
      | | l1 := l1 + 1;
      | | z[k1+l1] := y[l1];
      | end else begin
      | | { такого не бывает }
      | end;
      end;
      {k1 = k, l1 = l, массивы соединены}

      Этот процесс можно пояснить так. Пусть у нас есть две стопки карточек, отсортированных по алфавиту. Мы соединяем их в одну стопку, выбирая каждый раз ту из верхних карточек обеих стопок, которая идет раньше в алфавитном порядке. Если в одной стопке карточки кончились, берём их из другой стопки.

      1.2.21. Даны два массива x[1] <= ... <= x[k] и y[1] <= ... <= y[l]. Найти их "пересечение", т.е. массив z[1] <= ... <= z[m], содержащий их общие элементы, причем кратность каждого элемента в массиве z равняется минимуму из его кратностей в массивах x и y. Число действий порядка k+l.

      1.2.22. Даны два массива 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.23. (из книги Д.Гриса) Некоторое число содержится в каждом из трех целочисленных неубывающих массивов
      x[1] <= ... <=
      x[p], y[1] <= ... <= y[q], z[1] <= ... <<y[q1] then begin
      | | p1:=p1+1;
      | end else if y[q1]><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] целых чисел (a: array [1..n] of array [1..m] of integer; a[1][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]z[r1] then begin
      | | q1:=q1+1;
      | end else if z[r1]= ... <= a[1][m], ..., a[n][1] <= ... <=
      a[n][m]). Известно, что существует число, входящее во все массивы
      a[i] (существует такое х, что для всякого i из [1..n]
      найдётся j из [1..m], для которого a[i][j]=x). Найти одно из таких
      чисел х.

      Решение. Введем массив b[1]..b[n], отмечающий начало "остающейся части" массивов a[1],...,a[n].
      for k:=1 to n do begin
      | b[k]:=1;
      end;
      eq := true;
      for k := 2 to n do begin
      | eq := eq and (a[1][b[1]] = a[k][b[k]]);
      end;
      {инвариант: оставшиеся части пересекаются, т.е. существует
      такое х, что для всякого i из [1..n] найдётся j из [1..m],
      не меньшее b[i], для которого a[i][j] = х; eq <=> первые
      элементы оставшихся частей равны}
      while not eq do begin
      | s := 1; k := 1;
      | {a[s][b[s]] - минимальное среди a[1][b[1]]..a[k][b[k]]}
      | while k <> n do begin
      | | k := k + 1;
      | | if a[k][b[k]] < a[s][b[s]] then begin
      | | | s := k;
      | | end;
      | end;
      | {a[s][b[s]] - минимальное среди a[1][b[1]]..a[n][b[n]]}
      | b [s] := b [s] + 1;
      | for k := 2 to n do begin
      | | eq := eq and (a[1][b[1]] = a[k][b[k]]);
      | end;
      end;
      writeln (a[1][b[1]]);

      1.2.26. Приведенное решение предыдущей задачи требует порядка m*n*n действий. Придумать способ с числом действий порядка m*n.

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

      1.2.27. (Двоичный поиск) Дана последовательность x[1] <= ... <= 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] <= x[i][j+1]
      x[i][j] <= x[i+1][j],

      и число a. Требуется выяснить, встречается ли a среди x[i][j].

      Решение. Представляя себе массив a как матрицу (прямоугольник, заполненный числами), мы выберем прямоугольник, в котором только и может содержаться a, и будем его сужать. Прямоугольник этот будет содержать x[i][j] при 1<=i<=l и k<=j<=m.
      1 k m
      -----------------------------------
      1| |***********|
      | |***********|
      | |***********|
      l| |***********|
      |---------------------------------|
      | |
      n| |
      -----------------------------------

      (допускаются пустые прямоугольники при l = 0 и k = m+1).
      l:=n; k:=1;
      {l>=0, k<=m+1, если a есть, то в описанном прямоугольнике}
      while (l > 0) and (k < m+1) and (x[l][k] <> a) do begin
      | if x[l][k] < a then begin
      | | k := k + 1; {левый столбец не содержит a, удаляем его}
      | end else begin {x[l][k] > a}
      | | l := l - 1; {нижняя строка не содержит a, удаляем ее}
      | end;
      end;
      {x[l][k] = a или прямоугольник пуст }
      answer:= (l > 0) and (k < m+1) ;

      Замечание. Здесь та же ошибка: x[l][k] может оказаться неопредёленным. (Её исправление предоставляется читателю.)

      1.2.29. (Московская олимпиада по программированию) Дан неубывающий массив положительных целых чисел a[1] <= a[2] <=...<= a[n]. Найти наименьшее целое положительное число, не представимое в виде суммы нескольких элементов этого массива (каждый элемент массива может быть использован не более одного раза). Число действий порядка n.

      Решение. Пусть известно, что числа, представимые в виде суммы элементов a[1],...,a[k], заполняют отрезок от 1 до некоторого N. Если a[k+1] > N+1, то N+1 и будет минимальным числом, не представимым в виде суммы элементов массива a[1]..a[n]. Если же a[k+1] <= N+1, то числа, представимые в виде суммы элементов a[1]..a[k+1], заполняют отрезок от 1 до N+a[k+1].
      k := 0; N := 0;
      {инвариант: числа, представимые в виде суммы элементов массива
      a[1]..a[k], заполняют отрезок 1..N}
      while (k <> n) and (a[k+1] <= N+1) do begin
      | N := N + a[k+1];
      | k := k + 1;
      end;
      {(k = n) или (a[k+1] > N+1); в обоих случаях ответ N+1}
      writeln (N+1);

      (Снова тот же дефект: в условии цикла при ложном первом условии второе не определено.)

      1.2.30. (Для знакомых с основами алгебры) В целочисленном массиве a[1]..a[n] хранится перестановка чисел 1..n (каждое из чисел встречается по одному разу).

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

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

      Решение.
      l:=0; r:=n;
      {инвариант: a[1]..a[l]<=b; a[r+1]..a[n]>=b}
      while l <> r do begin
      | if a[l+1] <= b then begin
      | | l:=l+1;
      | end else if a[r] >=b then begin
      | | r:=r-1;
      | end else begin {a[l+1]><b}
      | | ..поменять a[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[r]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}
      | | ..обменять a[m+1] и a[l+1]
      | | l:=l+1; m:=m+1;
      end;

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

      1.2.34. Дан массив a[1]..a[n] и число
      m>b then begin
      | | ..обменять a[m+1] и a[r]
      | | r:=r-1;
      | end else begin {a[m+1]=n.

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

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

      1.2.35. Дана квадратная таблица a[1..n][1..n] и число m<<n,m><x[1],...,x[n]><x[1],...,x[n-1]><x[1],...,x[k]>=n. Для каждого квадрата размера m на m в этой таблице вычислить сумму стоящих в нем чисел. Общее число действий должно быть порядка n*n.

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

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

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

Другие записи

10.06.2016. 1.3. Индуктивные функции (по А.Г.Кушниренко)
      (а) среднее арифметическое последовательности вещественных чисел; (б) число элементов последовательности целых чисел, равных ее максимальному элементу; (в) второй по величине элемент последовательности…