- •Анализ алгоритмов (Лекции 2000)
- •Глава 1. Модели вычислений.
- •Глава 3. Перестановки как абстрактный тип данных
- •3.1 Представление перестановок в естественной форме.
- •Var a : array [1..N] of Boolean;
- •Var I, j, k, m:1..N; a:array[1..N] of Boolean;
- •If a[I] then
- •Var I,j:1..N; s:boolean:
- •Var I,j,k:1..N: a:array[1..N] of boolean;
- •If a[I] then
- •3.2 Представление перестановок в циклической форме.
- •Procedure trsl(var f: tpe; var g: tpc);
- •Var I : 1..N; s : Boolean;
- •If a[I] then
- •Procedure u1(var f : tpe; var g : tpk);
- •Var r : real;
- •3.3 Представление перестановок в виде таблицы инверсий.
- •Var I : 0..N; s : Boolean;
- •Var I, j, k : integer;
- •Var c : array [0..N] of 0..1;
- •X : array [1..N] of real;
- •Function ч3 (var r :tpi) : Boolean;
- •Var k, I, j, s, : integer;
- •3.4 Задача о складывании карт.
- •Var I,a,b : integer;
- •Var z:integer;
- •Глава 4. Генерация перестановок
- •4.1Генерация перестановок в лексикографическом порядке.
- •Var р : array [0..N] of 0..N; { текущая перестановка}
- •Var p : array [1..N] of 1..N;
- •Генерация перестановок за минимальное число транспозиций
- •Var I,k : integer;
- •Var p:array [0..N1] of 1..N1;
- •I,j,k,t: integer;
- •Глава 5. Генерация подмножеств множества
- •5.1Генерация подмножеств в лексикографическом порядке.
- •5.2 Генерация подмножеств за счет их минимального изменения.
- •Var s : array [1..N] of 0..1;
- •I : integer;
- •Var s : array [1..N] of 0..1;
- •I,j,k,p : integer;
- •Var t : array [0..N] of 1..N1; {стек}
- •Var t : array [0..N1] of 1..N2;
- •I,p : integer;
- •5.3Генерация мультимножеств.
- •Глава 6. Генерация k-подмножеств
- •Var s : array[1..K] of 1..N;
- •I,p : integer;
- •6.1Генерация k-подмножеств заменой одного элемента.
- •Var I : integer;
- •Var I,m,h:integer;
- •Упражнение. Выполните приведенный алгоритм для деревьв
- •В режиме неполного вычисления
- •Глава 8 Теорема о сложности рекурсивных программ
- •Глава 9 Производящие функции
Var I, j, k, m:1..N; a:array[1..N] of Boolean;
begin
for i:=1 to n do a[i]:=true;
for i:= 1 to n do
If a[I] then
begin j:=f[i]; a[i]:=false; k:=i; {1}
while j<>i do
begin m:=f[j]; f[j]:=k; k:=j; j:=m; a[k]:=false {2}
end;
f[i]:=k {3}
end;
end {4} ;
Тест f=<5 7 3 1 6 4 2>
{1} i=1 j=5 a[1]=false k=1 m – не определено
{2} m=6 f[5]=1 k=5 j=6 a[5]=false
{2} m=4 f[6]=5 k=6 j=4 a[6]=false
{2} m=1 f[4]=6 k=4 j=1 a[4]=false
{3} f[1]=4
{1} i=2 j=7 a[2]=false k=2 m=1
{2} m=2 f[7]=2 k=7 j=2 a[7]=false
{3} f[2]=7
{1} i=3 j=3 a[3]=false k=3 m=2
{3} f[3]=3
{4} f=<4 7 3 6 1 5 2>
<5 7 3 1 6 4 2>.<4 7 3 6 1 5 2>=<1 2 3 4 5 6 7>
Доказательство правильности реализации алгоритма основано на том, что перестановки f и f-1 имеют взаимосвязанные структуры при разложении их на циклы.
Пример. Разложение перестановки на циклы.
f=<5 7 3 1 6 4 2>
1564
27
3
Каждый цикл выписан на отдельной строчке. Внутри цикла следующим выписывается элемент перестановки являющейся образом в f текущего, т. е. xf(x). Образ последнего элемента совпадает с первым. В этом примере первым в каждом цикле выписан элемент с наименьшим номером внутри цикла, a циклы расположены в порядке возрастания первых элементов.
Для того чтобы получить разложение на циклы обратной для f перестановки, достаточно перевернуть “стрелочки” в каждом цикле разложения f в обратную сторону.
Пример. Разложение на циклы обратной перестановки.
f -1=<5 7 3 1 6 4 2>-1=<4 7 3 6 1 5 2>
1465
27
3
Упражнение. Докажите свойство взаимосвязи разложений на циклы f и f-1 для произвольной перестановки из Sn.
В приведенном алгоритме массив a служит для пометки включенных в циклы элементов f. В каждом цикле первым выбирается элемент, имеющий наименьший номер (второй оператор цикла типа for). Обход каждого цикла с переориентацией стрелок осуществляется оператором цикла типа while.
ЧЕТНОСТЬ ПЕРЕСТАНОВКИ. Алгоритм вычисления четности перестановки непосредственно по определению может быть представлен следующем образом:
function Ч(var. f: TPE): boolean;
Var I,j:1..N; s:boolean:
begin s:=true;
for i:=2 to n do
for j:=1 to i-1 do
if f[j]>f[i] then s:=not s;
Ч:=s
end;
Этот алгоритм имеет временную вычислительную сложность О(n2). Однако оказывается, что существует алгоритм определения четности перестановки со сложностью О(n). Такой алгоритм также строится на анализе свойств циклической структуры перестановки на основе следующей теоремы:
Теорема 1. Перестановка f является четной тогда и только тогда когда и в ее циклическом разложении число циклов четной длины четно.
Здесь под длиною цикла понимается число элементов перестановки, входящих в данный цикл.
На основе этой теоремы алгоритм определения четности перестановки может быть реализован по схеме процедуры O1 с изменениями некоторых действий внутри цикла while.
Function ч1 (var f: TPE) : boolean;