Жанр: Учеба
Программирование в теоремах и задачах
... begin
| | k := k + 1;
| | u[k+1] := x[n1];
| end else begin {i " k, u[i] " x[n1] "= u[i+1] }
| | u[i+1] := x[n1];
| end;
end;
Фрагмент ... использует идею двоичного поиска; в инварианте
условно полагаем u[0] равным минус бесконечности, а u[k+1]
- плюс бесконечности; наша цель: u[i] " x[n1] "= u[i+1].
i:=0; j:=k+1;
{u[i] " x[n1] "= u[j], j " i}
while (j - i) "" 1 do begin
| s := i + (j-i) div 2; {i " s " j}
| if u[s] "= x[n1] then begin
| | j := s;
| end else begin {u[s] " x[n1]}
| | i := s;
| end;
end;
{u[i] " x[n1] "= u[j], j-i = 1}
Замечание. Более простое (но не минимальное) индуктивное
расширение получится, если для каждого i хранить максимальную
длину возрастающей подпоследовательности, оканчивающейся на
x[i]. Это расширение приводит к алгоритму с числом действий порядка
n*n.
1.3.5. Какие изменения нужно внести в решение предыдущей
задачи, если надо искать максимальную неубывающую последовательность?
Глава 2. Порождение комбинаторных объектов.
Здесь собраны задачи, в которых требуется получить один за
другим все элементы некоторого множества.
2.1. Размещения с повторениями.
2.1.1. Напечатать все последовательности длины k из чисел
1..n.
Решение. Будем печатать их в лексикографическом порядке
(последовательность a предшествует последовательности b, если
для некоторого s их начальные отрезки длины s равны, а (s+1)-ый
член последовательности a меньше). Первой будет последовательность
"1, 1, ..., 1", последней - последовательность "n, n,
..., n". Будем хранить последнюю напечатанную последовательность
в массиве 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", последней - "n...2 1".) Для составления
алгоритма перехода к следующей перестановке зададимся
вопросом: в каком случае k-ый член перестановки можно увеличить,
не меняя предыдущих? Ответ: если он меньше какого-либо из следующих
членов (членов с номерами больше k). Мы должны найти наибольшее
k, при котором это так, т. е. такое k, что x[k] "
x[k+1] " ... " x[n]. После этого x[k] нужно увеличить минимальным
возможным способом, т. е. найти среди x[k+1], ..., x[n]
наименьшее число, большее его. Поменяв x[k] с ним, остается расположить
числа с номерами k+1, ..., n так, чтобы перестановка
была наименьшей, то есть в возрастающем порядке. Это облегчается
тем, что они уже расположены в убывающем порядке.
Алгоритм перехода к следующей перестановке.
{"x[1],...,x[n-1], x[n]" "" "n,...,2, 1".}
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) счит
...Закладка в соц.сетях
