Структурированные данные и алгоритмы их обработки

Для повышения производительности и качества работы необходимо иметь данные, максимально приближенные к реальным аналогам. Тип данных, позволяющий хранить вместе под одним именем несколько переменных, называется структурированным. Каждый язык программирования имеет свои структурированные типы. Рассмотрим структуру, объединяющую элементы одного типа данных — массив.

Массивом называется упорядоченная совокупность однотипных величин, имеющих общее имя, элементы которой адресуются (различаются) порядковыми номерами (индексами). В качестве иллюстрации можно представить шкаф, содержащий множество пронумерованных ящиков (совокупность — «Ящик № 1», «Ящик № 2», «Ящик № 3» и т. д.; «Ящик» — общее имя всех ее элементов). Доступ к содержимому конкретного ящика (элементу массива) осуществляется после выбора ящика по его номеру (индексу). Элементы массива в памяти компьютера хранятся по соседству, одиночные элементы простого типа такого расположения данных в памяти не предполагают. Массивы различаются количеством индексов, определяющих их элементы.

Одномерный массив (шкаф ящиков в один ряд) предполагает наличие у каждого элемента только одного индекса. Примерами одномерных массивов служат арифметическая (а_i) и геометрическая (b_i) последовательности, определяющие конечные ряды чисел. Количество элементов массива называют размерностью. При определении одномерного массива его размерность записывается в круглых скобках, рядом с его именем. Например, если сказано: «задан массив А (10)», это означает, что даны элементы: a₁, a₂, …, а₁₀. Рассмотрим алгоритмы обработки элементов одномерных массивов.

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

Рассмотрим двумерный массив (шкаф с множеством ящиков, положение которых определяется двумя координатами — по горизонтали и по вертикали). В математике двумерный массив (таблица чисел) называется матрицей. Каждый ее элемент имеет два индекса а_ij, первый индекс i определяет номер строки, в которой находится элемент (координата по горизонтали), а второй, j — номер столбца (координата по вертикали). Двумерный массив характеризуется двумя размерностями N и М, определяющими число строк и столбцов соответственно.

Ввод элементов двумерного массива осуществляется построчно, в свою очередь, ввод каждой строки производится поэлементно, тем самым определяется циклическая конструкция, реализующая вложение циклов. Внешний цикл определяет номер вводимой строки (i), внутренний — номер элемента по столбцу (j). На рис. Представлен алгоритм ввода матрицы A (N на М).

Разберем примеры алгоритма на псевдокоде:

Дан массив целых чисел {A_i}, где i=1,2,3,…, M. Пусть M равно 15. Программа вычисляет произведение сумм некоторых элементов этого массива. В программе введены следующие константы: G=1; W=12; T=8; L=15.

ПРОГРАММА 15;

ФУНКЦИЯ SUMMA (I1,I2);

НАЧАТЬ ФУНКЦИЮ.

||S:=0;

||НЦ ДЛЯ I:=I1 ДО I2.

||||S:=S + A[I].

||КЦ;

||SUMMA:=S.

КОНЕЦ ФУНКЦИИ;

НАЧАТЬ ПРОГРАММУ.

||ПИСАТЬ ('ВВЕДИТЕ ЗНАЧЕНИЯ МАССИВА A:');

||НЦ ДЛЯ J:=1 ДО M.

||||ЧИТАТЬ (A[J]);

||КЦ;

||P:=SUMMA (G, W)*SUMMA (T, L);

||ПИСАТЬ ('ПРОИЗВЕДЕНИЕ РАВНО:', P:6).

КОНЕЦ ПРОГРАММЫ.

Для удобства дальнейших пояснений, перепишем псевдокод с номерами строк:

• 1 ПРОГРАММА 15;
• 2 ФУНКЦИЯ SUMMA (I1,I2);
• 3 НАЧАТЬ ФУНКЦИЮ
• 4 ||S:=0;
• 5 ||НЦ ДЛЯ I:=I1 ДО I2
• 6 ||||S:=S + A[I]
• 7 ||КЦ;
• 8 ||SUMMA:=S
• 9 КОНЕЦ ФУНКЦИИ;
• 10 НАЧАТЬ ПРОГРАММУ
• 11 ||ПИСАТЬ ('ВВЕДИТЕ ЗНАЧЕНИЯ МАССИВА A:');
• 12 ||НЦ ДЛЯ J:=1 ДО M
• 13 ||||ЧИТАТЬ (A[J]);
• 14 ||КЦ;
• 15 ||P:=SUMMA (G, W)*SUMMA (T, L);
• 16 ||ПИСАТЬ ('ПРОИЗВЕДЕНИЕ РАВНО:', P)
• 17 КОНЕЦ ПРОГРАММЫ.

В строке 1 записано название программы — «Программа 15».

В строке 2 описан заголовок функции Summa. Как видно из заголовка в функцию передается 2 формальных параметра — I1 и I2. Само тело функции записано в строках с 3 по 9. Проанализируем тело функции.

В строке 4 переменной S присваивается начальное значение равное 0.

В строках с 5 по 7 записан цикл. Количество повторений цикла известно — оно равно I2-I1. В теле цикла (строка 6) производится прибавление к прежнему значению переменной S элемента под номером I массива из A.

После цикла, в строке 8 записан результат, который будет выдавать функция (это называется — возвращать результат) — результат равен значению переменной S.

Например, если I1=1, I2=1, A[1]=1, A[2]=2, A[3]=4, то выполнение тела функции будет происходить следующим образом:

Шаг 1: 4 ||S:=0;

Шаг 2: 5 ||НЦ ДЛЯ I:=1 ДО 3.

Шаг 3: 6 ||||S:=0 + A[1]=0+1=1.

Шаг 4: увеличение счетчика цикла: I=I+1=1+1=2.

Шаг 5: возврат на начало цикла (строка 5).

Шаг 6: 6 ||||S:=1 + A[2]=1+2=3.

Шаг 7: увеличение счетчика цикла: I=I+1=2+1=3.

Шаг 8: возврат на начало цикла (строка 5).

Шаг 9: 6 ||||S:=3 + A[3]=3+3=6.

Шаг 10: увеличение счетчика цикла: I=I+1=3+1=4.

Шаг 11: возврат на начало цикла (строка 5).

Шаг 12: поскольку значение счетчика цикла больше чем заданный предел (I2=3) то происходит выход из цикла и переход на сроку за циклом Шаг 13: 8 ||SUMMA:=S=6.

Шаг 14: завершение функции Итак, функция производит суммирование всех элементов массива A, начиная с элемента с номером I1 и заканчивая номером I2. Математически, это записывается:

В строке 10 начинается выполнение программы.

В строке 11 на экран выводится надпись «ВВЕДИТЕ ЗНАЧЕНИЯ МАССИВА A:».

В строках с 12 по 14 записан цикл, в котором последовательно вводятся элементы массива A.

В строке 15 вызывается функция SUMMA с фактическими параметрами G и W и еще раз с фактическими параметрами T и L. Результат перемножается и присваивается переменной P.

В строке 16 на экран выводится надпись «ПРОИЗВЕДЕНИЕ РАВНО» и после нее значение переменной P.

Итак, программа выполняется следующим образом:

Шаг 1: на экран пишется «ВВЕДИТЕ ЗНАЧЕНИЯ МАССИВА A:» (строка 10).

Шаг 2: в цикле вводятся элементы массива A (строки 12−14, количество повторений цикла М-1).

Шаг 3: выполняется вызов функции SUMMA (строка 15).

Шаг 4: выполняется тело функции SUMMA (строки 2−9. При.

этом вместо I1 подставляется G, а вместо I2 подставляется W. Результат:

).

Шаг 5: выполняется тело функции SUMMA (строки 2−9. При.

этом вместо I1 подставляется T, а вместо I2 подставляется L. Результат:

).

Шаг 6: переменной P присваивается произведение результатов вызовов функций SUMMA (строка 15. Результат:

).

Шаг 7: на экран выводится «ПРОИЗВЕДЕНИЕ РАВНО:» (строка 16).

Шаг 8: на экран выводится значение переменной P (строка 16).

Шаг 9: выполнение программы завершается (строка 17).