Разработка программ с использованием алгоритмов перебора

Цель работы: познакомиться с особенностями алгоритмов перебора.

Задача работы: освоить способы программирования алгоритмов перебора.

 

Теоретическая часть

Перестановки

Задача: Напечатать все перестановки чисел 1..N (то есть последовательности длины N, в которые каждое из чисел 1..N входит ровно по одному разу).

First = (1,2,...,N) Last = (N,N-1,...,1)

Всего таких перестановок будет N!=N*(N-1)*...*2*1 (докажите!). Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).

Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i]<X[i+1]>...>X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1],...,X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1,...,N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:

procedure Next;

begin

{найти i: X[i]<X[i+1]>X[i+2]>...>X[N]};

{найти j: X[j]>X[i]>X[j+1]>...>X[N]};

{обменять X[i] и X[j]};

{X[i+1]>X[i+2]>...>X[N]};

{перевернуть X[i+1],X[i+2],...,X[N]};

end;

Теперь можно написать программу:

program Perestanovki;

type Pere=array [byte] of byte;

var N,i,j:byte;

X:Pere;

Yes:boolean;

procedure Next(var X:Pere;var Yes:boolean);

var i:byte;

procedure Swap(var a,b:byte); {обмен переменных}

var c:byte;

begin c:=a;a:=b;b:=c end;

begin

i:=N-1;

{поиск i}

while (i>0)and(X[i]>X[i+1]) do dec(i);

if i>0 then

begin

j:=i+1;

{поиск j}

while (j<N)and(X[j+1]>X[i]) do inc(j);

Swap(X[i],X[j]);

for j:=i+1 to (N+i) div 2 do Swap(X[j],X[N-j+i+1]);

Yes:=true

end

else Yes:=false

end;

begin

write('N=');readln(N);

for i:=1 to N do X[i]:=i;

repeat

for i:=1 to N do write(X[i]);writeln;

Next(X,Yes)

until not Yes

end.

Разбиения

Задача: Перечислить все разбиения целого положительного числа N на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно).

Пример: N=4, разбиения: 1+1+1+1, 2+1+1, 2+2, 3+1, 4.

First = (1,1,...,1) - N единиц Last = (N)

Чтобы разбиения не повторялись, договоримся перечислять слагаемые в невозрастающем порядке. Сказать, сколько их будет всего, не так-то просто (см.следующий пункт). Для составления алгоритма Next зададимся тем же вопросом: в каком случае i-ый член разбиения можно увеличить, не меняя предыдущих?

Во-первых, должно быть X[i-1]>X[i] или i=1. Во-вторых, i должно быть не последним эле ментом (увеличение i надо компенсировать уменьшением следующих). Если такого i нет, то данное разбиение последнее. Увеличив i, все следующие элементы надо взять минимально возможными, т.е. равными единице:

procedure Next;

begin

{найти i: (i<L) and ((X[i-1]>X[i]) or (i=1))}

X[i]:=X[i]+1;

{ L:= i + X[i+1]+...+X[L] - 1 }

X[i+1]:=...:=X[L]:=1

end;

Через L мы обозначили количество слагаемых в текущем разбиении (понятно, что 1<=L<=N). Программа будет выглядеть так:

program Razbieniya;

type Razb=array [byte] of byte;

var N,i,L:byte;

X:Razb;

procedure Next(var X:Razb;var L:byte);

var i,j:byte;

s:word;

begin

i:=L-1;s:=X[L];

{поиск i}

while (i>1)and(X[i-1]<=X[i]) do begin s:=s+X[i];dec(i) end;

inc(X[i]);

L:=i+s-1;

for j:=i+1 to L do X[j]:=1

end;

begin

write('N=');readln(N);

L:=N; for i:=1 to L do X[i]:=1;

for i:=1 to L do write(X[i]);writeln;

repeat

Next(X,L);

for i:=1 to L do write(X[i]);writeln

until L=1

end.

Отчет о выполнении

Отчет выполняется в электронном виде. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.

Текст задачи

Листинг алгоритма исполняемого файла

Скриншот интерфейса запускного файла программы

Контрольные вопросы:

1. Какие бывают комбинаторные объекты?

2. Что называется перестановкой?

3. Что такое разбиение?

4. Объясните алгоритм перестановки?

5. Объясните алгоритм разбиения?

6. Какие виды перебора вы знаете?

ЛАБОРАТОРНАЯ РАБОТА №6

Разработка программ с использованием алгоритмов сортировки

Цель работы: ознакомится с различными методами сортировки данных

Задача работы: освоить способы программирования алгоритмов сортировки.

 

Теоретический материал

Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировки - облегчить последующий поиск элементов в отсортированном множестве. В этом смысле сортировка присутствует почти во всех задачах обработки информации. С сортировкой связаны многие фундаментальные приемы построения алгоритмов, которые и будут нас интересовать в первую очередь. В частности, сортировка является идеальным примером огромного разнообразия алгоритмов, выполняющих одну и ту же задачу, многие из которых в некотором смысле оптимальные, а большинство имеет какие-либо преимущества по сравнению с остальными. Поэтому на примере сортировки мы убеждаемся в необходимости сравнительного анализа алгоритмов. Зависимость выбора алгоритмов от структуры данных - явление довольно частое, а в случае сортировки она настолько сильна, что методы сортировки обычно разделяются на две категории:

· сортировка массивов (внутренняя сортировка)

· сортировка файлов (внешняя сортировка).

 

ПОСТАНОВКА ЗАДАЧИ

ДАНО

ТРЕБУЕТСЯ

СВЯЗЬ

и последовательность является перестановкой исходной последовательности.

Основное требование к методам внутренней сортировки - экономное использование памяти. Это означает, что переупорядочивание элементов надо выполнять на том же месте.

Методы внутренней сортировки можно разбить на четыре основных класса в зависимости от лежащего в их основе приема:

· сортировка включением(вставкой),

· сортировка выбором,

· сортировка обменом,

· разделением.

·

СОРТИРОВКА ВКЛЮЧЕНИЕМ. Этот метод состоит в том, что на каждом шаге берут i -ый элемент последовательности и передают его в готовую отсортированную часть последовательность, вставляя его на свое место. Алгоритм сортировки включениями выглядит следующим образом:

FOR I:= 2 TO N DO

BEGIN X:= a[I];

< вставить X на подходящее место в a[1],a[2],...,a[I] >

END

СОРТИРОВКА ВЫБОРОМ. Этот метод основан на следующем

правиле. Выбирается минимальный (максимальный) элемент последовательности и обменивается с первым элементом (элементом) последовательности. Очевидно, один элемент при этом встанет на свое место в отсортированной части последовательности. Далее все выше изложенное надо повторить в не отсортированной части последовательности и т.д.

FOR I = 1 TO N-1 DO

BEGIN

< присвоить K индекс наименьшего элемента из a[I]...a[N] >

< поменять местами a[I] и a[K] >

END

СОРТИРОВКА ОБМЕНОМ. Алгоритм обмена основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут отсортированы все элементы. В качестве примера рассмотрим сортировку методом пузырька.

 

FOR I:= 2 TO N DO

FOR J:= N DOWNTO I DO

IF a[J-1] > a[J] THEN

BEGIN X:= a[J-1]; a[J-1]:= a[J]; a[J]:= X END

 

СОРТИРОВКА РАЗДЕЛЕНИЕМ. Алгоритм разделением основан на разбиении последовательности на две подпоследовательности по некоторому правилу. При этом каждая из них может не являться упорядоченной, но последовательное применение указанного правила приводит к упорядоченности последовательности. Примером этого класса алгоритмов является алгоритм быстрой сортировки.

Procedure quicksort(S);

begin

if < S содержит один элемент> then <возвратить S>

else begin <выбрать произвольный элемент a из S>;

<пусть S_1,S₂ и S₃ - последовательности элементов из S, соответственно меньших, равных и больших a>;

<возвратить quicksort(S₁), затем S_2,, затем quicksort(S₃) >

end

end

Внешняя сортировка, т.е. сортировка данных, находящихся на внешних запоминающих устройствах, имеет свои особенности.

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

Рассмотрим один из алгоритмов внешней сортировки.

 

СОРТИРОВКА СЛИЯНИЕМ. Главная идея, которая лежит в основе этой сортировки это представлении файла в виде постепенно увеличивающихся серий, т.е. упорядоченных подпоследовательностей. Если есть, по крайней мере, два файла и число серий в них равно или отличается на единицу, то последовательным слиянием отсортированных серий в новый файл можно уменьшить количество серий, по крайней мере, в два раза.

Отчет о выполнении

Отчет выполняется в электронном виде. Если заданий несколько, то повторить всю систему отчета необходимое количество раз.

Текст задачи

Листинг алгоритма исполняемого файла

Скриншот интерфейса запускного файла программы

Контрольные вопросы:

1. Что такое одномерный массив?

2. Что такое двухмерный массив?

3. Что такое сортировка массива?

4. Какие методы сортировки вы знаете?

ЛАБОРАТОРНАЯ РАБОТА №7