                        ПЕРЕБОРНЫЕ ЗАДАЧИ.

                            Задача 1.
     Этот алгоpитм  хорошо  известен  и  достаточно подробно изло-
жен.Опишем его (при N=5), от чего рассуждения не утратят общности.
Алгоритм составлен так, что в процессе его исполнения перестановки
N чисел располагаются лексикографически (в словарном порядке). Это
значит,  что  перестановки сравниваются слева направо поэлементно.
Больше та,  у которой  раньше  встретился  элемент,  больше  соот-
ветствующего  ему элемента во второй перестановке.(Например,  если
S=(3,5,4,6,7),а L=(3,5,6,4,7), то S<L).
     Принцип работы алгоритма разъясним на примере.  Допустим, не-
обходимо воспpоизвести все перестановки цифр 3,4,5,6,7. Первой пе-
рестановкой считаем перестановку (3,4,5,6,7).  Последней воспроиз-
водимой перестановкой будет (7,6,5,4,3).
   Предположим, что на некотором шаге  работы  алгоритма  получена
перестановка

                          P=(5,6,7,4,3).

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

                              (5,6,7,4,3).
                                 ^
                                 │

   Затем вновь  просматриваем  пройденный путь ( справа налево ) до
тех пор, пока не дойдем до первого числа, которое уже больше отме-
ченного. Ниже место второго останова отмечено двойной стрелкой.

                               (5,6,7,4,3).
                                  ^ ^
                                  │ ║

   Поменяем местами отмеченные числа:

                               (5,7,6,4,3).
                                  ^ ^
                                  ║ │
   Теперь в зоне, расположенной справа от двойной стрелки, упорядо-
чим  все числа в порядке возрастания.  Так как до сих пор они были
упорядочены по убыванию , то это легко сделать, перевернув указан-
ный отрезок. Получим:

                          Q=(5,7,3,4,6).

Q и  есть  та  перестановка,  которая  должна воспроизводиться не-
посредственно после P.
   Действительно, P<Q,  так  как,  пересматривая  эти перестановки
слева направо, (P(2)=6,Q(2)=7). Пусть существует такая перестановка
R,  что P<R<Q.  Тогда P(1)=R(1)=Q(1). По построению же Q(2) -- это
наименьшее  во  множестве  Q\Q(1)={3,4,6,7}  число,   такое,   что
Q(2)>P(2). Поэтому для R(2) верно одно из двух равенств: R(2)=Q(2)
или R(2)=P(2).  Но так как в P элементы,  начиная с P(3), убывают,
то из P<R следует,  что если P(2)=R(2),  то и P=R. Аналогично, так
как в Q элементы,  начиная с Q(3),  возрастают, то из R<Q следует,
что если R(2)=Q(2), то и R=Q.

                            Задача 2.
     Заведем массив B[0..n] из (n+1) элемента.  B[i]=0,  если i-ый
элемент в подмножество не входит,  и B[i]=1  иначе.  Т.о.  пустому
подмножеству будет соответствовать набор из n нулей,  а n-элемент-
ному подмножеству - набор из n  единиц.  Тут  явно  заметна  связь
подмножества с двоичным представлением числа.
     Алгоритм: будем генерировать числа от 0 до 2^n-1, находить их
двоичное представление,  и формировать подмножество из элементов с
индексами единичных битов в этом представлении.
     Но число 2^n-1 может не поместиться в разрядную сетку машины.
Поэтому генерацию будем проводить, используя массив B:
     Сначала B[i]=0 для всех i,  что соответствует пустому подмно-
жеству.
     Будем рассматривать массив B как запись двоичного числа
                         B[N]...B[1]B[0],
и моделировать операцию сложения этого числа с единицей.  При сло-
жении будем просматривать число справа  налево  заменяя  единичные
биты нулями до тех пор,  пока не найдем нулевой бит, в который за-
несем 1.  Генерация подмножеств заканчивается,  как только  B[N]=1
(предыдущая конфигурация была 1...1 = 2^n-1).
                                   2

     while B[N]<>0 do begin
       i:=0;  { индекс бита двоичного числа }
       while (B[i]=1) do begin
         B[i]:=0;  { моделируем перенос в следующий разряд, }
         i:=i+1    { возникающий при сложении }
       end;
       B[i]:=1;
       { Распечатываем индексы единичных элементов массива B --
         новое сгенерированное подмножество }
       For i:=0 to N-1 do
          if B[i]=1 then write(i);
       writeln; { переход на новую строку при печати }
     end;

                            Задача 3.
    Воспользуемся следующим  алгоритмом  генерации  сочетаний по k
элементов из множества A:
    В массиве  B  будут  находиться индексы используемых на данном
шаге элементов из A (общее их число k).  В качестве начальной кон-
фигурацией возьмем следующую: B[j]=j, j=1,...,k.
    Ищем B[j] с максимальным индексом j такое, что
                           B[j]<n+j-k,
увеличиваем  это B[j] на 1,  а для всех m>j полагаем B[m]=B[m-1]+1
(B[j] растут с ростом j, и мы ищем и увеличиваем на 1 такое B[j] с
максимальным номером j,  чтобы при заполнении возрастающими значе-
ниями элементов массива B[m],  m>j, последний элемент B[k] не пре-
восходил бы n). Если такого B[j] не существует, то генерация соче-
таний для данного k закончена.

                           Задача 4.2.
     Эта задача реализуется следующим рекурсивным  алгоритмом  по-
иска с возвращением (все слова набора A упорядочены по номерам):
     а) Если строка пустая, то одна из возможных дешифровок найде-
на, иначе при разборе текста мы проверяем А[i] (при изменении i от
1 до n) на вхождение в начало дешифруемой в данный момент строки.
    б) Если какое-то A[i] входит в строку как префикс,  то запоми-
наем номер i этого слова,  затем выделяем слово  из  строки,  а  с
остатком текста производим операцию разбора по пункту а).
    Если ни одно из A[i] не входит в качестве префикса в дешифруе-
мую сейчас строку,  то осуществляем возврат на пункт а), предвари-
тельно  добавляя в начало строки последнее удаленное оттуда слово,
и пытаемся выделить из текста слово с большим номером  в  A.  Если
возврат осуществить невозможно (т. к. мы находимся в начале исход-
ной строки),  то алгоритм заканчивает свою работу.  Все  возможные
дешифровки найдены.

                            Задача 5.
     Решается используя перебор с возвратом (Backtracking),  изло-
женный в задаче 4.

                            Задача 6.
     а) Всего может быть 4 арифметических  операции - "+","-","*",
"/".  Занумеруем их от 0 до 3.  Вместо каждого из пяти знаков  "?"
может стоять один из знаков операции.  Заведем массив A из 5 целых
чисел, в i-ом элементе массива будет храниться код соответствующей
i-му знаку "?" операции,  т.е. число от 0 до 3. Начальная конфигу-
рация - все элементы массива нулевые,  конечная - все они равны 3.
Генерация  очередной  конфигурации  знаков равносильна прибавлению
единицы в четверичной системе  счисления,  в  которой  разрешается
пользоваться  только  цифрами от 0 до 3 (подобный метод решения мы
уже встречали в задаче 2).
     Приведем программный фрагмент генерации конфигураций.
     Для удобства возьмем массив A не из  5,  а  из  6  элементов.
О получении  последней конфигурации знаков будет свидетельствовать
появление 1 в шестом разряде (если к 33333  прибавить 1, то полу-
                                          4
чим 100000 ).
          4

     for i:=1 to 6 do A[i]:=0;
     while A[6]=0 do
      begin
              ....
     { проверка, получили ли мы нужный результат }
              ....
        i:=1;
        while A[i]=3  do { Перенос в следующий разряд при }
         begin           { прибавлении единицы }
           A[i]:=0;
           i:=i+1;
         end;
        A[i]:=A[i]+1;
      end;

                            Задача 7.
     Можно воспользоваться вторым способом решения задачи 22 главы
"Разное" и  написать  рекурсивный алгоритм перечисления всех путей
из начальной вершины в конечную.

                             Задача 8.
     Предложим простой  способ построения всех разбиений числа
на слагаемые.  Разбиения будут строится  в  порядке,  обратном
лексикографическому.  Очевидно,  что первым разбиением в таком
порядке будет разбиение, содержащее одно слагаемое, равное , а
последним - разбиение из слагаемых, равных 1.
     Как выглядит разбиение, следующее непосредственно за раз-
биением
      n=с[1]+...+с[к]                  (1)
     Будем искать  разбиение,которое имеет самое большое число
начальных слагаемых,  равных начальным слагаемым разбиения (1)
-  обозначим эти слагаемые а[1],...,а[t-1] - и оставшиеся сла-
гаемые которого определяются разбиением,  непосредственно сле-
дующим за разбиением
    s=a[t]+a[t+1]+...+a[k].
      Легко видеть, что эти условия однозначно определяют зна-
чение t
        t=max{i:a[i]>1}.
      Таким образом,  задача свелась к  нахождению  разбиения,
непосредственно  следующего за разбиением s=a[t]+1+...+1,  где
a[t]>1,  а количество единиц равно k-t.Таким разбиением  явля-
ется разбиение s1=p+p+...+p+(s mod p), где p=a[t]-1.



