Билет 6. Генерация множеств в лексикографическом порядке

Стр 1 из 4Следующая ⇒

Содержание

1. Поиск индекса элемента в упорядоченном массиве (бинарный поиск).

2. Генерация перестановок в лексикографическом порядке по рекурсивной схеме (Оценка сложности).

3. Генерация перестановок в лексикографическом порядке по итеративной схеме (Оценка сложности).

4. Записи.

5. Множества.

6. Генерация множеств в лексикографическом порядке.

7. Коды Грея и их генерация.

8. Генерация К-подмножеств в лексикографическом порядке.

9. Генерация К-подмножеств в порядке минимального изменения.

10. Строки.

11. Процедурные типы.

12. Файлы.

13. Текстовые файлы.

14. Модули.

15. Динамические типы данных.

16. Простой линейный список.

17. Представление графа списком смежности.

18. Дерево поиска.

19. Коды Прюфера.

20. Транспортная задача.

Билет 1. Поиск индекса элемента в упорядоченном массиве (бинарный поиск).

Program BinSearch

const

N=7;

var

i,v,left,right,middle:integer;

A:array[1..N] of integer;

begin

for i:=1 to n do

read(a[i]);

writeln('The source array is:');

for i:=1 to N-1 do

write(A[i],', ');

writeln(A[N],'.');

write('Input a value for searching: ');

readln(v);

left:=1;

right:=N;

while left+1<right do

begin

middle:=(left+right) div 2;

if v<A[middle]

then right:=middle

else left:=middle;

writeln('It should be somewere between ',left,' and ', right);

end;

if v=A[left]

then writeln('Requested value was found at position ',left)

else

if v=A[right]

then writeln('Requested value was found at position ',right)

else writeln('Requested value is NOT found');

readln;

end.

*Билет 2. Генерация перестановок в лексикографическом порядке по рекурсивной схеме (Оценка сложности).

program LEX1;

uses crt;

const n=4; {n порядок перестановок}

var p : array [1..n] of 1..n;

i,r : 1..n;

procedure INVERT (m : integer); {инвертирование p[m]...p[n] }

var i,j: 1..n;

begin i:=m; j:=n;

while i<j do begin r:=p[i]; p[i]:=p[j]; p[j]:=r;

i:=i+1; j:=j-1

end

end {INVERT};

procedure Lec (k:integer);

var j : 1..n;

begin

if k=n then

begin for i:=1 to n do write (p[i]); writeln end

else

for j:=n downto k do

begin

LEC (k+1);

if j<>k then

begin

r:=p[j]; p[j]:=p[k]; p[k]:=r;

INVERT (k+1)

end

end {LEC};

b*egin

for i:=1 to n do p[i]:=i;

LEC (1)

end.

Для оценки сложности приведенной рекурсивной программы наряду со средним числом количества транспозиций элементов перестановки, нам необходимо определить среднее число вызовов процедуры L EC, как функции от n - порядка перестановок.

Пусть B_n - число вызовов процедуры LEC при генерации всех перестановок n - порядка программой LEX1. Для B_n справедливо следующее рекуррентное соотношение

B₁=1

B_n= n×B_n_-1+1

Его решением является последовательность B_n=n!× . Это приводит к тому, что в среднем на одну перестановку приходится e-1 вызовов процедуры LEC. Этот результат позволяет сравнить алгоритмы LEX и LEX1. Фактически сравнение сводится к оценке того, что эффективнее реализуется на конкретной ЭВМ: e-1 вызовов рекурсивной процедуры или 3.077 сравнений целых чисел.

procedure PERM( m : integer); {1 £ m £ n}

var i,k : integer;

{p, b – глобальные массивы}

begin

if m=1 then

{p[1], … , p[n] содержит новую перестановку}

for i:=1 to n do write (p[i])

else

for i:=1 to m do

begin PERM( m-1);

if i<m then

begin k:=p[m];

{*} p[m]:=p[b[m,i]];

p[b[m,i]]:=k

end

end;

Function b(m,i :integer) : integer; {m>i}

begin

if (m mod 2 = 0) and m > 2 then

if i < m-1 then b:=1 else b:=m-2

else b:=m-1

end;

Билет 3. Генерация перестановок в лексикографическом порядке по итеративной схеме (Оценка сложности).

Program Lex;

const n=4; {порядок перестановок}

var p:array [0..n] of 0..n; { текущая перестановка}

k : 0..n; j,r,m : 0..n;

procedure invert(m:integer);

var i,j:integer;

begin

i:=m;

j:=n;

while i<j do

begin r:=p[j];

p[j]:=p[m];

p[m]:=r;

j:=j-1;

im:=im+1

end

end;

begin

for k:=0 to n do p[k]:=k; {задание начальной перестановки}

k:=1;

while k<> 0 do

begin

for k:=1 to n do write(p[k]); writeln; {вывод перестановки}

k:=n-1; while p[k]>p[k+1] do k:=k-1; {поиcк k}

j:=n; while p[k]>p[j] do j:=j-1; {поиск j}

r:=p[k]; p[k]:=p[j]; p[j]:=r; {транспозиция рк и pj }

invert(k+1); {инвертирование хвоста перестановки}

end;

end.

Л1) В первой перестановке элементы располагаются в возрастающей последовательности, в последней - в убывающей (докажите это свойство для произвольного n).

Л2) Последовательность всех перестановок можно разбить на n блоков длины (n-1)!, соответствующих возрастающим значениям элемента в первой позиции. Остальные n-1 позиций блока, содержащего элемент p в первой позиции, определяют последовательность перестановок множества {1,...,n}/{р} в лексикографическом порядке.

Л3) Последовательность всех перестановок можно разбить на n*(n-1)*...*(n-k+1) блоков выбором значений р₁,...,p_k элементов, расположенных на первых k позициях. При этом блок p₁,...,p_k предшествует блоку q₁,...,q_k, если р₁,...,p_k меньше q₁,...,q_k в лексикографическом порядке. Кроме того, для перестановок каждого такого обобщенного блока элементы, расположенные с k+1-ой по n-ую позиции, представляют собой генерацию перестановок этих элементов в лексикографическом порядке.

Л4) Любая текущая перестановка является заключительной для некоторого обобщенного блока. Этот блок определяется элементами текущей перестановки, расположенными на позициях в конце перестановки и представляющими собой максимально возможную убывающую последовательность значений элементов перестановки. Справедливость последнего замечания следует из свойства Л1 лексикографического порядка.

Оценим их число. Пусть T_k - число транспозиций, выполняемых при вызове оператора LEC(n-k+1), т. е. T_k –число транспозиций, которые необходимо выполнить при генерации перестановок k-го порядка. Имеем

T_k = k * T_k_-1+ (k-1) * (1 + ë(k-1)/2û ) =

k * T_k_-1+ (k-1)*ë(k+1)/2û, где ëaû = ‘целой части числа a’.

Первое слагаемое определяет число транспозиций при вызовах оператора LEC(n-k), а второе - число транспозиций, выполняемых в операторах {3} и {4}. Заметим, что T₁=0.

Для решения этого рекуррентного уравнения сделаем замену переменной. Пусть S_k=T_k+ë(k+1)/2û, тогда

S₁= 1, S_k = k * (S_k_-1+ d_k-1),

где d_k=0, если k нечетно, и d_k=1, если k четно.

Решение этого рекуррентного соотношения легко получается по индукции:

S_k= ,

т. е.

T_k= - ë(k+1)/2û.

Учитывая, что »ch(1)»1.543 и ë(k+1)/2û=o(k!). получаем

T_k»k!_*ch(1),

т. е. на генерирование одной перестановки в лексикографическом порядке требуется в среднем ch(1)»1.543 транспозиций.

Перейдем теперь к оценке числа сравнений элементов перестановки в операторах {поиск k}и {поиск j}; обозначим это число С_n.

Определим С_n как функцию от С_n-1. Отметим, что при генерации каждого из n блоков, определенных в Л2, требуется C_n_-1 сравнений, а таких блоков n. Далее, при переходе от одного блока к другому оператор {поиск k} выполняется n-1 раз, а оператор {поиск J} при переходе от блока p к блоку p+1 (1£p<n) - p раз, т. е.

C_n= n*C_n_-1+(n-1)*(n-1)+1+...+(n-1), C₁=0

или

C_n= n*C_n_-1+(n-1)*(3n-2)/2 C₁=0.

Пусть D_n=C_n+(3n+1)/2, тогда D₁=2, D_n=n*D_n_-1+3/2,

и по индукции получаем

D_n=n!*( + )

или

учитывая, что е= ,получаем D_n»n!*( e-1).

Тогда, C_n» n!*( e-1)-(3n+1)/2, учитывая, что (3n+1)/2=о(n!),получаем

C_n/n!»( e-1)

Таким образом, на генерирование одной перестановки алгоритмом LEX в среднем выполняется ( e-1)» 3.077 сравнений.

program gen (input, output);

const n= ; n1= ; {n1=n+1}

var p:array [0..n1] of 1..n1;

{p[1],...,p[n] - генерируемая перестановка}

r:array [1..n] of 1..n;

{r - перестановка, обратная к p[1],...,p[n] }

d:array [1..n] of -1..1; {d - вектор направлений}

i,j,k,t: integer;

begin

for i:=1 to n do

begin p[i]:=i; r[i]:=i; d[i]:=-1 end;

d[1]:=0; p[0]:=n1; p[n1]:=n1; i:=n;

while i<>1 do

begin

for j:= 1 to n do write (p[j]); writeln;

i:=n;

while p[ r[i]+d[i] ] > i do

begin

{*} d[i]:=-d[i]; i:=i-1 {поиск перемещаемого элемента}

end;

k:=r[i]; t:=k+d[i];

j:=p[t]; p[k]:=j; p[t]:=i; {транспозиция элементов}

r[i]:=r[j]; r[j]:=k {корректировка обратной перестановки}

end

end.

Билет 4. Записи

Структурированный (сложный) тип – тип, который строит новые типы на основе старых по средствам структуризации.

Запись – статистический тип данных, объединяющий компоненты различных типов в один тип

Представляет собой совокупность ограниченного числа логически связанных компонент, принадлежащих к разным типам. Компоненты записи называются полями, каждое из которых определяется именем. Поле записи содержит имя поля, вслед за которым через двоеточие указывается тип этого поля. Поля записи могут относиться к любому типу, допустимому в языке Паскаль, за исключением файлового типа.

Описание записи в языке Паскаль осуществляется с помощью служебного слова RECORD, вслед за которым описываются компоненты записи. Завершается описание записи служебным словом END.

Например, телефонный справочник содержит фамилии и номера телефонов, поэтому отдельную строку в таком справочнике удобно представить в виде следующей записи:

type TRec = Record

FIO: String[20];

TEL: String[7]

end;

var rec: TRec;

Записи отличаются от массивов тем, что , во-первых, к компонентам записи необходимо обращаться по имени, во-вторых, все компоненты записи необязательно должны принадлежать одному типу.

Обращение к записи в целом допускается только в опеpатоpах пpисваивания, где слева и спpава от знака пpисваивания используются имена записей одинакового типа. Во всех остальных случаях опеpиpуют отдельными полями записей. Чтобы обpатиться к отдельной компоненте записи, необходимо задать имя записи и чеpез точку указать имя нужного поля, напpимеp:

TRec.FIO

TRec.TEL

Type Ticket: record

Arrive: string [20];

VagonType: {‘плац’, ‘купе’, ‘СВ’ };

Time: record

Date: string;

Hour: integer;

Minute:integer;

End;

Оператор With:

With x do

Arrive:=’Moskow’;

VagonType:=’купе’;

VagonType:= y.VagonType;

End;

Билет 5

Множество

Понятие множества в языке Паскаль основывается на математическом представлении о конечных множествах: это ограниченная совокупность различных элементов. Для построения конкретного множественного типа используется перечисляемый или интервальный тип данных. Тип элементов, составляющих множество, называется базовым типом.

Множественный тип описывается с помощью служебных слов SET OF, например:

type M = Set of B;

Здесь М - множественный тип, В - перечислимый тип.

Пример описания переменной множественного типа:

type

M = Set of 'A'..'D';

var

MS: M;

Принадлежность переменных к множественному типу может быть определена прямо в разделе описания переменных:

var C: Set of 0..7;

Следует отметить, что описания множеств с использованием типа SET OF фактически сводится к представлению множеств в виде упакованных булевских массивов и реализация соответствующих операций над ними. Но для удобства пользователя все это выполняется в процессе трансляции программы.

Оператор in:

5 in X = true

False

Объединение = +

Пересечение = *

Вычитание = -

Билет 6. Генерация множеств в лексикографическом порядке.

Определение. Пусть A=(x₁,…,x_n) и B=(y₁,…,y_n), x_i,y_iÎ{0,1}, 1£i£n. Будем говорить, что множество А предшествует множеству B лексикографическом порядке ,если существует i, 1£i£n, x_i<y_i и x_j=y_j для любого j, 1£j<i; обозначим это А<B.

Пусть 0 £ a < b <2ⁿ, a, b - натуральные; представим a и b в двоичной системе с выписыванием всех n двоичных разрядов и пусть a = и b = . Доказать, что тогда (x₁,...,x_n) < (y₁,...,y_n).