2. Построение остовного дерева поиском в глубину (нерекурсивный вариант).

Билет № 6

1.Создание удобного пользовательского интерфейса: системы меню, окна для ввода, корректировки, просмотра информации. Модуль Crt.

Модуль Crt позволяет использовать все возможности дисплея и клавиатуры персонального компьютера РС, включая управление режимом экрана, расширенные коды клавиатуры, цвет, окна и звуковые сигналы.

Процедура TextColor. Определяет цвет выводимых символов: Procedure TextColor(Color: Byte);

Процедура TextBackground.Определяет цвет фона: Procedure TextBackground(Color: Byte);

Процедура ClrScr. Очищает экран или окно

Процедура Window. Определяет текстовое окно - область экрана, которая в дальнейшем будет рассматриваться процедурами вывода как весь экран.

Процедура GotoXY. Переводит курсор в нужное место экрана или текущего окна. Заголовок процедуры:

Функции whereX и WhereY. С помощью этих функций типа Byte можно определить текущие координаты курсора: WhereX возвращает его горизонтальную, a WhereY - вертикальную координаты.

Процедура DelLine. Уничтожает всю строку с курсором в текущем окне.

Функция KeyPressed. Возвращает значение типа Boolean, указывающее состояние буфера клавиатуры: False означает, что буфер пуст, a True - что в буфере есть хотя бы один символ, еще не прочитанный программой.

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

Dеlау - Выполняет задержку на указанное число миллисекунд.

2.Сортировка подсчетом

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов.

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

Program CountingSort;

Var A,B : array[1..1000] of byte;

C : array[byte] of integer;

N,i : integer;

Begin

{Определение размера массива A (N) и его заполнение}

…

{сортировка данных}

for i:=0 to 255 do

C[i]:=0;

for i:=1 to N do

C[A[i]]:=C[A[i]]+1;

for i:=1 to 255 do

C[i]:=C[i-1]+C[i];

for i:=N downto 1 do

begin

B[C[A[i]]]:=A[i];

C[A[i]]:=C[A[i]]-1; {здесь мы избегаем возможности записи двух одинаковых чисел в одну ячейку}

end;

{Вывод массива B}

…

End.

Билет № 7