Основные процедуры обработки массивов данных

Цель работы: получение практических навыков при алгоритмизации и программировании циклических вычислительных процессов при работе с одномерными массивами.

Теоретическая часть

Массивом называется упорядоченная последовательность величин, обозначаемая одним идентификатором (именем). Члены этой последовательности называются элементами массива. Отношение порядка между элементами массива задается с помощью индексирования. Каждый элемент массива определяется именем массива и его положением в массиве, т.е. значениями индексов.

Для массива характерно следующее:

каждый элемент массива может быть явно обозначен и к нему имеется прямой доступ;

Максимальное число компонент массива определяется при его описании и в дальнейшем не меняется.

Например:

var t: array [1..20] of real;

F: ARRAY [1..50] oF INTEGER;

Эти записи означают, что в программе будут использоваться массив t_k, состоящий из 20 вещественных элементов, и массив f_m, состоящий из 50 целых чисел.

Индексы заключаются в скобки. Например, запись T[1], T[2], T[К] - соответствует индексированным переменным t₁, t₂, t_к.

Индекс задается целой константой, целой переменной или выражением, принимающим целые значения.

Значение индекса в программе должно быть не меньше нижней границы и не больше верхней.

Привлечение переменных типа integer позволяет использовать третий оператор цикла, который называется оператором цикла с параметром:

for i:=A to B do Р,

здесь i - некоторая переменная типа integer, которая называется параметром цикла, А и В - выражения со значением типа integer, P - оператор (тело цикла).

Оператор цикла с параметром выполняется так. Сначала вычисляются значения выражений А и В. Получаются два целых числа, которые мы обозначим, соответственно, через А и В. Если А £ В, то переменная i последовательно принимает значения, равные А, А + 1, А + 2,..., В, и для каждого из этих значений выполняется оператор P. Если А > В, то оператор P не будет выполнен ни разу и выполнение оператора цикла с параметром сразу же закончится. Для описания действия оператора цикла FOR используем блок "модификация" (см. рис. 5.1).

 

Рис. 5.1. Блок-схема оператора FOR

 

Например, для начального s=0 и любого положительного n при выполнении оператора

for i:=1 to n do s:=s+i*i*i

переменная s примет значение 1³+2³+...+n³.

Имеется еще один вариант последнего оператора цикла с параметром:

for i:= A downto B do P;

Здесь i принимает последовательно значения А, А-1,..., В и для каждого из них выполняется оператор P, если же А меньше В, то оператор P не выполняется ни разу.

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

Работа с элементами массива сводится к организации циклов, где параметром цикла является индекс, обычно используется оператор: for i:=N to K do S, где i - индекс, N и K – начальное и конечное значение индекса, S - оператор (тело цикла).

Так, чтобы ввести значения t₁, t₂, t_3,..t₂₀ вместо предложения

read (t[1], t[2], t[3],...t[20]);

достаточно указать:

for i:=1 to 20 do read (t [i]);

Пример 5.1. Ввести последовательность a_i,...,a_n, состоящую из целых чисел, где n<=15. Требуется определить наибольший член массива a_k a_i,...,a_n вместе с его порядковым номером k. В программе текст, выделенный жирным шрифтом, следует запомнить и использовать для всех программ, где требуется ввести одномерный массив.

Программа 5.1.

program maximum;

var i, n, k, M: integer;

a: array [1...15] of integer;

begin

writeln (‘Введите количество элементов массива ‘);

readln (n);

writeln (‘Введите элементы массива ‘);

for i:=1 to n do readln (a [i]);

k:=1; M:=a[1];

for i:=2 to n do

if a[i]> M then begin M:=a[i]; k:=i end;

write (‘наибольшее=‘,M:5,’ индекс =‘,k:2);

end.

Пример 5.2. Пример относится к упорядочиванию (сортировке) массива x₁,..., x_n. Задача упорядочивания возникает при оформлении статистических сводок, справочных материалов и т.д. Процесс упорядочивания при большом объеме данных очень трудоемок и здесь часто прибегают к помощи компьютеров. Пока рассмотрим задачу упорядочивания в простейшей постановке: дан числовой массив x₁,..., x_n, элементы которого различны, требуется переставить элементы массива так, чтобы после перестановки они были упорядочены в порядке возрастания: x₁<...< x_n. Опишем один из алгоритмов решения этой задачи.

Очевидно, что первое место в массиве должен занять наименьший элемент, второе место - наименьший из всех остальных элементов и т.д.

Схема решения может быть следующей (см. рис. 5.2):

описание данных;

вывод исходного массива х;

поиск наименьшего элемента среди всего массива;

перестановка местами с первым элементом;

печать первого элемента;

поиск наименьшего среди оставшихся элементов;

перестановка местами со вторым элементом;

печать второго элемента;

выполнение аналогичных действий, вплоть до сравнения последних элементов массива x_n-1 и x_n.

Для перестановки текущего x[i] с найденным x[k] привлекаем дополнительную переменную v: v:=x[i]; x[i]:=x[k]; x[k]:=v;

 

Рис. 5.2. Блок-схема алгоритма решения примера 5.2

Программа 5.2. program poradok; var x: array[1..100] of real; v: real; n, i, j, k: integer; begin writeln (‘Введите количество элементов ‘); readln (n); writeln (‘Введите элементы ‘); for i:=1 to n do readln (x [i]); writeln (‘Исходный массив ‘); for i:=1 to n do writeln (' x [',i:4,'] = ', x[i]:7:2);   writeln (‘Упорядоченный массив ‘); for i:=1 to n-1 do { внешний цикл, где будут рассматри-ваться все элементы, затем без первого, без второго и т.д.} begin for k:=i+1 to n do { внутренний цикл по поиску минимального элемента } if x[i] > x[k] then     begin v:=x[i]; x[i]:=x[k]; x[k]:=v; end;     writeln (' x [',i:4,'] = ', x[i]:8:2); end;     end.

Задание к лабораторной работе

Модифицировать полученную при выполнении работы №3 программу таким образом, чтобы на ПК автоматически осуществлялись многократное "решение" задачи при различных значениях одного из исходных данных, предварительно введенных в оперативную память ПК. Численные результаты должны запоминаться в памяти в виде одномерного массива (исходная переменная, ряд значений которой задается для многократного решения задачи, определяется студентом самостоятельно). Результат вывести в виде таблицы.

Методические указания

Задание на программирование предполагает организацию на ПК циклического вычислительного процесса - определение результатов задачи должно автоматически осуществляться для нескольких вариантов исходных данных, которые отличаются значениями одного из них. Однако все значения этого изменяемого аргумента должны заранее вводиться в оперативную память ПК в виде одномерного массива чисел. Кроме того, в задании оговаривается, что и результаты каждого решения задачи должны запоминаться как численный массив. Таким образом, в процессе обработки данных на ПК должны выполняться операции над элементами одномерных массивов чисел.

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

ввод исходных данных, в том числе количества значений и самих значений массива;

многократно выполняемый цикл определения и запоминания в памяти ПК результатов вычислений - формирование массива значений результатов;

вывод результатов как элементов соответствующего массива.

В качестве идентификаторов элементов массивов следует использовать индексированные переменные, учитывая, что значение индекса определяет порядковый номер элемента в массиве (например, X_i, означает первый элемент массива X, если i = 1, второй элемент этого же массива, если i = 2 и т.д.). Поэтому управляющей переменной циклического алгоритма должна быть переменная - индекс, используемая в теле цикла (вместе с именами массивов) для обозначения элементов исходного и искомого массивов. Значение же индекса при повторении цикла должно меняться от 1 до N с шагом 1, где N - количество значений аргумента.

В Паскаль-программе, предусматривающей ввод, обработку, формирование и вывод массивов данных, следует обязательно описать их соответствующими невыполняемыми операторами. В операторе описания одномерного массива указывается тип значении элементов массива с помощью определенного ключевого слова (INTEGER, REAL и т.п.), имя массива и количество элементов в массиве.

Ввод массива значений аргумента в программе следует предусмотреть с помощью структуры повторения оператора ввода одного элемента этого массива., например, так:

Writeln ('N='); Readln (N);

For k:=1 tо N do Read (X[k]);

Контрольные вопросы и упражнения

Что собой представляют массивы данных?

Какова роль индексированных переменных при программировании задач по обработке массивов данных?

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

Что собой представляют структуры повторения по обработке массивов данных?

В чем смысл и необходимость описания массивов в Паскаль-программах?

Все ли операторы цикла можно использовать для организации работы с элементами массивов?

Какие ограничения накладываются на использование оператора FOR для описания циклов?

Прокомментируйте составленную вами программу.

Определите в массиве количество нулевых элементов, сумму положительных элементов, индексы отрицательных элементов.

Определите, есть ли в данном массиве два соседних положительных числа. Если есть, выведите индексы первой (последней) пары.

Используя оператор FOR, решите старинную задачу. Сколько можно купить быков, коров и телят, если плата за быка 10 руб., за корову – 5 руб., за теленка = полтинник (0,5 руб.), если на 100 руб. надо купить 100 голов скота.

Лабораторная работа №6

Разработка и отладка Паскаль - программы со сложным циклом

Цель работы: получение практических навыков при алгоритмизации и программировании сложных циклических вычислительных процессов при работе с массивами.

Теоретическая часть

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

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

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

Следует отличать размерность массива от размера массива. Если размерность массива - это, по существу, число индексов, определяющих положение элемента в массиве, то размер массива - это число элементов в массиве.

Так, например, элементы матрицы

y₁₁ y₁₂ y₁₃

y =

y₂₁ y₂₂ y₂₃

записываются в программе как Y [1,1], Y [1,2], Y [1,3] и т.д., или в общем виде как Y [I, K]; где I - номер строки, К - номер столбца. При этом переменная I может принимать значения 1, 2, а переменная К - значения 1, 2, 3. Таким образом, индекс указывает не только положение элемента в массиве, но и количество измерений массива.

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

При алгоритмизации и программировании сложного циклического процесса используются вложенные в друг друга типовые структуры повторения таким образом, чтобы за одно использование внешнего цикла внутренний цикл повторялся многократно. Этого можно добиться, если тело внешнего цикла будет содержать внутренний цикл полностью (см. рис. 6.1).

Рассмотрим некоторые примеры решения задач с использованием сложных циклов и индексированных переменных.

Пример 6.1. Пусть дана матрица размера n x K (значение n – не более 10), состоящая из действительных чисел, надо преобразовать матрицу: поэлементно вычесть последний столбец из всех столбцов, кроме последнего (столбец с номером j - это элементы a[1, j], a[2, j],..., a[n, j]).

Текст, выделенный жирным шрифтом, можно использовать для ввода и вывода матрицы в своих программах.

Программа 6.1.

program COLUMN;

var а: array[1..10,1..10] of real; i, j, n, k: integer;

begin

writeln ('Введите размеры матрицы');

read(n,k);

writeln('Введите элементы матрицы построчно');

for i:=1 to n do for j:=1 to k do read(a[i,j]);

writeln(' Исходная матрица: ');

for i:=1 to n do

Begin

for j:=1 to k do write (a[i,j]:10:2); writeln(' ');

end;

for j:=1 to k-1 do

for i:=1 to n do a[i,j]):= a[i,j]):- a[i,n]);

writeln (' Результат выполнения программы: ');

for i:=1 to n do begin

for j:=1 to k do write (a[i,j]:10:2);

writeln(' ');

end;

end.

 

 

For i:=1 to n do

 

 

For j:=1 to m do

 

Begin

Процедура Р₁

Процедура Р₁ Процедура Р₂

………

end

 

 

Рис. 6.1. Блок-схема алгоритма сложного цикла

 

Пример 6.2. Дана матрица размера N x M, состоящая из вещественных чисел. Требуется упорядочить (переставить) строки матрицы по возрастанию первых элементов строк. Взяв за образец схему программы poradok из предыдущей работы, указав 5х6 в качестве размера матрицы, получаем следующее:

Программа 6.2.

program poradok;

const n=5; m:=6;

var x: array[1..n,1..m] of real; i, j, l: integer; v: real;

begin

writeln(' Введите элементы матрицы построчно'); writeln(' Количество строк=', n:2,

'Количество столбцов=', m:2);

for i:=1 to n do

for j:=1 to m do read(x[i,j]);

writeln(' Исходная матрица: ');

for i:=1 to n do begin

for j:=1 to m do write (x[i,j]:8:2); writeln(' ');

end;

for i:=1 to n-1 do

for j:=i+1 to n do

if x[j,l] < x[i,l] then

for l:=1 to m do begin

v:=x[i,l]; x[i,l]:=x[j,l]; x[j,l]:=v;

end;

writeln (' Упорядоченная матрица ');

for i:=1 to n do begin

for j:=1 to m do write (x[i,j]:8:2); writeln(' ');

end;

end.

Задание к лабораторной работе

Модифицировать полученную при выполнении работы №5 программу таким образом, чтобы на ПК автоматически осуществлялись многократные решения задачи при изменении значений двух исходных переменных (для каждой пары заданных значений). Численные результаты должны быть получены в виде двумерного массива данных (исходные переменные, значения которых должны изменяться при многократном решении задачи, определяются студентом самостоятельно). Вывод по-прежнему в виде таблицы.

Методические указания

Задание предполагает организацию на ПК "сложного" циклического вычислительного процесса, в ходе которого результаты решения задачи (обозначены здесь R) определяются многократно для разных значений двух аргументов (например, X, Y):

R _i,j = P (X_i,Y_j,...), где i = 1,2,...,N; j = 1,2,..., M.

Данный циклический процесс является (называется) "сложным", т.к. содержит два вложенных друг в друга цикла. Повторение внутреннего цикла М раз приводит к определению результатов при некотором фиксированном значении одного из изменяющихся аргументов (например, при X_i) для каждого значения второго аргумента (Y₁, Y₂,..., Y_M):

R _i,1 = P (X_i, Y₁,...),

R _i,2 = P (X_i,Y₂,...),

...

R _i,m = P (X_i,Y_m,...),

Повторение же внешнего цикла N раз - киспользованию всех заданных значений первого аргумента для определения результатов (Х₁ для получения R₁,₁, R _1,2,…, Х₂ для получения R ₂,₁, R _2,2,…, R _2,m и т.д.).

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

Результаты же решения задачи для каждого варианта исходных данных (этого требует задание) должны представляться как элементы двумерных массивов чисел. Следовательно, искомыми переменными будут индексированные переменные с двумя индексами (например, R _i.j).

С учетом вышеизложенного внешняя и внутренняя структуры повторения сложного цикла алгоритма задачи в качестве управляющих переменных должны содержать переменные - индексы (например, I, J), используемые для обращения к элементам исходных и искомых массивов чисел (рис. 6.1). Подчеркнем, что внутренняя структура повторения, задаваемая в ПАСКАЛЬ-программе с помощью операторов цикла, должна полностью находиться между операторами цикла внешней структуры повторения.

Контрольные вопросы и упражнения

Что понимают под сложным циклическим процессом?

Каковы правила записи вложенных друг в друга структур повторения (сложных циклов) на языке ПАСКАЛЬ.

Что собой представляют двумерные массивы данных? Каким образом предусматриваются операции над элементами их в алгоритмах и программах?

Прокомментируйте разработанную вами программу.

Напишите программу вывода элементов главной диагонали квадратной матрицы и вычисления суммы этих элементов.

Поменяйте местами первый максимальный и последний минимальный элементы двумерного массива.

Составьте программу вычисления и вывода на экран арифметического квадрата, в котором первый столбец и первая строка заполнены 1 (единицами), а каждый из остальных элементов равен сумме соседних элементов сверху и слева.

Заменить все четные элементы матрицы на ближайшие нечетные, определить их количество.

Приложения

Приложение 1