Файл: ответы.doc

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

{==== Программный пример 4.3 ====}

unit Queue; { Очередь FIFO - кольцевая }

Interface

const SIZE=...; { предельный размер очереди }

type data = ...; { эл-ты могут иметь любой тип }

Procesure QInit;

Procedure Qclr;

Function QWrite(a: data) : boolean;

Function QRead(var a: data) : boolean;

Function Qsize : integer;

Implementation { Очередь на кольце }

var QueueA : array[1..SIZE] of data; { данные очереди }

top, bottom : integer; { начало и конец }

Procedure QInit; {** инициализация - начало=конец=1 }

begin top:=1; bottom:=1; end;

Procedure Qclr; {**очистка - начало=конец }

begin top:=bottom; end;

Function QWrite(a : data) : boolean; {** запись в конец }

begin

if bottom mod SIZE+1=top then { очередь полна } QWrite:=false

else begin

{ запись, модификация указ.конца с переходом по кольцу }

Queue[bottom]:=a; bottom:=bottom mod SIZE+1; QWrite:=true;

end; end; { QWrite }

Function QRead(var a: data) : boolean; {** выборка из начала }

begin

if top=bottom then QRead:=false else

{ запись, модификация указ.начала с переходом по кольцу }

begin a:=Queue[top]; top:=top mod SIZE + 1; QRead:=true;

end; end; { QRead }

Function QSize : integer; {** определение размера }

begin

if top <= bottom then QSize:=bottom-top

else QSize:=bottom+SIZE-top;

end; { QSize }

END.

Очереди с приоритетами

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

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

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

2. Моделирование как процесс познания. Математическая модель, понятие вычислительного эксперимента и его структура.

Моделирование – метод познания. Модель – неполное описание объекта относительно поставленной задачи.

Математическая модель – модель описанная на математическом языке.

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

Вычислительный эксперимент можно разделить на этапы:

1)Постановка задачи

2)Разработка математической модели

3)Разработка алгоритма

4)Программная реализация

5)Проведение расчетов

6)Анализ результата

7)Обработка результата

Последний этап: этап принятия решения

3. Составить программу, которая формирует стек, добавляя в него произвольное количество компонент.

Билет 37

1. Улучшенные методы сортировки. Сортировка Шелла, Хоара, улучшенная сортировка выбором. Сортировка с помощью дерева.

Сортировка – упорядочение элементов множества по возрастанию или убыванию.

Сортировку можно разбить на 2 вида:

1. Простые методы сортировки – выбором, пузырьковая, вставками.

2. Улучшенные методы сортировки – Шелла, Хоара.

Сортировка Шелла - общая идея заимствована из сортировки вставками и основывается на уменьшении шагов(расстояние между сортируемыми элементами на конкретном этапе сортировки). Сначала сортируются все элементы, отстоящие друг от друга на три позиции. Затем сортируются элементы, расположенные на расстоянии двух позиций. Наконец, сортируются все соседние элементы.

Проход 1 f d a c b e

\___\___\___/ / /

\___\_____/ / /

\_______/

Проход 2 c b a f d e

\___\___|___|___/ /

\______|______/

Проход 3 a b c d e f

|___|___|___|___|___|

Результат a b c d e f

Конкретная последовательность шагов может быть и другой. Единственное правило состоит в том, чтобы последний шаг был равен 1. Например, такая последовательность: 9, 5, 3, 2, 1

/* Сортировка Шелла. */

void shell(char *items, int count)

{

register int i, j, gap, k;

char x, a[5];

a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;

for(k=0; k < 5; k++) {

gap = a[k];

for(i=gap; i < count; ++i) {

x = items[i];

for(j=i-gap; (x < items[j]) && (j >= 0); j=j-gap)

items[j+gap] = items[j];

items[j+gap] = x;

}

}

}

Внутренний цикл for имеет два условия проверки. Очевидно, что сравнение x<items[j] необходимо для процесса сортировки. Выражение j>=0 предотвращает выход за границу массива items. Эти дополнительные проверки в некоторой степени понижают производительность сортировки Шелла.

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

Быстрая сортировка Хоара – в ее основе лежит сортировка обменами.

Быстрая сортировка построена на идее деления. Общая процедура заключается в том, чтобы выбрать некоторое значение, называемое компарандом(операнд в операции сравнения. Иногда называется также основой и критерием разбиения) ,а затем разбить массив на две части. Все элементы, большие или равные компаранду, перемещаются на одну сторону, а меньшие — на другую. Потом этот процесс повторяется для каждой части до тех пор, пока массив не будет отсортирован. Например, если исходный массив состоит из символов f e d a c b, а в качестве компаранда используется символ d, первый проход быстрой сортировки переупорядочит массив следующим образом:

Начало f e d a c b

Проход 1 b c a d e f

Затем сортировка повторяется для обеих половин массива, то есть b с а и d e f. Как вы видите, этот процесс по своей сути рекурсивный, и, действительно, в чистом виде быстрая сортировка реализуется как рекурсивная функция.

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

/* Функция, фызывающая функцию быстрой сортировки. */

void quick(char *items, int count)

{

qs(items, 0, count-1);

}

/* Быстрая сортировка. */

void qs(char *items, int left, int right)

{

register int i, j;

char x, y;

i = left; j = right;

x = items[(left+right)/2]; /* выбор компаранда */

do {

while((items[i] < x) && (i < right)) i++;

while((x < items[j]) && (j > left)) j--;

if(i <= j) {

y = items[i];

items[i] = items[j];

items[j] = y;

i++; j--;

}

} while(i <= j);

if(left < j) qs(items, left, j);

if(i < right) qs(items, i, right);

}

В этой версии функция quick() готовит вызов главной сортирующей функции qs(). Это обеспечивает общий интерфейс с параметрами items и count, но несущественно, так как можно вызывать непосредственно функцию qs() с тремя аргументами.

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

Сортировка выбором

Отыскивается максимальный (минимальный) элемент и переносится в конец массива. Затем этот метод применяется ко всем элементам, кроме последнего (он уже находится на своем месте).

Другой вариант метода - перенос найденного элемента в начало массива и последующее применение метода ко всем элементам, кроме первого.

Сортировка двоичным деревом

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

Вместо 'предшественник' и 'преемник' также употребляют термины 'родитель' и 'сын'. Все элементы дерева также называют 'узлами'. При добавлении в дерево нового элемента его последовательно сравнивают с нижестоящими узлами, таким образом вставляя на место. Если элемент >= корня - он идет в правое поддерево, сравниваем его уже с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым, и так далее, пока есть сыновья, с которыми можно сравнить. Процесс построения дерева из последовательности 44 55 12 42 94 18 06 67: