Жанр: Учеба
Программирование в теоремах и задачах
...нные
от фотоэлементов в двоичный код угла поворота.
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 может быть
слишком велико.)
Глава 3. Обход дерева. Перебор с возвратами.
3.1. Ферзи, не бьющие друг друга: обход дерева позиций
В предыдущей главе мы рассматривали несколько задач одного
и того же типа: "перечислить все элементы некоторого множества
A". Схема решения была такова: на множестве A вводился порядок и
описывалась процедура перехода от произвольного элемента множества
A к следующему за ним (в этом порядке). Такую схему не
всегда удается реализовать непосредственно, и в этой главе мы
рассмотрим другой полезный прием перечисления всех элементов некоторого
множества. Его называют "поиск с возвратами", "метод
ветвей и границ", "backtracking". На наш взгляд наиболее точное
название этого метода - обход дерева.
3.1.1. Перечислить все способы расстановки n ферзей на шахматной
доске n на n, при которых они не бьют друг друга.
Решение. Очевидно, на каждой из n горизонталей должно стоять
по ферзю. Будем называть k-позицией (для k = 0, 1,...,n)
произвольную расстановку k ферзей на k нижних горизонталях (ферзи
могут бить друг друга). Нарисуем "дерево позиций": его корнем
будет единственная 0-позиция, а из каждой k-позиции выходит n
стрелок вверх в (k+1)-позиции. Эти n позиций отличаются положением
ферзя на (k+1)-ой горизонтали. Будем считать, что расположение
их на рисунке соответствует положению этого ферзя: левее
та позиция, в которой ферзь расположен левее.
Дерево позиций для
n = 2
Среди позиций этого дерева нам надо отобрать те n-позиции, в которых
ферзи не бьют друг друга. Программа будет "обходить дерево"
и искать их. Чтобы не делать лишней работы, заметим вот что:
если в какой-то k-позиции ферзи бьют друг друга, то ставить
дальнейших ферзей смысла нет. Поэтому, обнаружив это, мы будем
прекращать построение дерева в этом направлении.
Точнее, назовем k-позицию допустимой, если после удаления
верхнего ферзя оставшиеся не бьют друг друга. Наша программа будет
рассматривать только допустимые позиции.
Дерево допустимых
позиций для n = 3
Разобьем задачу на две части: (1) обход произвольного дерева
и (2) реализацию дерева допустимых позиций.
Сформулируем задачу обхода произвольного дерева. Будем считать,
что у нас имеется Робот, который в каждый момент находится
в одной из вершин дерева (вершины изображены на рисунке кружочками).
Он умеет выполнять команды:
вверх_налево (идти по самой левой
из выходящих вверх стрелок)
вправо (перейти в соседнюю справа
вершину)
вниз (спуститься вниз на один уро-
вень)
вверх_налево
вправо
вниз
и проверки, соответствующие возможности выполнить каждую из команд,
называемые "есть_сверху", "есть_справа", "есть_снизу"
(последняя истинна всюду, кроме корня). Обратите внимание, что
команда "вправо" позволяет перейти лишь к "родному брату", но не
к "двоюродному".
Так команда "вправо"
НЕ действует!
Будем считать, что у Робота есть команда "обработать" и что
его задача - обработать все листья (вершины, из которых нет
стрелок вверх, то есть где условие "есть_сверху" ложно). Для нашей
шахматной задачи команде обработать будет соответствовать
проверка и печать позиции ферзей.
Доказательство правильности приводимой далее программы использует
такие определения. Пусть фиксировано положение Робота в
одной из вершин дерева. Тогда все листья дерева разбиваются на
три категории: над Роботом, левее Робота и правее Робота. (Путь
из корня в лист может проходить через вершину с Роботом, сворачивать
влево, не доходя до нее и сворачивать вправо, не доходя
до нее.) Через (ОЛ) обозначим условие "обработаны все листья левее
Робота", а через (ОЛН) - условие "обработаны все листья левее
и над Роботом".
Нам понадобится такая процедура:
procedure вверх_до_упора_и_обработать
| {дано: (ОЛ), надо: (ОЛН)}
begin
| {инвариант: ОЛ}
| while есть_сверху do begin
| | вверх_налево
| end
| {ОЛ, Робот в листе}
| обработать;
| {ОЛН}
end;
Основной алгоритм:
дано: Робот в корне, листья не обработаны
надо: Робот в корне, листья обработаны
{ОЛ}
вверх_до_упора_и_обработать
{инвариант: ОЛН}
while есть_снизу do begin
| if есть_справа then begin {ОЛН, есть справа}
| | вправо;
| | {ОЛ}
| | вверх_до_упора_и_обработать;
| end else begin
| | {ОЛН, не есть_справа, есть_снизу}
| | вниз;
| end;
end;
{ОЛН, Робот в корне =" все листья обработаны}
Осталось воспользоваться следующими свойствами команд Робота
(сверху записаны условия, в которых выполняется команда, снизу -
утверждения о результате ее выполнения):
(1) {ОЛ, не есть_сверху} (2) {ОЛ}
обработать вверх_налево
{ОЛН} {ОЛ}
(3) {есть_справа, ОЛН} (4) {не есть_справа, ОЛН}
вправо вниз
{ОЛ} {ОЛН}
3.1.2. Доказать, что приведенная программа завершает работу
(на любом конечном дереве).
Решение. Процедура вверх_налево завершает работу (высота
Робота не может увеличиваться бесконечно). Если программа работает
бесконечно, то, поскольку листья не обрабатываются повторно,
начиная с некоторого момента ни один лист не обрабатывается.
А это возможно, только если Робот все время спускается вниз.
Противоречие. (Об оценке числа действий см. далее.)
3.1.3. Доказать правильность следующей программы обхода дерева:
var state: (WL, WLU);
state := WL;
while есть_снизу or (state "" WLU) do begin
| if (state = WL) and есть_сверху then begin
| | вверх;
| end else if (state = WL) and not есть_сверху then begin
| | обработать; state := WLU;
| end else if (state = WLU) and есть_справа then begin
| | вправо; state := WL;
| end else begin {state = WLU, not есть_справа, есть_снизу}
| | вниз;
| end;
end;
Решение. Инвариант цикла:
state = WL =" ОЛ
state = WLU =" ОЛН
Доказательство завершения работы: переход из состояния ОЛ в ОЛН
возможен только при обработке вершины, поэтому если программа
работает бесконечно, то с некоторого момента значение state не
меняется, что невозможно.
3.1.4. Решить задачу об обходе дерева, если мы хотим, чтобы
обрабатывались все вершины (не только листья).
Решение. Пусть x - некоторая вершина. Тогда любая вершина y
относится к одной из четырех категорий. Рассмотрим путь из корня
в y. Он может:
(а) быть частью пути из корня в x (y ниже x);
(б) свернуть налево с пути в x (y левее x);
(в) пройти через x (y над x);
(г) свернуть направо с пути в x (y правее x);
В частности, сама вершина x относится к категории (в). Условия
теперь будут такими:
(ОНЛ) обработаны все вершины ниже и левее;
(ОНЛН) обработаны все вершины ниже, левее и над.
Вот как будет выглядеть программа:
procedure вверх_до_упора_и_обработать
| {дано: (ОНЛ), надо: (ОНЛН)}
begin
| {инвариант: ОНЛ}
| while есть_сверху do begin
| | обработать
| | вверх_налево
| end
| {ОНЛ, Робот в листе}
| обработать;
| {ОНЛН}
end;
Основной алгоритм:
дано: Робот в корне, ничего не обработано
надо: Робот в корне, все вершины обработаны
{ОНЛ}
вверх_до_упора_и_обработать
{инвариант: ОНЛН}
while есть_снизу do begin
| if есть_справа then begin {ОНЛН, есть справа}
| | вправо;
| | {ОНЛ}
| | вверх_до_упора_и_обработать;
| end else begin
| | {ОЛН, не есть_справа, есть_снизу}
| | вниз;
| end;
end;
{ОНЛН, Робот в корне =" все вершины обработаны}
3.1.5. Приведенная только что программа обрабатывает вершину
до того, как обработан любой из ее потомков. Как изменить ее,
чтобы каждая вершина, не являющаяся листом, обрабатывалась дважды:
один раз до, а другой раз после всех своих потомков? (Листья
по-прежнему обрабатываются по разу.)
Решение. Под "обработано ниже и левее" будем понимать "ниже
обработано по разу, слева обработано полностью (листья по разу,
останые по два)". Под "обработано ниже, левее и над" будем понимать
"ниже обработано по разу, левее и над - полностью".
Программа будет такой:
procedure вверх_до_упора_и_обработать
| {дано: (ОНЛ), надо: (ОНЛН)}
begin
| {инвариант: ОНЛ}
| while есть_сверху do begin
| | обработать
| | вверх_налево
| end
| {ОНЛ, Робот в листе}
| обработать;
| {ОНЛН}
end;
Основной алгоритм:
дано: Робот в корне, ничего не обработано
надо: Робот в корне, все вершины обработаны
{ОНЛ}
вверх_до_упора_и_обработать
{инвариант: ОНЛН}
while есть_снизу do begin
| if есть_справа then begin {ОНЛН, есть справа}
| | вправо;
| | {ОНЛ}
| | вверх_до_упора_и_обработать;
| end else begin
| | {ОЛН, не есть_справа, есть_снизу}
| | вниз;
| | обработать;
| end;
end;
{ОНЛН, Робот в корне =" все вершины обработаны полностью}
3.1.6. Доказать, что число операций в этой программе по порядку
равно числу вершин дерева. (Как и в других программах, которые
отличаются от этой лишь пропуском некоторых команд "обработать".)
Указание. Примерно каждое второе действие при исполнении
этой программы - обработка вершины, а каждая вершина обрабатывается
максимум дважды.
Теперь реализуем операции с деревом позиций. Позицию будем
представлять с помощью переменной k: 0..n (число ферзей) и массива
c: array [1..n] of 1..n (c [i] - координаты ферзя на i-ой
горизонтали; при i " k значение c [i] роли не играет). Предполагается,
что все позиции допустимы (если убрать верхнего ферзя,
остальные не бьют друг друга).
program queens;
| const n = ...;
| var
| k: 0..n;
| c: array [1..n] of 1..n;
|
| procedure begin_work; {начать работу}
| begin
| | k := 0;
| end;
|
| function danger: boolean; {верхний ферзь под боем}
| | var b: boolean; i: integer;
| begin
| | if k "= 1 then begin
| | | danger := false;
| | end else begin
| | | b := false; i := 1;
| | | {b "=" верхний ферзь под боем ферзей с номерами " i}
| | | while i "" k do begin
| | | | b := b or (c[i]=c[k]) {вертикаль}
| | | | or (abs(c[[i]-c[k]))=abs(i-k)); {диагональ}
| | | | i := i+ 1;
| | | end;
| | | danger := b;
| | end;
| end;
|
| function is_up: boolean {есть_сверху}
| begin
| | is_up := (k " n) and not danger;
| end;
|
| function is_right: boolean {есть_справа}
| begin
| | is_right := (k " 0) and (c[k] " n);
| end;
| {возможна ошибка: при k=0 не определено c[k]}
|
| function is_down: boolean {есть_снизу}
| begin
| | is_up := (k " 0);
| end;
|
| procedure up; {вверх_налево}
| begin {k " n}
| | k := k + 1;
| | c [k] := 1;
| end;
|
| procedure right; {вправо}
| begin {k " 0, c[k] " n}
| | c [k] := c [k] + 1;
| end;
|
| procedure down; {вниз}
| begin {k " 0}
| | k := k - 1;
| end;
|
| procedure work; {обработать}
| | var i: integer;
| begin
| | if (k = n) and not danger then begin
| | | for i := 1 to n do begin
| | | | write ('"', i, ',' , c[i], '" ');
| | | end;
| | | writeln;
| | end;
| end;
|
| procedure UW; {вверх_до_упора_и_обработать}
| begin
| | while is_up do begin
| | | up;
| | end
| | work;
| end;
|
begin
| begin_work;
| UW;
| while is_down do begin
| | if is_right then begin
| | | right;
| | | UW;
| | end else begin
| | | down;
| | end;
| end;
end.
3.1.7. Приведенная программа тратит довольно много времени
на выполнение проверки есть_сверху (проверка, находится ли
верхний ферзь под боем, требует числа действий порядка n). Изменить
реализацию операций с деревом позиций так, чтобы все три
проверки есть_сверху/справа/снизу и соответствующие команды требовали
бы количества действий, ограниченного не зависящей от n
константой.
Решение. Для каждой вертикали, каждой восходящей и каждой
нисходящей диагонали будем хранить булевское значение - сведения
о том, находится ли на этой линии ферзь (верхний ферзь не учитывается).
(Заметим, что в силу допустимости позиции на каждой из
линий может быть не более одного ферзя.).
3.2. Обход дерева в других задачах.
3.2.1. Использовать метод обхода дерева для решения следующей
задачи: дан массив из n целых положительных чисел
a[1]..a[n] и число s; требуется узнать, может ли число s быть
представлено как сумма некоторых из чисел массива a. (Каждое
число можно использовать не более чем по одному разу.)
Решение. Будем задавать k-позицию последовательностью из k
булевских значений, определяющих, входят ли в сумму числа
a[1]..a[k] или не входят. Позиция допустима, если ее сумма не
превосходит s.
Замечание. По сравнению с полным перебором всех (2 в степени
n) подмножеств тут есть некоторый выигрыш. Можно также предварительно
отсортировать массив a в убывающем порядке, а также
считать недопустимыми те позиции, в которых сумма отброшенных
членов больше, чем разность суммы всех членов и s. Последний
приём называют "методом ветвей и границ". Но принципиального
улучшения по сравнению с полным перебором тут не получается (эта
задача, как говорят, NP-полна, см. подробности в книге Ахо,
Хопкрофта и Ульмана "Построение и анализ вычислительных алгоритмов").
Традиционное название этой задачи - "задача о рюкзаке"
(рюкзак общей грузоподъемностью s нужно упаковать под завязку,
располагая предметами веса a[1]..a[n]). См. также в главе 7
(раздел о динамическом программировании) алгоритм её решения,
полиномиальный по n+s.
3.2.2. Перечислить все последовательности из n нулей, единиц
и двоек, в которых никакая группа цифр не повторяется два
раза подряд (нет куска вида XX).
3.2.3. Аналогичная задача для последовательностей нулей и
единиц, в которых никакая группа цифр не повторяется три раза
подряд (нет куска вида XXX).
К этой же категории относятся задачи типа "можно ли сложить
данную фигуру из пентамино" и им подобные. В них важно умелое
сокращение перебора (вовремя распознать, что имеющееся расположение
фигурок уже противоречит требованиям, и по этой ветви поиск
не продолжать).
4.1. Квадратичные алгоритмы.
4.1.1. Пусть a[1], ..., a[n] - целые числа. Требуется
построить массив b[1], ..., b[n], содержащий те же числа, для
которых b[1] "= ... "= b[n].
Замечание. Среди чисел a[1]...a[n] могут быть равные. Требуется,
чтобы каждое целое число входило в b[1]...b[n] столько
же раз, сколько и в a[1]...a[n].
Решение. Удобно считать, что числа a[1]..a[n] и b[1]..b[n]
представляют собой начальное и конечное значения массива x. Требование
"a и b содержат одни и те же числа" будет заведомо выполнено,
если в процессе работы мы ограничимся перестановками
элементов x.
k := 0;
{k наименьших элементов массива x установлены на свои места
...Закладка в соц.сетях
