Четвертая задача. По разбиению (Now) получить его но- мер. Принцип прост. Брать текущее число из разбиения, начи- ная с первого, и смотреть на его «вклад» в количество номеров.
Например, разбиение «22211». Определяем, сколько номеров приходится на первую 2, затем на вторую и т. д.
Function GetNumByWh:LongInt;
Var
Begin
{*Формируем номер разбиения.*}
{*Номер строки в массиве
For i : = 1
Do Begin {*Просматриваем
For
To
Do
числа из разбиения определяет
число столбцов в массиве
{*Изменяем номер строки.*}
End;
58 2.
Комбинаторные алгоритмыEnd;Трассировка логики
(N=8, Now —
1 2
3 4
4 8
6 4
2 1
i
1 2
3 4
5
Р
0 1
0 1
0 1
0 0
SCновое2 3
4 4
4
jkновое6 4
2 1
0
Итак, номер определен, он равен 4.
2.2.5. Последовательности из нулей и единиц длины
Nбез двух единиц подряд
Первая задача. Подсчет числа таких последовательностей.
Приведем пример при
N=4. Таких последовательностей 8.
0000 0001 0010 0100 0101 1000 1001 1010
Как подсчитать количество таких последовательностей (обо- значим через
P(N))? Пусть есть последовательность длины
N. На первом месте в последовательностях записан ноль. Число таких последовательностей
P(N—1). Рассмотрим случай, когда на пер-вом месте записана единица. Тогда на втором месте обязате-льно должен быть записан 0. Число таких последовательно- P(N-2). Итак, получили формулу:
P(N)=P(N-1)+P(N-2), a это не что иное, как формула вычисления чисел Фибоначчи. Та- ким образом, число последовательностей длины
N, в которых нет двух идущих подряд 1, равно числу Фибоначчи. Огра- ничимся диапазоном чисел типа
LongInt (N=<44). Для вычисле- ния количества последовательностей при больших значениях
Nтребуется использовать «длинную» арифметику, в частности процедуры сложения и вывода длинных чисел. А при наших ограничениях можно ввести результаты в массив констант.
Of
2. Комбинаторные алгоритмы
59
1597, 2584, 4181, 6765, 10946, 17711, 28657,
46368, 75025, 121393, 196418, 317811, 514229,
832040, 1346269, 2178309, 3524578, 5702887,
9227465, 14930352, 24157817, 39088169,
63245986, 102334155, 165580141, 267914296,
433494437, 701408733, 1134903170, 1836311903);
И процедура вычисления количества последовательностей.
Function
(N: Integer) :
Begin
If
Then
Else
;
End;
Вторая задача. Генерация последовательностей. Рассмот- рим пример для
(номер последовательности, последовате- льность).
0 1
2 3
4 5
6 000000 000001 000010 000100 000101 001000 001001 7
8 9
10 11 12 13 001010 010000 010001 010010 010100 010101 100000 14 15 16 17 18 20 100001 100010 100100 100101 101000 101001 101010
Принцип перехода к следующей последовательности: начи- наем с конца последовательности, подпоследовательности типа
..0010... переходят в тип ...0100... и типа ..001010... в тип
010000.... Формализация этого принципа приведена в следую- щей процедуре. Для хранения последовательности использует- ся массив Now.
Procedure GetNext;
Var i: Integer;
Begin
i :
While
Or ( (i>l) And
=1) )
Do Begin
Now[i] :=0;Dec(i) ;
End;
End;
60
Комбинаторные алгоритмы
Третья задача. Необходимо по номеру получить последова- тельность. Зададим себе простой вопрос. Если значение L боль- ше, чем число последовательностей длины N—1, то что находится на первом месте (слева) в последовательности — 0
или 1? Ответ очевиден: 1. Вычтем из значения!- число последо- вательностей длины N—1 и продолжим сравнение с новым зна- чением L. В этом суть решения.
Пример N=6,
15 2
2 2
2 0
/
1 3
4 5
6
Р
13 8
5 3
2
Now
* * * * *
10****
100***
1000**
10001*
100010
Procedure
Longlnt);
Var i: Integer;
Begin
For
To N Do
If
(N-i) Then Begin
Else
End;
Четвертая задача. По последовательности необходимо по- лучить ее номер в соответствии с введенным отношением по- рядка. Если в последовательности на месте i находится 1, то в номере есть вклад от числа всех последовательностей длины
N-i. Итак, следует просмотреть последовательность и по значе- нию 1 подсчитать сумму количества последовательностей соот- ветствующих
Function
Longlnt;
Var i: Integer;
sc: Longlnt;
Begin
For i:=l To N Do If Now[i]=l Then
(sc,
(N-i));
:=s
End;
2. Комбинаторные алгоритмы 61 2.2.6. Подмножества
Проблема. Научиться работать с подмножествами iV-элемен- тного множества натуральных чисел от 1 до N такими, что каждое следующее подмножество отличалось бы от предыдуще- го только на один элемент.
традиционные четыре зада- чи: подсчет количества подмножеств; генерация подмножеств;
определение подмножества по номеру и определение номера по подмножеству.
Первая задача. Количество подмножеств множества из N
элементов равно 2N. Эта задача проста, если значение N не очень большое. Однако уже при N=15 количество подмножеств
32768, поэтому тип данных требуется использовать осторожно. Пусть N меньше или равно 100. При таких значе- ниях N необходимо использовать элементы «длинной» арифме- тики, а именно: умножение «длинного» числа на короткое (пя- тая задача 1-й главы, процедура Mul) и вывод «длинного»
числа (вторая задача 1-й главы, процедура SayTLong).
Процедура вычисления количества подмножеств множества из N элементов. Есть небольшой «нюанс». Возводить двойку в степень N — утомительное занятие, сократим его по возможно- сти.
Procedure
Var i: Integer;
Tmp: TLong;
Begin
i :=N; {
для
Основанием
системы счисления в нашей задаче является
10000, а два в степени 13 равно 8192.*}
в степени 0 равно
While i>0 Do Begin
If i>13 Then Begin
1
13, Tmp);
i:=i-13; End
что команда shl -
сдвиг влево, итак 1 сдвигается на 13
разрядов влево, т.е. мы умножаем на
А почему нельзя умножать на 2
14
?*}
Else Begin Mul (Res, 1 shl i, Tmp); i:=0; End;
End;
End;
Вторая задача. Подмножества iV-элементного множества натуральных чисел от 1 до N будем представлять двоичными последовательностями длины N —
62 2. Комбинаторные алгоритмы
(массив Now). Элемент равный единице, говорит о том,
что принадлежит подмножеству.
Число
0 1
2 3
4 5
6 7
8 9
10 11 12 13 14 15
Двоичное представление числа
(В)
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Двоичная последовательность
(Now)
0000 0001 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000
Подмножество
[]
[1]
[1,2]
[2]
[2,3]
[1,2,3]
[1,3]
[3]
[3,4]
[1,3,4]
[1,2,3,4]
[2,3,4]
[2,4]
[1,2,4]
[1,4]
[4]
Во втором столбце таблицы записаны двоичные представле- ния чисел от 0 до
Каждое из чисел мы подвергли преобра- зованию (кодирование по Грею), заменив каждую двоичную цифру, кроме первой, на ее сумму с предыдущей цифрой по мо- дулю 2, таким образом, получив элементы массива Now. Т. е.,
и для всех i от 2 до N. В
четвертом столбце таблицы записаны подмножества, построен- ные по единичным элементам массива Now. Обратите внимание на то, что каждое следующее отличается от предыдущего толь- ко на один элемент. Запишем формирование массива Now в виде процедуры.
Procedure
Var i: Integer;
Begin
FillChar (Now,
(Now) , 0) ;
Now[l]:=B[1];
For i:=2 To N Do Now[i] :=B[i] Xor B[i-1] ;
End;
2. Комбинаторные алгоритмы 63
Обратное преобразование:
для i от 2 до N.
Procedure
Var i ,
Integer;
Begin
FillChar(B,
0);
B[l]
;
For
To N Do B[i]
Xor B[i-1] ;
End;
Воспринимая данное преобразование как факт, осмысление которого лежит за пределами данного материала, генерацию подмножеств можно осуществлять с использованием массива
В. В качестве материала для самостоятельного осмысления предлагается следующая изящная процедура генерации оче- редного разбиения.
Procedure GetNext;
Var i: Integer;
Begin
Repeat
Dec (i) ;
B[i] :=B[i] Xor 1;
Until
Xor 1;
End; {*Будет ли работать данная процедура для
последовательности 1111 (N=4) ?*}
Можно решать задачу по-другому. Вспомним зрительный образ «лесенки» со стрелками, который мы использовали при генерации перестановок, таких, что каждая следующая отли- чалась от предыдущей только одной транспозицией соседних элементов. В данной задаче следует использовать не лесенку, а прямоугольное поле 2*N. Шашки в начальный момент нахо- дятся в первой строке (она соответствует нулевым значениям в двоичной последовательности) и двигаются в направлении стрелок. Определяется первая справа шашка, которую можно сдвинуть в направлении стрелки. Сдвигаем ее, а у шашек, на- ходящихся справа от нее, меняем направление движения. По- следовательности 0000 при N=4 соответствует следующая
«картинка».
64
2. Комбинаторные алгоритмы
А последовательности 0100:
Следующее состояние поля будет иметь вид (последователь- ность 1100):
и процесс генерации окончится при состоянии (последователь- ность
Третья задача. Получение последовательности В по номеру разбиения на подмножества L соответствует записи числа L в двоичной системе счисления с использованием массива В. Дво- ичный разряд числа L — это значение соответствующего эле- мента массива В.
Procedure
Var i: Integer;
Begin
For i:=l To N Do Begin
B[N-i+l] :=L And
младший разряд
числа L. *} •
shr
L в два раза (деление
на 2) . *}
End;
End;
Четвертая задача. Логика получения номера разбиения на подмножества по последовательности соответствует в нашем случае переводу числа из двоичной системы счисления в деся- тичную.
Function
Longlnt;
Var sc: Longlnt;
i: Integer;
Begin
For
To N Do
+ B[i] ;
End;
2. Комбинаторные алгоритмы
65 2.2.7. Скобочные последовательности
Последовательность из
2*N скобок правильная, если для любого значения
i (l число открывающих скобок, на- пример «(», больше или равно числу закрывающих скобок «)»
и общее число открывающих скобок в последовательности рав- но числу закрывающих.
Пример. Последовательность (())()() — правильная последовательность (()))(() — не является правильной.
Мы по-прежнему решаем наши четыре задачи. Однако изме- ним порядок их рассмотрения. Начнем с генерации последова- тельностей.
Пусть N равно 4. В нечетных столбцах таблицы приведены номера последовательностей, а в соседних — соответствующие последовательности.
0
1
2
3
4
5
6
0000 00(0)
0(0)0 0(00)
()((()))
(0)00
(())(())
7
8
9
10
11
12
13
(00)0
(000)
(()(()))
((()))()
((())())
((()()))
(((О)))
Что же мы делаем? Какое отношение порядка введено на множестве последовательностей? Сколько существует таких по- следовательностей для заданного значения N? Вопросов много,
ответов пока нет.
Пусть наша последовательность хранится в переменной строкового типа Now. Мы просматриваем строку справа налево до первой комбинации скобок типа «)(». Она обязательно дол- жна встретиться, ибо, считаем, что текущая последователь- ность не является последней. Заменяем эту комбинацию скобок на
Подсчитываем с начала строки (последовательности),
на сколько число открывающих скобок больше числа закрыва- ющих, дописываем это количество закрывающих скобок, и если строка не длины 2*N, то дополняем ее комбинациями ско- бок «()».
Procedure
Var i, j, sc: Integer;
Begin
While (i>l) And
+
(')
Do
комбинации
3500
66
Комбинаторные алгоритмы
Now[i-1]: = ' (';
= ') ';{"Замена. *}
разности числа открывающих и
числа закрывающих скобок. *}
For j:=l
i Do If Now[j ] = ' (' Then Inc(sc) Else
Dec (sc) ;
While sc<>0 Do
подпоследовательности закрывающими скобками. *}
;
End;
While Length (Now) <2*N Do
() ' ;
строку, максимально "ухудшая"
ее, т.е. из остатка строки делаем ее
начальное
End;
Даны две последовательности и
например ()()(()) и
()(()())• Какая из них имеет больший номер? Просматриваем по- следовательности слева направо, сравнивая соответствующие символы. Найдем первое значение i, при котором
Если окажется, что a
то имеет мень- ший номер, чем
Можно записать сей факт и в математиче- ских обозначениях, но суть не изменится, поэтому воздержим- ся. Перейдем к первой задаче. Введем понятие частично правильной скобочной последовательности. Последователь- ность частично правильная, если для любой позиции в последо- вательности число открывающих скобок больше или равно чис- лу закрывающих, естественно, что количество тех и других считается от начала последовательности. Так, последователь- ность «(((((» является частично правильной, а последователь- ность «(()))((» — нет, для позиции 5 число закрывающих боль- ше числа открывающих скобок. Оформим наши дальнейшие рассуждения в виде таблицы. Номер строки указывает на чис- ло скобок в последовательности, номер столбца — на разность между числом открывающих и закрывающих скобок, имя таб- лицы элемент таблицы ScSmall[i,j] равен количеству частично правильных последовательностей из i скобок, причем разность между числом открывающих и закрывающих равна
Это ключевой момент для понимания: «разность — номер столбца». На диагонали таблицы записаны 1, число последова- тельностей, состоящих из одних открывающих скобок, а они попадают под определение частично правильной последовате- льности. Элементы таблицы ScSmall[i,j] равны 0, если и j
числа разной четности.
2. Комбинаторные алгоритмы
67
Примеры. ScSmall[3,l]=2: ((), ()(.
(((),
(()(, ()((.
()(), (()).
()()(,
(())(,
(()(). ()(()•
«крохотный факт»:
Дописываем в ко-
нец последовательностей из ScSmall[4,0] открывающую скоб-
ку, а в конец ScSmall[4,2] — закрывающую. А это уже реаль-
ный путь подсчета числа последовательностей. Ответом задачи
будет
0 1
2 3
4
5
6 7
8
-1 0
0 0
0 0
0 0
0 0
0 1
0 1
0 2
0
5
0 14 1
0 1
0 2
0
5
0 14 0
2 0
0 1
0 3
0 9
0 28 3
0 0
0
1
0 4
0 14 0
4 0
0 0
0 1
0
5
0
20
5 0
0 0
0 0
1 0
6 0
0 0
0 0
0 0
1 0
7 7
0 0
0 0
0 0
0 1
0 8
0 0
0 0
0 0
0 0
1
Ограничимся при вычислениях диапазоном типа
Const SmallN=37;
Var
+
-1.
+ 1]
Of Longlnt;
Процедура формирования таблицы вряд ли нуждается в по-
яснениях.
Procedure
Var i , : Integer;
Begin
(ScSmall,
0) ;
0]:=l;
For
To
Do
For j:=0 To SmallN Do
End;
Дополним ее функцией определения количества частично
правильных последовательностей из массива SCSmall. •'
Function
Up: Longlnt): Longlnt;
Begin
If (N<0) Or (Up<0) Then
Else
68 2. Комбинаторные алгоритмы
If
Or (Up>SmallN) Then
Else
Up];
End;
Вычисление последовательности номеру и обратное пре- образование можно вынести на самостоятельную часть работы.
Ниже приведены соответствующие процедура и функция. В пе- ременной Up, как и выше, формируется текущая разность меж- ду числом открывающих и закрывающих скобок.
Procedure
Var i, Up: Integer;
P: Longlnt;
Begin
Up:=0;
For i:=l To N*2 Do Begin
If (L>=P) Then Begin
(Up);
End
Else Begin Dec (Up);
End;
End;
End;
Function
Longlnt;
sc: Longlnt;
Up: Integer;
Begin
sc:=l; Up:=0;
For i:=l To N*2 Do
If
Then Begin
(N*2-i,Up-l) ;Inc (Up) ;End
Else
End;
2.3. Задачи
1. Разработать программу генерации всех последовательно- стей длины k из чисел 1, 2, ... N. Первой последовательностью является 1,
...,1, последней — N, N, ..., N.
2. Разработать программу генерации всех последовательно- стей длины k, у которых i-й элемент не превосходит значения
i. Первой последовательностью является 1, 1,
послед- ней — 1, 2, ..., k.
Комбинаторные алгоритмы 69 3.
Перечислить все разбиения натурального числа N на на- туральные слагаемые (разбиения, отличающиеся лишь поряд- ком слагаемых, считаются за одно) в следующих порядках
(пример, при
N=4): 4, 3+1, 2+2, 2+1+1, 1+1+1+1;
2+2, 1+3, 1+1+2, 1+1+1+1;
1+1+1+1, 1+1+2, 1+3, 2+2, 4.
4. Разработать программу генерации всех последовательно- стей длины
2*N, составленных из
N единиц и
N минус единиц,
у которых сумма любого начального отрезка неотрицательна,
т. е. количество минус единиц в нем не превосходит количества единиц.
5. Определить, что делает следующая процедура. Первое об- ращение —
R(N,1).ProcedureVarBeginIf Then Begin к элементовмассива A>;EndElse Begin к элементов массива А>;For Do BeginEnd;End;6. На множестве перестановок задается антилексикографи- ческий порядок. Решить задачи 2-5 из п. 2.2.1.
7. Решить задачи 1-5 из п. 2.2.1 для перестановок с повторе- ниями.
8. Решить задачи 1-5 из п. 2.2.2 для размещений с повторе- ниями.
9. Решить задачи 1-5 из п. 2.2.3 для сочетаний с повторени- ями.
10. Путем трассировки приведенной программы [18] опреде- лите её назначение и логику работы.
Const п-4 ;Var A:Array[l..n] Of Integer;Function Place (i Integer) -.Integer;BeginIf Mod 2=0) And (m>2) ThenIf i
70 2. Комбинаторные алгоритмы
Else
Else
End;
Procedure Perm
Var
If m=l Then Begin For i:=l To n Do Write (A[i]
;
Else
For i : = J
Do Begin
Perm
;
If Km Then Begin
(i ,m) ] ;
End;
End;
Begin
For i:=l
n Do
Perm (n);
End.
Путем трассировки приведенной программы [18] опреде- лите её назначение и логику работы.
Const
Var
Of Integer;
Begin
For i:=l
n Do
Repeat
For
To n Do Write (A[l] : 3)
;
i : =i +1
=1 ;j : =i ;
While j Mod 2=0 Do Begin
j:=j Div 2;p:=p+l;
End;
If
Then
;
Until p>n;
End.
12. Путем трассировки приведенной программы [18] опреде- лите её назначение и логику работы.
Const
Var
Of Integer;
2. Комбинаторные алгоритмы
71
Begin
For
к Do A[i] :=i;
p:=k;
While p>=l Do Begin
For i:=l
к Do Write (A [i] : 3) ;
If A[k]=n Then
Else
If p>=l Then
For i:=k DownTo p Do A[i] :=A[p] +i-p+l ;
End;
End.
13.
На одном из секретных заводов осу- ществляется обработка радиоактивных материалов, в результа- те которой образуются радиоактивные отходы двух типов: А
(особо опасные) и Б (неопасные). Все отходы упаковываются в специальные прямоугольные контейнеры одинаковых разме- ров, после чего эти контейнеры укладываются в стопку один над другим для сохранения. Стопка является взрывоопасной,
если в ней соседствуют два ящика с отходами типа А.
Требуется написать программу, которая подсчитывает коли- чество возможных вариантов формирования не- взрывоопасной стопки из заданного общего числа контейнеров N
Входные данные. Во входном файле
put.txt) содержится единственное число N.
Выходные данные. В выходной файл (out-
put.txt) необходимо вывести искомое число ва- риантов.
Указание. Обозначим опасный контейнер 1, а неопасный —
0. Моделью стопки является последовательность из 0 и 1.
Взрывоопасная стопка есть последовательность из 0 и 1, в кото- рой соседствуют хотя бы две 1 подряд. Задача сводится к под- счету числа последовательностей длины N без двух соседних 1.
Приведем пример при N=4. Таких последовательностей 8.
0000 0001 0010 0100 0101 1000 1001 1010
Как подсчитать количество таких последовательностей (обо- значим через
Пусть есть последовательность длины N.
На первом месте в последовательности записан 0. Число таких последовательностей P(N—1). Рассмотрим случай, когда на первом месте записана 1. Тогда на втором месте обязательно должен быть записан 0. Число таких последовательностей
72 Комбинаторные алгоритмы
P(N-2). Итак, получили формулу:
a это не что иное, как формула вычисления чисел Фибоначчи.
Таким образом, число последовательностей длины
N, в кото- рых нет двух идущих подряд 1, равно iV-му числу Фибоначчи.
Типа данных достаточно только для вычислений при
N<44. Для вычисления количества последовательностей при больших значениях
N требуется использовать «длинную»
арифметику, а именно процедуры сложения и вывода «длин- ных» чисел. Если задачу чуть-чуть изменить — вычислять ко- личество взрывоопасных стопок, то потребуется процедура вы- читания «длинных» чисел. Из необходимо вычесть число невзрывоопасных стопок.
14. Натуральные числа от 1 до
N поступают на об- работку в определенной последовательности. Например, 3, 4, 6,
2, 5, 1. Числа размещаются в таблице следующим образом: по- следовательно просматриваются числа из первой строки и срав- ниваются с поступившим числом
k. Если число больше всех чисел строки, то оно размещается в конце строки. Если же най- дено (первое) число
t, такое, что то число
k записывается на это место, а число
t «выдавливается» из строки и размещается во второй строке по этому же принци- пу, затем в третьей (если потребуется) и т. д., пока для числа или «выдавливаемого») не будет най- дено место. Для приведенной последователь- ности вид размещения дан в таблице.*
Требуется по конечному результату восста- новить все возможные входные последовате- льности чисел, обработка которых по данной логике приводит к этому размещению. Так,
для
примера из формулировки задачи, отве- том являются 16 последовательностей.
Указание. Простейший способ решения за- ключается в генерации всех перестановок и про- верке — удовлетворяет ли очередная переста- новка «правилам игры». Однако если ввести ограничение на время решения, то этот способ не выдерживает элементарной критики. Обра- тим внимание на следующие моменты. На обра- ботку поступила последовательность
(N=6) 1, 2,
3, 4, 5, 6. Её размещение имеет вид:
3 4 5 6.
Обратный порядок поступления дает размеще-
Задача с международной олимпиады школьников 2001 г. (формулировка со- кращена).
2. Комбинаторные алгоритмы 73
ние по одному элементу в строке: в первой — 1, во второй — 2 и т. д. Зададим себе вопрос: а возмож- ны ли размещения, при которых элементы в столб- цах (не в строках!) идут не в порядке возрастания,
как, например, приведенное на следующем рисун- ке. Оказывается, нет.** Мы всегда получаем раз- мещения, элементы в столбцах и строках которых записаны в порядке возрастания. Если так, то первое решение получается простым выписыванием элементов по столбцам в обратном по- рядке. Для примера из формулировки задачи это будет 3 2 4
5. Второй вариант решения может заключаться в том, что из полученной (первой) последовательности путем перестановки соседних элементов мы получаем какую-то последовательность.
Проверяем ее на «пригодность» и если она удовлетворяет
«условиям игры», то запоминаем ее в очереди. Итак, выполня- ем все перестановки соседних элементов в исходной последова- тельности, а затем переходим к очередному необработанному элементу очереди, если он есть. Недостаток алгоритма очеви- ден. Мы можем получать одну и ту же последовательность не- сколькими способами. Поэтому приходится их хранить и перед записью в очередь проверять, нет ли дублирования. А это уже потеря времени и, естественно, данное решение (приведем его
«костяк») является только очередным приближением, хотя и работающим, к окончательному варианту.
Const
Type
Of Word;
Var
Function Check (Const
проверки - удовлетворяет ли очередная
последовательность условиям задачи?*}
Begin
End;
Procedure
Type
элемент очереди.
Очередь размещаем
куче". Обычный список.
Записываем в конец - указатель
считываем первый элемент - указатель
*}
В этом заключается неточность в формулировки задачи на международной олимпиаде. Если проверять по несуществующим размещениям, то часть ре- шений, включая опубликованные в газете «Информатика», будут генериро- вать неизвестные входные последовательности.
Комбинаторные алгоритмы
End;
Var
p:pnt;
i -.Word;
Function
проверки -
есть ли данная
в очереди?*}
Begin
End;
Begin
New
первый элемент в очередь. *}
While ykrOnil Do Begin {*Пока очередь не пуста. *}
элемент из очереди. *}
For i:=l
Do Begin
все
возможные последовательности путем
перестановок соседних
*}
;
If Check (Qj And NotQue Then Begin {*Если
последовательность удовлетворяет условиям
задачи и её нет в очереди, то записываем
в
*}
New
Print
вывода элементов
одномерного массива в файл не
*}
End;
End;
к следующему
элементу очереди. *}
End;
End;
Begin {*Основная программа. Ввод данных.
Формирование первой последовательности
массив А) . *}
Solve;
End.
2. Комбинаторные алгоритмы
75 15. На клетчатой полоске бумаги высотой в одну клеточку и длиной клеток некоторые клетки раскрашены в зеленый и белый цвета.
По этой полоске строится ее код, которым явля- ется последовательность чисел — количества по- дряд идущих зеленых клеток слева направо. На- пример, для такой полоски кодом будет последовательность 2 3 2 8 1. При этом количество белых клеток, которыми разделяются группы зеленых клеток,
нигде не учитывается (главное, что две группы разделяются, по крайней мере, одной белой клеткой). Одному и тому же коду могут соответствовать несколько полосок. Например, указанно- му коду соответствует и такая полоса:
Задача состоит в том, чтобы найти количество полосок дли- ны
N, соответствующих заданному коду.
Входные данные. В единственной строке входного файла
in-put.txt записано число
N — длина полоски (l
— количество чисел в коде и далее чисел, определяющих код.
Выходные данные. В выходной файл output.txt записывает- ся количество полосок длины N, соответствующих заданному коду.
Указание. Добавляем к каждому числу кода по единице (со- ответствует пробелу), получаем значение s. Остается решить за- дачу о подсчете числа размещений N-s пробелов по известному количеству мест — количеству чисел в коде плюс единица. Ес- тественно, что ограничения требуют применения многоразряд- ной арифметики.
16. Между числами нужно вставить знаки арифме- тических операций +, —, * так, чтобы результат вычисления полученного арифметического выражения был равен заданно- му целому числу В.
Входные данные. Во входном файле input.txt записано сна- чала требуемое число В
затем число
— коли-
76
2. Комбинаторные алгоритмы чество чисел в арифметическом выражении а затем целые числа
Выходные данные. В выходной файл out-
put.txt вывести искомое арифметическое вы- ражение или число 0, если его построить не удается. Если решений несколько, вывести любое из них.
Указание. Количество мест для расста- новки знаков —
Требуется сгенериро-
вать все строки этой длины, состоящие из
символов +, —, *, их
Для каждой строки вычислить арифметическое выражение и, в зависимости от результата, продолжить про- цесс генерации или закончить работу.
Представляет определенный интерес логика вычисления вы- ражения. Приведем её. В строке (глобальная переменная от- носительно приведенных функций) записана очередная после- довательность из символов +, —, *, а в массиве А —
последовательность чисел.
Function
Comp;
Var tm: Comp;
Begin
•
While (p
(p) ;
Case B[p-1] Of
' + ' :
(p);
End;
End;
GetRes:=tm;
End;
И функция, вычисляющая произведение очередных сомно- жителей.
Function
p: Integer): Comp;
Var tm: Comp;
Begin
;
While (p
Do Begin
2. Комбинаторные алгоритмы 77
;
(p) ;
End;
End;
Обратной задачей является поиск количества «счастливых билетов» (например, троллейбусных, т. е. шестизначных). Об- щая формулировка задачи. Последовательность из 2N цифр,
каждая цифра от 0 до 9, называется счастливым билетом, если сумма первых N цифр равна сумме последних цифр. Опера- ции даны, требуется найти числа. Так, пусть нам необходимо подсчитать количество счастливых чисел в диапазоне [А,В],
где А, В — заданные натуральные числа, имеющие в десяти- чной записи не более 20 цифр. Пусть
Ответ задачи — 55251. Следующая функция является наброс- ком решения. Она правильная, но работает достаточно мед- ленно.
Function Rec
рекурсии являются k номер позиции в числе и
Sum - сумма цифр в числе до позиции к.*}
Var
Begin
If k=2*N+l Then If
Then Rec:=l Else Rec:=0
Else Begin
Ans:=0;
For
To 9 Do
If k<=N Then
Else If
Then
End;
End;
Работа логики ускоряется за счет следующего приема. Схе- ма рекурсивного подсчета замедляется из-за многократного подсчета одного и того же значения, например Rec(3,8)
iV=2. Следует ввести структуру данных для хранения подсчи- танных значений сумм типа
Of Сотр.
Пусть начальное значение элементов массива равно
1. После того, как вычислено какое-то значение, оно запоминается в массиве и используется при дальнейшей работе. Проведите со- ответствующее изменение логики.
78 2. Комбинаторные алгоритмы
На плоскости заданы N точек с целочисленными коорди- натами. Требуется выделить те точки этого множества, кото- рые образуют выпуклую оболочку (вырожденные случаи — все точки на одной прямой и т. д. не рассматриваются).
Указание. Специальные методы построения выпуклой обо- лочки будут рассмотрены в главе 5. В данном случае можно воспользоваться следующим фактом. Точка (х, у) принадлежит выпуклой оболочке, если она не лежит внутри любого треуго- льника, образованного остальными точками исходного множе- ства. Всего треугольников, которые можно построить из N то- чек, —
общая временная сложность задачи
3. Перебори методы его сокращенияОбучение программированию, алгоритмизации — сверх- сложное дело*. Знание конструкций языка программирования,
способов описания алгоритмов не решает проблемы. Требуется проделать огромную работу для того, чтобы сформировать стиль мышления, присущий специалисту по информатике.
Этот стиль характеризуется, на наш: взгляд, двумя основопола- гающими моментами: язык информатики (он не зависит от конкретного языка программирования) должен стать естест- венным языком выражения своих мыслей (рассуждений); мето- дология решения задач, присущая информатике, должна быть освоена не на фактографическом уровне. Тема «перебор и мето- ды его сокращения» является одной из ключевых в этой систе- ме обучения. Весь процесс обучения построен через решение за- дач, естественно, с использованием компьютера.
3.1. Перебор с возвратом (общая схема)
Даны
N уопрядоченных множеств
..., — изве- стно), и
требуется построить вектор ...,
где удовлетворяющий заданному множе- ству условий и ограничений.
Может быть, это явилось одной из причин, по которой, после появления мощных персональных компьютеров, образовательная информатика с таким энтузиазмом «бросилась» в изучение так называемых информационных тех- нологий.
80 3. Перебор и методы его сокращения
В алгоритме перебора вектор А строится покомпонентно сле- ва направо. Предположим, что уже найдены значения первых
к-1
...,
?, ..., ?), тогда заданное мно- жество условий ограничивает выбор следующей компоненты некоторым множеством Если
] (не пустое), мы вправе выбрать в качестве наименьший элемент и перейти к выбору компоненты и так далее. Однако если условия та- ковы, что оказалось пустым, то мы возвращаемся к выбору
к-1 компоненты, отбрасываем и выбираем в качестве ново- го тот элемент который непосредственно следует за только что отброшенным. Может оказаться, что для нового условия задачи допускают непустое и тогда мы пытаемся снова выбрать элемент
Если невозможно выбрать мы возвращаемся еще на шаг назад и выбираем новый элемент и так далее.
Графическое изображение — дерево поиска. Корень дерева
(О уровень) есть пустой вектор. Его сыновья суть множество кандидатов для выбора и, в общем случае, узлы fc-ro уровня являются кандидатами на выбор при условии, что выбраны так, как указывают предки этих узлов. Вопрос о том, имеет ли задача решение, равносилен вопросу, являются ли какие-нибудь узлы дерева решениями. Разыскивая все ре- шения, мы хотим получить все такие узлы.
Рекурсивная схема реализации алгоритма.
Procedure Backtrack
Begin
<вектор является
Then
его>
Else Begin
<вычислить
For
Backtrack
;
{*\\ - добавление к вектору компоненты. *}
End;
End;
Оценим временную сложность алгоритма. Данная схема реа- лизации перебора приводит к экспоненциальным алгоритмам.
Действительно, пусть все решения имеют длину 2V, тогда иссле- довать требуется порядка
*|
узлов дерева. Если значение ограничено некоторой константой С, то получаем порядка узлов.
3. Перебор и методы его сокращения 81 3.2. Примеры задач для разбора общей схемы перебора
Пример 1 — «Задача о расстановке ферзей». Для разбораобщей схемы одной из лучших задач является задача о расста- новке ферзей. На шахматной доске
N*N требуется расставить
N ферзей таким образом, чтобы ни один ферзь не атаковал дру- гого.
Отметим следующее. Все возможные способы расстановки ферзей —
(около для
N=8). Каждый столбец содер- жит самое большее одного ферзя, что дает только расстано- вок для iV=8). Никакие два ферзя нельзя поставить в одну строку, а поэтому, для того чтобы вектор
...,
был решением, он должен быть перестановкой элементов (1,2,
...,
N), что дает только
(4,0*10 4
для N==8) возможностей. Ни- какие два ферзя не могут находиться на одной диагонали, это сокращает число возможностей еще больше (для в дереве остается 2056 узлов). Итак, с помощью ряда наблюдений мы исключили из рассмотрения большое число возможных расста- новок
N ферзей на доске размером
N*N. Использование подоб- ного анализа для сокращения процесса перебора называется поиском с ограничениями или отсечением ветвей в связи с тем,
что при этом удаляются поддеревья из дерева. Второе. Другим усовершенствованием является слияние, или склеивание, вет- вей. Идея состоит в том, чтобы избежать выполнения дважды одной и той же работы: если два или больше поддеревьев дан- ного дерева изоморфны, мы хотим исследовать только одно из них. В задаче о ферзях мы можем использовать склеивание, за- метив, что если то найденное
решение можно отра- зить и получить решение, для которого
Следователь- но, деревья, соответствующие, например, случаям и
изоморфны.Следующие рисунки иллюстрируют сказанное и поясняют ввод используемых структур данных.
Структуры данных.
Up: Array .16] Of Boolean ;•{ занятостидиагоналей первого *} 7] Of занятостидиагоналей второго типа. Of Boolean;{*Признак занятостивертикали. *}X: Array .8] Of вертикали,на которой стоит ферзь на каждой горизонтали. *}
82 3. Перебор и методы его сокращения
Далее идет объяснение «кирпичиков», из которых «склады- вается» решение (технология «снизу вверх»).
Procedure
{*Сделать ход.*}
Begin
:=j;Vr[j] :
:=False;
End;
Procedure
ход.*}
Begin
Vr
End;
Function
допустимости хода в позицию (i,j). *}
Begin
D_hod:=Vr[j] And Up[i+j] And Down [i-j] ;
End;
Основная процедура поиска одного варианта расстановки ферзей имеет вид:
Procedure
Var
Перебор и методы его сокращения 83
Begin
Repeat
Inc
вертикали. *}
If
Then Begin
If i<8 Then Begin
Solve
,q) ;
If Not q Then
;
End
Else
найдено.*}
End;
Until q Or (j=8) ;
End;
Изменим формулировку задачи. Пусть требуется найти все способы расстановки ферзей на шахматной доске N*N. Для до- ски 8*8 ответ 92. Возможный вариант реализации приведен ниже по тексту.
Procedure
Var
Begin
If
Then Begin
For j : =1 To N Do
If D_hod(i,j) Then Begin
Hod(i,j) ;
Solve (i+1) ;
;
End;
End
Else Begin
Inc (S);{*Счетчик числа решений, глобальная
*}
Print;{*Вывод решения. *}
End;
End;
Продолжим изучение задачи. Нас интересуют только несим- метричные решения. Для доски 8*8 ответ 12. Это задание тре- бует предварительных разъяснений. Из каждого решения зада- чи о ферзях можно получить ряд других при помощи вращений доски на 90°, 180° и 270° и зеркальных отражений относитель- но линий, разделяющих доску пополам (система координат
84
Перебор я методы его сокращения фиксирована). Доказано, что в общем случае для любой допус- тимой расстановки N ферзей возможны три ситуации:
• при одном отражении доски возникает новая расстановка ферзей, а при поворотах и других отражениях новых ре- шений не получается;
• поворот на 90° и его отражение дают еще две расстановки ферзей;
• три поворота и четыре отражения дают новые расстанов- ки. ,
Для отсечения симметричных решений на всем множестве решений требуется определить некоторое отношение порядка.
Представим решение в виде вектора длиной N, координатами которого являются числа от 1 до N. Для ферзя, стоящего в строке, координатой его столбца является координата век- тора. Для того, чтобы не учитывать симметричные решения,
будем определять минимальный вектор среди всех векторов,
получаемых в результате
Процедуры
Sim2,
Sim3 выполняют зеркальные отображения вектора решения от- носительно горизонтальной, вертикальной и одной из диагона- льных осей. Известно (из геометрии), что композиция этих дает все определенные выше симметрии шахматной доски, причем не принципиально, в какой последовательности выполняются эти процедуры для каждой конкретной компози- ции. Проверка «на минимальность» решения производится функцией которая возвращает значение True в том слу- чае, когда одно из симметричных решений строго меньше теку- щего решения. Возможный вариант реализации (отсечение на выводе решений) приведен ниже по тексту.
Type
Of 'Integer;
Procedure
Var
Begin
For
To N Do
:
;
End;
Procedure Sim2 (Var
;
Var i ,
Begin
For i:=l To N Div 2 Do Begin
End;
End;
Procedure
Перебор и методы его сокращения 85
Var
Begin
For i:=l To N Do
End;
Function
-.Boolean;
Var
Begin
i : =1 ;
While
And (Y[i]=X[i]) Do Inc(i);
If i>N Then Cmp:=False
Else If Y[i]
End;
Procedure
Var j
Y:
Begin
If i<=N Then Begin
For
To N Do
If
Then Begin
;
Solve
;
;
End;
End
Else Begin
For
To 7 Do Begin
Y:=X;
If j And 1 =0 Then
(Y) ;
If j And 2 =0 Then
(Y) ;
If j And 4 =0 Then
(Y) ;
If
Then
End;
If f Then Begin
Inc(S);{*Счетчик числа решений, глобальная
переменная. *}
Print-; {*Вывод решения. *}
End;
End;
End;
86 3. Перебор и методы его сокращения
Примечание
Программу решения задачи о шахматных ферзях можно написать по-разному. Ниже по тексту приведено одно из возможных реше- ний . Решение очень компактное, по-своему изящное, но не будем комментировать его. Попробуйте разобраться с ним и ответить на вопрос: в чем заключается отличие в стилях при написании про- грамм в этом примере и в целом в данном учебнике.
Program Ferz;
Uses Crt;
Const N=8;
Var
Of
Procedure Rf
;
Var
Begin
For j:=l To N Do Begin
While (k
Do Begin
If
Or
(k-i)=Abs(B[k]-B[i] ) )
Then
Inc(k) ;
End;
If p=0 Then
If i
Else Begin
For t:=l To N Do Write (B [t] : 3) ;
End;
End;
End;
Begin
ClrScr;
End.
Пример 2 — «Задача о шахматном коне». Существуют спо- собы обойти шахматным конем доску, побывав на каждом поле по одному разу. Составить программу подсчета числа способов обхода.
Разбор задачи начинается с оценки числа 64! — таково об- щее число способов разметки доски 8*8. Каждую разметку сле- дует оценивать на предмет того, является ли она способом обхо- программы из учебника по информатике для студентов педагогиче- ских вузов.
3. Перебор и методы его сокращения
87да конем доски (решение в
Затем оцениваем порядок сокращения перебора исходя из условия — логика выбора оче- редного хода коня. Будем считать, что поля для хода выбира- ются по часовой стрелке. Объяснение иллюстрируется следую- щими рисунками.
Структуры данных.
Const N= ; ; Of .8] OfVar Of Integer;Основной фрагмент реализации — процедура
Solve.ProcedureVarBeginIf q=N*M Then (t)Else For z:=l To 8 Do BeginIf Then Solve (i , j ,q+l)End;End; 
Скачать 5.46 Mb.