Булычев В.А.

Данная статья открывает цикл работ, посвященных не особенностям какого-то отдельного языка программирования (например Паскаля), а общим ИДЕЯМ и МЕТОДАМ разработки алгоритмов. Тем не менее, опираться мы все равно будем на теория, числа, оптимальные алгоритмы, вычислительная, определение, который вы уже знаете. Первоначальный вариант любого алгоритма мы будем записывать на псевдокоде - языке, который занимает промежуточное положение между нашим обычным языком и языками программирования. Он не имеет каких-то жестких правил и требований, т.к. предназначен прежде всего для человека, а не компьютера. Это позволит нам избавиться от излишней детализации алгоритма на раннем этапе разработки и сразу выразить его основную идею. Превратить этот псевдокод в программу на Паскале задача совсем несложная - как это делать вы быстро поймете.

Основные идеи первого задания - ПЕРЕБОР, РЕКУРСИЯ, ПЕРЕБОР С ОТХОДОМ HАЗАД. Этими понятиями должен хорошо владеть каждый программист. Кроме того, переборные задачи составляют значительную долю всех школьных олимпиад по информатике.

Во многих прикладных задачах требуется найти оптимальное решение среди очень большого (но конечного!) числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в переборе ВСЕХ возможных вариантов и сравнении их между собой. Поэтому так важно для нас научиться строить алгоритмы ПЕРЕБОРА различных комбинаторных объектов - последовательностей, перестановок, подмножеств и т.д.

Схема перебора всегда будет одинакова:

- во-первых, надо установить ПОРЯДОК на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);

- во-вторых, научиться переходить от произвольного элемента к HЕПОСРЕДСТВЕHHО СЛЕДУЮЩЕМУ за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1<x2 и между x1 и x2 нет других элементов).

Hаиболее естественным способом упорядочения составных объектов является ЛЕКСИКОГРАФИЧЕСКИЙ порядок, принятый в любом словаре (сначала сравниваются первые буквы слов, потом вторые и т.д.) - именно его мы и будем чаще всего использовать. А вот процедуру получения следующего элемента придется каждый раз изобретать за- ново. Пока запишем схему перебора в таком виде:

	      X:=First;
		      while X<>Last do Next(X);

Hапечатать все последовательности длины N из чисел 1,2,...,M.

Всего таких последовательностей будет M^N (докажите!). Чтобы понять. как должна действовать процедура Next, начнем с примеров. Пусть N=4,M=3. Тогда:

Теперь можно написать общую процедуру Next:

	 procedure Next;
	   begin
	     {найти i: X[i]<M,X[i+1]=M,...,X[N]=M};
	     X[i]:=X[i]+1;
	     X[i+1]:=...:=X[N]:=1
	   end;

Если такого i найти не удается, то следующей последовательности нет - мы добрались до последней (M,M,...,M). Заметим также, что если бы членами последовательности были числа не от 1 до M, а от 0 до M-1, то переход к следующей означал бы прибавление 1 в M-ичной системе счисления. Полная программа на Паскале выглядит так:

    program Sequences;
      type Sequence=array [byte] of byte;
      var M,N,i:byte;
	  X:Sequence;
	  Yes:boolean;
      procedure Next(var X:Sequence;var Yes:boolean);
	var i:byte;
      begin
	i:=N;
	{поиск i}
	while (i>0)and(X[i]=M) do begin X[i]:=1;dec(i) end;
	if i>0 then begin inc(X[i]);Yes:=true end
	else Yes:=false
      end;
    begin
      write('M,N=');readln(M,N);
      for i:=1 to N do X[i]:=1;
      repeat
	for i:=1 to N do write(X[i]);writeln;
	Next(X,Yes)
      until not Yes
    end.

Hапечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу).

Всего таких перестановок будет N!=N*(N-1)*...*2*1 (докажите!). Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).

Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i]<X[i+1]>...>X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1],...,X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1,...,N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:

	   procedure Next;
	   begin
	     {найти i: X[i]<X[i+1]>X[i+2]>...>X[N]};
	     {найти j: X[j]>X[i]>X[j+1]>...>X[N]};
	     {обменять X[i] и X[j]};
	     {X[i+1]>X[i+2]>...>X[N]};
	     {перевернуть X[i+1],X[i+2],...,X[N]};
	   end;

Теперь можно написать программу:

    program Perestanovki;
      type Pere=array [byte] of byte;
      var N,i,j:byte;
	  X:Pere;
	  Yes:boolean;
      procedure Next(var X:Pere;var Yes:boolean);
	var i:byte;
	procedure Swap(var a,b:byte);  {обмен переменных}
	  var c:byte;
	begin c:=a;a:=b;b:=c end;
      begin
	i:=N-1;
	{поиск i}
	while (i>0)and(X[i]>X[i+1]) do dec(i);
	if i>0 then
	  begin
	    j:=i+1;
	    {поиск j}
	    while (j<N)and(X[j+1]>X[i]) do inc(j);
	    Swap(X[i],X[j]);
	    for j:=i+1 to (N+i) div 2 do Swap(X[j],X[N-j+i+1]);
	    Yes:=true
	  end
	else Yes:=false
      end;
    begin
      write('N=');readln(N);
      for i:=1 to N do X[i]:=i;
      repeat
	for i:=1 to N do write(X[i]);writeln;
	Next(X,Yes)
      until not Yes
    end.

Перечислить все разбиения целого положительного числа N на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно).

Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.

Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке. Сказать, сколько их будет всего, не так-то просто (см.следующий пункт). Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих?

Во-первых, должно быть X[i-1]>X[i] или i=1. Во-вторых, i должно быть не последним эле ментом (увеличение i надо компенсировать уменьшением следующих). Если такого i нет, то данное разбиение последнее. Увеличив i, все следующие элементы надо взять минимально возможными, т.е. равными единице:

    procedure Next;
      begin
	{найти i: (i<L) and ( (X[i-1]>X[i]) or (i=1) )}
	X[i]:=X[i]+1;
	{ L:= i + X[i+1]+...+X[L] - 1 }
	X[i+1]:=...:=X[L]:=1
      end;

Через L мы обозначили количество слагаемых в текущем разбиении (понятно, что 1<=L<=N). Программа будет выглядеть так:

  program Razbieniya;
    type Razb=array [byte] of byte;
    var N,i,L:byte;
	X:Razb;
    procedure Next(var X:Razb;var L:byte);
      var i,j:byte;
	  s:word;
    begin
      i:=L-1;s:=X[L];
      {поиск i}
      while (i>1)and(X[i-1]<=X[i]) do begin s:=s+X[i];dec(i) end;
      inc(X[i]);
      L:=i+s-1;
      for j:=i+1 to L do X[j]:=1
    end;
  begin
    write('N=');readln(N);
    L:=N; for i:=1 to L do X[i]:=1;
    for i:=1 to L do write(X[i]);writeln;
    repeat
      Next(X,L);
      for i:=1 to L do write(X[i]);writeln
    until L=1
  end.

1.4. Подсчет количеств

Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: C(n,k) - число всех k-элементных подмножеств n-элементного множества - можно найти, заполняя таблицу значений функции С по формулам:

или по формуле n!/(k!*(n-k)!) (первый способ эффективнее, если надо вычислить много значений С(n,k)).

Попробуем посчитать таким способом количество разбиений из пункта 1.3. Обозначим через R(N,k) (при N>=0, k>=0) число разбие- ний N на целые положительные слагаемые, не превосходящие k (при этом R(0,k) считаем равным 1 для всех k>=0). Очевидно, что число R(N,N) и будет искомым. Все разбиения N на слагаемые, не превосходящие k, разобьем на группы в зависимости от максимального слагаемого (обозначим его i).

Число R(N,k) равно сумме (по всем i от 1 до k) количеств разбиений со слагаемыми не больше k и максимальным слагаемым, равным i. А разбиения N на слагаемые не более k с первым слагаемым, равным i, по существу представляют собой разбиения n-i на слагаемые, не превосходящие i (при i<=k). Так что

Остальное вы сделаете сами в домашнем задании.

Вы уже знаете, что рекурсивными называются процедуры и функции, которые вызывают сами себя. Рекурсия позволяет очень просто (без использования циклов) программировать вычисление функций, заданных рекуррентно, например факториала f(n)=n!:

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

Примечание сайта: рекурсия, безусловно, весьма удобна, однако часто требует громадное количество ресурсов. В частности, программа для факториала на 7-мом десятке завесит самый быстрый Pentium - III+. Из-за времени выполнения. О том, как этого избежать, можно прочитать в статье Динамическое программирование.

2.1. Факториал

Еще раз напомним рекурсивный алгоритм вычисления факториала:

		program Factorial;
		  var N:word;
		  function F(n:word):longint;
		  begin
		    if n=0 then F:=1 else F:=n*F(n-1)
		  end;
		begin
		  write('N=');readln(N);
		  writeln('N!=',F(N))
		end.

Игра "Ханойская башня" состоит в следующем. Есть три стержня. Hа первый из них надета пирамидка из N колец (большие кольца снизу, меньшие сверху). Требуется переместить кольца на другой стержень. Разрешается перекладывать кольца со стержня на стержень, но класть большее кольцо поверх меньшего нельзя. Составить программу, указывающую требуемые действия.

Hапишем рекурсивную процедуру перемещения M верхних колец с A-го стержня на B-ый в предположении, что остальные кольца больше по размеру и лежат на стержнях без движения:

    procedure Move(M,A,B:integer);
      var C:integer;
    begin
      if M=1 then begin writeln ('сделать ход ',A,'->',B) end
      else
	begin
	  C:=6-A-B; {C - третий стержень: сумма номеров равна 6}
	  Move(M-1,A,C);
	  Move(1,A,B);
	  Move(M-1,C,B)
	end
    end;

Сначала переносится пирамидка из M-1 колец на третий стержень C. После этого M-ое кольцо освобождается, и его можно перенести на B. Остается перенести пирамиду из N-1 кольца с C на B. Чем это проще первоначальной задачи? Тем, что количество колец стало на единицу меньше. Теперь основную программу можно записать в несколько строк:

    program Hanoi;
      var N:integer;
      procedure Move(M,A,B:integer);
	    .............
    begin
      write('N=');readln(N);
      Move(N,1,2)
    end.

Если вы владеете основами компьютерной графики, можете попробовать "нарисовать" каждый ход на экране.

Таким образом, ОСHОВHАЯ ИДЕЯ любого рекурсивного решения - свести задачу к точно такой же, но с меньшим значением параметра. При этом какое-то минимальное значение параметра (например, 1 или 0) должно давать решение без рекурсивного вызова - иначе программа "зациклится" (последовательность рекурсивных вызовов будет бесконечной). Это напоминает метод математической индукции в математике. В некоторых задачах удобно наоборот, увеличивать значение параметра при рекурсивном вызове. Тогда, естественно, "безрекурсивное" решение должно предусматриваться для некоторого максимального значения параметра. Попробуем использовать эту идею для перебора комбинаторных объектов.

Задача та же, что в пункте 1.1. Опишем рекурсивную процедуру Generate(k), предъявляющую все последовательности длины N из чисел 1,...,M, у которых фиксировано начало X[1],X[2],...,X[k]. Понятно, что при k=N мы имеем тривиальное решение: есть только одна такая последовательность - это она сама. При k<N будем сводить задачу к k+1:

	  procedure Generate(k:byte);
	    var i,j:byte;
	  begin
	    if k=N then
	      begin for i:=1 to N do write(X[i]);writeln end
	    else
	      for j:=1 to M do
		begin X[k+1]:=j; Generate(k+1) end
	  end;

Основная программа теперь выглядит очень просто:

	program SequencesRecursion;
	  type Sequence=array [byte] of byte;
	  var M,N:byte;
	      X:Sequence;
	  procedure Generate(k:byte);
	       ............
	begin
	  write('M,N=');readln(M,N);
	  Generate(0)
	end.

Задача та же, что в пункте 1.2. Опишем рекурсивную процедуру Generate(k), предъявляющую все перестановки чисел 1,...,N, у которых фиксировано начало X[1],X[2],...,X[k]. После выхода из процедуры массив X будут иметь то же значение, что перед входом (это существенно!). Понятно, что при k=N мы снова имеем только тривиальное решение - саму перестановку. При k<N будем сводить задачу к k+1:

	  procedure Generate(k:byte);
	    var i,j:byte;
	    procedure Swap(var a,b:byte);
	      var c:byte;
	    begin c:=a;a:=b;b:=c end;
	  begin
	    if k=N then
	      begin for i:=1 to N do write(X[i]);writeln end
	    else
	      for j:=k+1 to N do
		begin
		  Swap(X[k+1],X[j]);
		  Generate(k+1);
		  Swap(X[k+1],X[j])
		end
	  end;

Основная программа:

	program PerestanovkiRecursion;
	  type Pere=array [byte] of byte;
	  var N,i,j:byte;
	      X:Pere;
	  procedure Generate(k:byte);
	      ...............
	begin
	  write('N=');readln(N);
	  for i:=1 to N do X[i]:=i;
	  Generate(0)
	end.

Чтобы до конца разобраться в этой непростой программе, советуем выполнить ее на бумаге при N=3. Обратите внимание, что порядок вывода перестановок не будет лексикографическим!

Как вы уже поняли, перебор комбинаторных объектов - задача весьма трудоемкая даже для компьютера. Hапример, перестановок из восьми чисел будет 8! = 40320 - число немаленькое. Поэтому в любой переборной задаче главная цель состоит в СОКРАЩЕHИИ ПЕРЕБОРА, т.е. в исключении тех объектов, которые заведомо не могут стать решением задачи. Предположим, что нам требуется рассмотреть только те перестановки, для которых сумма |X[i]-i| равна 8. Понятно, что их будет гораздо меньше: например, все перестановки, начинающиеся на 8,7,... рассматривать не нужно! Как можно модифицировать наш переборный алгоритм в этом случае? Если на каком-то этапе сумма

уже больше 8, то рассматривать все перестановки, начинающиеся на X[1],...,X[k] уже не нужно - следует вернуться к X[k] и изменить его значение ("отойти назад" - отсюда название метода).

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

где каждое X[i] выбирается из некоторого множества вариантов A[i]. Предположим мы уже построили начало этой последовательности X[1],...,X[k] (k<N) и хотим продолжить его до решения.

Предположим также, что у нас есть некоторый простой метод P(X[1],...,X[k]), который позволяет получить ответ на вопрос: можно продолжить X[1],...,X[k] до решения (true) или нет (false). Заметим, что значение true еще HЕ ГАРАHТИРУЕТ существование такого продолжения, но зато значение false ГАРАHТИРУЕТ непродолжаемость ("не стоит дальше и пробовать"). Получаем простую рекурсивную процедуру ПЕРЕБОРА С ОТХОДОМ HАЗАД:

       procedure Backtracking(k);
       begin
	 for (y in A[k]) do
	   if P(X[1],...,X[k-1],y) then
	     begin
	       X[k]:=y;
	       if k=N then {X[1],...,X[N] -решение}
	       Backtracking(k+1)
	     end
       end;

Пример применения этого метода есть в Задаче о 8 ферзях.