                    РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ И
                  ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.

                            Задача 1.
     Можно, конечно,  каждый  раз  вычислять  очередное p!,  затем
1/p!, и полученное слагаемое добавлять к сумме.  Но обратим внима-
ние на следующее очевидное равенство:
                     1/(p+1)! = (1/p!)/(p+1),
и программа вычисления запишется следующим образом
     S:=1; p:=1;       { S = p = 1/1! }
     for i:=2 to k do
       begin
         p:=p/i;
         S:=S+p;
       end;

                            Задача 2.
     Метод 1.  Самое простое - это перебрать все возможные комбина-
ции шести цифр и подсчитать число "счастливых" билетов.
     Count:=0;             { количество "счастливых" билетов }
     for a1:=0 to 9 do
       for a2:=0 to 9 do
         for a3:=0 to 9 do
           for a4:=0 to 9 do
             for a5:=0 to 9 do
               for a6:=0 to 9 do
                 if a1+a2+a3=a4+a5+a6  { "счастливый"? }
                 then Count:=Count+1;
     Под сложностью алгоритма будем понимать количество  выполнений
тела  наиболее  глубоко  вложенного цикла.  Условие if во вложенных
циклах будет проверяться 10^6  раз,  поэтому  будем  говорить,  что
сложность этого алгоритма 10^6.
     Метод 2.  Обратим внимание на то,  что в  "счастливом"  билете
последняя цифра a6 однозначно определяется первыми пятью:
     a6=(a1+a2+a3)-(a4+a5).
     Если 0<=a6<=9,  то билет "счастливый", иначе - нет. Таким об-
разом, мы можем убрать шестой вложенный цикл:
     Count:=0;
     for a1:=0 to 9 do
       for a2:=0 to 9 do
         for a3:=0 to 9 do
           for a4:=0 to 9 do
             for a5:=0 to 9 do
             begin
               a6:=(a1+a2+a3)-(a4+a5);
               if (a6>=0) and (a6<=9)
               then Count:=Count+1;
             end;
     Сложность алгоритма 10^5.  Используя элементарное соображение,
мы уменьшили сложность алгоритма и, вообще говоря, время выполнения
программы в 10 раз!
     Метод 3.  Если  комбинаций  a1 a2 a3 первых трех цифр с суммой
T=a1+a2+a3 насчитывается C[T], то всего "счастливых" билетов с сум-
мой половины T=a1+a2+a3=a4+a5+a6 будет C[T]^2.  Действительно, каж-
дое "счастливое" шестиразрядное число может быть получено  склейкой
двух произвольных  трехразрядных  чисел  с  одинаковой суммой цифр.
Всего существует 28 всевозможных значений сумм T -  от  0=0+0+0  до
27=9+9+9.  Подсчитаем C[i], i=0, ..., 28, затем найдем интересующее
нас количество "счастливых" билетов C[0]^2 + C[1]^2 + ... + C[27]^2.
     Заметим, что  "счастливых"  билетов  с  суммой  T столько же,
сколько и с суммой 27-T.  Действительно, если билет a1 a2 a3 a4 a5
a6  с  суммой  T  -  "счастливый",  то таковым же является и билет
(999999 -  a1 a2 a3 a4 a5 a6) с суммой 27-T.  Поэтому число билетов
можно вычислять и по формуле 2(C[0]^2+ ... +C[13]^2), т.е. рассмат-
ривать только суммы T от 0 до 13.
     var C:array[0..13] of longint;  { массив С из 14 элементов -
       . . .                           по числу возможных сумм  }
     Count:=0;
     for T:=0 to 13 do C[T]:=0;
     for a1:=0 to 9 do    { перебираем все }
       for a2:=0 to 9 do  { возможные a1 a2 a3 }
         for a3:=0 to 9 do
         begin
           T:=a1+a2+a3;
           C[T]:=C[T]+1   { нашли еще один билет }
         end;             { с суммой T }
     for T:=0 to 13 do    { считаем число билетов }
       Count:=Count+C[T]*C[T];
     Count:=Count*2;      { удваиваем сумму }
     Сложность этого алгоритма 10^3.
     Метод 4. В методе 3 мы перебирали комбинации цифр и искали ко-
личество комбинаций с суммами C[T].  Сейчас мы пойдем от суммы T, и
по ней будем определять,  какое количество комбинаций a1 a2  a3  ее
имеет. Итак T=a1+a2+a3.
     Минимальное значение,  которое  может  принимать  a1,  -  это
max{0,T-18}.  Член T-18 появляется из следующих соображений: пусть
a2=a3=9, тогда a1=T-18, но a1 не может быть меньше 0. Максимальное
значение a1=min{9,T} (так как a2 и a3 неотрицательны,  то a1<=T  и
одновременно a1<=9).
     Для цифры a2 аналогично получаем, что она лежит в пределах от
                  max{0,T-a1-9} до min{9,T-a1}.
     Цифра a3 по T, a1 и a2 определяется однозначно.
     Получаем, что  комбинаций a1 a2 a3 с суммой T и с первой циф-
рой  a1  столько  же,  сколько  возможных  цифр   a2,   а   именно
                   min{9,T-a1}-max{0,T-a1-9}+1.
Как и в методе 3 мы можем рассматривать диапазон сумм T от 0 до 13.
     Count:=0;
     for T:=0 to 13 do
     begin
       CT:=0;
       for a1:=max(0,T-18) to min(9,T) do
         CT:=CT+min(9,T-a1)-max(0,T-a1-9)+1;
       Count:=Count+CT*CT
     end;
     Count:=Count*2;
     Сложность этого  алгоритма  (т.е.  количество  выполнений
операций присваивания внутри двух вложенных циклов) есть 95.

                            Задача 3.
     Задача опять же имеет очевидное решение, которое состоит в ге-
нерации  всех  2N-разрядных  чисел  и  проверке  их  на   требуемое
свойство.  Однако общее количество таких чисел равно 10^(2N) и поэ-
тому при N>3 практически очень трудно получить  результат  на  ЭВМ.
Следовательно необходимо разработать алгоритм, не требующий генера-
ции чисел.
     Определим через S(k,i) количество  k-разрядных  чисел,  сумма
цифр  которых равна i.  Например,  S(2,3)=4,  так как существует 4
двуразрядных числа (03,12,21,30), сумма цифр которых равна 3. Лег-
ко заметить, что S(1,i)=1 при i<10 и S(1,i)=0 при i>9. Предположим
теперь, что мы сумели вычислить значения величин S(N,i) для всех i
от 0 до 9N,  т.е.  мы знаем, сколько существует N-разрядных чисел с
суммой цифр,  равной 0,1,...,9N ( 9N - максимальная  сумма  цифр  в
N-разрядном числе).  Тогда нетрудно убедиться, что общее количество
"счастливых" 2N-разрядных чисел равно
                P=S(N,0)^2+S(N,1)^2+...+S(N,9N)^2.
     Действительно, рассуждая как и в методе 3, каждое "счастливое"
2N-разрядное число может быть получено склейкой  двух  произвольных
N-разрядных чисел с одинаковой суммой цифр.
     Таким образом,  необходимо уметь  вычислять  значения  величин
S(k,i)  для  всех k<=N,i<=9k.  Определим способ вычисления S(k+1,i)
через значения величин S(k,j), j<=i. Понятно, что любое k+1-разряд-
ное число может быть получено из k-разрядного добавлением еще одно-
го разряда (цифры). Следовательно
               S(k+1,i) = S(k,i-ц1)+S(k,i-ц2)+...,
где ц1,ц2,... - возможные добавленные цифры. Ясно, что это 0,1,...,m
где m=min(9,i). Следовательно,
           S(k+1,i) = S(k,i-0)+S(k,i-1)+...+ S(k,i-m).
                                                              
                            Задача 3.2.
     Используем метод решения задачи 3.
     Решение 3.2b. Обозначим это количество Сm(k,n). Последняя циф-
ра числа в m-ичной системе счисления может принимать одно из значе-
ний 0, 1, ..., m-1. В соответствии с этим сумма цифр (n-1)-значного
числа,  получающаяся  из  n-значного  числа отбрасыванием последней
цифры,  может принимать одно из значений k, k-1, ..., k-m+1. Отсюда
получаем, что
               Cm(k,n)=Cm(k,n-1)+...+Cm(k-m+1,n-1).
     Кроме того Cm(k,1)=1 при 0<=k<=m-1, и Cm(k,1)=0 иначе (в m-ич-
ной системе  счисления  существует  только одно однозначное число с
суммой цифр  k, 0<=k<=m-1, и ни одного такого числа, если k>=m.

                            Задача 4.
     Очевидное решение задачи предполагает разложение числа  N  на
всевозможные  суммы таким образом,  чтобы каждое слагаемое в сумме
не превосходило k.  Очевидно,  что таких разложений  очень  много,
особенно если учитывать,  порядок слагаемых в разложении существе-
нен,  так как он соответствует различной последовательности  ходов
фишки.
     Обозначим через S(i) количество различных путей,  по  которым
фишка может пройти поле от начала до позиции с номером i.  Предпо-
ложим теперь, что для любого j от 1 до i известны значения величин
S(j).  Задача  состоит  в  определении правила вычисления значения
S(i+1),  используя значения известных величин. Легко заметить, что
в  позицию  с  номером  i+1  фишка  может  попасть  из  позиций i,
i-1,...,i-k. Следовательно,
                  S(i+1)=S(i)+S(i-1)+...+S(i-k).
     Таким образом,  вычисляя  последовательно  значения   величин
S(1), S(2),  ..., S(N) по описанному выше правилу, получаем значе-
ние S(N), которое и указывает общее количество различных путей, по
которым фишка может пройти поле от начала до позиции с номером N.

                            Задача 5.
     Если покупатель отдаст все свои купюры продавцу,  то понятно,
что для решения исходной задачи размер минимальной сдачи,  которую
продавец не может вернуть, используя любые имеющиеся теперь у него
купюры C[i] (его и покупателя). Для этого удобно отсортировать ку-
пюры согласно их достоинства в порядке неубывания.
     Предположим, что  продавец  может вернуть любую сдачу от 1 до
S, используя только меньшие i купюр. Для следующей (i+1)-ой купюры
достоинства C[i+1] возможны 2 ситуации.
    1. C[i+1]<S+2. Тогда понятно, что продавец может вернуть любую
сдачу от 1 до C[i+1]+S,  т.к.  любая из этих сумм представима либо
первыми i купюрами,  либо (i+1)-ой купюрой вместе с некоторыми  из
первых i купюр.
    2. C[i+1]>S+1.  Тогда понятно,  что продавец не может  вернуть
сдачу S+1.
     Опишем процедуру вычисления S.
             S:=0;
             i:=1;
             пока (i<=N) и (C[i]<=S+1)
             нц
               S:=S+C[i];
               i:=i+1
             кц
     Если значение S не меньше суммарного количества денег покупа-
теля,  то  покупатель может купить товар любой доступной ему стои-
мости, точно рассчитавшись за покупку. Иначе P=A[1]+...+A[N]-S.

                            Задача 6.
     Решается аналогично задаче 5.

                            Задача 7.
     Если S>H(1)+...+H(n),  то сумму выплатить нельзя.
     Если покупатель отдаст все свои купюры продавцу,  то понятно,
что для решения исходной задачи надо определить, может ли продавец
вернуть сумму H(1)+...+H(n)+B(1)+...+B(l)-S, используя любые имею-
щиеся  теперь  у  него  купюры M[i] (его и покупателя).  Для этого
удобно отсортировать купюры согласно их достоинства в порядке неу-
бывания.
     Пусть P=M[1]+M[2]+ ... +M[n+l].
     Решим чуть более общую задачу: найдем все непредставимые дан-
ными купюрами суммы на промежутке от 0 до P.
     Заведем массив A[0 .. P]  натуральных  чисел. Элемент A[i]=1,
если мы можем выплатить сумму i (т.е.  существует набор купюр сум-
марного достоинства i), и A[i]=0 иначе.
     Будем строить  всевозможные суммы,  используя последовательно
0,1,2,...,N купюр.
     Очевидно, что сумма из ноля купюр - это ноль, поэтому сначала
A[0]=1.
     Предположим, что  мы нашли всевозможные суммы,  которые можно
составить, используя не более (k-1) - ой купюры M[1], ..., M[K-1].
Добавим еще одну купюру M[k].
     Теперь мы можем выплатить следующие суммы:
     1) Все  суммы,  которые  можно было составить с помощью купюр
M[1], ... , M[K-1].
     2) Все  суммы,  которые  можно было составить с помощью купюр
M[1], ... , M[K-1], увеличенные на M[K].
     Расстановка новых пометок в массиве A может выглядеть следую-
щим образом:
     for i:=P-M[K] downto 0 do
       if A[i]=1
       then A[i+M[K]]:=1;
     Мы проходим по массиву  справа  налево  для  того,  чтобы  не
использовать повторно впервые образованную на данном шаге сумму.
     После выполнения n+l шагов алгоритм заканчивает работу.
     Если известно, что H(1)+...+H(n)+B(1)+...+B(l)-S не превосхо-
дит некоторой константы D,  то тогда массив A имеет смысл брать не
из P, а из D элементов.

                            Задача 8.
     Решается аналогично задаче 7.  При  этом  достаточно  завести
массивы
var A,  KOL,  PredSum, B: array [0..P] of byte;
     Назначение массива  A  - как и в предыдущей задаче.  Массив В
служит для временного хранения предыдущих сумм.  Элементы KOL[i] и
PredSum[i] указывают соответственно минимальное количество элемен-
тов,  участвующих в получении суммы со значением  i  и  предыдущую
сумму, из которой была получена добавлением одного слагаемого сум-
ма i.  Формирование этих массивов осуществляется параллельно с за-
полнением массива А. Сначала
    A[0]=1, A[i]=0 для всех i>0,
    KOL[0]=0, KOL[i]=254, для всех i>0, (считаем, что если
              KOL[i]=254, то сумму i набрать нельзя),
    PredSum[i]=0 для всех i>0;

 for i:=1 to N do  { цикл по всем купюрам }
  begin
   for j:=M[i] to P { цикл по всем возможным суммам с участием
                      купюры M[i] }
     if (A[j-M[i]]<>0) and      { если можно набрать сумму j-M[i]  }
        (KOL[j]>KOL[j-M[i]]+1)  { и добавлением купюры M[i] мы по- }
                                { лучаем сумму j из меньшего коли- }
                                { чества купюр                     }
     then begin
            KOL[j]:=KOL[j-M[i]]+1 { то запоминаем это новое коли- }
                                  { чество и в B[j] заносим новую }
            B[j]:=j-M[i];         { информацию о предыдущей сумме }
            A[j]:=1;              { и помечаем, что сумму j наб-  }
                                  { рать можно                    }
          end
     else B[i]:=PredSum[j];   { иначе дублируем старую информацию }
   for j:=M[i] to P do   { Дублируем информацию из B }
     PredSum[j]:=B[j];   { в PredSum                 }
  end;

     Почему мы  не можем непосредственно записывать новую информа-
цию о предыдущей сумме в массив PredSum?  Обратите  внимание,  что
массивы A и KOL дублируют друг друга. Напишите тот же фрагмент
программы, объединив функции массивов A и KOL в одном массиве A.
     После завершения работы предыдущего фрагмента если A[S]=1, то
сумму S набрать можно с помощью KOL[S] купюр. Предыдущая сумма (до
добавления последней  купюры)  была S'= PredSum[S],  следовательно
последняя купюра есть S-PredSum[S].  Аналогично выписываем купюры,
требуемые для представления суммы S' (используя PredSum[S']).

                            Задача 9.
     Очевидное решение  задачи  состоит  в использовании некоторой
процедуры,  которая по заданным координатам (номеру строки i и но-
меру  столбца j) элемента определяет максимальное значение элемен-
тов, расположенных в нужной части матрицы A.
     Однако нетрудно  заметить,  что для элементов первого столбца
матрицы В справедливо  соотношение  B[i,1]=A[i,1],  i=1,...N.  Вы-
числение же других столбцов можно проводить следующим образом:
      B[i,j]=max(A[i,j], B[i-1,j-1], B[i,j-1], B[i+1,j-1]).
     При этом  необходимо учитывать,  что индексы элементов должны
находится в пределах границ массива.

                            Задача 10.
     В элемент a[i,j] матрицы будем  заносить  длину  максимальной
стороны квадрата из единиц,  у которого элемент (i,j) есть верхний
левый угол (очевидно,  что если  a[i,j]=0,  то  квадрат  построить
нельзя).
     Матрицу A будем просматривать по строкам справа налево, снизу
вверх.
     Предположим, что текущий просматриваемый элемент a[i,j]  (все
элементы,  лежащие в строках с номерами больше i,  равно как и все
элементы строки i правее a[i,j]  считаются  уже  к  этому  моменту
просмотренными).
     Если элемент a[i,j]=0, то его значение остается нулевым. Если
же a[i,j]=1, то для того, чтобы найти максимальный размер квадрата
из единиц,  у которого (i,j) - верхний левый угол,  проанализируем
уже просмотренные элементы a[i,j+1],  a[i+1,j+1], a[i+1,j] - соот-
ветственно длины сторон максимальных квадратов с левым углом спра-
ва, по диагонали вниз и просто вниз от данного элемента. Квадрат с
верхним левым углом (i,j) может протянуться вправо на  больше  чем
на a[i+1,j]+1, вниз - не больше чем на a[i,j+1]+1 и по диагонали -
не больше чем на a[i+1,j+1]+1. Следовательно, максимальная сторона
квадрата есть
     a[i,j]=min{a[i,j+1],a[i+1,j],a[i+1,j+1]}+1.
     Программа:
     MaxDim:=0;     { текущая максимальная длина стороны }
     for i:=n-1 downto 1 do
       for j:=m-1 downto 1 do
         if a[i,j]<>0
         then begin
           a[i,j]:=min(a[i,j+1],a[i+1,j+1],a[i+1,j])+1;
           if a[i,j]>MaxDim
           then a[i,j]:=MaxDim
         end;
     writeln('максимальная длина стороны= ',MaxDim);

                            Задача 11.
     Пусть верхний левый угол матрицы имеет индекс (1,1).
     Будем для  каждой  строки i формировать вектор p[1..M] такой,
что p[j] есть число последовательных единичных элементов в столбце
j,  начиная  с  элемента  (i,j)  и выше его.  Таким образом,  если
p[j]=0, то A[i,j]=0, а если p[j]=u>0, то
     A[i,j]=A[i,j+1]= ... =A[i,j-u+1]=1,
а элемент A[i,j-u] нулевой (если,  конечно,  такой элемент есть  в
матрице, т.е. если j-u>0).
     Тогда площадь  (сумма  элементов)  единичного  прямоугольника
S_i(L,R) с нижними правым и левым углами в элементах (i,R) и (i,L)
соответственно есть площадь основания (R-L+1) умноженная на высоту
этого прямоугольника
    h(L,R)=минимальное p[i] по всем j, изменяющимся от L до R.
Для каждой  строки  i  надо  найти  максимум величины S_i(L,R) при
1<=L<=R<=M, а максимум по всем строкам и даст искомую величину.
     Очевидно, что для первой строки
     p[j]=A[1,j].
     Если мы  знаем  вектор l для строки i,  то мы можем вычислить
его для строки (i+1) по следующей формуле
     if A[i+1,j]=0 then p[j]:=0
                   else p[j]:=p[j]+1;
     Более коротко это же можно записать и так:
                     p[j]:=(p[j]+1)*A[i+1,j];
     Будем рассматривать вектор p, соответствующий строке i, и для
каждого индекса j,  1<=j<=M, определим максимальный размер единич-
ного прямоугольника с высотой p(j),  располагающегося в столбцах с
номерами от L(j) до R(j), L(j)<=j<=R(j), нижняя граница которого -
строка  i.  Очевидно,  что L(j) есть увеличенный на единицу индекс
первого меньшего чем p[j] элемента вектора p при  просмотре  p  от
j-го  элемента  влево,  или L(j)=1,  если такого меньшего элемента
нет. Аналогично, R(j) есть уменьшенный на 1 индекс первого меньше-
го  чем  p[j]  элемента вектора p при просмотре p от j-го элемента
вправо, или R(j)=M, если такого элемента нет.
     Как быстро вычислить L(j) и R(j)?  Используя алгоритм 8 Главы
"Структуры данных" мы можем найти все L и R за два прохода по век-
тору p:
     Будем заполнять массив R. Вектор p просматриваем слева напра-
во.  Организуем  стек для позиций элементов.  Для каждого текущего
p[j] будем выталкивать из стека все позиции, на которых стоят эле-
менты большие текущего, и заносить в соответствующие этим позициям
места массива R число (j-1). Замет позицию текущего элемента j по-
местить в стек.  После просмотра всех элементов в стеке будут сто-
ять индексы позиций массива R,  в которые необходимо занести число
M.
     var Stack: array [0..M] of byte;
       . . .
       S[0]:=0; { стек пуст, S[0] есть указатель на последнюю
                  помещенную в стек позицию}
       for j:=1 to M do
       begin
         while p[j]<p[S[S[0]]] do
           { S[0] -- это индекс последней занятой позиции в стеке,}
           { на которой находится число S[S[0]] - индекс элемента }
           { массива p, а сам этот элемент -- это p[S[S[0]]]      }
         begin
           R[S[S[0]]]:=j-1; {для элемента массива p с индексом
                            S[S[0]] нашли координату правой стенки}
           S[0]:=S[0]-1;    { убрать элемент из стека }
         end;
         S[0]:=S[0]+1;      { индекс - в стек }
         S[S[0]]:=j;
       end;
       for j:=1 to S[0] do R[S[S[0]]]:=M;

     Для заполнения массива L необходимо  проделать  те  же  самые
операции, но вектор p будет просматриваться справа налево:
       . . .
       S[0]:=0; { стек пуст, S[0] есть указатель на последнюю
                  помещенную в стек позицию}
       for j:=M downto 1 do
       begin
         while p[j]<p[S[S[0]]] do
         begin
           L[S[S[0]]]:=j+1; {для элемента массива p с индексом
                             S[S[0]] нашли координату левой стенки}
           S[0]:=S[0]-1;    { убрать элемент из стека }
         end;
         S[0]:=S[0]+1;      { индекс - в стек }
         S[S[0]]:=j;
       end;
       for j:=1 to S[0] do L[S[S[0]]]:=1;

     Последнее, что остается сделать -  это  за  один  проход  вы-
числить максимум по всем j выражения
     p[j]*(R[j]-L[j]+1).
     Этот максимум  есть  размер  максимального единичного прямоу-
гольника с нижней гранью в строке i.
     Максимум по всем i и даст решение.
     Сложность алгоритма O(N*M),  т.е. количество операции линейно
зависит от числа элементов матрицы A!

                            Задача 12.
     Комбинируем идеи пунктов a) и c) задачи 16 (глава "Сортировки
и последовательности"). Пусть элемент C[i,j] массива C есть следу-
ющая сумма
                   C[i,j]=A[1,j]+ ... +A[i,j].
     Переменная MaxSoFar имеет то же самое назначение, что и рань-
ше,  MaxFndingHere есть максимальное значение суммы элементов пря-
моугольной подматрицы с правым нижним углом (i,j) и высоты k.

     MaxSoFar:=A[1,1];
     for i:=1 to M do begin
       MaxEndingHere:=0;
       for k:=1 to i do
         for j:=1 to N do begin
           { смотрим, что произойдет с максимальным значением суммы
             элементов прямоугольной подматрицы с правым нижним уг-
             лом (i-1,j) и высоты k при приписывании к этой подмат-
             рице очередного i-го столбца с суммой C[i,j]-C[i-k,j].
           }
           MaxEndingHere:=max(MaxEndingHere+C[i,j]-C[i-k,j],
                              C[i,j]-C[i-k,j]);
           MaxSoFar:=max(MaxSoFar, MaxEndingHere);
         end
     end;

                          Задача 13.
     Для решения  пункта  1  задачи достаточно воспользоваться
тем фактом,  что для определения минимальной величины  штрафа,
взимаемого  за  проход  в клетку i-той строки достаточно знать
минимальные величины штрафа,  взимаемого за  проход  в  клетки
(i-1)-той  строки,  которые являются соседними рассматриваемой
клетке. Поэтому алгоритм решения пункта 1 следующий:
    для i от 1 до n
     Штраф[i,1]:=A[i,1]
    для i от 2 до n
     для j от 1 до m
     нц
       Штраф[i,j]:=Штраф[i-1,j]+A[i,j];
       если j>1 и Штраф[i,j] < Штраф[i-1,j-1]+A[i,j];
           то Штраф[i,j]:=Штраф[i-1,j-1]+A[i,j];
       если j<m и Штраф[i,j] < Штраф[i-1,j+1]+A[i,j];
           то Штраф[i,j]:=Штраф[i-1,j+1]+A[i,j];
     кц
   Для решения  пункта  2  можно  воспользоваться   алгоритмом
Дейкстры  нахождения  минимального пути в графе из главы 'Гра-
фы'.

                            Задача 14.
     а) Обозначим вершины N-угольника x(0),  ..., x(N-1) в порядке
обхода по контуру.  В дальнейшем будем считать,  что если у нас  в
выкладках  встречается вершина с индексом k,  то это то же,  что и
вершина с номером k mod N (остаток от деления k на N).
     Рассмотрим выпуклый L-угольник, вершинами которого являются L
последовательных вершин данного N-угольника,  начиная с x(p) и  до
x(p+L-1) (в порядке обхода по контуру).  У этого L-угольника будем
считать,  что отрезок (x(p),x(p+L-1)) - это его  диагональ.  Сумму
диагоналей этой фигуры обозначим S(p,p+L-1).
     Очевидно, что по условию задачи:
     S(p,p)=0; S(p,p+1)=0 (у точки и отрезка нет диагоналей),
     S(p,p+2)=d(p,p+2)
(тут d(p,p+2) - длина отрезка (x(p),x(p+2))).
     Предположим, что мы знаем S(p,p+L-1) для всех p=0, ... ,N-1 и
L=1,...k.
     Найдем S(p,p+k).
     Мы знаем, что диагонали разбивают k+1 угольник на треугольни-
ки, и что (x(p),x(p+k)) - диагональ, т.е. одна из сторон какого-то
треугольника.  Итак,  мы  зафиксировали две вершины треугольника -
x(p) и x(p+k).  Третьей вершиной  может  быть  либо  x(p+1),  либо
x(p+2),...,  либо x(p+k-1).  Если мы считаем, что третья вершина -
это x(i), то сумма диагоналей будет
     d(p,p+k) + S(p,i) + S(i,k).                               (1)
     Тут мы уже знаем S(p,i) и S(i,k) - они, по предположению, бы-
ли вычислены на предыдущих шагах.  d(p,p+k) - это расстояние между
вершинами x(p) и x(p+k), его мы тоже можем вычислить.
     Так как нас интересует минимальная сумма триангуляции (разби-
ения на треугольники), то мы ищем выражение (1) с минимальным зна-
чением
     S(p,p+k)=d(p,p+k)+ min{ S(p,i)+S(i,k)}                    (2)
                         i

     при i=p+1,p+2,...,k-1.
     Находим S(p,p+k) для каждого p=0,...,N-1.
     Минимум S(p,p+N-2) по p=0,...,N-1,  и даст искомую триангуля-
цию (действительно,  S(p,p+N-2)  есть  стоимость  разбивки  фигуры
после проведения N-3 диагоналей).
     б) Алгоритм остается тем же,  за исключением того, что вместо
формулы (2) надо использовать следующую:
     S(p,p+k)=min max {d(p,p+k),S(p,i),S(i,k)},
               i

где S(p,p+k)  -  длина максимальной диагонали в фигуре с вершинами
x(p),  x(p+1),  ...,x(p+k) (отрезок (x(p),x(p+k)) считается диаго-
налью).  Мы  берем  минимум по всем возможным разбивкам фигуры,  а
стоимость разбивки определяется как максимум  из  длины  диагонали
d(p,p+k) и длин максимальных диагоналей S(p,i) и S(i,k).

                            Задача 15.
     Будем считать, что вектор С определяет веса элементов, а век-
тор В - стоимость.
     Обозначим через F[k,y] величину  наибольшей  суммарной  стои-
мости элементов с номерами не большими k, суммарный вес которых не
превышает y.  Покажем,  как  можно  вычислить  значение  F[k+1,y],
используя величины с меньшими значениями индексов.
     Понятно, что величина F[k+1,y] может соответствовать множест-
ву элементов,  которое содержит или не содержит элемент k+1.  Если
множество не  содержит  элемент  k+1,  то  F[k+1,y]=F[k,y].  Иначе
F[k+1,y]=B[k+1]+F[k,y-С[k+1]],  т.е.  максимальная суммарная стои-
мость есть стоимость k+1 элемента плюс максимальная стоимость эле-
ментов с номерами не большими k, суммарный вес которых не превыша-
ет величины y-С[k+1].
     Таким образом, мы имеем рекуррентную формулу вычисления вели-
чин
            F[k+1,y]=max(F[k,y],B[k+1]+F[k,y-С[k+1]]).
     Вычисляя последовательно элементы  матрицы  F,  учитывая  при
этом,  что F[0,y]=0 для любого y,  и F[j,0] для любого j,  получим
значение F[N,A],  которая является значением максимально возможной
стоимости.
     Для выяснения номеров элементов, вошедших в множество, доста-
точно, начав с элемента с индексами [i,y] (которые вначале равны N
и A соответственно),сравнить его со значением F[i-1,y].  Если зна-
чения равны,  то i элемент не входит в множество, а процесс повто-
ряется для элемента с индексами [i-1,y]. В случае неравенства эле-
ментов  элемент  i  входит в множество,  а процесс повторяется для
элемента с индексами [i-1,y-C[i]].  Процесс выполняется для всех i
от N до 1.

                            Задача 16.
     Для x=a(1)...a(m)  и  y=b(1)...b(n),  a(i)  и  b(i)  символы,
1<=i<=m,  1<=j<=n,  d(x,y) можно вычислить, применяя метод динами-
ческого программирования.
     Определим массив d[0..m,0..n], элементы которого
      d[i,j] = d(a(1)...a(i), b(1)...b(j)), 0<=i<=m,0<=j<=n,
так что
         d[0,j]=j;
         d[i,0]=i;
очевидным образом получаем
         d[i,j]=min{d[i-1,j]+1,d[i,j-1]+1,d[i-1,j-1]+Pij}
где Pij=1 если a(i)<>b(i) и Pij=0 иначе (в правой части  приведен-
ного  выше выражения первому элементу в min соответствует операция
удаления из строки  a(1)...a(i-1)a(i)  последнего  элемента  a(i),
после чего за d[i-1,j] операцию строка a(1)...a(i-1) преобразуется
в строку b(1)...b(j),  второму элементу - операция вставки символа
b(j) в конец строки b(1)...b(j-1), полученной за d[i,j-1] операцию
из строки a(1)...a(i),  а третьему - контекстная замена ai на  bj,
замена  осуществляется в случае ai<>bj (тогда Pij=1) и не происхо-
дит при совпадении ai и bj).
     Получаем необходимое d(x,y)=d[m,n].
     Алгоритм может быть записан так:

     for i:=1 to m do
       d[i,0]:=i;
     for j:=1 to n do
       d[0,j]:=j;
     for i:=1 to m do
     for j:=1 to n do
          d[i,j]=min{d[i-1,j]+1,d[i,j-1]+1,d[i-1,j-1]+Pij};

                            Задача 17.
     Делается аналогично задаче 16.

                            Задача 18.
     Пусть строка S1 состоит из цифр 0 и 1 и имеет длину N, а стро-
ка S2 (из символов A и B) - длину M.
     Заведем матрицу А размера N на M, при этом строки матрицы по-
мечаются i-ой цифрой строки S1, а j-й столбец - j-м символом стро-
ки S2.
     Возьмем в качестве примера S1='00110', S2='AAAABBAA'.
     Первая цифра строки S1 (цифра 0) может быть  преобразована  в
одну из последовательностей букв 'A','AA','AAA','AAAA', являющиеся
префиксами строки S2. Заносим символ 'x' в те столбцы первой стро-
ки, буквы-пометки которых соответствуют последним буквам возможных
последовательностей.  Таким образом,  помечаются элементы  A[1,1],
A[1,2], A[1,3] и A[1,4].
     Шаг алгоритма:  будем преобразовывать очередную цифру  S1[i],
которой соответствует строка i.
     Находим 'x' в предыдущей строке при просмотре ее слева напра-
во  (этому столбцу соответствует последняя буква в какой-то из не-
пустых последовательностей букв,  порожденных на предыдущем шаге).
Если  текущую цифру можно преобразовать в последовательность букв,
помечающих следующие за данным столбцы,  то в этих столбцах в дан-
ной строке ставим 'x'.
     Далее от места над последней помеченной ячейкой ищем в преды-
дущей строке 'x' и, когда находим, повторяем указанные выше опера-
ции.
     Эти действия проводим далее для i=2,...,N.
     Вид матрицы после N шагов:

     A A A A B B A A       Если  после  N  шагов  в позиции (N,M)
    ┌───────────────┐      стоит x, то строки можно преобразовы-
  0 │x x x x        │      вать друг в друга.
  0 │  x x x        │
  1 │    x x x x    │
  1 │      x x x x x│
  0 │            x x│
    └───────────────┘

     Замечание: Можно обойтись и одномерным массивом.  В самом де-
ле, при заполнении следующей строки мы обращаемся только к элемен-
там предыдущей строки, к каждому - по одному разу.
     Алгоритм (без учета замечания) может быть следующим:

     for i:=1 to N do
       for j:=1 to M do
         A[i,j]:=' ';                            { инициализация }
     if S1[1]=0
     then element:='A'             { 0 преобразуется в A }
     else element:=S2[1];          { 1 - в A или в  B }
     i:=1;
     while (i<=M) and (S2[i]=element) do begin   { первый шаг }
       A[1,i]:='x';
       i:=i+1
     end;
     for i:=2 to N do begin
        j:=2;
      while j<M do begin                   { просмотр строки i }
        if A[i-1,j-1]='x'
        then begin
          if S1[i]=0
          then element:='A'
          else element:=S2[j];
          if S2[j]=element
          then
            while (j<=M) and (S2[j]=element) do begin
              A[i,j]:='x';
              j:=j+1;
            end       { end for while }
          else j:=j+1
        end           { end for then  }
        else j:=j+1
      end             { end for while }
     end;             { end for for   }
   if A[N,M]='x'
   then writeln('Можно преобразовать')
   else writeln('Нельзя преобразовать');

     Напишите программу, использующую одномерный массив.

                            Задача 19.
     Определим через F[i,j] минимальное  число  операций,  которое
требуется  для  перемножения  группы  матриц  с номерами от i до j
включительно.  Ясно,  что F[i,i]=0.  Перемножение матриц  в  такой
группе может производиться различными способами,  а именно, произ-
водить сначала перемножение наилучшим способом группы от i  до  k,
затем от k+1 до j,  наконец перемножить получившиеся матрицы.  По-
нятно, что k может быть величиной от i до j-1. Учитывая требование
получить наилучший результат, величина F[i,j] определяется как
          F[i,j]=max(F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j]),
где k может быть величиной от i до j-1, n[i], n[k+1], m[j] опреде-
ляют размеры матриц, получившихся при перемножении в группах.

     для  i от 1 до N выполнять
        F[i,i]:=0;
     для  l от 1 до N-1 выполнять
       для  i от 1 до N-l выполнять
       нц
         Kol:=бесконечность;
         j:=i+l;
         для  k от i до j-1 выполнять
          если Kol > F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j]
             то Kol:=F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j];
          все
         F[i,j]:=Kol;
       кц

                            Задача 20.
     а). Пусть К(L,i) обозначает множество возрастающих  подпоследова-
тельностей длины L, которые составлены из элементов с номерами от 1 до
i-1. Понятно, что их может быть очень много. Однако их число можно су-
щественно сократить,  воспользовавшись следующим фактом: из двух цепо-
чек длины L более перспективной будет цепочка, у которой величина пос-
леднего  элемента  меньше,  так  как ее может продолжить большее число
элементов. Пусть S(L,i) - это именно такая самая перспективная цепочка
длины  L  с минимальным по величине последним элементом,  а S(i) - это
множество всех цепочек S(L,i) со всевозможными L.  Понятно, что в S(i)
содержится не более i-1 цепочек (с длинами 1,...,i-1).  Пусть мы знаем
S(i).
     Для того,  чтобы определить, какие цепочки может продолжать i-й
элемент,  достаточно знать последние элементы перспективных цепочек.
Для  этого  удобно  завести  массив  адресов АДР последних элементов
перспективных цепочек длины 1,2,...,n.  При этом легко  понять,  что
последний элемент перспективной цепочки длины s не превышает послед-
него элемента перспективной цепочки длины  s+1.  Следовательно,  для
очередного  i-го элемента достаточно найти только максимальную длину
перспективной цепочки,  для которой он будет последним. Понятно, что
это  будет  цепочка  максимальной  длины,  последний элемент которой
меньше текущего элемента. Учитывая упорядоченность последних элемен-
тов  перспективных  цепочек,  поиск  можно  сделать дихотомией.  При
присоединении i-го элемента к какой-нибудь цепочке длины p ее  длина
увеличивается на  1,  a ее последним элементом становится элемент i.
При этом множество S(i+1) совпадает с S(i) за исключением одной  це-
почки
          S(p+1,i+1) = S(p,i) сцепленная с i-ым элементом.
     Для хранения цепочек удобно хранить для каждого элемента  номер
элемента, который ему предшествует в цепочке.

     Другое решение этой задачи:
     Заведем 3  массива  длины N:  в массиве A[1..N] помещаются сами
числа последовательности.  Элемент B[i] имеет значение длины  макси-
мальной возрастающей подпоследовательности,  завершающейся элементом
A[i], а величина C[i] есть индекс предшествующего элементу A[i] эле-
мента  в  этой  максимальной  последовательности (A[i]=0 есть такого
элемента нет).
     Если N=1,  то  A[1]  и есть искомая подпоследовательность.  При
этом B[1]=1,  C[1]=0.  Предположим, что мы заполнили массивы A,B и C
от  начала  до  элемента  M-1.  Попытаемся  обработать элемент A[M].
Просматривая массив A от 1 до M-1-го элемента мы  ищем  такое  A[k],
что одновременно
     1) A[k]<A[M],
     2) B[k] максимально.
     Очевидно, что для того,  чтобы получить максимальную  по  длине
подпоследовательность,  заканчивающуюся A[M], этот элемент надо при-
писать к подпоследовательности с последним элементом A[K]. Получаем,
что B[M]=B[K]+1, C[M]=K.
     Пусть мы обработали все N элементов массива A.  Находим  макси-
мальный элемент массива B,  пусть это будет B[K].  По построению это
длина максимальной подпоследовательности.
     Выписываем эту подпоследовательность:  полагаем j:=k;  печатаем
элемент A[j];  так как предшествующий в  последовательности  элемент
имеет  индекс  C[j],  то делаем присваивание j:=C[j],  распечатываем
этот элемент и т.д.,  до тех пор,  пока j не станет 0 (т.е. мы дошли
до начала последовательности).
     Запись алгоритма:
     for i:=2 to N do B[i]:=0;
       C[1]:=0; B[1]:=1; Max:=1; IndexMax:=1;
     for i:=2 to N do
       for j:=1 to i-1 do
         if (A[j]<A[i]) AND (B[i]<B[j]+1)
         then begin
                C[i]:=j;
                B[i]:=B[j]+1;
                if B[i]>Max
                then begin Max:=B[i]
                           IndexMax:=i
                     end;
     while IndexMax<>0 do begin
       writeln(A[Index-Max]);
       IndexMax:=C[IndexMax]
     end;
     В программе в переменной Max хранится максимальная найденная до
сих пор длина подпоследовательности,  в  IndexMax  находится  индекс
последнего элемента этой подпоследовательности.
     Структура данных, каждый элемент которой (в данном случае A[i])
содержит  ссылку  (в  этой  задаче C[i]) на предыдущий элемент (или,
если требуется,  на последующий элемент) называется однонаправленным
списком.  Если  у  элемента есть ссылка как на предыдущий,  так и на
последующий за ним элемент, то список двунаправленный (его можно ре-
ализовать, используя не один массив для индексов, а два).
     б). Частный случай пункта в).
     в). Заведем  матрицу  С[0..m+1,1..n].  В ней i-тая строка будет
хранить информацию о последовательностях с i-1 разрывами;  j-ый эле-
мент  в  этой  строке есть длина самой длинной подпоследовательности
элементов "хвоста" массива А ( от j-го элемента до  n-го),  начинаю-
щейся в j-ой позиции и с не более чем i-1 разрывом.
     Правило заполнения матрицы:
     Заполним нулевую строку нулями (чтобы можно было заполнить пер-
вую строку по общему алгоритму).
     Для каждого  номера  строки  i  от 1 до m+1 выполнить следующие
действия:
     Для j-го  элемента  массива  A (j изменяется от n до 1) находим
максимальную по длине подпоследовательность, которую можно присоеди-
нить к этому элементу так, чтобы получить подпоследовательность мак-
симальной длины с не более чем i-1 разрывом. Для этого мы:
     1) ищем элемент A[k] последовательности A,  больший A[j], стоя-
щий в массиве A правее j-го элемента и с максимальным С[i,k];
     2) затем просматриваем элементы i-1 -ой строки матрицы С, начи-
ная с j+1 -го и до конца, и находим C[i-1,s] - максимальный из них;
     3) сравниваем C[i-1,s] с С[i,k].  Больший из них (обозначим его
C[row,col]), увеличенный на 1, запоминаем в C[i,j]. Это и будет дли-
на максимальной подпоследовательности,  начинающейся в позиции j,  с
не более чем i-1 разрывом.
     4) Запоминаем индексы row и col элемента массива C, предшеству-
ющего C[i,j], в ячейках X[i,j] и Y[i,j] соответственно.

     После окончания цикла максимальный элемент m+1 -ой строки  мат-
рицы  C и есть максимальная длина возрастающей подпоследовательности
с m разрывами.  Выписать всю подпоследовательность  можно  следующим
образом: для каждого элемента подпоследовательности в массивах X и Y
хранится информация о предшественнике.  Мы,  начиная с максимального
элемента m+1 -ой строки матрицы C, восстанавливаем всю подпоследова-
тельность.

     Обоснование алгоритма:
     Пусть мы  знаем  C[i-1,j] для всех j от 1 до n и для некоторого
i, а также C[i,k] для k от j+1 до n. Мы хотим вычислить C[i,j].
     Для j-го  элемента  массива  А существует максимальная по длине
подпоследовательность с не более чем i-1 -им разрывом,  начинающаяся
с  A[j].  Второй элемент (обозначим его A[k]) этой максимальной под-
последовательности (если он, конечно, есть) может быть
     1) больше,  чем A[j]. Тогда мы находим его среди элементов, об-
ладающих следующими свойствами:
       а) k>j,
       б) C[i,k] максимальный (т.е.  мы присоединяем к  A[j]  макси-
мальную  по длине подпоследовательность с не более чем i-1 разрывом,
формируя подпоследовательность опять не более чем с i-1 разрывом);
     2) меньше или равный, чем A[j]. Тогда мы ищем его среди элемен-
тов, обладающих следующими свойствами:
       а) k>j;
       б) C[i-1,k] максимальный (т.е.  мы присоединяем  максимальную
подпоследовательность  с  не  более чем i-2 -мя разрывами,  формируя
подпоследовательность с не более чем i-1 разрывом).
     Полученная подпоследовательность получается максимальной длины,
так как длина подпоследовательности, начиная с A[k], максимальная.
     Упоминавшиеся выше  индексы  row и col,  которые запоминаются в
X[i,j] и Y[i,j] соответственно, обозначают
     col - индекс следующего за A[j] элемента в максимальной по дли-
не подпоследовательности,  начинающейся в позиции j и имеющей не бо-
лее i-1 разрыва;
     row-1 - максимальное количество разрывов в подпоследовательнос-
ти, начинающейся в A[col].

{ Программа написана Д.Медведевым и А.Гавриловым }
const max=100;           { максимальная длина массива A }
var
  sw,l,i,j,k,n,m,maxind,swind:integer;
  c:array [0..max,1..max] of integer;
  x,y:array [1..max,1..max] of integer;
  a,b:array [1..max] of integer;
begin
  Write('Введите N:');
  readln(n);
  Writeln('Введите последовательность');
  for i:=1 to n do
    read(a[i]);
  readln;
  Write('Введите количество разрывов подпоследовательности:');
  readln(m);
  fillchar(c,sizeof(c),0);  { зануление с, x и y }
  fillchar(x,sizeof(x),0);
  fillchar(y,sizeof(y),0);
  for i:=1 to m+1 do
    for j:=n downto 1 do
      begin
        c[i,j]:=1;
        for k:=j+1 to n do
          if (a[k]>a[j]) and (c[i,k]>=c[i,j]) then
            begin
              c[i,j]:=c[i,k]+1;
              x[i,j]:=k;
              y[i,j]:=i;
            end;
        for k:=j+1 to n do
          if c[i-1,k]>=c[i,j] then
            begin
              c[i,j]:=c[i-1,k]+1;
              x[i,j]:=k;
              y[i,j]:=i-1;
            end;
      end;
  maxind:=1;
  for i:=1 to n do
    if c[m+1,i]>c[m+1,maxind] then
      maxind:=i;
  l:=c[m+1,maxind];
  j:=maxind;i:=m+1;k:=1;
  while (c[i,j]<>1) do
    begin
      b[k]:=j;        { в массив b выписываем индексы элементов }
      inc(k);         { максимальной по длине подпоследователь- }
      sw:=x[i,j];     { ности в прямом порядке }
      i:=y[i,j];
      j:=sw;
    end;
  b[k]:=j;
  for i:=1 to k do write(a[b[i]],' ');
  writeln;
  writeln('Длина=',l);
end.


                            Задача 21.
     Для решения задачи элементы  массива  удобно  упорядочить  по
абсолютной  величине  (в порядке неубывания).  Если в массиве есть
элементы,  равные 0,  то один из них и будет  последним  элементом
искомой последовательности,  поэтому их можно игнорировать.  Пусть
К(i) обозначает максимальное количество элементов,  которое  может
находится  в  некоторой  последовательности с требуемым свойством,
последним элементом которой является i-й элемент.
     Понятно, что  наименьшему по абсолютной величине элементу ни-
чего не может предшествовать ни один элемент,  поэтому К(р)=0, где
р - индекс первого ненулевого элемента.
     Для каждого следующего элемента с номером j, j=р+1,...,N, не-
обходимо определить максимальное количество элементов, которое мо-
жет  предшествовать рассматриваемому элементу, с учетом требуемого
свойства.  Понятно,  что  это  количество есть максимум из величин
К(р1),  К(р2),...,  К(рm),  где элементы с номерами  p1,p2,...,pm,
р<=p1<p2<...<pm<j являются делителями элемента с номером j. Поэто-
му мы имеем рекуррентную формулу для вычисления К(j):
               К(j) = мах (К(p1),К(p2),...,К(pm)).
     Значение К(N),  вычисленное по описанному выше правилу, и оп-
ределяет  максимальное  количество элементов,  которое может нахо-
дится в некоторой последовательности с  требуемым  свойством  (без
учета возможного нуля в конце последовательности).
     Для того,  чтобы установить,  какие элементы образуют  макси-
мальную  последовательность,  достаточно для каждого номера j пом-
нить тот номер из p1,p2,...,pm,  на котором  достигается  максимум
для чисел  К(p1),К(p2),...,К(pm).  Эти номера можно определять па-
раллельно с вычислением значения К(j) в некотором массиве,  напри-
мер ПРЕДОК. Используя эту информацию, легко определить номера эле-
ментов последовательности,  проходя от элемента i  с  максимальным
значением  К(i) к элементу,  который ему предшествует (ПРЕДОК(i)),
до тех пор, пока не придем к первому элементу f последовательности
(ПРЕДОК(f)=0).

                            Задача 22.
      Можно, конечно,  число A умножить само на себя n-1  раз,  но
для этого надо выполнить n-1 операцию умножения. Рассмотрим метод,
требующий меньшего числа умножений (он, однако, не всегда дает ми-
нимальное число умножений).
     Если n - четное,  n=2m то будем вычислять A^n, используя тож-
дество
          A^2m=(A^m)^2;
     если же n=2m+1, то
          A^(2m+1)=(A^2m)*A=((A^m)^2)*A.
     Таким образом, возведение A в 13 степень будет выглядеть сле-
дующим образом:
  (A^13)=((A^6)^2)*A=(((A^3)^2)^2)*A=(((A*A*A)^2)^2)*A
     и вычисление требует 5 операций умножения.
     Используя данный  метод,  для возведения в степень n потребу-
ется порядка log2(n) операций умножения.

     Программа на Паскале может выглядеть так:
      var A,N: integer;
      function power(N: integer): integer;
      begin
        if N>1
        then if odd(N)     { N нечетно? }
             then power:=SQR(power(N div 2))*A
             else power:=SQR(power(N div 2))
        else power:=A
      end;
      begin
        read(A,N);
        writeln(power(N));
      end;

      Можно ту же самую идею реализовать и по другому (  далее  мы
приводим выдержку из книги Д.Кнута "Искусство программирования для
ЭВМ", т.2, с.482):
      "Запишем n в двоичной системе счисления и заменим в этой за-
писи каждую цифру "1" парой букв SX,  а каждую цифру "0" -  буквой
S, после чего вычеркнем крайнюю левую пару букв SX. Результат, чи-
таемый слева направо, превращается в правило вычисления x**n, если
букву  "S"  интерпретировать как операцию возведения в квадрат,  а
букву "X" - как операцию умножения на x.  Например,  если n=23, то
его двоичным представлением будет 10111; строим последовательность
SX S SX SX SX, удаляем из нее начальную пару SX и в итоге получаем
следующее правило вычисления:  S SX SX SX. Согласно этому правилу,
мы должны "возвести x в квадрат,  затем снова возвести в  квадрат,
затем умножить на x, возвести в квадрат, умножить на x, возвести в
квадрат и,  наконец,  умножить на x";  при этом мы последовательно
вычисляем x**2, x**4, x**5, x**10, x**11, x**22, x**23.
      Этот "бинарный метод" легко обосновать,  рассмотрев последо-
вательность получаемых  в  ходе  вычисления показателей:  если "S"
интерпретировать как операцию умножения на 2, а "X" - как операцию
прибавления 1  и если начать с 1,  а не с x,  то наше правило дает
нам в соответствии со свойствами двоичной системы счисления  число
n".
      Приведенный метод не дает минимального числа операций  умно-
жения.  Для вычисления x**23 нам, по изложенному выше методу, пот-
ребуется 7 операций умножения.  В действительности  их  необходимо
только 6:
      x -> x**2 -> x**3 -> x**5 -> x**10 -> x**20 -> x**23.
      Алгоритм нахождения  минимального числа операций (кроме пол-
ного перебора) сейчас неизвестен (см. там же у Д.Кнута).

                            Задача 23.
     Пусть z есть массив из N элементов,  y - из M.  Положим i=1 и
j=1.  Берем элемент z[i] и ищем минимальное k,  k>=j,  k<=M, такое
что y[k]=z[i] (мы находим очередной совпадающий символ в строках z
и y).  Полагаем i=i+1 и j=k+1.  Повторяем поиск  элемента  z[i]  в
оставшемся куске последовательности y. Условия окончания  поиска:
     a) Если  i стало больше N (т.е.  все элементы массива z явля-
ются  подпоследовательностью элементов y), - и тогда z можно полу-
чить вычеркиванием элементов из y.
     б) Если  в  оставшимся  куске последовательности y не найдено
элемента,  совпадающего с очередным z[i], то z из y получить нель-
зя.

                            Задача 24.
     Пусть x=x1,x2, ... ,xm,  y=y1,y2, ... ,yn.
     Заведем матрицу  A[0..m,0..n].  Элемент  A[i,j]  будет длиной
максимальной общей подпоследовательности y x1, ... ,xi и y y1, ...,
yj. Сначала A[i,0]=A[0,j]=0, i=0, ... ,m, j=0, ... ,n.
     Пусть xi=yj, тогда требуется увеличить длину максимальной об-
щей подпоследовательности x1,  ... ,x[i-1] и y1, ... ,y[j-1] на 1:
A[i,j]=A[i-1,j-1]+1, если xi=yj.
     В случае, если xi<>yj, то, очевидно,
     A[i,j]=max{A[i-1,j],A[i,j-1],A[i-1,j-1]},
но так как всегда A[i-1,j-1]<=A[i,j-1], то
     A[i,j]=max{A[i-1,j],A[i,j-1]}.
     Величина A[m,n] и дает длину максимальной общей подпоследова-
тельности. Найдем саму подпоследовательность. Пусть A[m,n]=d. Дви-
гаясь по последней строке справа налево ищем самый левый элемент в
этой строке со значением d.  Двигаемся от него вверх по столбцу  в
поиске  элемента столбца с минимальным первым индексом и значением
d.  Пусть это A[i,j].  Элемент A[i-1,j-1] обязан быть равен d-1, а
xi и yi - это последние общие совпадающие элементы в x и y.
     Начиная от элемента A[i-1,j-1] повторяем,  как  было  описано
выше,  движение  влево  и вверх по матрице,  находим предпоследний
совпадающий элемент в x и y, и т.д.
     Программа:
     for i:=0 to m do A[i,0]:=0;
     for j:=0 to n do A[0,j]:=0;
     for i:=1 to m do
       for j:=1 to n do
         if x[i]=y[i]
         then A[i,j]:=A[i-1,j-1]+1
         else A[i,j]:=max(A[i-1,j],A[i,j-1]);
     writeln('Длина последовательности =',A[m,n]);
     d:=A[m,n]; i:=m; j:=n;
     while (d<>0) do begin
       while A[i,j-1]=d do j:=j-1;
       while A[i-1,j]=d do i:=i-1;
     write('Элемент последовательности номер',d,'есть',x[i]);
     i:=i-1; j:=j-1; d:=d-1; { переход к поиску предшествую- }
                        { щего элемента в последовательности }
     end;

                            Задача 25.
     В последовательностях  x и y избавляемся от лидирующих нулей.
Если хоть одна из последовательностей стала пустой,  то z=0. Иначе
крайние левые цифры и в x и в y есть 1.
     Запускаем на полученных последовательностях  алгоритм  задачи
24 (для получения максимального z необходимо,  чтобы старшая цифра
z была 1 и двоичная запись z имела  максимальную  длину),  но  при
этом  для  каждого  A[i,j] - длины последовательности,  необходимо
хранить добавочно и саму последовательность; при присвоении значе-
ния  A[i,j]  одновременно  будем  запоминать  и последовательность
максимальной длины. Если таких несколько, то берем из них последо-
вательность  с максимальным значением.  Поэтому алгоритм задачи 23
запишется так:
     Пусть S[0..m,0..n]  - массив строк.  В S[i,j] будет храниться
подпоследовательность, длина которой A[i,j].
     for i:=0 to m do A[i,0]:=0;
     for j:=0 to n do A[j,0]:=0;
     for i:=0 to m do
       for j:=0 to n do S[i,j]:='';
     for i:=1 to m do
       for j:=1 to n do begin
         if x[i]=y[j]
         then begin A[i,j]:=A[i-1,j-1]+1;
                    S[i,j]:=S[i-1,j-1]+x[i];
              end;
         A[i,j]:=max(A[i,j],A[i-1,j],A[i,j-1]);
         S[i,j]:=max(S[i,j],S[i-1,j],S[i,j-1]);
     end;
     write(A[m,n],'- длина',S[m,n]);
     Попробуйте не заводить массив S[0..m,0..n],  а обойтись одно-
мерным массивом S[0..n].

