3 Порядок выполнения работы
3.1 Получить задание у преподавателя по определению эйлерова и гамильтонова цикла.
3.2 Составить алгоритм программы, реализующей нахождение эйлерова и гамильтонова цикла в графе.
3.3 Создать программу, реализующую реализующей нахождение эйлерова и гамильтонова цикла в графе.
4 Содержание отчета по работе
4.1 Исходное задание и цель работы.
4.2 Блок-схема программы по п.3.2.
4.3 Распечатка текста программы по п.3.3.
4.4 Контрольный пример и результаты машинного расчета.
4.5 Выводы по работе.
5 Контрольные вопросы
5.1. Дайте определение пути и цикла в графе.
5.2 Дайте определение эйлерова пути и эйлерова цикла.
5.3 Дайте определение гамильтонова пути и гамильтонова цикла.
5.4. Сформулируйте теорему Эйлера.
5.5 Опишите алгоритмы нахождения эйлерова и гамильтонова циклов.
Тема 2. Алгоритмы комбинаторного перебора (18 часов).
Цель: Практическое изучение базовых алгоритмов комбинаторной генерации и комбинаторного перебора, а также способов их реализации на компьютере.
Лабораторная работа № 10-11
ГЕНЕРАЦИЯ ПЕРЕСТАНОВОК
1 Цель работы
Целью работы является изучение различных алгоритмов генерации всех перестановок.
2 Теоретическая часть
Перестановки
Первая задача. Научимся вычислять число перестановок для заданного значения N. Известно, что число перестановок равно факториалу числа
Рекурсивное определение:
Функция имеет ограниченную область применения.
Function Fac (k:LongInt): LongInt;
Var r,i: LongLnt;
Begin
r:=1;
For i:=l To к Do r:=r*i;
Faс:=r;
End;
Функция работоспособна при N, меньшем или равном 12.Для больших значений N требуется использовать «длинную» арифметику: умножение «длинного» числа на короткое; вывод «длинного» числа
Вторая и третья задачи. Необходимо перечислить или сгенерировать все перестановки для заданного значения N, что требует введения отношения порядка на множестве перестановок. Только в этом случае задача имеет смысл. Предполагаем, что перестановка хранится в массиве Р длины N. Лексикографический порядок на множестве всех перестановок определяется следующим образом P1<P2 тогда и только тогда, когда существует такое t>=1, что P1[t]<P2[t] и P1[i]<P2[i] для всех i<t. При решении данной задачи решается и задача получения следующей в лексикографическом порядке перестановки. Аналогично определяется антилексикографический порядок.
Пример (N=4). Столбцы, обозначенные буквой А, означают генерацию перестановок в лексикографическом порядке, буквой В — антилексикографическом.
Пример. Перестановка 11, 8, 5, 1, 7, 4, 10, 9, 6, 3, 2. Какая следующая перестановка идет в лексикографическом порядке? Находим «скачок» — 4 меньше 10. Затем «в хвосте» перестановки находим первый элемент с конца перестановки, больший значения 4, на рисунке это значение 6. Меняем местами элементы 4 и 6 и «хвост» перестановки ухудшаем максимально, т. е. расставляем элементы в порядке возрастания. Процедура получения следующей в лексикографическом порядке перестановки имеет вид:
Procedure GetNext;
Var i,j:Integer;
Begin {*Для перестановки N, N-1,...,1 процедура
не работает, проверить. *}
i : =N;
While (i>l) And (P [i] <P [i-1] ) DoDec(i);
{*Находим "скачок".*}
j:=N;
While P[j]<P[i-1] Do Dec(j); {*Находим первый
элемент, больший значения P[i-1].*}
Swap (P[i-1], P[j]) ;
For j:=0 To (N-i+1) Div 2 - 1 Do Swap (P[i+j] ,
P[N-j]) ; {*Переставляем элементы "хвоста"
перестановки в порядке возрастания.*}
End;
Procedure Swap (Var a,b:Integer);
Var t:Integer;
Begin
t:=a; a:=b; b:=t;
End;
Фрагмент общей схемы генерации:
Init;{*Инициализация: в массиве Р - первая
перестановка, в массиве Last - последняя.*}
Print;{*Вывод перестановки.*}
While Not(Eq(P,Last)) Do Begin {*Функция Eq
определяет равенство текущей перестановки
и последней; если не равны, то генерируется
следующая *}
GetNext;
Print;
End;
Изменим задачу. Необходимо перечислить все перестановки чисел от 1 до N так, чтобы каждая следующая перестановка получалась из предыдущей с помощью транспозиции двух соседних элементов.
Например:
Возьмем перестановку p1,…,pN и сопоставим с ней следующую последовательность целых неотрицательных чисел у1,…,yN. Для любого i от 1 до N найдем номер позиции s, в которой стоит значение i в перестановке, т. е. такое s, что ps=i, и подсчитаем количество чисел, меньших i среди p1,…,pN . Это количество и будет значением yi
Пример
Очевидно, что 0=<yi<i. Всего таких последовательностей N!, т. е. множества перестановок и последовательностей чисел совпадают по мощности. Построение последовательности чисел из перестановки очевидно, как и то, что разным перестановкам соответствуют разные последовательности чисел. Эта таблица называется таблицей инверсий. М. Холл установил, что таблица инверсий единственным образом определяет соответствующую перестановку — обратное построение.
Пример. Последовательность 0111. Четверка записана на втором месте, ибо только одна цифра в перестановке «стоит» левее ее; имеем *4**. Тройка с учетом занятого места находится на третьем месте — *43*. Двойке с учетом занятых мест принадлежит четвертое место, т. е. получаем перестановку 1432.
Таблица последовательностей чисел и соответствующих перестановок для N=4.
Зрительный образ предлагаемой схемы генерации. Пусть есть доска в форме лестницы. Высота i вертикали равна i. В первоначальном состоянии шашки стоят на первой горизонтали. Стрелки указывают направление движения шашек (вверх). За один ход можно передвинуть одну шашку в направлении стрелки. Если шашку передвинуть нельзя, то осуществляется переход к следующей слева шашке. После того как найдена шашка, которую можно передвинуть помимо передвижения шашки, осуществляется смена направления движения всех шашек справа от найденной. Ниже на рисунке приведена смена состояний шашек на доске при N=4, начиная с последовательности чисел 0023. Под последовательностями чисел записаны соответствующие им перестановки.
Оказывается, что изменение на единицу одного из элементов последовательности соответствует транспозиции двух соседних элементов перестановки. Увеличение y[i] на единицу соответствует транспозиции числа i с правым соседом, уменьшение — с левым соседом. Итак, помимо генерации последовательностей необходимо уметь находить число i в перестановке и менять его местами с одним из «соседей», но это уже чисто техническая
задача.
Опишем используемые данные.
ConstNmax=12;
Var P:Array[1. .Nmax] Of 0 . .Nmax; {*Хранение
перестановки.*}
Y:Array[1..Nmax] Of 0..Nmax-1; {*Хранение
последовательности чисел.*}
D:Array[1..Nmax] Of-1..1; {*Направление
движения "шашек". *}
Процедура формирования начальной перестановки и начальных значений в массивах Y и D.
Procedure First;
Var i:Integer;
Begin
For i:=1 To N Do Begin
P[i]:=N-i+1; Y[i]:=0; D[i]:=1;
End;
End;
Поиск номера «шашки», которую можно передвинуть. При D[i]=l и Y[i]=i-1 или D[i]=-l и Y[i]=0 шашку с номером i нельзя передвинуть.
Function Ok:Integer; {*Если значение функции равно
1, то нет ни одной шашки, которую можно
передвинуть.*}
Var i:Integer;
Begin
i:=N;
While (i>1) And (((D[i]=1) And (Y[i]=i-1)) Or
((D[i]=-1) And (Y[i]=0))) DoDec(i);
Ok: =i ;
End;
Основная логика генерации перестановок имеет вид:
Begin
First;
рр:=True;
While pp Do Begin
Solve (pp) ;
If pp Then Print;
End;
End;
Уточним процедуру генерации следующей перестановки.
Procedure Solve(Var q:Boolean);
Var i, j, dj:Integer;
Begin
i:=Ok; q:=(i>l); {*Haходим номер шашки, которую
можно передвинуть. *}
If i>1 Then Begin
Y[i]:=Y[i]+D[i]; {*Передвигаем шашку - изменяем
последовательность чисел.*}
For j:=i+1 To N Do D[j]:=-D[j]; {*Изменяем
направление движения шашек, находящихся
справа от передвинутой.*}
j:=Who_i(i); {*Находим позицию в перестановке,
в которой записано число i.*}
dj:=j+D[i]; {*Определяем соседний элемент
перестановки для выполнения транспозиции.*}
Swap(P[j], P[dj]); {*Транспозиция.*}
End;
End;
Остался последний фрагмент логики, требующий уточнения, — поиск в перестановке позиции, в которой находится элемент i. Он достаточно прост.
Function Who_i (i : Integer): Integer;
Var j: Integer;
Begin
j:=N;
While (j>0) And (P[j]<>i) Do Dec(j);
Who_i :=j;
End;
Четвертая задача. Как по номеру определить перестановку относительно того порядка, разумеется, который введен на множестве перестановок? Остановимся на лексикографическом порядке. Рассмотрим идею решения на примере. Пусть N равно 8 и дан номер L, равный 37021. Найдем соответствующую перестановку. Пусть на первом месте записана единица. Таких перестановок 7!, или 5040 (1*******). При 2 тоже 5040 (2*******). Итак, 37021 Div 5040=7. Следовательно, первая цифра в перестановке 8. Новое значение L (37021 Mod 5040=1741) 1741. Продолжим рассуждения. Оформим, как обычно, их в виде таблицы. Обратим внимание на третью строку, в которой на третье
место записывается цифра 4. То, что записываются не цифры 1 и 2, очевидно: их требуется пропустить. Цифра три «занята», поэтому записываем 4. Точно так же в строках 4, 5 и 7.
О программной реализации. Пусть N=<12, таким образом,
значение L не превосходит максимального значения типа LongInt. Определим следующие константы.
Const Nsmall=12;
ResSm: Array[0..Nsmall] Of LongInt
=(1,1,2,6,24,120, 720,5040,40320,362880,3628800,3991
6800,479001600) ; {*3начения N! для N от 0 до 12.*}
И процедура.
Procedure GetPByNum(L:LongInt);
Var Ws: Set Of Byte;
i,j,sc: Integer;
Begin
Ws:=[]; {*Множество для фиксации цифр,
задействованных в перестановке.*}
For i:=1 То N Do Begin
Sc:=L Div ResSm[N-i]; L:=L Mod ResSm[N-i]; j:=1;
While (sc<>0) Or (j In Ws) Do Begin
If Not (j In Ws) Then Dec(sc);
Inc (j) ;
End;
Ws:=Ws+[j]; {*Нашли очередную цифру. *}
P[i]:=j;
End;
End;
Пятая задача. По перестановке получить ее номер, не выполняя генерацию множества перестановок.
Начнем с примера. Пусть N равно 8 и дана перестановка 53871462.
Схема:
7!*<количество цифр в перестановке на 1-м месте, идущих до цифры 5, с учетом занятых цифр — ответ 4>
6!*< количество цифр в перестановке на 2-м месте, идущих до цифры 3, с учетом занятых цифр — ответ 2>
5!*< количество цифр в перестановке на 3-м месте, идущих до цифры 8, с учетом занятых цифр — ответ 5>
4!*< количество цифр в перестановке на 4-м месте, идущих до цифры 7, с учетом занятых цифр — ответ 4>
3!*< количество цифр в перестановке на 5-м месте, идущих до цифры 1, с учетом занятых цифр — ответ 0>
2!*< количество цифр в перестановке на 6-м месте, идущих до цифры 4, с учетом занятых цифр — ответ 1>
1!*< количество цифр в перестановке на 7-м месте, идущих до цифры 6, с учетом занятых цифр — ответ 1>
Итак,
7!*4+6!*2+5!*5+4!*4+3!*0+2!*1+1!*1=4*5040+2*720+5*120+4*24+0*6+1*2+1*1=22305.
Function GetNumByP: LongInt;
Var ws:Set Of Byte;
i,j,sq:Integer; sc:LongInt;
Begin
ws:=[]; {*Множество цифр перестановки.*} sc:=1;
{*Номер перестановки.*}
For i:=1 To N Do Begin
j:=1; sq:=0; {*Определяем количество цифр.*}
While j<P[i] Do Begin
If Not (j In ws) Then Inc (sq);
Inc (j);
End;
ws:=ws+[P[i]]; {*Цифра P[i] задействована.*}
sc:=sc+ResSm[N-i]*sq; {*Умножаем число
перестановок на значение текущей цифры.*}
End;
GetNumByP:=sс;
End;
3 ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
3.1. Составить алгоритмы программ, реализующих генерацию перестановок рассмотренными способами.
3.2. Создать программы, реализующие генерацию перестановок рассмотренными способами.
4 СОДЕРЖАНИЕ ОТЧЕТА ПО РАБОТЕ
4.1 Исходное задание и цель работы.
4.2 Блок-схема программы по п.3.1.
4.3 Распечатка текста программы по п.3.2.
4.4 Контрольный пример и результаты машинного расчета.
4.5 Выводы по работе.
5 КОНТРОЛЬНЫЕ ВОПРОСЫ
5.1 Чему равно число перестановок множества из N элементов?
5.2. Определите лексикографический порядок на множестве перестановок.
5.3. Как задать перестановку при помощи инверсий?
5.4. Опишите известные Вам алгоритмы генерации всех перестановок.
5.5. Как получить номер заданной перестановки?
5.6. Как получить перестановку по ее номеру?