- •1. Двоичная система счисления.
- •2. Восьмеричная система счисления.
- •3. Шестнадцатеричная система счисления.
- •4. Сложение и вычитание в 2, 8 и 16 c/c.
- •2. Вещественные числа (числа с плавающей запятой).
- •3. Логические данные.
- •2. Зарезервированные слова.
- •X a8 alpha Massiv z52d9 eps Res_52_a ___75
- •6. Метка.
- •2. Целые типы данных.
- •4. Вещественные типы.
- •1. Раздел описания меток.
- •2. Раздел описания констант.
- •3. Раздел описания типов.
- •4. Раздел описания переменных.
- •6. Раздел операторов.
- •7. Последовательность разделов.
- •1. Формульно-словесный способ.
- •2. Блок-схемный способ.
- •Ввод - вывод одномерного массива
- •2. Ввод массива из текстового файла.
- •3. Вывод одномерного массива на экран.
- •Примеры обработки одномерных массивов
- •1. Параметр цикла должен быть ординального типа.
- •2. Параметр должен быть описан в том же блоке, где находится сам оператор цикла.
- •5. В теле цикла параметр не должен изменяться.
- •6. Начальное и конечное значения параметра цикла вычисляются только один раз, до начала цикла.
- •7. При нормальном завершении цикла значение его параметра считается неопределенным.
- •Контроль ординальных переменных
- •Вставка элемента в упорядоченный массив
- •Удаление элементов из массива
- •«Школьный» алгоритм сортировки
- •Группировка массива методом прямой выборки
- •Группировка массива методом прямого обмена
- •Var c : array[1..10,1..15,1..8] of real.
- •1. Ввод элементов матрицы с клавиатуры.
- •2. Ввод матрицы из текстового файла.
- •3. Вывод матрицы на экран.
- •Тождественные и совместимые типы
- •Обработка в процедуре одномерных массивов с различными именами типов
- •Обработка в процедуре матриц с различными именами типов
- •Var s : string[V],
- •Процедуры и функции для обработки строк
- •Определение битовой структуры поля памяти
- •Процедуры и функции для файлов любого типа
- •Var p : pointer;
- •1. Формирование стека из текстового файла.
- •7. Определение значения и местоположения максимального элемента в стеке.
- •8. Удаление из стека максимального элемента.
- •9. Добавление элемента в упорядоченный стек.
- •2. Добавление нового элемента в очередь.
- •3. Удаление элемента из очереди.
- •6. Удаление произвольного элемента из очереди.
- •7. Добавление нового элемента в произвольное место очереди.
- •1. Формирование дека.
- •Var sin : integer;
- •Процедура заполнения FillChar
- •Процедура перемещения данных move
- •Управление экраном в текстовом режиме
- •Сохранение и восстановление экрана
- •Interface
- •Implementation
- •Процедуры управления текстовым режимом экрана
- •Intr(n:byte; Var Reg:Registers),
- •If KeyPressed then
- •Автоматическая оптимизация программ
- •1. Свертывание констант.
- •2. Слияние констант.
- •3. Вычисление по короткой схеме.
- •4. Удаление неиспользуемого кода.
- •If false then
- •5. Эффективная компоновка.
- •Оверлейная структура программы
- •Interface
- •Implementation
- •Interface
- •Implementation
- •Использование сопроцессора
«Школьный» алгоритм сортировки
Сортировка массива (ее также называют группировкой) заключается в такой перестановке элементов массива, при которой они будут расположены в заданном порядке – по возрастанию (группировка по возрастанию) или по убыванию (группировка по убыванию). В первом случае между элементами массива имеет место соотношение
;
во втором случае - соотношение
.
В дальнейшем, рассматривая различные методы группировки, речь будет идти о группировке по возрастанию.
На начальном этапе изучения программирования, в частности в школьном курсе информатики программу сортировки одномерного массива обычно представляют в следующем виде:
For i:=1 to n do
For j:=1 to n do
If x[i]>x[j] then
Begin
R:=x[i]; x[i]:=x[j];
x[j]:=R
End;
Это самая простая из возможных программ сортировки, однако одновременно следует отметить, что более худшего метода сортировки еще не придумано.
Недостатки школьного алгоритма сортировки:
1. Дважды проверяется каждая пара элементов (например, при ипроверяются элементыи; прии─ те же элементыи).
2. При производится ненужная проверка одного и того же элемента.
3. Алгоритм совершенно не учитывает исходное расположение элементов массива. Это означает, что время обработки массива, элементы которого уже были расположены по возрастанию, будет примерно таким же, как и в случае, когда элементы массива расположены в обратном порядке, т.е. по убыванию.
Избавиться от первых двух недостатков довольно легко. Для этого алгоритм сортировки запишем в следующем виде:
For i:=1 to n-1 do
For j:=i+1 to n do
If x[i]>x[j] then
Begin
R:=x[i]; x[i]:=x[j];
x[j]:=R
End;
Назовем этот вариант модифицированным школьным алгоритмом сортировки.
Как будет в дальнейшем показано в сравнительной таблице методов группировки, в данном случае время обработки массива сокращается примерно в два раза.
Группировка массива методом прямой выборки
В рассмотренном ниже алгоритме последовательно выбирается минимальный элемент в подмассивах ; в связи с этим данный метод группировки можно назвать также методом выделения минимального элемента.
Последовательность реализации алгоритма:
1) Просматриваем массив и определяем индекс минимального элемента. Если , то выполняем обмен элементов и .
2) Просматриваем подмассив и определяем индекс минимального элемента. Если , то выполняем обмен элементов и .
3) То же по отношению к подмассиву и т.д.
Последним подмассивом, подвергающимся просмотру, является подмассив .
Program MinElem;
Const Nmax = 500;
Type Ar = array[1..Nmax] of real;
Var i,j,n,k : word;
Xmin : real;
X : Ar;
Begin
Ввод и печать n, X
For i:=1 to n-1 do
Begin
Xmin:=x[i]; k:=i;
For j:=i+1 to n do { определение индекса k }
If x[j]<Xmin then { мин.элемента в подмассиве }
Begin { xi, xi+1, ..., xn }
Xmin:=x[j]; k:=j
End;
If k>i then { обмен элементов }
Begin { xn и xk }
x[k]:=x[i]; x[i]:=Xmin
End;
End;
Печать массива Х
End.
Здесь внешний цикл - перебор подмассивов; внутренний - поиск минимального элемента в подмассиве. Количество выполнений внешнего и внутреннего циклов не зависит от исходной упорядоченности массива .
Примечание. Аналогичным образом можно реализовать метод прямой выборки путем выделения максимального элемента в последовательных подмассивах.