Контрольные задания

1. Разработайте алгоритм и программу расстановки ферзей на шахматном поле таким образом, чтобы ни один из них не бил другого,

2. Разработайте программу игры «Ханойские башни».

3. Предложите другие модификации алгоритма полного тура коня.

4.5. Важнейшие невычислительные алгоритмы (поиск и сортировка)

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

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

Существуют различные алгоритмы сортировки данных. И понятно, что не существует универсального, наилучшего во всех отношениях алгоритма сортировки. Эффективность алгоритма зависит от множества факторов, среди которых можно выделить основные:

• числа сортируемых элементов;

• степени начальной отсортированности (диапазона и распределения значений сортируемых элементов);

• необходимости исключения или добавления элементов;

• доступа к сортируемым элементам (прямого или последовательного).

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

В этой связи выделяют сортировку двух классов объектов: массивов (внутреняя сортировка) и файлов (внешняя сортировка).

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

a₁, а₂… а_n → a_k1, a_k2…a_kn

F(a_k1) < F(a_k2) < F(a_kn)

где знак неравенства понимается в смысле того порядка, который установлен в сортируемом множестве.

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

Поиск. Для определенности примем, что множество, в котором осуществляется поиск, задано как массив

var a:array[0..N] of item;

где item- заданный структурированный тип данных обладающий хотя бы одним полем (ключом), по которому необходимо проводить поиск.

Результатом поиска, как правило, служит элемент массива, равный эталону, или отсутствие такового.

Линейный поиск.Процедура заключается в простом последовательном просмотре всех элементов массива и сравнении их с эталоном X.

i:=0;

while (i<=N)and(a[i]<>X) do i:=i+1 end.

Часто бывает целесообразнее осуществлять поиск с барьером, вводя дополнительно граничный элемент массива a[N+l]:

a[N+l]:=X;i:=0;

while a[i]<>X do i:=i+l end.

Равенство i= N + 1 означает, что совпадений не было, т.е. что эталонный элемент отсутствует.

Попытайтесь разобраться в чем различие представленных конструкций. Приведем пример программы поиска эталона х в массиве а[0..n].

Программа 42

program poiskl; (*линейный поиск*) const N=8;

type item= integer;

var a : array[0..n] of item; i :integer; x : item;

begin

(*задание искомого массива*) for i:=0 to N do

begin writet'Bвeди элемент a[ ',i, ']= '); readln(a[i]);

end;

writeln; write('введи эталон x= '); readln(x);

(* линейный поиск*)

i:=0; while (i<=N)and(a[i]<>X) do begin i:=i+l end;

(*вывод результата*)

if i<=N then write( 'найден элемент на ',i, ' месте ') else write( 'такого элемента в массиве нет ') ;

readin

end.

Поиск делением пополам.В большинстве случаев процедура поиска применяется к упорядоченным данным (телефонный справочник, библиотечные каталоги и пр.). В подобных ситуациях эффективным алгоритмом является поиск делением пополам. В этом методе сравнение эталона Х осуществляется с элементом, расположенным в середине массива и в зависимости от результата сравнения (больше или меньше) дальнейший поиск проводится в левой или в правой половине массива.

L:=0; R:=N; while L<R do

begin

m:=(L+R) div 2;

if a[m]<X then L:=m+l else R:=m;

end;.

Например, пусть эталонный ключ х=13, а в массиве имеются следующие элементы:

а[0]=1; а[1]=3; а[2]=4; а[3]=7; а[4]=8; а[5]=9; а[6]=13; а[7]=20; а[8]=23.

Бинарный процесс поиска показан ниже:

1 3 4 7 8 9 13 20 23 - элементы массива

0 1 2 3 4 5 6 7 8- порядковые номера элементов

L m R

L m R

a[m]=x=>поиск закончен иm= 6

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

Программа 43

program poisk2; (*поиск делением пополам*)

const N=8;

type item= integer;

var a: array[0..n] of item; i, L, R, m:integer; x: item; f:

boolean;

begin

(*задание искомого массива*)

for i:=0 to N do

begin write( 'введи элемент a[',i, '1= '); readln(a[i])

end;

writeln; write( 'введи эталон х= '); readln(x);

(*бинарный поиск*)

L:=0; R:=N; f:=false;

repeat m:=(L+R) div 2; if a[m]=X then f:=true;

if a[m]<X then L:=m+l

else R:=m;

writeln(m,L,R);

until (L>=R)or(f);

(*вывод результата*)