- •Анализ алгоритмов (Лекции 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 : 0..N; s : Boolean;
begin i := n; s := true;
while (i > 0) and s do
begin s:=f[i] <= n-1; i := i-1 end;
TYPEJ :=s
end;
Непосредственно из определения вытекает следующий алгоритм построения таблицы инверсий для перестановки, заданной в естественной форме:
procedure TABIN (var f :TPE; var r :TPI);
Var I, j, k : integer;
begin for i := 1 to n do
begin k := f[i]; r[k] := 0;
for j := i-1 downto 1 do
{1} if f[j] > k then r[k] :=r[k]+1
end
end;
Временная сложность этого алгоритма фактически определяется числом выполнения {1}, которое равно n(n-1)/2, т. е. является О(n2).
Рассмотрим теперь алгоритм восстановления перестановки в естественной форме по его таблице инверсий. Здесь возможны два похода.
1. Будем последовательно, начиная с единицы и кончая n, расставлять элементы перестановки на свои места. Вначале всем вставляемым элементам перестановки соответствуют нулевые значения. Тогда для того чтобы определить место элемента i, достаточно перед ним оставить ri нулей для элементов со значениями, большими i. Реализация этого подхода на языке Паскаль выглядит так:
type P = array [1..0] of 1..n;
. . .
procedure TABOUT1 (var r : TPI; var f : P);
var i, j, k : 0..n;
begin for i := 1 to n do f[i] := 0;
for i := 1 to n do
begin k := r[i]+1; j := 0;
repeat j := j+1;
if f[j] = 0 then k :=k-1
until k = 0;
f[j] := i
end
end;
Комментарий. Для параметра f определен новый тип P, отличающийся от типа TPE тем, что его элементы массива могут получать нулевые значения. После исполнения процедуры TABOUT1 параметр f принимает значения типа TPE. Переменная k служит для пропуска нулевых значений, а j - для определения места элемента i.
Упражнение. Исполните алгоритм TABOUT1 при n=5, r=/2,3,1,1,0/.
Оценим временную сложность алгоритма. Она определяется числом выполнения операторов внутри цикла repeat. Пусть Ti - точное число выполнения операторов внутри цикла для заданного i. Тогда r[i]+1 Ti n. Если все перестановки из Sn равновероятны, то среднее значение r[i] равно (n-i)/2. Это приводит к тому, что вычислительная сложность этого алгоритма в среднем по всем перестановкам есть O(n2).
2. Запишем число n. Далее если r[n-1]=1, то значение n-1 поместим после n или перед ним, если r[n-1]=0. Предположим, что уже расставлены элементы n, n-1,..., i+1, тогда i нужно поставить после r[i] значений уже построенной последовательности.
Например, пусть n=5, r=/2,2,1,0,0/
1 шаг (постановка 5) r[5]=0 5
2 шаг (постановка 5) r[5]=0 4 5
3 шаг (постановка 5) r[5]=1 4 3 5
4 шаг (постановка 5) r[5]=2 4 3 2 5
5 шаг (постановка 5) r[5]=2 4 3 1 2 5
f = < 4 3 1 2 5>
В реализации этого алгоритма на языке Паскаль хранение формируемой последовательности естественней всего организовать в виде линейного цепного списка. В этом случае включение в список значения i сводится к вставке в него соответствующего элемента после r[i] ранее включенных элементов. Вследствие того, что каждое значение элементов списка лежит в промежутке от 1 до n, а число элементов не превосходит n, список удобно хранить в массиве (c) из n+1 ячейки. При этом в нулевой ячейке хранится значение первого элемента списка, а в ячейке с индексом i - значение элемента следующего в списке за ним. Для последнего включенного в список элемента перестановки и для не включенных значений соответствующие ячейки равны нулю.
Например, список 4325 при n=5 будет представлен c[0]=4, c[1]=0, c[2]=5, c[3]=2, c[4]=3, c[5]=0.
Реализация этого подхода на языке Паскаль выглядит так:
рrocedure TABOUT2 ( var r : :TPI; var f :TPE);