Индивидуальные задания
ЗАДАНИЕ № 4.
Составить алгоритм и написать программу, согласно своему варианту.
Номер варианта |
З А Д А Н И Е |
1. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Сумму отрицательных элементов массива. 2. Произведение элементов массива, расположенных между максимальным и минимальным элементами. Упорядочить элементы массива по возрастанию. |
2. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Сумму положительных элементов массива. 2. Произведение элементов массива, расположенных между максимальным по модулю и минимальным по модулю элементами. Упорядочить элементы массива по убыванию. |
3. |
В одномерном массиве, состоящем из n целочисленных элементов, вычислить: 1. Произведение элементов массива с четными номерами. 2. Сумму элементов массива, расположенных между первым и последним нулевыми элементами. Преобразовать массив таким образом, чтобы сначала располагались все положительные элементы, а потом — все отрицательные (элементы, равные нулю, считать положительными). |
4. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Сумму элементов массива с нечетными номерами. 2. Сумму элементов массива, расположенных между первым и последним отрицательными элементами. Сжать массив, удалив из него все элементы, модуль которых не превышает единицу. Освободившиеся в конце массива элементы заполнить нулями. |
5. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Максимальный элемент массива. 2. Сумму элементов массива, расположенных до последнего положительного элемента. Сжать массив, удалив из него все элементы, модуль которых находится в интервале [а, b]. Освободившиеся в конце массива элементы заполнить нулями. |
6. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Минимальный элемент массива. 2. Сумму элементов массива, расположенных между первым и последним положительными элементами. Преобразовать массив таким образом, чтобы сначала располагались все элементы, равные нулю, а потом — все остальные. |
7. |
В одномерном массиве, состоящем из n целочисленных элементов, вычислить: 1. Номер максимального элемента массива. 2. Произведение элементов массива, расположенных между первым и вторым нулевыми элементами. Преобразовать массив таким образом, чтобы в первой его половине располагались элементы, стоявшие в нечетных позициях, а во второй половине — элементы, стоявшие в четных позициях. |
8. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Номер минимального элемента массива. 2. Сумму элементов массива, расположенных между первым и вторым отрицательными элементами. Преобразовать массив таким образом, чтобы сначала располагались все элементы, модуль которых не превышает единицу, а потом — все остальные. |
9. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Максимальный по модулю элемент массива. 2. Сумму элементов массива, расположенных между первым и вторым положительными элементами. Преобразовать массив таким образом, чтобы элементы, равные нулю, располагались после всех остальных. |
10. |
В одномерном массиве, состоящем из n целочисленных элементов, вычислить: 1. Минимальный по модулю элемент массива. 2. Сумму модулей элементов массива, расположенных после первого элемента, равного нулю. Преобразовать массив таким образом, чтобы в первой его половине располагались элементы, стоявшие в четных позициях, а во второй половине — элементы, стоявшие в нечетных позициях. |
11. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Номер минимального по модулю элемента массива. 2. Сумму модулей элементов массива, расположенных после первого отрицательного элемента. Сжать массив, удалив из него все элементы, величина которых находится в интервале [а, b]. Освободившиеся в конце массива элементы заполнить нулями. |
12. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Номер максимального по модулю элемента массива. 2. Сумму элементов массива, расположенных после первого положительного элемента. Преобразовать массив таким образом, чтобы сначала располагались все элементы, целая часть которых лежит в интервале [а, b], а потом — все остальные. |
13. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Количество элементов массива, лежащих в диапазоне от А до B. 2. Сумму элементов массива, расположенных после максимального элемента. Упорядочить элементы массива по убыванию модулей. |
14. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Количество элементов массива, равных нулю. 2. Сумму элементов массива, расположенных после минимального элемента. Упорядочить элементы массива по возрастанию модулей. |
15. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Количество элементов массива, больших С. 2. Произведение элементов массива, расположенных после максимального по модулю элемента. Преобразовать массив таким образом, чтобы сначала располагались все отрицательные элементы, а потом — все положительные (элементы, равные нулю, считать положительными). |
16. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Количество отрицательных элементов массива. 2. Сумму модулей элементов массива, расположенных после минимального по модулю элемента. Заменить все отрицательные элементы массива их квадратами и упорядочить элементы массива по возрастанию. |
17. |
В одномерном массиве, состоящем из п целочисленных элементов, вычислить: 1. Количество положительных элементов массива. 2. Сумму элементов массива, расположенных после последнего элемента, равного нулю. Преобразовать массив таким образом, чтобы сначала располагались все элементы, целая часть которых не превышает единицу, а потом — все остальные. |
18. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Количество элементов массива, меньших С. 2. Сумму целых частей элементов массива, расположенных после последнего отрицательного элемента. Преобразовать массив таким образом, чтобы сначала располагались все элементы, отличающиеся от максимального не более чем на 20%, а потом — все остальные. |
19. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Произведение отрицательных элементов массива. 2. Сумму положительных элементов массива, расположенных до максимального элемента. Изменить порядок следования элементов в массиве на обратный. |
20. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Произведение положительных элементов массива. 2. Сумму элементов массива, расположенных до минимального элемента. Упорядочить по возрастанию отдельно элементы, стоящие на четных местах, и элементы, стоящие на нечетных местах. |
21. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Сумму отрицательных элементов массива. 2. Произведение элементов массива, расположенных между максимальным и минимальным элементами. Упорядочить элементы массива по возрастанию. |
22. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Максимальный элемент массива. 2. Сумму элементов массива, расположенных до последнего положительного элемента. Сжать массив, удалив из него все элементы, модуль которых находится в интервале [а, b]. Освободившиеся в конце массива элементы заполнить нулями. |
23. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Номер минимального по модулю элемента массива. 2. Сумму модулей элементов массива, расположенных после первого отрицательного элемента. Сжать массив, удалив из него все элементы, величина которых находится в интервале [а, b]. Освободившиеся в конце массива элементы заполнить нулями. |
24. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Количество элементов массива, больших С. 2. Произведение элементов массива, расположенных после максимального по модулю элемента. Преобразовать массив таким образом, чтобы сначала располагались все отрицательные элементы, а потом — все положительные (элементы, равные нулю, считать положительными).
|
25. |
В одномерном массиве, состоящем из n вещественных элементов, вычислить: 1. Произведение положительных элементов массива. 2. Сумму элементов массива, расположенных до минимального элемента. Упорядочить по возрастанию отдельно элементы, стоящие на четных местах, и элементы, стоящие на нечетных местах. |
После выполнения данного практикума студент должен знать:
Массив не является стандартным типом данных, он задается в разделе описания типов. Если тип массива используется только в одном месте программы, можно задать тип прямо при описании переменных.
Размерность массива может быть только константой или константными выражениями. Рекомендуется задавать ее с помощью именованной константы.
Тип элементов массива может быть любым, кроме файлового, тип индексов – интервальным, перечисляемым или byte.
При описании массива можно задать начальные значения его элементов. При этом он описывается в разделе описания констант.
С массивами в целом можно выполнять только одну операцию - присваивание. При этом массивы должны быть одного типа. Все остальные действия выполняются с отдельными элементами массива.
Автоматический контроль выхода индекса за границы массива по умолчанию не выполняется. Можно включить его с помощью директивы {$R+}.
Существует много алгоритмов сортировки. Они различаются по быстродействию, занимаемой памяти и области применения.
Приложение № 5.
КОЛИЧЕСТВО ЭЛЕМЕНТОВ МЕЖДУ МИНИМУМОМ И МАКСИМУМОМ
Написать программу, которая для 10 целочисленных элементов определяет, сколько положительных элементов располагается между максимальным и минимальным элементами.
Запишем алгоритм в общем виде:
Считать исходные данные в массив.
Определить, где расположены его максимальный и минимальный элементы, т.е. найти их индексы.
Просмотреть все элементы, расположенные между ними. Если элемент массива больше нуля, увеличить счетчик элементов на единицу.
Перед написанием программы полезно составить тестовые примеры, чтобы более наглядно представить себе алгоритм. Пусть дан массив из 10 чисел и обозначены искомые величины:
6
|
-8
|
15 макс |
9 + |
-1
|
3 + |
5 + |
-10 мин |
12
|
2
|
Для этого примера программа должна вывести число 3. Порядок расположения элементов в массиве заранее неизвестен – сначала может следовать как максимальный, так и минимальный элемент, более того, они могут совпадать. Поэтому прежде чем искать количество положительных элементов, требуется определить, какой из этих индексов больше, чтобы просматривать массив от меньшего номера к большему.
Рассмотрим подробно принцип поиска максимального элемента в массиве. Он весьма прост. Очевидно, что для его отыскания нужно сравнить между собой все элементы массива. Поскольку компьютер может сравнивать одновременно только два числа, элементы выбираются попарно. Например, сначала первый элемент сравнивается со вторым, затем тот из них, который оказался больше – с третьим, тот, который оказался больше – с четвертым, и так далее до последнего элемента. Иными словами, при каждом сравнении из двух чисел выбирается наибольшее. Поскольку его надо где-то хранить, в программе описывается переменная того же типа, что и элементы массива. После окончания просмотра массива в ней окажется самый большой элемент. Для того чтобы все элементы сравнивались единообразно, перед началом просмотра в эту переменную заносится первый элемент массива.
Сформулируем алгоритм поиска максимума:
Принять за максимальный первый элемент массива.
Просмотреть массив, начиная со второго элемента.
Если очередной элемент оказывается больше максимального, принять его максимальным.
Программа поиска максимального элемента:
{***************************************************}
{Программа: MAX_ELEM. }
{Программист: Иванов И.И. }
{Дата выполнения: 10 апреля 2006 г. }
{***************************************************}
Program MAX_ELEM;
Const n = 10;
Var a : array [1 . . n] of integer; {массив}
i : integer; {номер текущего элемента}
max : integer; {максимальный элемент}
Begin
Writeln(‘Введите ‘, n, ‘ элементов массива’);
For i:=1 to n do
Begin
Writeln(‘a[‘, i:2, ‘]=’);
Read(a[i])
End;
max := a[1]; {принять за максимальный первый элемент массива}
For i := 1 to n do {просмотреть массив, начиная с первого элемента}
if a[i]> max then max := a[i];
writeln(‘Максимальный элемент: ’, max)
End. { MAX_ELEM }
Для решения поставленной задачи требуется знать не значение максимума, в его положение в массиве, т. е. индекс:
{***************************************************}
{Программа: INDEX_MAX_ELEM. }
{Программист: Иванов И.И. }
{Дата выполнения: 10 апреля 2006 г. }
{***************************************************}
Program INDEX_MAX_ELEM;
Const n = 10;
Var a : array [1 . . n] of integer; {массив}
i : integer; {номер текущего элемента}
imax : integer; {номер максимального элемента}
Begin
Writeln(‘Введите ‘, n, ‘ элементов массива’);
For i:=1 to n do
Begin
Writeln(‘a[‘, i:2, ‘]=’);
Read(a[i])
End;
imax := 1;
For i := 1 to n do
if a[i]> a[imax] then imax := i;
writeln(‘Номер максимального элемента: ’, imax);
writeln(‘Максимальный элемент: ’, a[imax])
End. { INDEX_MAX_ELEM }
В этой программе в переменной imax запоминается номер максимального из просмотренных элементов. По этому номеру осуществляется выборка элементов из массива.
Запишем уточненный алгоритм решения рассматриваемой задачи:
Определить, где в массиве расположены его максимальный и минимальный элементы:
задать начальные значения индексов искомых максимального и минимального элементов (например, равные номеру его первого элемента, но можно использовать любые другие значения индекса, не выходящие за границу массива);
просмотреть массив, поочередно сравнивая каждый его элемент с ранее найденными максимумом и минимумом. Если очередной элемент больше ранее найденного максимума, принять этот элемент за максимум (т.е. запомнить его индекс). Если очередной элемент меньше ранее найденного минимума, принять этот элемент за минимум.
Определить границы просмотра массива для поиска положительных элементов, находящихся между его максимальным и минимальным элементами:
если максимум расположен в массиве раньше, чем минимум, принять левую границу просмотра равной индексу максимума, иначе – индексу минимума;
если максимум расположен в массиве раньше, чем минимум, принять правую границу просмотра равной индексу минимума, иначе – индексу максимума.
Определить количество положительных элементов в найденном диапазоне:
обнулить счетчик положительных элементов;
просмотреть массив в указанном диапазоне. Если очередной элемент больше нуля, увеличить счетчик на единицу.
Для экономии времени значения элементов массива при отладке можно задать путем инициализации:
{***************************************************}
{Программа: NUM_POSITIV. }
{Программист: Иванов И.И. }
{Дата выполнения: 10 апреля 2006 г. }
{***************************************************}
Program NUM_POSITIV;
Const n = 10;
a : array [1 . . n] of integer = (1, 3, -5, 1, -2, 1, -1, 3, 8, 4);
Var i : integer; {индекс текущего элемента}
imax : integer; {индекс максимального элемента}
imin : integer; {индекс минимального элемента}
ibeg : integer; {начало интервала}
iend : integer; {конец интервала}
count : integer; {количество положительных элементов}
Begin
For i:=1 to n do writeln(a[i]:3);
Writeln;
imax := 1;
imin := 1;
For i := 1 to n do
Begin
if a[i]> a[imax] then imax := i;
if a[i]<a[imin] then imin := i
end;
writeln(‘max= ’, a[imax]:3, ‘min= ‘, a[imin]:3);
if imax < imin then ibeg := imax
else ibeg := imin;
if imax < imin then iend := imin
else iend := imax;
count := 0;
for i := ibeg + 1 to iend – 1 do
if a[i] > 0 then inc(count);
writeln(‘Количество положительных: ’, count:5)
End. { NUM_POSITIV }
Массив просматривается, начиная с элемента, следующего за максимальным (минимальным), до элемента, предшествующего минимальному (максимальному). Тестовых примеров для этой задачи должно быть, по крайней мере, три – для случаев, когда:
элемент a[imin] расположен левее элемента a[imax];
элемент a[imin] расположен правее элемента a[imax];
элементы a[imin] и a[imax] совпадают.
Последняя ситуация имеет место, когда в массиве все элементы имеют одно и то же значение. Желательно также проверить, как работает программа, если элемент a[imin] и a[imax] расположены рядом, а также в начале и в конце массива (граничные случаи). В массиве должны присутствовать как положительные, так и отрицательные элементы.
Приложение № 6.
СУММА ЭЛЕМЕНТОВ ПРАВЕЕ ПОСЛЕДНЕГО ОТРИЦАТЕЛЬНОГО
Написать программу, которая для n вещественных элементов определяет сумму элементов, расположенных правее последнего отрицательного элемента.
В этой задаче количество элементов задано переменной величиной. Предполагается, что она будет известна на этапе выполнения программы до того, как будут вводиться сами элементы. Допустим также, что известно максимально возможное количество элементов. В этом случае память под массив можно выделить по «максимуму», а затем заполнить только часть этой памяти. Фактическое количество введенных элементов запоминается в переменной, которая затем участвует в организации циклов по массиву, задавая его верхнюю границу. Ниже приведена программа, иллюстрирующая этот подход. В ней выполняются только считывание элементов с клавиатуры и их вывод на экран:
{***************************************************}
{Программа: EXAMPLE. }
{Программист: Иванов И.И. }
{Дата выполнения: 10 апреля 2006 г. }
{***************************************************}
Program EXAMPLE;
Const n = 10000;
Var a : array [1 . . n] of integer; {массив}
i : integer; {номер текущего элемента}
nf : integer; {фактическое количество элементов в массиве}
Begin
Writeln(‘Введите количество элементов массива’);
Readln(nf);
If nf > n then
Begin
Writeln(‘Превышение размеров массива’);
Exit
End;
Writeln(‘Ввести элементы массива’);
For i:=1 to nf do
Begin
Writeln(‘a[‘, i:2, ‘]=’);
Read(a[i])
End;
For i := 1 to n do writeln(‘a[’, i:2, ‘]=’, a[i]:4)
End. { EXAMPLE }
Несмотря на то, что значение константы n определяется «с запасом», надо обязательно проверять, не запрашивается ли большее количество элементов, чем возможно. Привычка к проверке подобных, казалось бы, маловероятных случаев позволит создавать более надежные программы, а нет ничего более важного для программы, чем надежность.
Если же стоит задача вводить заранее неизвестное количество чисел до тех пор, пока не будет введен какой-либо признак окончания ввода, то заранее выделить достаточное количество памяти не удастся и придется воспользоваться так называемыми динамическими структурами данных, например списком. Остановимся на первом предположении – что количество элементов массива вводится с клавиатуры до начала ввода самих элементов. Перейдем к созданию алгоритма решения задачи. По аналогии с предыдущей задачей, рассмотренной в приложении № 5, можно принять такое решение: просматривая массив с начала до конца, найти номер последнего отрицательного элемента, а затем организовать цикл суммирования всех элементов, расположенных правее него. Вот как выглядит построенная по этому алгоритму программа (следует отметить, что она далеко не так хороша, как может показаться с первого взгляда):
{***************************************************}
{Программа: SUM_ELEM_1. }
{Программист: Иванов И.И. }
{Дата выполнения: 10 апреля 2006 г. }
{***************************************************}
Program SUM_ELEM_1;
Const n = 10000;
Var a : array [1 . . n] of real;
i : integer; {индекс текущего элемента}
ineg : integer; {номер последнего отрицательного элемента}
nf : integer; {фактическое количество элементов в массиве}
sum : real; {сумма элементов}
Begin
Writeln(‘Введите количество элементов массива’);
Readln(nf);
If nf > n then
Begin
Writeln(‘Превышение размеров массива’);
Exit
End;
Writeln(‘Ввести элементы массива’);
For i:=1 to nf do
Begin
Writeln(‘a[‘, i:2, ‘]=’);
Read(a[i])
End;
Writeln(‘Исходный массив:’);
For i := 1 to nf do writeln(‘a[’, i:2, ‘]=’, a[i]:4);
Writeln;
For i:=1 to nf do
If a[i] < 0 then ineg := i;
sum := 0;
For i := ineg + 1 to nf do sum := sum +a[i];
writeln(‘Сумма: ’, sum:7:2)
End. { SUM_ELEM_1 }
Номер последнего отрицательного элемента массива формируется в переменной ineg. При просмотре массива в эту переменную последовательно записываются номера всех отрицательных элементов массива. Таким образом, после выхода из цикла в ней остается номер самого последнего элемента. Может возникнуть мысль с целью оптимизации программы объединить цикл нахождения номера последнего отрицательного элемента с циклами ввода и контрольного вывода элементов массива, но так делать не советую, потому что ввод данных, их вывод и анализ – разные по смыслу действия, и смешивание их в одном цикле не прибавит программе ясности. После отладки программы операторы вывода можно удалить или закомментировать.
Теперь перейдем к критическому анализу первой попытки решения задачи. Для массивов, содержащих отрицательные элементы, эта программа работает верно, но при их отсутствии выдает сумму всех элементов массива. Это связано с тем, что если в массиве нет ни одного отрицательного элемента, переменной ineg значение в цикле не присваивается. Оно остается равным значению, заданному по умолчанию. Следовательно, в программу необходимо внести проверку, есть ли в массиве хотя бы один отрицательный элемент. Для этого переменной ineg присваивается начальное значение, не входящее в множество допустимых индексов массива (например, -1). После цикла поиска номера отрицательного элемента выполняется проверка, сохранилось ли начальное значение ineg неизменным. Если да, то это означает, что условие a[i] < 0 в операторе не выполнилось ни разу и отрицательных элементов в массиве нет:
{***************************************************}
{Программа: SUM_ELEM_2. }
{Программист: Иванов И.И. }
{Дата выполнения: 10 апреля 2006 г. }
{***************************************************}
Program SUM_ELEM_2;
Const n = 10000;
Var a : array [1 . . n] of real;
i : integer; {индекс текущего элемента}
ineg : integer; {номер последнего отрицательного элемента}
nf : integer; {фактическое количество элементов в массиве}
sum : real; {сумма элементов}
Begin
Writeln(‘Введите количество элементов массива’);
Readln(nf);
If nf > n then
Begin
Writeln(‘Превышение размеров массива’);
Exit
End;
Writeln(‘Ввести элементы массива’);
For i:=1 to nf do
Begin
Writeln(‘a[‘, i:2, ‘]=’);
Read(a[i])
End;
Writeln(‘Исходный массив:’);
For i := 1 to nf do writeln(‘a[’, i:2, ‘]=’, a[i]:4);
Writeln;
Ineg := -1;
For i:=1 to nf do
If a[i] < 0 then ineg := i;
If ineg = -1 then writeln(‘Отрицательных лементов нет’)
else begin
sum := 0;
For i := ineg + 1 to nf do sum := sum +a[i];
writeln(‘Сумма: ’, sum:7:2)
end
End. { SUM_ELEM_2 }
Если не останавливаться на достигнутом и подумать, можно предложить более рациональное решение: просматривать массив в обратном порядке, суммируя его элементы, и завершить цикл, как только встретиться отрицательный элемент:
{***************************************************}
{Программа: SUM_ELEM_3. }
{Программист: Иванов И.И. }
{Дата выполнения: 10 апреля 2006 г. }
{***************************************************}
Program SUM_ELEM_3;
Const n = 10000;
Var a : array [1 . . n] of real;
i : integer; {индекс текущего элемента}
nf : integer; {фактическое количество элементов в массиве}
sum : real; {сумма элементов}
is_neg : boolean; {признак наличия отрицательного элемента}
Begin
Writeln(‘Введите количество элементов массива’);
Readln(nf);
If nf > n then
Begin
Writeln(‘Превышение размеров массива’);
Exit
End;
Writeln(‘Ввести элементы массива’);
For i:=1 to nf do
Begin
Writeln(‘a[‘, i:2, ‘]=’);
Read(a[i])
End;
Writeln(‘Исходный массив:’);
For i := 1 to nf do writeln(‘a[’, i:2, ‘]=’, a[i]:4);
Writeln;
Is_neg := false;
sum := 0;
For i := nf downto 1 do begin
If a[i] < 0 then begin
is_neg := true;
Break
end;
sum := sum +a[i]
end;
if is_neg then writeln(‘Сумма: ’, sum:7:2)
else writeln(‘Отрицательных элементов нет’)
End. { SUM_ELEM_3 }
В этой программе каждый элемент массива анализируется не более одного раза, а ненужные элементы не просматриваются вообще, поэтому для больших массивов этот вариант предпочтительнее. Для исчерпывающего тестирования этой программы необходимо ввести по крайней мере три варианта исходных данных для случаев, когда массив содержит один, более одного и ни одного отрицательного элемента.
Приложение № 7.
СЖАТИЕ МАССИВА
Написать программу, которая «сжимает» целочисленный массив из 10 элементов, удаляя из него элементы, меньшие заданной величины. Освободившиеся в конце массива элементы заполнить нулями.
Исходный массив:
6 |
-8 |
15 |
9 |
-1 |
3 |
5 |
-10 |
12 |
2 |
Допустим, требуется удалить из него все элементы, значение которых меньше 5. Результат должен иметь вид:
6 |
15 |
9 |
5 |
12 |
0 |
0 |
0 |
0 |
0 |
Исходными данными являются массив и заданное число, результатом – преобразованный массив.
Проще всего решать эту задачу с использованием дополнительного массива того же типа, что и исходный. В этом случае при просмотре исходного массива элементы, которые требуется оставить, помещаются один за другим во второй массив, после чего он присваивается исходному.
{***************************************************}
{Программа: COMPRESS_1. }
{Программист: Иванов И.И. }
{Дата выполнения: 10 апреля 2006 г. }
{***************************************************}
Program COMPRESS_1;
Const n = 10;
Type mas = array [1 . . n] of integer;
Var a, b : mas;
i : integer; {индекс текущего элемента в массиве a}
j : integer; {индекс текущего элемента в массиве b}
x : integer; {заданное число}
Begin
Writeln(‘Введите число’);
Readln(x);
Writeln(‘Ввести элементы массива’);
For i:=1 to n do
Begin
Writeln(‘a[‘, i:2, ‘]=’);
Read(a[i])
End;
j := 0;
For i := 1 to n do
If a[i] >= x then begin
inc(j);
b[j] := a[i]
end;
a := b;
Writeln(‘Преобразованный массив:’);
For I := 1 to n do write(‘a[‘, i:2, ‘]=’, a[i]:4)
End. {COMPRESS_1}
Обнуление «хвоста» массива происходит естественным образом, поскольку в Паскале глобальные переменные обнуляются. Однако для массивов большой размерности выделение двойного объема памяти может оказаться слишком расточительным. Поэтому ниже приведен вариант программы, в которой преобразование массива выполняется «in situ», что по-латински означает «на месте».
Алгоритм работы этой программы выглядит следующим образом:
Просматривая массив, определить номер самого первого из удаляемых элементов.
Если таковой есть, сдвигать каждый последующий элемент массива на первое «свободное» место, обнуляя оставшуюся часть массива.
Иллюстрация алгоритма:
В
приведенной ниже программе переменная
j так же, как и в
предыдущей, используется для указания
позиции, в которую помещается очередной
элемент массива. После сдвига очередного
элемента она увеличивается на единицу,
чтобы следующий подходящий элемент
массива помещался в соседнюю позицию:
{***************************************************}
{Программа: COMPRESS_2. }
{Программист: Иванов И.И. }
{Дата выполнения: 10 апреля 2006 г. }
{***************************************************}
Program COMPRESS_2;
Const n = 10;
Type mas = array [1 . . n] of integer;
Var a : mas;
i : integer; {индекс текущего элемента}
j : integer; {индекс элемента, в который помещается текущий}
x : integer; {заданное число}
Begin
Writeln(‘Введите число’);
Readln(x);
Writeln(‘Ввести элементы массива’);
For i:=1 to n do
Begin
Writeln(‘a[‘, i:2, ‘]=’);
Read(a[i])
End;
j := 0;
For i := 1 to n do
If a[i] < x then begin
j := i;
break
end;
if j <> 0 then begin;
for i := j + 1 to n do
if a[i] >= x then begin
a[j] := a[i];
inc(j)
end;
for i := j to n do a[i] := 0
end;
Writeln(‘Преобразованный массив:’);
For I := 1 to n do write(‘a[‘, i:2, ‘]=’, a[i]:4)
End. {COMPRESS_2}
Для тестирования этой программы надо использовать несколько значений переменной x – таких, чтобы из массива:
не был удален ни один элемент;
были удалены все элементы;
была удалена часть элементов.
Приложение № 8.
БЫСТРАЯ СОРТИРОВКА МАССИВА
Написать программу, которая упорядочивает вещественный массив из 500 элементов методом быстрой сортировки.
Под сортировкой понимается упорядочивание в соответствии с каким-либо критерием – чаще всего по возрастанию или убыванию. Существует множество методов сортировки, различающихся по поведению, быстродействию, требуемому объему памяти, а также ограничениям, накладываемым на исходные данные. Одним из наиболее простых методов является сортировка выбором. Он характеризуется квадратичной зависимостью времени сортировки t от количества элементов N:
.
Здесь a и b – константы, зависящие от программной реализации алгоритма. Иными словами, для сортировки массив требуется просмотреть порядка N раз. Существуют алгоритмы и с лучшими характеристиками, самый известный из которых предложен Ч.Э.Хоаром и называется алгоритмом быстрой сортировки. Для него зависимость имеет вид
Рассмотрим этот алгоритм. Его идея состоит в следующем. К массиву применяется так называемая процедура разделения относительно среднего элемента. Вообще-то в качестве «среднего» можно взять любой элемент массива, но для наглядности будет выбираться элемент примерно из середины интервала. Процедура разделения делит массив на две части. В левую помещаются элементы, меньшие элемента, выбранного в качестве среднего, а в правую – большие. Это достигается путем просмотра массива попеременно с обоих концов, причем каждый элемент сравнивается с выбранным средним и элементы, находящиеся в «неподходящей» части, меняются местами. После завершения процедуры разделения средний элемент оказывается на своем окончательном месте, т.е. его «судьба» определена. Далее процедуру разделения необходимо повторить отдельно для левой и правой частей: в каждой части выбирается среднее, относительно которого она делится на две, и т.д. Понятно, что одновременно процедура не может заниматься и левой, и правой частями, поэтому необходимо каким-то образом запомнить на обработку одной из двух частей (например, правой) и заняться оставшейся частью (например, левой). Так продолжается до тех пор, пока не окажется, что очередная обрабатываемая часть содержит ровно один элемент. Тогда нужно вернуться к последнему из необработанных запросов, применить к нему все ту же процедуру разделения и т.д. В конце концов массив будет полностью упорядочен. Для хранения границ еще не упорядоченных частей массива более всего подходит структура данных, называемая стеком. Можно представить себе длинный туннель, в который въезжает вереница машин. Ширина туннеля позволяет ехать только в один ряд. Если окажется, что выезд из туннеля закрыт и придется ехать обратно задним ходом, машина, ехавшая первой, сможет покинуть туннель в самую последнюю очередь. Это и есть стек, принцип организации которого – «первым пришел, последним ушел».
В приведенной программе, стек реализуется в виде двух массивов stackl и stackr, а также переменной sp, используемой как «указатель» на вершину стека (она хранит номер последнего заполненного элемента массива).
Для этого алгоритма количество элементов в стеке не может превышать n, поэтому размер массивов задан равным именно этой величине. При занесении в стек переменная sp увеличивается на единицу, а при выборке – уменьшается. Ниже приведена программа, реализующая этот алгоритм:
{***************************************************}
{Программа: QUICK_SORT. }
{Программист: Иванов И.И. }
{Дата выполнения: 10 апреля 2006 г. }
{***************************************************}
Program QUICK_SORT;
Const n = 500;
Var arr : array [1 . . n] of real;
middle : real; {средний элемент}
temp : real; {буферная переменная для обмена двух значений в массиве}
sp : integer; {указатель на вершину стека}
i, j : integer;
stackl, stackr : array [1 . . n] of integer; {стеки границ фрагментов}
left, right : integer; {границы сортируемого фрагмента}
Begin
Writeln(‘Ввести элементы массива’);
For i:=1 to n do
Begin
Writeln(‘arr[‘, i:2, ‘]=’);
Read(arr[i])
End;
sp := 1; { 1 }
stackl[1] := 1; { 1 }
stackr[1] := n; { 1 }
while sp > 0 do begin { 2 }
left := stackl[sp]; { 3 }
right := stackr[sp]; { 4 }
dec(sp); { 5 }
while left < right do begin { 6 }
i := left; { 7 }
j := right; { 7 }
middle := arr[(left + right) div 2]; { 8 }
while i < j do begin { 9 }
while arr[i] < middle do inc(i); { 10}
while middle < arr[j] do dec(j); { 11}
if i <= j then begin
temp := arr[i];
arr[i] := arr[j];
arr[j] := temp;
inc(i);
dec(j)
end
end;
if i < right then begin { 12}
inc(sp);
stackl[sp] := i;
stackr[sp] := right
end;
right := j { 13}
end
end;
Writeln(‘Упорядоченный массив:’);
For I := 1 to n do write(‘arr[‘, i:2, ‘]=’, arr[i]:8:2);
writeln
End. { QUICK_SORT }
На каждом шаге сортируется один фрагмент массива. Левая граница фрагмента хранится в переменной left, а правая – в переменной right. Сначала фрагмент устанавливается размером с массив целиком (операторы 1). В операторе 8 выбирается «средний» элемент фрагмента. Для продвижения по массиву слева направо в цикле 10 используется переменная I, справа налево – переменная j (в цикле 11). Их начальные значения устанавливаются в операторе 7. После того как оба счетчика «сойдутся» где-то в средней части массива, происходит выход цикла 9 на оператор 12, в котором заносятся в стек границы правой части фрагмента. В операторе 13 устанавливаются новые границы левой части для сортировки на следующем шаге. Если сортируемый фрагмент уже настолько мал, что сортировать его не требуется, происходит выход из цикла 6, после чего выполняется выборка из стека границ еще не отсортированного фрагмента (операторы 3 и 4). Если стек пуст, происходит выход из главного цикла 2. Массив отсортирован.
Быстрая сортировка является одним из лучших методов упорядочивания, однако существует целый ряд алгоритмов, которые предпочтительнее применять для данных, отвечающих определенным критериям. Оптимальный выбор наиболее подходящего для каждого случая метода сортировки данных – показатель класса программиста.
Примечание.
На выполнение данного практикума отводится 10 часов аудиторных занятий. Максимальное количество баллов за в срок сданную работу – 20.
Номер задания |
Задание № 1 |
Задание № 2 |
Задание № 3 |
Задание № 4 |
||
4.1. |
4.2. |
4.0. |
||||
Количество баллов |
3 |
3 |
3 |
3 |
3 |
5 |