count:integer; {количество положительных элементов}
begin
clrscr;
for i:=1 to n do write(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],' min=',a[imin]); {отладочная печать}
if imax<imin then ibeg:=imax else ibeg:=imin; {левая граница}
if imax<imin then iend:=imin else iend:=imax; {правая граница}
writeln('ibeg=',ibeg,' iend=',iend); {отладочная печать}
count:=0;
for i:=ibeg+1 to iend-1 do {подсчет кол-ва положительных}
if a[i]>0 then inc(count);
writeln('Количество положительных: ',count);
readln;
end.
Замечание: inc(x) – увеличивает на 1;
dec(x) – уменьшает на 1.
Лабораторная работа №6. Преобразование массивов.
Цель: Приобретение основных навыков при решение задач на массивы.
…………………………………………………………………………………………………
Задача 6.1. Создать массив случайных чисел из 30 элементов. Произвести сортировку по невозрастанию и неубыванию. Найти минимальный и максимальный элементы, определить номера этих элементов. Если этих элементов несколько, то создать массив минимальных и максимальных чисел. Подсчитать сумму всех элементов массива и найти среднее арифметическое.
Задание: Уметь объяснить работу программы.
uses crt;
const n=30;
var a,mn,mx: array[1..n] of integer;
min,max,imin,imax,i,j,sum,t:integer;
sred:double;
begin
clrscr;
randomize;
writeln;writeln;
writeln('Исходный массив');writeln;
sum:=0;
for i:=1 to n do begin
a[i]:=random(101);
write(a[i],' ');
sum:=sum+a[i];
end;
sred:=sum/n;
writeln;
writeln;
writeln('Сумма элементов массива=',sum,' ','Среднее ариф-ое=',sred);
min:=a[1];max:=a[1];
for i:=2 to n do begin
if a[i]<min then min:=a[i];
if a[i]>max then max:=a[i];
end;
imin:=0; imax:=0;
for i:=1 to n do begin
if a[i]=min then inc(imin);
if a[i]=max then inc(imax);
end;
if imin>1 then begin writeln;writeln('Массив мин-ых эл-ов');
for i:=1 to imin do begin
mn[i]:=min;
write(mn[i],' ');
end;end
else begin for i:=1 to n do if a[i]=min then begin imin:=i; break;end;
writeln;
writeln('Мин-ый=',min,' номер мин-го=',imin);end;
if imax>1 then begin writeln;writeln('Массив максим-ых эл-ов');
for i:=1 to imax do begin
mx[i]:=max;
write(mx[i],' ');
end;end
else begin for i:=1 to n do if a[i]=max then begin imax:=i; break; end;
writeln;
writeln('Макс-ый=',max,' номер макс-го=',imax);end;
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]<a[j] then begin t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
writeln;
writeln('Сорт-ка1');
for i:=1 to n do write(a[i],' ');
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j] then begin t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
writeln;
writeln;
writeln('Сортировка2');
for i:=1 to n do write(a[i],' ');
readln;
end.
Задача 6.2. Написать программу, которая «сжимает» целочисленный массив из 10 элементов, удаляя из него элементы, меньшие заданной величины. Освободившиеся в конце массива элементы заполнить нулями.
…………………………………………………………………………………………………
Исходный массив:
| 6 | -8 | 15 | 9 | -1 | 3 | 5 | -10 | 12 | 2 |
Допустим, требуется удалить из него все элементы, значение которых меньше 5. Результат должен иметь вид
| 6 | 15 | 9 | 5 | 12 | 0 | 0 | 0 | 0 | 0 |
Проще всего решать эту задачу с использованием дополнительного массива того же типа, что и исходный. В этом случае при просмотре исходного массива элементы, которые требуется оставить, помещаются один за другим во второй массив, после чего он присваивается исходному. Однако для массивов большой размерности выделение двойного объема памяти может оказаться слишком расточительным. Поэтому, предлагаю решить задачу по следующему алгоритму:
1) Просматривая массив, определить номер самого первого из удаляемых элементов.
2) Если таковой есть, сдвигать каждый последующий элемент массива на первое «свободное» место, обнуляя оставшуюся часть массива.
Индивидуальное задание. (у преподавателя)
Вариант 1
……………………………………………………………………………………………………
В одномерном массиве, состоящем из n вещественных элементов, вычислить:
1) сумму отрицательных элементов массива;
2) произведение элементов массива, расположенных между максимальным и минимальным элементами.
Упорядочить элементы массива по возрастанию.
Вариант 2
……………………………………………………………………………………………………
В одномерном массиве, состоящем из n вещественных элементов, вычислить:
1) сумму положительных элементов массива;
2) произведение элементов массива, расположенных между максимальным по модулю и минимальным по модулю элементами.
Упорядочить элементы массива по убыванию.
Вариант 3
……………………………………………………………………………………………………
В одномерном массиве, состоящем из n целочисленных элементов, вычислить:
1) произведение элементов массива с четными номерами;
2) сумму элементов массива, расположенных между первым и последним нулевыми элементами.
Преобразовать массив таким образом, чтобы сначала располагались все положительные элементы, а потом – все отрицательные (элементы, равные нулю, считать положительными).
Вариант 4
……………………………………………………………………………………………………
В одномерном массиве, состоящем из n вещественных элементов, вычислить:
1) сумму элементов массива с нечетными номерами;
2) сумму элементов массива, расположенных между первым и последним отрицательными элементами.
Сжать массив, удалив из все элементы, модуль которых не превышает единицу. Освободившиеся в конце массива элементы заполнить нулями.
Вариант 5
……………………………………………………………………………………………………
В одномерном массиве, состоящем из n вещественных элементов, вычислить:
1) максимальный элемент массива;
2) сумму элементов массива, расположенных до последнего положительного элемента.
Сжать массив, удалив из все элементы, модуль которых находится в интервале [a,b]. Освободившиеся в конце массива элементы заполнить нулями.
Вариант 6
……………………………………………………………………………………………………
В одномерном массиве, состоящем из n вещественных элементов, вычислить:
1) минимальный элемент массива;
сумму элементов массива, расположенных между первым и последним положительными элементами]. Освободившиеся в конце массива элементы заполнить нулями.
Лабораторная работа №7. Сортировка массива.
Цель: Рассмотреть различные методы сортировки массивов. Сравнить их эффективность.
Линейная сортировка (сортировка отбором)
Идея линейной сортировки по невозрастанию заключается в том, чтобы, последовательно просматривая весь массив, отыскать наибольшее число и поменять его местами с первым элементом. Затем просматриваются элементы массива, начиная со второго, снова находится наибольший, который меняется местами со вторым и т. д.
I Программа линейной сортировки по невозрастанию
const n=20;
m: array [1..n] of byte =
(9,11,12,3,19,1,5,17,10,18,3,19,17,9,12,20,20,19,2,5);
var i,j,buf,l: byte; a: integer;
begin
writeln(‘Исходный массив:’);
for i:=l to n do write (‘_’, m[i]);
writeln; readln;
a:=0; { обнуляем счетчик итераций };
{ изменение размера неотсортированной части массива }
for i:=l to n-1 do
{ сравниваем поочередно i-й элемент неотсортированной части массива }
{ со всеми от i+1-го до конца }
for j:=i+l to n do
begin
a:=a+l;
if m[i]<rn[j] then { если в неотсортированной части массива }
{ нашли элемент, больший, чем i-й, то меняем их местами }
begin
buf := m[i]; { buf — буфер обмена }
m[i] := m[j] ; m[j] := buf;
end;
for 1:=1 to n do write (‘__‘, m[l]); { после сортировки }
writeln(‘; итерация # ' ',a); end.
По последнему значению a определяем, что для данного массива линейная сортировка по невозрастанию выполняется за 190 итераций.
Лабораторная работа №8. Сортировка массива.
Цель: Рассмотреть различные методы сортировки массивов. Сравнить их эффективность.
Сортировка методом "пузырька"
Один из самых популярных методов сортировки — "пузырьковый" основан на том, что в процессе исполнения алгоритма более "легкие" элементы массива постепенно "всплывают". Особенностью данного метода является сравнение, а затем, если нужно, и перестановка соседних элементов.
const n=20;
m: array [1..count] of byte =
(9,11,12,3,19,1,5,17,10,18,3,19,17,9,12,20,20,19,2,5);
var i,j,buf,l: byte; a: integer;
begin
riteln('Исходный массив:');
for i:1 to n do write(' ',m[i]);
writeln; readln;
a:=0;
for i:=2 to n do
begin
for j:=n downto i do
begin
a:=a+l;
if m[j-l]<in[j] then{ если элемент справа больше элемента }
{слева, то "вытесняем" его влево — пузырек "всплывает" }
begin
buf:=m[j-l]; { перестановка элементов }
m[j-l] :=m[j];
m[j]:=buf;
for i:=1 to n do write(' ',m[l]);
writeln(‘; итерация # ',a);
end;
end;
end;
end.
Определить количество итераций.
Лабораторная работа №9. Сортировка массива.
Цель: Рассмотреть различные методы сортировки массивов. Сравнить их эффективность.
Метод быстрой сортировки с разделением.
Оба выше рассмотренных метода достаточно просты и наглядны, но не эффективны. Значительно быстрее работает алгоритм сортировки К. Хоора, который называют сортировкой с разделением или "быстрой сортировкой". В основу алгоритма положен метод последовательного дробления массива на части и обмен элементами между частями.
Алгоритм метода является очень сложным и требует знания процедур и рекурсии,, поэтому приведем его здесь с минимальными комментариями в тексте самой программы.
Программа быстрой сортировки.
uses crt;
const n=20;
m: array [1..n] of byte =
(9,11,12,3,19,1,5,17,10,18,3,19,17,9,12,20,20,19,2,5) ;
var i,a: integer;
procedure quicks (first, last: integer) ;
var i,j,x,buf,1:integer;
begin
i:=first; { левая граница массива — первый элемент }