Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11642
Последний выпуск: 19.06.2015

Глава 1. Переменные, выражения, присваивания.

     Глава 1. Переменные, выражения, присваивания.

     1.1. Задачи без массивов

     1.1.1. Даны две целые переменные a, b.  Составить  фрагмент
программы, после исполнения которого значения переменных поменя-
лись бы местами (новое значение a равно старому значению b и на-
оборот).

     Решение. Введем дополнительную целую переменную t.
        t := a;
        a := b;
        b := t;
Попытка обойтись без дополнительной переменной, написав
        a := b;
        b := a;
не приводит к цели (безвозвратно утрачивается начальное значение
переменной a).

     1.1.2.  Решить  предыдущую  задачу,  не  используя дополни-
тельных переменных (и предполагая, что значениями целых перемен-
ных могут быть произвольные целые числа).

     Решение. (Начальные значения a и b обозначим a0, b0.)
        a := a + b; {a = a0 + b0, b = b0}
        b := a - b; {a = a0 + b0, b = a0}
        a := a - b; {a = b0, b = a0}

     1.1.3.  Дано  целое  число а и натуральное (целое неотрица-
тельное) число n. Вычислить а в степени n. Другими словами,  не-
обходимо  составить  программу,  при исполнении которой значения
переменных а и n не меняются, а значение некоторой другой  пере-
менной  (например, b) становится равным а в степени n. (При этом
разрешается использовать и другие переменные.)

     Решение. Введем целую переменную k, которая меняется от  0
до  n,  причем  поддерживается такое свойство: b = (a в степени
k).

        k := 0; b := 1;
        {b = a в степени k}
        while k <> n do begin
        | k := k + 1;
        | b := b * a;
        end;

Другое решение той же задачи:

        k := n; b := 1;
        {a в степени n = b * (a в степени k)}
        while k <> 0 do begin
        | k := k - 1;
        | b := b * a;
        end;

     1.1.4. Решить предыдущую задачу, если требуется, чтобы чис-
ло действий (выполняемых операторов присваивания)  было  порядка
log n (то есть не превосходило бы C*log n для некоторой констан-
ты C; log n - это степень, в которую нужно возвести 2, чтобы по-
лучить n).

     Решение. Внесем некоторые изменения во второе из предложен-
ных решений предыдущей задачи:

        k := n; b := 1; c:=a;
        {a в степени n = b * (c в степени k)}
        while k <> 0 do begin
        | if k mod 2 = 0 then begin
        | | k:= k div 2;
        | | c:= c*c;
        | end else begin
        | | k := k - 1;
        | | b := b * c;
        | end;
        end;

Каждый второй раз (не реже)  будет  выполняться  первый  вариант
оператора  выбора  (если  k  нечетно, то после вычитания единицы
становится четным), так что за два цикла величина k  уменьшается
по крайней мере вдвое.

     1.1.5.  Даны натуральные числа а, b. Вычислить произведение
а*b, используя в программе лишь операции +, -, =, <>.

     Решение.
        var a, b, c, k : integer;
        k := 0; c := 0;
        {инвариант: c = a * k}
        while k <> b do begin
        | k := k + 1;
        | c := c + a;
        end;
        {c = a * k и k = b, следовательно, c = a * b}

     1.1.6.  Даны  натуральные  числа  а и b. Вычислить их сумму
а+b. Использовать операторы присваивания лишь вида

        <переменная1> := <переменная2>,
        <переменная> := <число>,
        <переменная1> := <переменная2> + 1.

     Решение.
          ...
         {инвариант: c = a + k}
          ...

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

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

     1.1.9.   Последовательность  Фибоначчи  определяется  так:
a(0)= 1, a(1) = 1, a(k) = a(k-1) + a(k-2) при k >= 2.  Дано  n,
вычислить a(n).

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

     Указание.  Пара соседних чисел Фибоначчи получается из пре-
дыдущей умножением на матрицу
            |1 1|
            |1 0|
так что задача сводится к возведению матрицы в  степень  n.  Это
можно сделать за C*log n действий тем же способом, что и для чи-
сел.

     1.1.11. Дано натуральное n, вычислить 1/0!+1/1!+...+1/n!.

     1.1.12.  То  же, если требуется, чтобы количество операций
(выполненных команд присваивания) было бы не более C*n для  не-
которой константы С.
     Решение.  Инвариант:  sum  =  1/1! +...+ 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>=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;
        if m = 0 then begin
        | k := n;
        end else begin
        | k := m;
        end;

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

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

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

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

        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;

     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 (принадлежащее Z[i]). (a) Проверить, явля-
ется ли оно простым (в Z[i]); (б) напечатать его разложение  на
простые (в Z[i]) множители.

     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 в обратном порядке}
        while k <> 0 do begin
        | write (k mod 10);
        | k:= k div 10;
        end;

     1.1.28. Дано натуральное n. Подсчитать  количество  решений
неравенства  x*x + y*y < 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
        |  (при данном k) }
        | k := k + 1;
        | s := s + t;
        end;
        {k*k >= n, поэтому s = количество всех решений
          неравенства}

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

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

     Решение. Нас интересуют точки решетки (с целыми координата-
  *              ми) в первом квадранте, попадающие внутрь круга
  * * *          радиуса  (n  в  степени  1/2). Интересующее нас
  * * * *        множество (назовем его X) состоит из  объедине-
  * * * *        ния  вертикальных  столбцов  убывающей  высоты.
  * * * * *      Идея решения состоит в  том,  чтобы  "двигаться
вдоль  его  границы",  спускаясь  по  верхнему  его краю, как по
лестнице. Координаты движущейся точки  обозначим  <k,l>.  Введем
еще одну переменную s и будем поддерживать истинность такого ус-
ловия:
     <k,l> находится сразу над k-ым столбцом;
     s - число точек в предыдущих столбцах.

     Формально:
l  - минимальное среди тех l >= 0, для которых <k,l> не принад-
    лежит X;
s - число пар натуральных x, y, для которых x < k и <x,y>  при-
    надлежит X.
Обозначим эти условия через (И).

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

Оценка числа действий очевидна: сначала мы движемся вверх не бо-
лее  чем  на  (n в степени 1/2) шагов, а затем вниз и вправо - в
каждую сторону не более чем на (n в степени 1/2) шагов.

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

     1.1.32 (Э. Дейкстра). Функция 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.33.  То  же,  если  f(0) = 13, f(1) = 17, а f(2n) =
43 f(n) + 57 f(n+1), f(2n+1) = 91 f(n) + 179 f(n+1) при n>=1.
     Указание.  Хранить  коэффициенты в выражении f(n) через три
соседних числа.

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

     Решение.

  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]
<= 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[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) 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;

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

     1.2.19.  Даны два массива 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.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]<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.23. Та же задача, только заранее не известно, существу-
ет  ли общий элемент в трех неубывающих массивах и требуется это
выяснить (и найти один из общих элементов, если они есть).

     1.2.24. Элементами  массива  a[1..n]  являются  неубывающие
массивы  [1..m]  целых чисел (a: array [1..n] of array [1..m] of
integer; a[1][1] <= ... <=  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.25.  Приведенное  решение предыдущей задачи требует по-
рядка m*n*n действий. Придумать способ с числом действий порядка
m*n.
     Указание.  Придется  пожертвовать симметрией и выбрать одну
из строк за основную. Двигаясь по основной строке,  поддерживаем
такое  соотношение:  во  всех  остальных  строках отмечен макси-
мальный элемент, не  превосходящий  текущего  элемента  основной
строки.

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

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

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

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

     1.2.30. Дан массив 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[r]<b}
        | | поменять a[l+1] и  a[r]
        | | l:=l+1; r:+r-1;
        | end;
        end;

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

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

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

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

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

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

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

     Пусть M - некоторое множество. Функция f, аргументами кото-
рой являются последовательности элементов множества M, а  значе-
ниями - элементы некоторого множества N, называется индуктивной,
если  ее значение на последовательности x[1]..x[n] можно восста-
новить по ее значению на последовательности  x[1]..x[n-1]  и  по
x[n],  т.  е.  если  существует  функция F из N*M (множество пар
<n,m>, где n - элемент множества N, а m - элемент множества M) в
N, для которой

      f(<x[1],...,x[n]>) = F (f (<x[1],...,x[n-1]>), x[n]).

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

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

     1.3.1.  Указать  индуктивные  расширения   для   следующих
функций:
   а)  среднее  арифметическое  последовательности вещественных
чисел;
   б) число элементов последовательности целых чисел, равных ее
максимальному элементу;
   в)  второй по величине элемент последовательности целых чисел
(тот, который будет вторым, если переставить члены в неубывающем
порядке);
   г) максимальное число идущих подряд одинаковых элементов;
   д) максимальная длина монотонного (неубывающего  или  невоз-
растающего)  участка  из  идущих  подряд элементов в последова-
тельности целых чисел;
   е) число групп из единиц, разделенных нулями  (в  последова-
тельности нулей и единиц).

     Решение.

а) <сумма всех членов последовательности; длина>;

б)  <число  элементов,  равных  максимальному;  значение макси-
     мального>;

в) <наибольший элемент последовательности; второй  по  величине
     элемент>;

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

д) <максимальная длина монотонного участка; максимальная  длина
      неубывающего  участка  в конце последовательности; макси-
      мальная длина невозрастающего участка в конце  последова-
      тельности; последний член последовательности>;

е) <число групп из единиц, последний член>.

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

     (2  вариант)  Функция x[1]..x[n1] |-> (максимальное k1, для
которого y[1]..y[k1] есть подпоследовательность x[1]..x[n1]) ин-
дуктивна.

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

     Решение  (сообщено М.Н.Вайнцвайгом, А.М.Диментманом). Обоз-
начим через  f(n1,k1)  максимальную  длину  общей  подпоследова-
тельности последовательностей x[1]..x[n1] и y[1]..y[k1]. Тогда

   x[n1] <> y[k1] => f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1));
   x[n1] = y[k1]  => f(n1,k1) = max (f(n1,k1-1), f(n1-1,k1),
                              f(n1-1,k1-1)+1 );

(Поскольку  f(n1-1,k1-1)+1  >= f(n1,k1-1), f(n1-1,k1), во втором
случае максимум трех чисел можно заменить на третье из них.)
     Поэтому можно заполнять таблицу значений функции f, имеющую
размер n*k. Можно обойтись и памятью порядка k (или n), если ин-
дуктивно  (по  n1) выписать <f(n1,0), ..., f(n1,k)> (как функция
от n1 этот набор индуктивен).

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

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

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

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог