Вопросы для проверки знаний

End.

Begin

Begin

Begin

End.

Begin

End.

Begin

writeln('Vvedite elementi massiva A');

for i:=1 to 10 do begin write(' A[',i,']=');readln(A[i]);end; {ввод элементов А}

writeln(' Entert massiv A:');

for i:=1 to 10 do write(' A[',i,']=',A[i]:4); writeln; {вывод элементов А}

MaxMod:=A[1];NMax:=1; {начальное присваивание элемента и его номера}

for i:=2 to 10 do if (abs(A[i])>abs(MaxMod))and((i mod 2)=1) {проверка на оптимальность выбранного элемента массива и нечетности текущего значения номера элемента i }

then begin MaxMod:=A[i]; NMax:=i end; {замена элемента и его номера}

writeln(' Rezult: NMax=',NMax,' MaxMod=', MaxMod); {вывод результатов расчета}

Рассмотрим другие характерные задачи, решаемые с помощью линейных массивов, и фрагменты кода, решающие их на примере массива a[1..n]. Для вспомогательных операций используется дополнительная переменная t.

1. Вставка и удаление элементов из массива. Если в процессе расчетов возникает необходимость выполнять операции данного вида, то простейшим решением является описание массива заведомо достаточного размера и запоминание его длины в дополнительной переменной-счетчике.

Например, необходимо вставить в достаточно объемный массив a со счетчиком n после элемента с номером k новый элемент, равный b. Для того, чтобы не потерять значения элементов массива и минимизировать число операций, присваивания лучше выполнять с конца массива:

n:=n+1; for i=n downto k+2 do a[i]:=a[i-1]; a[k+1]:=b;

Удаление из массива a со счетчиком n элемента с номером k:

n:=n-1; for i=k to n do a[i]:=a[i+1];

2. Циклический сдвиг элементов в рамках массива. Обычно применяют сдвиг слева направо с возрастанием номеров элементов: a[1]®a[2]; a[2]®a[3];… a[n-1]®a[n]; a[n]®a[1].

Как и при вставке, меньшее число операций затрачивается при выполнении операции, начиная со старших элементов (при этом необходимо запомнить только последний элемент a[n]):

t:=a[n]; for i=n downto 2 do a[i]:=a[i-1]; a[1]:=t;

Cдвиг справа налево с убыванием номеров элементов (a[2]®a[1]; a[3]®a[2];… a[n]®a[n-1]; a[1]®a[n]) выполняется аналогично:

t:=a[1]; for i=1 to n-1 do a[i]:=a[i+1]; a[n]:=t;

3. Вычисление средних значений элементов массива. Важнейшей статистической характеристикой элементов числового массива a[1..n] является среднее значение его элементов: m=(a[1]+a[2]+…+a[n])/n. С использованием текущего значения суммы элементов S код для расчета m имеет вид:

S:=0; for i=1 to n do S:=S+a[i]; m:=S/n;

С применением рассмотренных операций можно решать более сложные задачи, требующие изменения структуры самого массива.

Пример 2. Инициализировать в программе значения элементов целочисленного линейного массива A[1..10] величинами { 81,-54,-72,295,-85,10,44,58,-32,59 }. Сформировать из массива A два массива размером 5, в первый с названием B поместить все элементы с нечетными номерами, во второй С – c четными. Перед обработкой распечатать исходный массив A[1..10], после обработки – новые массивы B и С.

Решение. Инициализацию массива A выполняем с использованием типизированной константы, предварительно введя тип массива. Для задания номеров элементов вводим в программе дополнительные счетчики j и k, которым вначале задаем нулевые значения. Массивы B[1..5] и С[1..5] формируем, поочередно занося в них элементы массива A и наращивая соответствующие счетчики.

type array_10 = array[1..10] of integer; {описание типа массива A}

const a:array_10 = (81, -54, -72, 295, -85, 10, 44, 58, -32, 59);

var b,c: array[1..5] of integer; {описание массивов B,C}

i,j,k: integer; {описание вспомогательных переменных i,j,k }

writeln(' Entert massiv a:');

for i:=1 to 10 do write(' a[',i,']=',a[i]:4); writeln; {вывод элементов a}

j:=0;k:=0; {начальные присваивания текущих номеров элементов в массивах B и С}

for i:=1 to 10 do if (i mod 2)=1 {проверка нечетности текущего номера элемента i }

then begin j:=j+1;b[j]:=a[i] end {засылка очередного элемента в массив B}

else begin k:=k+1;c[k]:=a[i] end; {засылка очередного элемента в массив С}

writeln(' Rezult massiv B:');

for i:=1 to 5 do write(' b[',i,']=',b[i]:4); writeln; {вывод элементов B}

writeln(' Rezult massiv C:');

for i:=1 to 5 do write(' c[',i,']=',c[i]:4); {вывод элементов C}

Пример 3. Пузырьковая сортировка. Алгоритмы сортировки, которые упорядочивают все элементы линейного массива по возрастанию или убыванию заданного их признака, составляют отдельный класс. Самым простым (но не очень эффективным) из них является сортировка простыми обменами (пузырьковая сортировка, англ. - bubble sort)). Данная сортировка относится к классу обменных сортировок, в котором все перестановки осуществляются на месте, в пределах массива за счет перемены мест его элементов. Работа алгоритма заключается в осуществлении последовательных проходов по массиву с обменом местами пар соседних элементов, у которых нарушен требуемый порядок. Заканчивается его работа после очередного прохода, на котором не было выявлено ни одного нарушения порядка относительного положения элементов. Алгоритм оформлен в виде процедуры сортировки по возрастанию числового массива A типа Num_Array с элементами типа integer и заданной длиной count. Для контроля окончания сортировки (завершения проходов по массиву) дополнительно введен логический ключ key. При смене местами элементов A[i] и А[i-1] использована круговая пересылка с использованием вспомогательной величины con: A[i]®con; А[i-1]®A[i]; con®А[i-1]:

{ сортировка пузырьковым методом}

procedure Bubble_sort(var A:Num_Array; count:integer);

var con,i: integer; key: boolean;

key:= true; {начальное задание истинного значения ключа}

while key do {цикл с предусловие по значению ключа}

key:= false; {задание ложного значения ключа, пока не найдено нарушения порядка}

for i:= 2 to count do {проход по массиву}

if A[i]<A[i-1] then { проверка правильности рядом стоящих элементов}

begin {регистрация нарушения порядка и смена двух подряд стоящих элементов}

key:= true; {задание истинного значения ключа - найдено нарушения порядка }

con:= A[i-1]; { круговая пересылка значений A[i-1],A[i],con }

A[i-1]:= A[i];

A[i]:= con;

end; {окончание действий при нарушении порядка соседних элементов}

end; {окончание тела цикла while }

end; {окончание тела процедуры}

Пример 4. Ввести с клавиатуры значения элементов (не превышающих по модулю 1000) двух целочисленных массивов A[1..5] и B[1..5]. Преобразовать их по правилу: больший из каждой пары элементов A[i] и B[i] принять в качестве нового значения A[i], а меньший – в качестве нового значения B[i]. Перед обработкой распечатать исходные массивы A[1..5] и B[1..5], после обработки – новые значения элементов массивов.

Решение. При необходимости смены местами элементов A[i] и B[i] использована круговая пересылка с использованием дополнительной величины con: A[i]® con; B[i]® A[i]; con ® B[i]. Код для ввода и начального вывода значений массивов A и B совпадает с аналогичным кодом из примера 1, вывод результирующих массивов – по примеру 2.

var a,b: array[1..5] of integer; {описание массивов}

i,con: integer; {описание вспомогательных переменных i и con }

…// ввод и начальный вывод массивов A и B - по примеру 1

for i:=1 to 5 do

if A[i]<=B[i] then {преобразование элементов массивов}

begin con:=A[i]; A[i]:= B[i]; B[i]:= con end;

…// вывод результирующих массивов A и B - по примеру 2

1. Какие массивы называют линейными?

2. Как контролируется в простейшем варианте размер массива при вставке и удалении из него отдельных элементов?

3. В чем заключается циклический сдвиг элементов в рамках массива? Назовите два его варианта.

4. Какие алгоритмы называют сортировкой?

5. Какие алгоритмы составляют класс обменных сортировок?

6. В чем заключается пузырьковая сортировка?

Практические задания.

1. Разработать и отладить код программы, в которой:

а) вводятся с клавиатуры значения элементов целочисленного массива A[1..10],

б) массив выводится на экран,

в) вычисляется общее количество отрицательных элементов N и их сумма S,

г) значения N и S выводятся на экран.

2. Разработать и отладить код программы, в которой:

а) вводятся с клавиатуры значения элементов вещественного массива A[1..12],

б) массив выводится на экран,

в) сформировать из A два массива, в одном из них – все неотрицательные элементы A, в другом – все отрицательные,

г) оба сформированных массива вывести на экран.

Дата добавления: 2014-01-06