Глава 2. Порождение комбинаторных объектов. Здесь собраны задачи, в которых требуется получить один за другим все элементы некоторого множества. 2.1. Размещения с повторениями. 2.1.1. Напечатать все последовательности длины k из чисел 1..n. Решение. Будем печатать их в лексикографическом порядке (последовательность a предшествует последовательности b, если для некоторого s их начальные отрезки длины s равны, а (s+1)-ый член последовательности a меньше). Первой будет последова- тельность <1, 1, ..., 1>, последней - последовательность . Будем хранить последнюю напечатанную последовательность в массиве x[1]...x[k]. ...x[1]...x[k] положить равным 1 ...напечатать x ...last[1]...last[k] положить равным n while x <> last do begin | ...x := следующая за x последовательность | ...напечатать x end; Опишем, как можно перейти от x к следующей последова- тельности. Согласно определению, у следующей последовательности первые s членов должны быть такими же, а (s+1)-ый - больше. Это возможно, если x[s+1] было меньше n. Среди таких s нужно выбрать наибольшее (иначе полученная последовательность не будет непос- редственно следующей). Соответствующее x[s+1] нужно увеличить на 1. Итак, надо, двигаясь с конца последовательности, найти самый правый член, меньший n (он найдется, так как по предположению x<>last), увеличить его на 1, а идущие за ним члены положить равными 1. p:=k; while not (x[p] < n) do begin | p := p-1; end; {x[p] < n, x[p+1] =...= x[k] = n} x[p] := x[p] + 1; for i := p+1 to k do begin | x[i]:=1; end; Замечание. Если членами последовательности считать числа не от 1 до n, а от 0 до n-1, то переход к следующему соответствует прибавлению 1 в n-ичной системе счисления. 2.1.2. В предложенном алгоритме используется сравнение двух массивов x <> last. Устранить его, добавив булевскую переменную l и включив в инвариант соотношение l <=> последовательность x - последняя. 2.1.3. Напечатать все подмножества множества {1...k}. Решение. Подмножества находятся во взаимно однозначном со- ответствии с последовательностями нулей и единиц длины k. 2.1.4. Напечатать все последовательности из k положительных целых чисел, у которых i-ый член не превосходит i. 2.2. Перестановки. 2.2.1. Напечатать все перестановки чисел 1..n (то есть пос- ледовательности длины n, в которые каждое из чисел 1..n входит по одному разу). Решение. Перестановки будем хранить в массиве x[1],..., x[n] и печатать в лексикографическом порядке. (Первой при этом будет перестановка <1 2...n>, последней - .) Для сос- тавления алгоритма перехода к следующей перестановке зададимся вопросом: в каком случае k-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следу- ющих членов (членов с номерами больше k). Мы должны найти на- ибольшее k, при котором это так, т. е. такое k, что x[k] < x[k+1] > ... > x[n]. После этого x[k] нужно увеличить мини- мальным возможным способом, т. е. найти среди x[k+1], ..., x[n] наименьшее число, большее его. Поменяв x[k] с ним, остается рас- положить числа с номерами k+1, ..., n так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке. Алгоритм перехода к следующей перестановке. { <> .} k:=n-1; {последовательность справа от k убывающая: x[k+1] >...> x[n]} while x[k] > x[k+1] do begin | k:=k-1; end; {x[k] < x[k+1] > ... > x[n]} t:=k+1; {t <=n, x[k+1] > ... > x[t] > x[k]} while (t < n) and (x[t+1] > x[k]) do begin | t:=t+1; end; {x[k+1] > ... > x[t] > x[k] > x[t+1] > ... > x[n]} ... обменять x[k] и x[t] {x[k+1] > ... > x[n]} ... переставить участок x[k+1] ... x[n] в обратном порядке Замечание. Программа имеет знакомый дефект: если t = n, то x[t+1] не определено. 2.2.2. Модифицировать алгоритм перехода к следующей перес- тановке так, чтобы он сам проверял, не является ли данная перес- тановка последней. 2.3. Подмножества. 2.3.1. Перечислить все k-элементные подмножества множества {1..n}. Решение. Будем представлять каждое подмножество последова- тельностью x[1]..x[n] нулей и единиц длины n, в которой ровно k единиц. (Другой способ представления разберем позже.) Такие пос- ледовательности упорядочим лексикографически (см. выше). Очевид- ный способ решения задачи - перебирать все последовательности как раньше, а затем отбирать среди них те, у которых k единиц - мы отбросим, считая его неэкономичным (число последовательностей с k единицами может быть много меньше числа всех последова- тельностей). Будем искать такой алгоритм, чтобы получение оче- редной последовательности требовало порядка n действий. В каком случае s-ый член последовательности можно увели- чить, не меняя предыдущие? Если x[s] меняется с 0 на 1, то для сохранения общего числа единиц нужно справа от х[s] заменить 1 на 0. Таким образом, х[s] - первый справа нуль, за которым стоят единицы. Легко видеть, что х[s+1] = 1 (иначе х[s] не первый). Таким образом надо искать наибольшее s, для которого х[s]=0, x[s+1]=1; ______________________ x |________|0|1...1|0...0| s За х[s+1] могут идти еще несколько единиц, а после них несколько нулей. Заменив х[s] на 1, надо выбрать идущие за ним члены так, чтобы последовательность была бы минимальна с точки зрения наше- го порядка, т. е. чтобы сначала шли нули, а потом единицы. Вот что получается: первая последовательность 0...01...1 (n-k нулей, k единиц) последняя последовательность 1...10...0 (k единиц, n-k нулей) алгоритм перехода к следующей за х[1]...x[n] последовательнос- ти (предполагаем, что она есть): s := n - 1; while not ((x[s]=0) and (x[s+1]=1)) do begin | s := s - 1; end; {s - член, подлежащий изменению с 0 на 1} num:=0; for k := s to n do begin | num := num + x[k]; end; {num - число единиц на участке x[s]...x[n], число нулей равно (длина - число единиц), т. е. (n-s+1) - num} x[s]:=1; for k := s+1 to n-num+1 do begin | x[k] := 0; end; for k := n-num+2 to n do begin | x[k]:=1; end; Другой способ представления подмножеств - это перечисление их элементов. Чтобы каждое подмножество имело ровно одно представление, договоримся перечислять элементы в возрастающем порядке. Приходим к такой задаче. 2.3.2. Перечислить все возрастающие последовательности дли- ны k из чисел 1..n в лексикографическом порядке. (Пример: при n=5, k=2 получаем 12 13 14 15 23 24 25 34 35 45.) Решение. Минимальной будет последовательность 1, 2, ..., k; максимальной - (n-k+1),..., (n-1), n. В каком случае s-ый член последовательности можно увеличить? Ответ: если он меньше n-k+s. После увеличения s-го элемента все следующие должны возрастать с шагом 1. Получаем такой алгоритм перехода к следующему: s:=n; while not (x[s] < n-k+s) do begin | s:=s-1; end; {s - элемент, подлежащий увеличению}; x[s] := x[s]+1; for i := s+1 to n do begin | x[i] := x[i-1]+1; end; 2.3.3. Пусть мы решили представлять k-элементные подмно- жества множества {1..n} убывающими последовательностями длины k, упорядоченными по-прежнему лексикографически. (Пример : 21 31 32 41 42 43 51 52 53 54.) Как выглядит тогда алгоритм перехода к следующей? Ответ. Ищем наибольшее s, для которого х[s]-x[s+1]>1. (Если такого s нет, полагаем s = 0.) Увеличив x [s+1] на 1, кладем ос- тальные минимально возможными (x[t] = k+1-t для t>s). 2.3.4. Решить две предыдущие задачи, заменив лексикографи- ческий порядок на обратный (раньше идут те, которые больше в лексикографическом порядке). 2.3.5. Перечислить все вложения (функции, переводящие раз- ные элементы в разные) множества {1..k} в {1..n} (предполагает- ся, что k <= n). Порождение очередного элемента должно требовать порядка k действий. Указание. Эта задача может быть сведена к перечислению подмножеств и перестановок элементов каждого подмножества. 2.4. Разбиения. 2.4.1. Перечислить все разбиения целого положительного чис- ла n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). (Пример: n=4, раз- биения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.) Решение. Договоримся, что (1) в разбиениях слагаемые идут в невозрастающем порядке, (2) сами разбиения мы перечисляем в лек- сикографическом порядке. Разбиение храним в начале массива x[1]...x[n], при этом количество входящих в него чисел обозначим k. В начале x[1]=...=x[n]=1, k=n, в конце x[1]=n, k=1. В каком случае x[s] можно увеличить не меняя предыдущих? Во-первых, должно быть x[s-1] > x[s] или s = 1. Во-вторых, s должно быть не последним элементом (увеличение s надо компенси- ровать уменьшением следующих). Увеличив s, все следующие элемен- ты надо взять минимально возможными. s := k - 1; while not ((s=1) or (x[s-1] > x[s])) do begin | s := s-1; end; {s - подлежащее увеличению слагаемое} x [s] := x[s] + 1; sum := 0; for i := s+1 to k do begin | sum := sum + x[i]; end; {sum - сумма членов, стоявших после x[s]} for i := 1 to sum-1 do begin | x [s+i] := 1; end; k := s+sum-1; 2.4.2. Представляя по-прежнему разбиения как невозрастающие последовательности, перечислить их в порядке, обратном лексиког- рафическому (для n=4, например, должно получиться 4, 3+1, 2+2, 2+1+1, 1+1+1+1). Указание. Уменьшать можно первый справа член, не равный 1; найдя его, уменьшим на 1, а следующие возьмем максимально воз- можными (равными ему, пока хватает суммы, а последний - сколько останется). 2.4.3. Представляя разбиения как неубывающие последова- тельности, перечислить их в лексикографическом порядке. Пример для n=4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4; Указание. Последний член увеличить нельзя, а предпоследний - можно; если после увеличения на 1 предпоследнего члена за счет последнего нарушится возрастание, то из двух членов надо сделать один, если нет, то последний член надо разбить на слагаемые, равные предыдущему, и остаток, не меньший его. 2.4.4. Представляя разбиения как неубывающие последова- тельности, перечислить их в порядке, обратном лексикографическо- му. Пример для n=4: 4, 2+2, 1+3, 1+1+2, 1+1+1+1. Указание. Чтобы элемент x[s] можно было уменьшить, необхо- димо, чтобы s = 1 или x[s-1] < x[s]. Если x[s] не последний, то этого и достаточно. Если он последний, то нужно, чтобы x[s-1] <= (целая часть (x[s]/2)) или s=1. 2.5. Коды Грея и аналогичные задачи. Иногда бывает полезно перечислять объекты в таком порядке, чтобы каждый последующий минимально отличался от предыдущего. Рассмотрим несколько задач такого рода. 2.5.1. Перечислить все последовательности длины n из чисел 1..k в таком порядке, чтобы каждая следующая отличалась от пре- дыдущей в единственной цифре, причем не более, чем на 1. Решение. Рассмотрим прямоугольную доску ширины n и высоты k. На каждой вертикали будет стоять шашка. Таким образом, поло- жения шашек соответствуют последовательностям из чисел 1..k дли- ны n (s-ый член последовательности соответствует высоте шашки на s-ой горизонтали). На каждой шашке нарисуем стрелочку, которая может быть направлена вверх или вниз. Вначале все шашки поставим на нижнюю горизонталь стрелочкой вверх. Далее двигаем шашки по такому правилу: найдя самую правую шашку, которую можно подви- нуть в направлении (нарисованной на ней) стрелки, двигаем ее на одну клетку в этом направлении, а все стоящие правее ее шашки (они уперлись в край) разворачиваем кругом. Ясно, что на каждом шаге только одна шашка сдвигается, т.е. один член последовательности меняется на 1. Докажем индукцией по n, что проходятся все последовательности из чисел 1...k. Случай n = 1 очевиден. Пусть n > 1. Все ходы поделим на те, где двига- ется последняя шашка, и те, где двигается не последняя. Во вто- ром случае последняя шашка стоит у стены, и мы ее поворачиваем, так что за каждым ходом второго типа следует k-1 ходов первого типа, за время которых последняя шашка побывает во всех клетках. Если мы теперь забудем о последней шашке, то движения первых n-1 по предположению индукции пробегают все последовательности длины n-1 по одному разу; движения же последней шашки из каждой после- довательности длины n-1 делают k последовательностей длины n. В программе, помимо последовательности x[1]...x[n], будем хранить массив d[1]...d[n] из чисел +1 и -1 (+1 соответствует стрелке вверх, -1 -стрелке вниз). Начальное состояние: x[1] =...= x[n] = 1; d[1] =...= d[n] = 1. Приведем алгоритм перехода к следующей последовательности (од- новременно выясняется, возможен ли он - ответ становится значе- нием булевской переменной p). {если можно, сделать шаг и положить p := true, если нет, положить p := false } i := n; while (i > 1) and | (((d[i]=1) and (x[i]=n)) or ((d[i]=-1) and (x[i]=1))) | do begin | i:=i-1; end; if (d[i]=1 and x[i]=n) or (d[i]=-1 and x[i]=1) | then begin {i=1} | p:=false; end else begin | p:=true; | x[i] := x[i] + d[i]; | for j := i+1 to n do begin | | d[j] := - d[j]; | end; end; Замечание. Для последовательностей нулей и единиц возможно другое решение, использующее двоичную систему. (Именно оно свя- зывается обычно с названием "коды Грея".) Запишем подряд все числа от 0 до (2 в степени n) - 1 в дво- ичной системе. Например, для n = 3 напишем: 000 001 010 011 100 101 110 111 Затем каждое из чисел подвергнем преобразованию, заменив каждую цифру, кроме первой, на ее сумму с предыдущей цифрой (по модулю 2). Иными словами, число a[1], a[2],...,a[n] преобразуем в a[1], a[1] + a[2], a[2] + a[3],...,a[n-1] + a[n] (сумма по модулю 2). Для n=3 получим: 000 001 011 010 110 111 101 100. Легко проверить, что описанное преобразование чисел обрати- мо (и тем самым дает все последовательности по одному разу). Кроме того, двоичные записи соседних чисел отличаются заменой конца 011...1 на конец 100...0, что - после преобразования - приводит к изменению единственной цифры. Применение кода Грея. Пусть есть вращающаяся ось, и мы хо- тим поставить датчик угла поворота этой оси. Насадим на ось ба- рабан, выкрасим половину барабана в черный цвет, половину в бе- лый и установим фотоэлемент. На его выходе будет в половине слу- чаев 0, а в половине 1 (т. е. мы измеряем угол "с точностью до 180"). Развертка барабана: 0 1 -> |_|_|_|_|*|*|*|*| <- (склеить бока). Сделав рядом другую дорожку из двух черных и белых частей и поставив второй фотоэлемент, получаем возможность измерить угол с точностью до 90 градусов: 0 0 1 1 0 1 0 1 _ _ _ _ |_|_|_|_|*|*|*|*| |_|_|*|*|_|_|*|*| Сделав третью, 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 _ _ _ _ |_|_|_|_|*|*|*|*| |_|_|*|*|_|_|*|*| |_|*|_|*|_|*|_|*| мы измерим угол с точностью до 45 градусов и т.д. Эта идея име- ет, однако, недостаток: в момент пересечения границ сразу нес- колько фотоэлементов меняют сигнал, и если эти изменения про- изойдут не одновременно, на какое-то время показания фотоэлемен- тов будут бессмысленными. Коды Грея позволяют избежать этой опасности. Сделаем так, чтобы на каждом шаге менялось показание лишь одного фотоэлемента (в том числе и на последнем, после це- лого оборота). 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 _ _ _ _ |_|_|_|_|*|*|*|*| |_|_|*|*|*|*|_|_| |_|*|*|_|_|*|*|_| Написанная нами формула позволяет легко преобразовать дан- ные от фотоэлементов в двоичный код угла поворота. 2.5.2. Напечатать все перестановки чисел 1..n так, чтобы каждая следующая получалась из предыдущей перестановкой (транспозицией) двух соседних чисел. Например, при n = 3 допус- тим такой порядок: 3.2 1 -> 2 3.1 -> 2.1 3 -> 1 2.3 -> 1.3 2 -> 3 1 2 (между переставляемыми числами вставлены точки). Решение. Наряду с множеством перестановок рассмотрим мно- жество последовательностей y[1]..y[n] целых неотрицательных чи- сел, у которых y[1] <= 0,..., y[n] <= n-1. В нем столько же эле- ментов, сколько в множестве всех перестановок, и мы сейчас уста- новим между ними взаимно однозначное соответствие. Именно, каж- дой перестановке поставим в соответствие последовательность y[1]..y[n], где y[i] - количество чисел, меньших i и стоящих ле- вее i в этой перестановке. Взаимная однозначность вытекает из такого замечания. Перестановка чисел 1...n получается из перес- тановки чисел 1..n-1 добавлением числа n, которое можно вставить на любое из n мест. При этом к сопоставляемой с ней последова- тельности добавляется еще один член, принимающий значения от 0 до n-1, а предыдущие члены не меняются. При этом оказывается, что изменение на единицу одного из членов последовательности y соответствует перестановке двух соседних чисел, если все следу- ющие числа последовательности y принимают максимально или мини- мально возможные для них значения. Именно, увеличение y[i] на 1 соответствует перестановке числа i с его правым соседом, а уменьшение - с левым. Теперь вспомним решение задачи о перечислении всех последо- вательностей, на каждом шаге которого один член меняется на еди- ницу. Заменив прямоугольную доску доской в форме лестницы (высо- та i-ой вертикали равна i) и двигая шашки по тем же правилам, мы перечислим все последовательности y, причем i-ый член будет ме- няться, лишь если все следующие шашки стоят у края. Надо еще уметь параллельно с изменением y корректировать перестановку. Очевидный способ требует отыскания в ней числа i; это можно об- легчить, если помимо самой перестановки хранить функцию i |---> позиция числа i в перестановке (обратное к перестановке отобра- жение), и соответствующим образом ее корректировать. Вот какая получается программа: program test; | const n=...; | var | x: array [1..n] of 1..n; {перестановка} | inv_x: array [1..n] of 1..n; {обратная перестановка} | y: array [1..n] of integer; {Y[i] < i} | d: array [1..n] of -1..1; {направления} | b: boolean; | | procedure print_x; | | var i: integer; | begin | | for i:=1 to n do begin | | | write (x[i], ' '); | | end; | | writeln; | end; | | procedure set_first;{первая перестановка: y[i]=0 при всех i} | | var i : integer; | begin | | for i := 1 to n do begin | | | x[i] := n + 1 - i; | | | inv_x[i] := n + 1 - i; | | | y[i]:=0; | | | d[i]:=1; | | end; | end; | | procedure move (var done : boolean); | | var i, j, pos1, pos2, val1, val2, tmp : integer; | begin | | i := n; | | while (i > 1) and (((d[i]=1) and (y[i]=i-1)) or | | | ((y[i]=-1) and (y[i]=0))) do begin | | | i := i-1; | | end; | | done := (i>1); | | {упрощение связано с тем, что первый член нельзя менять} | | if done then begin | | | y[i] := y[i]+d[i]; | | | for j := i+1 to n do begin | | | | d[j] := -d[j]; | | | end; | | | pos1 := inv_x[i]; | | | val1 := i; | | | pos2 := pos1 + d[i]; | | | val2 := x[pos2]; | | | {pos1, pos2 - номера переставляемых элементов; | | | val1, val2 - их значения} | | | tmp := x[pos1]; | | | x[pos1] := x[pos2]; | | | x[pos2] := tmp; | | | tmp := inv_x[val1]; | | | inv_x[val1] := inv_x[val2]; | | | inv_x[val2] := tmp; | | end; | end; | begin | set_first; | print_x; | b := true; | {напечатаны все перестановки до текущей включительно; | если b ложно, то текущая - последняя} | while b do begin | | move (b); | | if b then print_x; | end; end. 2.6. Несколько замечаний. Посмотрим еще раз на использованные нами приемы. Вначале удавалось решить задачу по такой схеме: определяем порядок на подлежащих перечислению объектах и явно описываем процедуру пе- рехода от данного объекта к следующему (в смысле этого порядка). В задаче о кодах Грея потребовалось хранить, помимо текущего объекта, и некоторую дополнительную информацию (направления стрелок). Наконец, в задаче о перечислении перестановок (на каж- дом шаге допустима одна транспозиция) мы применили такой прием: установили взаимно однозначное соответствие между перечисляемым множеством и другим, более просто устроенным. Таких соответствий в комбинаторике известно много. Мы приведем несколько задач, связанных с так называемыми "числами Каталана". 2.6.1. Перечислить все последовательности длины 2n, состав- ленные из n единиц и n минус единиц, у которых сумма любого на- чального отрезка положительна (т.е. число минус единиц в нем не превосходит числа единиц). Решение. Изображая единицу вектором (1,1), а минус единицу вектором (1,-1), можно сказать, что мы ищем пути из точки (0,0) в точку (n,0), не опускающиеся ниже оси абсцисс. Будем перечислять последовательности в лексикографическом порядке, считая, что -1 предшествует 1. Первой последова- тельностью будет "пила" 1, -1, 1, -1, ... а последней - "горка" 1, 1, 1, ..., 1, -1, -1, ..., -1. Как перейти от последовательности к следующей? До некоторо- го места они должны совпадать, а затем надо заменить -1 на 1. Место замены должно быть расположено как можно правее. Но заме- нять -1 на 1 можно только в том случае, если справа от нее есть единица (которую можно заменить на -1). Заменив -1 на 1, мы при- ходим к такой задаче: фиксирован начальный кусок последова- тельности, надо найти минимальное продолжение. Ее решение: надо приписывать -1, если это не нарушит условия неотрицательности, а иначе приписывать 1. Получаем такую программу: ... type array2n = array [1..2n] of integer; ... procedure get_next (var a: array2n; var last: Boolean); | {в a помещается следующая последовательность, если} | {она есть (при этом last=false), иначе last:=true} | var k, i, sum: integer; begin | k:=2*n; | {инвариант: в a[k+1..2n] только минус единицы} | while a[k] = -1 do begin k:=k-1; end; | {k - максимальное среди тех, для которых a[k]=1} | while (k>0) and (a[k] = 1) do begin k:=k-1; end; | {a[k] - самая правая -1, за которой есть 1; | если таких нет, то k=0} | if k = 0 then begin | | last := true; | end else begin | | last := false; | | i:=0; sum:=0; | | {sum = a[1]+...+a[i]} | | while i<> k do begin | | | i:=i+1; sum:= sum+a[i]; | | end; | | {sum = a[1]+...+a[k]} | | a[k]:= 1; sum:= sum+2; | | {вплоть до a[k] все изменено, sum=a[1]+...+a[k]} | | while k <> 2*n do begin | | | k:=k+1; | | | if sum > 0 then begin | | | | a[k]:=-1 | | | end else begin | | | | a[k]:=1; | | | end; | | | sum:= sum+a[k]; | | end; | | {k=n, sum=a[1]+...a[2n]=0} | end; end; 2.6.2. Перечислить все расстановки скобок в произведении n сомножителей. Порядок сомножителей не меняется, скобки полностью определяют порядок действий. (Например, для n = 4 есть 5 расста- новок ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)).) Указание. Каждому порядку действий соответствует последова- тельность команд стекового калькулятора. 2.6.3. На окружности задано 2n точек, пронумерованных от 1 до 2n. Перечислить все способы провести n непересекающихся хорд с вершинами в этих точках. 2.6.4. Перечислить все способы разрезать n-угольник на тре- угольники, проведя n - 2 его диагонали. Еще один класс задач на перечисление всех элементов задан- ного множества мы рассмотрим ниже, обсуждая метод поиска с возвратами (backtracking). 2.7. Подсчет количеств. Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: C(n,k) - число всех k-элементных подмножеств n-элементного множества - можно найти, заполняя таблицу значений функции С по формулам: C (n,0) = C (n,n) = 1 (n >= 1) C (n,k) = C (n-1,k-1) + C (n-1,k) (n > 1, 0 < k < n); или по формуле n!/((k!)*(n-k)!). (Первый способ эффективнее, ес- ли надо вычислить много значений С(n,k).) Приведем другие примеры. 2.7.1 (Число разбиений). (Предлагалась на всесоюзной олим- пиаде по программированию 1988 года.) Пусть P(n) - число разби- ений целого положительного n на целые положительные слагаемые (без учета порядка, 1+2 и 2+1 - одно и то же разбиение). При n=0 положим P(n) = 1 (единственное разбиение не содержит слагаемых). Построить алгоритм вычисления P(n) для заданного n. Решение. Можно доказать (это нетривиально) такую формулу для P(n): P(n) = P(n-1)+P(n-2)-P(n-5)-P(n-7)+P(n-12)+P(n-15) +... (знаки у пар членов чередуются, вычитаемые в одной паре равны (3*q*q-q)/2 и (3*q*q+q)/2). Однако и без ее использования можно придумать способ вычис- ления P(n), который существенно эффективнее перебора и подсчета всех разбиений. Обозначим через R(n,k) (при n >= 0, k >= 0) число разбиений n на целые положительные слагаемые, не превосходящие k. (При этом R(0,k) считаем равным 1 для всех k >= 0.) Очевидно, P(n) = R(n,n). Все разбиения n на слагаемые, не превосходящие k, ра- зобьем на группы в зависимости от максимального слагаемого (обозначим его i). Число R(n,k) равно сумме (по всем i от 1 до k) количеств разбиений со слагаемыми не больше k и максимальным слагаемым, равным i. А разбиения n на слагаемые не более k с первым слагаемым, равным i, по существу представляют собой раз- биения n - i на слагаемые, не превосходящие i (при i <= k). Так что R(n,k) = сумма по i от 1 до k чисел R(n-i,i) при k <= n; R(n,k) = R(n,n) при k >= n, что позволяет заполнять таблицу значений функции R. 2.7.2 (Счастливые билеты). (Задача предлагалась на Всесоюз- ной олимпиаде по программированию 1989 года). Последовательность из 2n цифр (каждая цифра от 0 до 9) называется счастливым биле- том, если сумма первых n цифр равна сумме последних n цифр. Най- ти число счастливых последовательностей данной длины. Решение. (Сообщено одним из участников олимпиады; к сожале- нию, не могу указать фамилию, так как работы проверялись зашиф- рованными.) Рассмотрим более общую задачу: найти число последо- вательностей, где разница между суммой первых n цифр и суммой последних n цифр равна k (k = -9n,..., 9n). Пусть T(n, k) - чис- ло таких последовательностей. Разобьем множество таких последовательностей на классы в зависимости от разницы между первой и последней цифрами. Если эта разница равна t, то разница между суммами групп из оставших- ся n-1 цифр равна k-t. Учитывая, что пар цифр с разностью t бы- вает 10 - (модуль t), получаем формулу T(n,k) = сумма по t от -9 до 9 чисел (10-|t|) * T(n-1, k-t). (Некоторые слагаемые могут отсутствовать, так как k-t может быть слишком велико.)