ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6812
Скачиваний: 51
276
linep(5,u); c(i); linep(3,u);
d(i); linep(l,u); delay(2000) until
i=5;
settextstyle(0,0,1) ;
outtextxy(200, 470, 'КРИВЫЕ СЕРПИНСКОГО S1 - S5');
readln; closegraph
end.
В 1891 г. Д. Гильберт открыл серию рекурсивных кривых, которые получили название кри-
вых Гильберта. Кривая Гильберта Hi, подобно кривым Серпинского, может быть получена из че-
тырех экземпляров кривой H(i-l) вдвое меньшего размера, повернутых должным образом и соеди-
ненных отрезками. Ниже приводится программа, рисующая узор из шести кривых Гильберта.
Программа 41
program hilbert;
uses crt,graph;
const
sq=448;
var i,x0,y0,x,y,t,u,gd,gm:integer; ch:char;
procedure linep(t,u:integer);
var xl,yl:integer;
begin x:=x+round(u*cos(t*pi/4)); y:=y-round(u*sin(t*pi/4)) ;
lineto (x,y) ;
end;
procedure b(i:integer); forward;
procedure с(i:integer); forward;
procedure d(i:integer); forward;
procedure a(i:integer);
begin
if i>0 then begin d(i-l); linep(4,u); a(i-l); linep(6,u);
a(i-l); linep(0,u); b(i-l)
end end;
procedure b;
begin
if i>0 then begin c(i-l); linep(2,u); b(i-l); linep(0,u);
b(i-l); linep(6,u); a(i-l)
end end;
procedure c;
begin
if i>0 then begin b(i-l); linep(0,u); c(i-l); linep(2,u);
c(i-l); linep(4,u); d(i-l)
end end;
procedure d;
begin
if i>0 then begin a(i-l); linep(6,u); d(i-l); linep(4,u);
d(i-l); linep(2,u); c(i-l)
end end;
begin gd:=0; initgraph(gd, gm, ' '); x0:=320; y0:=240; u:=sq;
i:=0;
repeat
i:=i+l; u:=u div 2;
x0:=x0+(u div 2); y0:=y0-(u div 2) ;
x:=x0; y:=y0; setcolor(2*i);
moveto(x,y); a(i); delay(2000) until i=6;
settextstyle(0,0,1) ;
277
outtextxy(220,470, 'КРИВЫЕ ГИЛЬБЕРТА HI - Н6');
readin; closegraph
end.
Контрольные задания
1. Разработайте алгоритм и программу расстановки ферзей на шахматном поле таким обра-
зом, чтобы ни один из них не бил другого,
2. Разработайте программу игры «Ханойские башни».
3. Предложите другие модификации алгоритма полного тура
коня.
4.5. ВАЖНЕЙШИЕ НЕВЫЧИСЛИТЕЛЬНЫЕ АЛГОРИТМЫ
(ПОИСК И СОРТИРОВКА)
Одними из важнейших процедур обработки структурированной информации являются
сор-
тировка и поиск
. Сортировкой называют процесс перегруппировки заданной последовательности
(кортежа) объектов в некотором определенном порядке. Определенный порядок (например, упо-
рядочение в алфавитном порядке, по возрастанию или убыванию количественных характеристик,
по классам, типам и т.п) в последовательности объектов необходим для удобства работы с этими
объектами. В частности, одной из целей сортировки является облегчение последующего поиска
элементов в отсортированном множестве. Под поиском подразумевается процесс нахождения в
заданном множестве объекта, обладающего свойствами или качествами задаваемого априори эта-
лона (или шаблона).
Очевидно, что с отсортированными (упорядоченными) данными работать намного легче,
чем с произвольно расположенными. Упорядоченные данные позволяют эффективно их обнов-
лять, исключать, искать нужный элемент и т.п. Достаточно представить, например, словари, спра-
вочники, списки кадров в неотсортированном виде и сразу становится ясным, что поиск нужной
информации является труднейшим делом, если не невозможным.
Существуют различные алгоритмы сортировки данных. И понятно, что не существует уни-
версального, наилучшего во всех отношениях алгоритма сортировки. Эффективность алгоритма
зависит от множества факторов, среди которых можно выделить основные:
• числа сортируемых элементов;
• степени начальной отсортированности (диапазона и распределения значений сортируемых
элементов);
• необходимости исключения или добавления элементов;
• доступа к сортируемым элементам (прямого или последовательного).
Принципиальным для выбора метода сортировки является последний фактор. Если данные
МОГУТ
быть расположены в оперативной памяти, то к любому элементу возможен прямой доступ.
Удобной структурой данных в этом случае выступает
массив
сортируемых элементов. Если дан-
ные размещены на внешнем носителе, то к ним можно обращаться лишь последовательно. В каче-
стве структуры подобных данных можно взять
файловый тип.
В этой связи выделяют сортировку двух классов объектов: массивов (внутреняя сортиров-
ка) и файлов (внешняя сортировка).
Процедура сортировки предполагает, что при наличии некоторой упорядочивающей функ-
ции
F
расположение элементов исходного множества меняется таким образом, что
a
1
, а
2
… а
n
→ a
k1
, a
k2
…a
kn
F(a
k1
) < F(a
k2
) < F(a
kn
)
где знак неравенства понимается в смысле того порядка, который установлен в сортируе-
мом множестве.
Поиск
и сортировка являются классическими задачами теории обработки данных, решают
эти задачи с помощью множества различных алгоритмов. Рассмотрим наиболее популярные из
них.
Поиск
. Для определенности примем, что множество, в котором осуществляется поиск, за-
дано как массив
278
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.
Бинарный процесс поиска показан ниже:
279
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);
(*вывод результата*)
if f then write('найден элемент на ',m, ' месте')
else write('такого элемента в массиве нет ');
readln
end.
Сортировка массивов.
Как и в случае поиска определим массив данных:
var a: array [0.. N] of item
Важным условием сортировки массива большого объема является экономное использова-
ние доступной памяти. В прямых методах сортировки осуществляется принцип перестановки эле-
ментов «на том же месте». Ниже рассмотрим три группы сортировок: с помощью включения, вы-
бора и обмена.
Сортировка с помощью включения
Кто играл в карты, процедуру сортировки включения-
ми осуществлял многократно. Как правило, после раздачи карт игрок, держа карты веером в руке,
переставляет карты с места на место стремясь их расположить по мастям и рангам, например, сна-
чала все тузы, затем короли, дамы и т.д. Элементы (карты) мысленно делятся на уже «готовую по-
следовательность» и неправильно расположенную последовательность. Теперь на каждом шаге,
начиная с i
=
2, из неправильно расположенной последовательности извлекается очередной эле-
мент и перекладывается в готовую последовательность на нужное место.
for i:=2 to N do begin
x:=a[i];
<включение х на соответствующее место готовой последо-
вательности a[l],...,a[i]>
end
Поиск подходящего места можно осуществить одним из методов поиска в массиве, описан-
ным выше. Затем
х
либо вставляется на свободное место, либо сдвигает вправо на один индекс
всю левую сторону. Схематично представим алгоритм для конкретного примера:
Исходные элементы
23
34
12
13
9
280
i=2
23
34
12
13
9
i=3
12
23
34
13
9
i=4
12
13
23
34
9
i=5
9
12
13
23
34
В алгоритме поиск подходящего места осуществляется как бы просеиванием
х
при движе-
нии по последовательности и сравнении с очередным a[j]. Затем
х
либо вставляется на свободное
место, либо a[j] сдвигается вправо и процесс как бы «уходит» влево.
Программа 44
program sortirov)ca_l;
(*сортировка включением по линейному поиску*) const N=5;
type item= integer;
var a: array[l..n] of item; i, j: integer; х: item;
begin (*задание искомого массива*)
for i:=l to N do begin write('введи элемент a[',i,']=');
readln(a[i]) end;
for i:=l to N do begin write(a[i], ' ' );
end;
writeln;
(*алгоритм сортировки включением*) .for i:=2 to n do begin
x:=a[i]; j:=i; a[0]:=x; (*барьер*)
while x<a[j-l] do
begin
a[j]:=a[j-l); j:=j-l;
end;
a[j]:=x; .
(for k:=l to n do write(a[k.l, ' ') end; writeln;) end;
(*вывод отсортированного массива*) for
i:=l to N do begin .
write(a[i], ' ') ;
end;
readln;
end.
В рассмотренном примере программы для анализа процедуры пошаговой сортировки мож-
но рекомендовать использовать трассировку каждого прохода по массиву с целью визуализации
его текущего состояния. В тексте программы в блоке непосредственного алгоритма сортировки в
фигурных скобках находится строка, которая при удалении скобок выполнит требуемое (параметр
k
необходимо описать в разделе переменных - var k:integer). Во всех последующих программах
сортировки легко осуществить подобную процедуру.
Вернемся к анализу метода прямого включения. Поскольку готовая последовательность
уже упорядочена, то алгоритм улучшается при использовании алгоритма поиска делением попо-
лам. Такой способ сортировки называют
методом двоичного
включения.
Программа 45
program sortirovka_2;
(*сортировка двоичным включением*) const N=5;
type item= integer;
var a: array(l..n] of item; i, j, m, L, R: integer; x: item;
begin
(*задание элементов массива*) for i:=l to
N do
begin write('Bведи элемент a[',i,']= '-); readln(a[i]) ;
end;
for i:=l to N do