Алгоритмы обработки одномерных информационных массивов

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

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

Каждый массив содержит однородные сведения о некоторой совокупности объектов. Такими объектами могут быть: последовательности заработных плат по табельным номерам работников; перечень выпуска различного вида продукции по месяцам года; товары на складе по кодовым номерам и т.д.

Обработка информационных массивов заключается: в пополнение массивов данных новыми сведениями, разнообразное изменение элементов массивов и вывод результатов обработки.

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

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

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

1) нахождение суммы, произведения, среднего значения;

2) нахождение суммы или количества элементов массива, удовлетворяющих некоторым условиям;

3) нахождение минимального (максимального) элемента массива и его номера;

4) создание нового массива из элементов имеющегося;

5) сортировка элементов массива.

Выполним построение математической модели и указанных выше алгоритмов 1) – 4) функциональной задачи денежного оборота торговой фирмы.

Пример 7. Имеются данные о ежедневном обороте торговой фирмы в течение месяца, т.е. одномерный массив, содержащий 30 элементов, A(30):

№ дня				...
Оборот				...

 

а) Обозначение переменных:

А(30) – массив оборота, размерностью 30 элементов;

А(i) – элемент массива А (оборот в i-тый день), тыс. руб.;

i – счётчик цикла, номер дня;

S – общая суммы оборота фирмы за месяц, тыс. руб.;

C – средний оборот фирмы за месяц, тыс. руб.;

D – план оборота за день, тыс. руб.;

К – количество дней c оборотом D;

М – минимальный (максимальный) оборот за месяц, тыс. руб.;

NM – номер дня с минимальным (максимальным) оборотом;

В(10) – новый массив оборота, размерностью 10 элементов;

B(i) – элемент массива В (оборот в i-тый день), тыс. руб.;

б) Тип переменных:

i, K, NM – простые переменные целого типа;

S, C, D, M – простые переменные вещественного типа;

А(i), B(i) – переменные с индексами вещественного типа.

в) Классификация по группам:

исходные данные: А(30); промежуточный результат: i;

результаты: S, C, D, M, NM, К, B(10).

г) Системы расчетных формул для различных типов задач:

1) определение общей и средней суммы оборота за месяц:

S = 0	сумма обнуляется, чтобы к S не добавилось случайное значение, оставшееся в переменной S от предыдущего вычисления
i = 1	начальный номер элемента
S = S + А(i)	накопление суммы в цикле
i = i + 1	формирование номера следующего элемента

Если i≤30, то повторять действия, иначе выход из цикла

C = S/30

нахождение среднего значения

2) нахождение количества дней с оборотом, равным (£, ³, ¹,>,<) плану D:

К = 0	обнуление К
i = 1	начальный номер элемента

Если А(i)=D, то K = K + 1 накопление количества

i = i + 1

формирование номера следующего элемента

Если i≤30, то повторять действия, иначе выход из цикла

3) определение максимального оборота предприятия за данный период и номера дня с максимальным оборотом:

M = A(1)	за начальное значение максимума выбираем первый элемент
NM = 1	начальный номер максимального элемента
i = 2	начальный номер следующего элемента
Если А(i)>M, то M = A(i); NM= i	формирование нового максимума и его номера
i = i + 1	формирование номера следующего элемента

Если i≤30, то повторять действия, иначе выход из цикла

Примечание. Если М – минимум, то условие имеет вид: A(i)<М.

4) 5% ежедневного оборота отчисляется в дополнительный фонд заработной платы. Организовать новый массив, содержащий информацию об ежедневном отчислении.

i = 1	начальный номер элемента
В(i) = 0,05*А(i)	формирование элемента нового массива
i = i + 1	формирование номера следующего элемента

Если i≤30, то повторять действия, иначе выход из цикла

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

Представим алгоритм определение общей и средней суммы оборота в виде блок-схемы (рис.10):

Рис. 10 Блок-схема обработки массива к примеру 7-1)

Примечание. Блок-схема накопления произведения элементов массива имеет тот же вид, что на рис. 10. Но первоначальное значение произведения Р=1; формула накопления произведения имеет вид: P = P * A(i).

Представим алгоритм нахождение количества дней с оборотом, равным плану D в виде блок-схемы (рис.11):

 

Рис. 11 Блок-схема обработки массива к примеру 7-2)

Представим алгоритм определение максимального оборота предприятия за данный период в виде блок-схемы (рис.12):

 

Рис. 12 Блок-схема обработки массива к примеру 7-3)

Представим алгоритм организации нового массива в виде блок-схемы (рис.13):

Рис. 13 Блок-схема обработки массива к примеру 7-4)

Примечание. В блок-схеме цикл вывода результативного массива реализуется через блок модификации аналогично циклу ввода.

Пример 8. Имеются данные о продуктах на складе. Определить общий вес продуктов, срок хранения которых менее 1 месяца и вывести их список.

Таблица 3 – Исходные данные для примера 8

N	Наименование	Вес, кг	Срок хранения, дни
	Картофель
	Сахар
	Мука
	Хлеб
	Крахмал
	Конфеты
	Печенье
	Вафли

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

а) Обозначения переменных:

N – количество продуктов;

Р(N) – массив наименований продуктов;

K(N) – массив веса продуктов;

С(N) – массив сроков хранения;

i – счётчик цикла, номер продукта в таблице;

P(i), K(i), C(i) – наименование, вес, срок хранения i-того продукта;

S – общий вес продуктов, срок хранения которых меньше месяца.

б) Тип переменных:

N, i – простые переменные целого типа;

Р(N) – массив символьного (строкового) типа;

K(N), С(N) – массив вещественного типа;

P(i), K(i), C(i) – переменные с индексом;

S – простая переменная вещественного типа.

в) Классификация по группам:

исходные данные: N, Р(N), K(N), С(N);

промежуточный результат: i; результат: S.

г) Система расчетных формул:

S = 0	обнуление К
i = 1	начальный номер элемента

Если C(i)<30, то S = S + K(i) накопление суммы веса

i = i + 1

формирование номера следующего элемента

Если i≤N, то повторять действия, иначе выход из цикла

Представим алгоритм накопления общего веса продуктов в виде блок-схемы (рис.14):

 

Рис. 14 Блок-схема алгоритма к примеру 8

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

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

Сортировка «пузырьком» (обменная) состоит в сравнении каждого элемента со следующим за ним стоящим элементом (x_i и x_i+1) и обмена (перестановки) их, если элементы стоят не в нужном порядке (допустим, x_i > x_i+1). После первого такого просмотра массива наибольший элемент переместится в нужную позицию (на последнее место в массиве). Затем подобная процедура выполняется для массива на один элемент короче, и т.д. На каждом просмотре новый элемент помещается в требуемую позицию, следовательно, для сортировки массива из n элементов нужно не более n-1 просмотра.

Исходными данными являются: целочисленное значение n и элементы массива x_i, i=1,2,...,n; результат уже отсортированный массив x. Учтем с помощью переменной fl тот факт, что если на каком-то промежуточном этапе массив уже отсортирован, то при просмотре его элементов не происходит ни одной перестановки и дальнейшие просмотры не нужны. Если выполняется ветвь алгоритма, в которой происходит перестановка (обмен) элементов, то переменной fl присваивается значение 1. Представим этот алгоритм в виде блок-схемы (рис. 15).

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

Исходными данными являются: целочисленное значение n и элементы a_i, i=1,2,...,n; результат уже отсортированный массив a.

Внешний цикл (счетчик i) «перебирает укорачивающиеся массивы, количество которых n-1 и переставляет наибольший элемент на последнее (i-тое) место массива. Внутренний цикл (счетчик j) в рассматриваемом массиве находит значение Be и место nBe максимального элемента. Представим этот алгоритм в виде блок-схемы (рис. 16).

 

Рис. 15 Блок-схема алгоритма обменной сортировки

 

Рис. 16 Блок-схема алгоритма сортировки посредством выбора

В примере сортировки посредством выборапоказана структура вложенных циклов: внешний цикл с параметром i, внутренний цикл – с параметром j.

Вложенным циклом или циклом в цикле называется такая структура, когда телом одного цикла является другой.

Примечание. В блок-схемах (рис. 15, рис. 16, рис.17) приведён укрупнённый цикл вывода массива в виде одного блока.

Пример 9. По условию примера 8 провести сортировку элементов массива К(N) – веса продуктов в порядке возрастания.

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

а)-б)-в) В дополнение к ранее объявленным переменным введём вспомогательные переменные, которые являются промежуточными результатами:

l – сохраняет номер продукта с наименьшим весом на определённом этапе сортировки, простая переменная целого типа;

j – счётчик внутреннего цикла, простая переменная целого типа;

Pr – сохраняет наименьший вес продукта на определённом этапе сортировки, простая переменная вещественного типа.

г) Система расчетных формул:

i = 1	начальное значение счётчика внешнего цикла
l = i	сохраняем начальный номер
j = i + 1	начальное значение счётчика внутреннего цикла

Если К(j)≤K(l), то l = j сохраняем номер продукта с

наименьшим весом

j = j + 1

следующее значение счётчика внутреннего цикла

Если j≤N, то повторять действия, иначе выход из цикла

Pr = K(i): K(i) = K(l): K(l) = Pr	перестановка
i = i + 1	следующее значение счётчика внешнего цикла

Если i≤N-1, то повторять действия, иначе выход из цикла

 

Представим алгоритм сортировки методом вставки в виде блок-схемы (рис. 17):

Рис. 17 Блок-схема алгоритма сортировки к примеру 9