Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
5
Лекция 8. Алгоритмы сортировки массивов.
Простой выбор.
Данный метод основан на выборе минимального элемента и обмене его с текущим элементом.
program sort_vybor;
uses crt;
const n=5;
type mas=array[1..n]of integer;
var i,j,nom:byte; a:mas; v:integer;
begin
clrscr;
for i:=1 to n do readln(a[i]);
for i:=1 to n-1 do
begin
nom:=i;
for j:=i+1 to n do
begin
if a[nom]>=a[j] then nom:=j;
end;
if nom<>i then
begin
v:=a[i];
a[i]:=a[nom];
a[nom]:=v
end
end;
for i:=1 to n do writeln(a[i]);
readkey;
end.
Простой обмен - метод "Пузырька".
Метод "пузырька" основан на том, что сравниваются пары соседних элементов и производится обмен значений таким образом, чтобы больший элемент оказался справа. При этом максимальный элемент как бы "всплывает" вверх.
program sort_puzirek;
uses crt;
const n=5;
type mas=array[1..n] of integer;
var a:mas; i:byte; v:integer; p:boolean;
begin
clrscr;
for i:=1 to n do readln(a[i]);
writeln;
p:=true;
while p<>false do
begin
p:=false;
for i:=1 to n-1 do
begin
if a[i]>=a[i+1] then
begin
v:=a[i];
a[i]:=a[i+1];
a[i+1]:=v;
p:=true;
end;
end;
end;
for i:=1 to n do writeln(a[i]);
readkey;
end.
Простые вставки.
Данный метод основан на поиске минимального, вставке его в начало фрагмента массива и сдвиге вправо оставшейся части фрагмента.
Просматривать последовательно x2,…,xn и каждый новый элемент вставлять на подходящее место в уже упорядоченную совокупность x1,…,xi-1. Это место определяется последовательным сравнением xi с упорядоченными элементами x1,…,xi-1.
program sort_prostye_vstavki;
uses crt;
const n=5;
type mas=array[1..n] of integer;
var a:mas; i,j,k:byte; v:integer;
begin
clrscr;
for i:=1 to n do readln(a[i]);
writeln;
for i:=2 to n do
begin
for j:=1 to i-1 do
begin
if a[i]<=a[j] then
begin
v:=a[i];
for k:=i downto j+1 do
a[k]:=a[k-1];
a[j]:=v;
end;
end;
end;
for i:=1 to n do writeln(a[i]);
readkey;
end.
Бинарные вставки.
Усовершенствованная разновидность метода сортировки простыми вставками. Место, на которое надо вставить xi, в уже упорядоченную совокупность x1,…,xi-1, определяется алгоритмом деления пополам. Получается новый алгоритм сортировки - сортировка бинарными вставками. По числу сравнений алгоритм сортировки бинарными вставками лучше, чем рассмотренные выше алгоритмы.
program sort_binary_vstavki;
uses crt;
const n=8;
type mas=array[1..n] of integer;
var a:mas; i,j,k,p,q,s:byte; v:integer;
begin
clrscr;
for i:=1 to n do readln(a[i]);
writeln;
for i:=2 to n do
begin
p:=1; q:=i;
while p<q do
begin
s:=(p+q) div 2;
if a[s]<a[i] then p:=s+1 else q:=s;
end;
if a[i]<a[s] then j:=s;
if a[i]>a[s] then j:=s+1;
v:=a[i];
for k:=i downto j+1 do
a[k]:=a[k-1];
a[j]:=v;
end;
for i:=1 to n do writeln(a[i]);
readkey;
end.
Использование модуля CRT
при оформлении результатов работы программы.
Модуль CRT содержит константы, переменные, процедуры и функции, предназначенные для работы с консолью. Если стандартные процедуры ввода/вывода реализуются через операционную систему, то модуль CRT позволяет работать с BIOS и непосредственно с видеопамятью.
При работе с экраном через модуль CRT весь экран разбивается на отдельные строки, а каждая строка - на отдельные позиции, в каждую из которых можно поместить один символ (в том числе и пробел). Таким образом весь экран разбивается на отдельные неделимые прямоугольные элементы. Положение каждого элемента экрана определяется его координатами X (номер столбца, в котором расположен элемент) и Y (номер строки). Для каждого элемента можно задать цвет фона (задний план - BackGround) и цвет символа (передний план). Кроме того, символ можно сделать мерцающим. Вся эта информация - атрибуты символа - помещается в одном байте информации следующим образом:
|
Биты |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
М |
Ф |
Ф |
Ф |
С |
С |
С |
С |
Буквой М обозначен бит мерцания (символ мерцает, если в этом бите установлена 1), буквами Ф - биты, в которые записывается код цвета фона (биты 4-6), буквами С - биты, в которые помещается код цвета символа (биты 0-3).
Модуль CRT позволяет работать не только со всем экраном, но и выделять в нем прямоугольные окна. Любое окно задается своим левым верхним и правым нижним углом. Эти углы, так же как и положение любого объекта на экране задаются двумя координатами X и Y. При работе в окне координаты отсчитываются от левого верхнего угла окна. При запуске программы выделенное окно совпадает по размеру со всем экраном. По умолчанию установлен режим работы адаптера - 25 строк по 80 позиций в каждой, соответственно координаты такого окна - (1,1) и (80,25).
Коды цветов.
|
Black |
0 |
Черный |
|
Blue |
1 |
Синий |
|
Green |
2 |
Зеленый |
|
Cyan |
3 |
Голубой |
|
Red |
4 |
Красный |
|
Magenta |
5 |
Фиолетовый |
|
Brown |
6 |
Коричневый |
|
LightGray |
7 |
Светло-серый |
|
DarkGray |
8 |
Темно-серый |
|
LightBlue |
9 |
Светло-синий |
|
LightGreen |
10 |
Светло-зеленый |
|
LightCyan |
11 |
Светло-голубой |
|
LightRed |
12 |
Розовый |
|
LightMagenta |
13 |
Светло-фиолетовый |
|
Yellow |
14 |
Желтый |
|
White |
15 |
Белый |
|
Blink |
128 |
Мерцание символа |
Цвета с кодами от 0 до 7 включительно можно использовать как для символов, так и для фона. Остальные цвета и код мерцания можно использовать только для символов.
Процедуры модуля CRT.
ClrScr - Очистка экрана: процедура очищает текущее окно, заполняя его цветом фона, и помещает курсор в его верхний левый угол с координатами (1,1).
TextMode(Mode: Word) - задание текстового режима: устанавливает текстовый режим, заданный параметром Mode, увеличивает текущее окно до целого экрана. Некоторые значения параметра Mode:
|
0 |
40х25 черно-белый для цветного адаптера |
|
1 |
40х25 цветной для цветного адаптера |
|
2 |
80х25 черно-белый для цветного адаптера |
|
3 |
80х25 цветной для цветного адаптера |
TextBackground(Color: Byte) - задание цвета фона. Для того, чтобы все окно изменило цвет фона, необходимо после данной процедуры вызвать процедуру ClrScr, иначе будет изменяться лишь фон отдельных элементов при их вводе или выводе.
TextColor(Color: Byte) - задание цвета символов и параметра мерцания.
Window(x1,y1,x2,y2: Byte) - задает размеры окна на экране и помещает курсор в левый верхний угол окна с координатами (1,1).
Delay(Ms: Word) - Задает задержку выполнения программы в миллисекундах.
GotoXY(X,Y:Byte) - перемещает курсор к элементу экрана с заданными координатами (координаты отсчитываются от левого верхнего угла текущего окна).
DelLine - удаляет строку, в которой находится курсор.
InsLine - вставляет пустую строку на экране в месте расположения курсора и заполняет ее цветом фона.
Функции модуля CRT.
WhereX: Byte - возвращает текущую координату X курсора.
WhereY: Byte - возвращает текущую координату Y курсора.
Readkey: Char - считывает символ с клавиатуры.
KeyPressed: Boolean - анализирует нажатие клавиши клавиатуры (за исключением вспомогательных клавиш Shift, Alt, NumLock и т.п.). Результат - True, если клавиша на клавиатуре нажата, False - клавиша не нажата.
Пример: Установить текстовый режим 40х25 для цветного адаптера. Разместить в центре экрана окно, размерами 15х15. Установить цвет фона - голубой. Вывести в окне 5 раз слово "ПРИВЕТ" таким образом, чтобы текст в результате разместился по центру окна, и каждая строка была нового цвета. Определить позицию курсора и вывести результат в нижней строке окна слева. По нажатию любой клавиши необходимо вернуть экран в режим 2.