- •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
- •Использование сопроцессора
Вставка элемента в упорядоченный массив
Методику вставки дополнительного элемента в массив, упорядоченный по возрастанию или по убыванию, рассмотрим на конкретном примере.
Пример.
Задан упорядоченный по возрастанию массив и произвольное число . Вставить число в массив , не нарушая упорядоченности этого массива.
При этом может иметь место один из трех вариантов:
а)
б)
в)
Пусть массив имеет вид
5 12 18 22 29 31 35 41 47 53 62 77 ()
Если , т.е. меньше первого элемента , то требуется сдвинуть весь массив вправо на один элемент, а элементу присвоить значение . Если , т.е. , то определяется индекс ближайшего элемента , после чего подмассив сдвигается вправо на один элемент, а элементу присваивается значение . Если , т.е. , то сдвиг элементов массива не производится, а значение переменной присваивается элементу . В любом случае при включении значения в состав массива количество элементов этого массива увеличивается на 1.
{$R+}
Program Insertion;
Const Nmax = 100;
Type Ar = array[1..Nmax] of integer;
Var X : Ar;
i,k,n : integer;
Begin
Ввод и печать n, X, b
k:=0;
For i:=1 to n do { Поиск ближайшего }
If x[i]>b then { элемента, большего }
Begin { значения b}
k:=i; Break
End;
If k=0 then { b >= x[n] }
x[n+1]:=b
Else
Begin { Сдвиг подмассива }
For i:=n+1 downto k+1 do { при b<x[n]}
x[i]:=x[i-1];
x[k]:=b { Вставка значения b }
End;
Inc(n); { Увеличение размера массива }
Печать n, X
End.
Примечание 1. Сдвиг части массива X вправо оператором
For i:=k+1 to n+1 do
x[i]:=x[i-1];
путем перебора его элементов слева направо делать нельзя, так как всем элементам , , ... , будет присвоено одно и то же значение элемента .
Примечание 2. Фраза {$R+} означает включение директивы компилятора R.
Примечание 3. Выход за пределы границ массива X будет иметь место при n = Nmax. Следствием этого может быть получение неправильных результатов или зацикливание программы. При включенной директиве R в этом случае будет сгенерировано прерывание 201, что позволит индицировать такую ошибку при отладке программы. Для повышения надежности работы программы целесообразно объявление типа массива выполнить в виде
Ar = array[1..Nmax+1] of integer,
а после ввода массива X проверить условие n Nmax и в случае его нарушения выдать соответствующее сообщение на экран.
Удаление элементов из массива
Чтобы удалить элемент из массива , необходимо сдвинуть элементы на один "шаг" влево и уменьшить значение на 1. Если , то в этом случае достаточно выполнить .
Пример 1. Из массива Х удалить минимальный элемент.
Program DelMin;
Const Nmax = 200;
Type Ar = array[1..Nmax] of integer;
Var i,imin,n : byte;
xmin : integer;
X : Ar;
Begin
В в о д n, X
Xmin:=x[1]; imin:=1; { Определение положения }
For i:=2 to n do { (индекса) минимального}
If x[i]<xmin then { элемента }
Begin
Xmin:=x[i]; imin:=i
End;
For i:=imin to n-1 do { Удаление элемента }
x[i]:=x[i+1]; { с индексом imin }
Dec(n); { Уменьшение размера массива }
П е ч а т ь n, X
End.
Если imin = n, то второй цикл For не работает (начальное значение параметра i больше его конечного значения), но размер массива n уменьшается на 1.
Пример 2. Из массива Х удалить все нулевые элементы.
В программе будем последовательно просматривать элементы массива и, если очередной элемент , то производим сдвиг подмассива на один элемент влево, одновременно уменьшая количество элементов .
Program Mas;
Const Nmax = 500;
Type Ar = array[1..Nmax] of integer;
Var i,j,n : integer;
X : Ar;
Begin
Ввод n, X
For i:=1 to n do
If x[i]=0 then
Begin
For j:=i to n-1 do
x[j]:=x[j+1];
Dec(n);
End;
Вывод n, X
End.
По поводу программы Mas можно сделать три замечания.
1. При i = n, когда анализируется последний элемент массива, параметр j изменяется от n до n-1, т.е. начальное значение параметра цикла больше его конечного значения. Как известно из описания оператора For, цикл в этом случае не выполняется, т.е. оператор цикла эквивалентен пустому оператору. Следовательно, при происходит лишь уменьшение значения n, что соответствует алгоритму решения задачи.
2. Начальное и конечное значения параметра цикла вычисляются до начала цикла и в процессе его выполнения не изменяются. Следовательно, уменьшение значения переменной n при = 0 не изменяет количество повторений цикла по параметру i. Это приводит к избыточной работе программы, но не отражается на правильности решения задачи.
3. Предположим, что в массиве X имеются подряд идущие нулевые элементы и . При i = k будет удален элемент , а на его место перемещается элемент , также равный нулю. Поскольку при новом повторении цикла For параметр цикла принимает очередное значение k+1, то новый нулевой элемент не будет анализироваться повторно и, как следствие, не будет удален из массива. Поэтому при наличии в массиве подряд идущих нулевых элементов программа Mas работает неправильно.
Для корректного решения поставленной задачи нужно, чтобы программа после удаления нулевого элемента повторно анализировала этот же элемент и переходила к рассмотрению элемента лишь при 0. Для этого нужно в программе вместо цикла For использовать цикл While:
Program DelZero1;
Const Nmax = 500;
Type Ar = array[1..Nmax] of integer;
Var i,j,n : integer;
X : Ar;
Begin
Ввод n, X
i:=1;
While i<=n do
If x[i]=0 then
Begin
For j:=i to n-1 do
x[j]:=x[j+1];
Dec(n);
End
Else
Inc(i);
End.
Тот же эффект можно достичь с помощью оператора For, если просмотр массива выполнять справа налево.
Program DelZero2;
Const Nmax = 500;
Type Ar = array[1..Nmax] of integer;
Var i,j,n : integer;
X : Ar;
Begin
Ввод n, X
For i:=n downto 1 do
If x[i]=0 then
Begin
For j:=i to n-1 do
x[j]:=x[j+1];
Dec(n);
End;
End.
Обнаружение нулевого элемента во внешнем цикле и, как следствие, его удаление из массива приводит к перемещению уже обработанных элементов в "хвосте" массива и не влияет ни на количество повторений внешнего цикла, ни на анализ оставшихся элементов.
Рассмотрим еще один вариант программы, предназначенной для удаления нулевых элементов из массива.
Program DelZero3;
Const Nmax = 500;
Type Ar = array[1..Nmax] of integer;
Var i,k,n : integer;
X : Ar;
Begin
Ввод n, X
For i:=1 to n do
If x[i]<>0 then
Begin
Inc(k);
If k<>i then
x[k]:=x[i];
End;
n:=k;
End.
Компьютерный эксперимент, проведенный по отношению к программам удаления однотипных элементов из массива (в данном случае нулей), показал, что быстродействие (время обработки одного и того же массива) программ DelZero1, DelZero2 и DelZero3 пропорционально численным значениям 7, 3 и 1.
Рассмотрим причины столь существенного различия в быстродействии приведенных здесь программ.
1) Цикл For в общем случае работает в 2 – 2,5 раза быстрее, чем цикл While (это объясняется в основном тем, что в цикле For используются более эффективные машинные команды).
2) В программе DelZero3 перемещается лишь один элемент массива (и то не в каждом цикле), в то время как в программе DelZero2 при удалении каждого элемента, кроме последнего, передвигается вся правая часть массива, причем чем ближе удаляемый элемент к началу массива, тем больше элементов перемещается справа налево.
Примечание. Удаление подряд расположенных элементов, т.е. подмассива рассмотрено в прил.1 (программа Task102).