![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритмы обработки одномерных информационных массивов
Информационный массив с позиции логической структуры, отображающей состояние экономической системы, представляет собой набор данных (документов) одной формы (одного названия) со всеми их значениями либо сочетание таких наборов данных, относящихся к одной функциональной задаче. При решении функциональных задач управления по планированию, учету, анализу и регулированию хозяйственной и коммерческой деятельности предприятия в памяти компьютера создаются информационные массивы - упорядоченные последовательности элементов одного типа, обращение к которым осуществляется при помощи его имени и индекса (т.е. порядкового номера элемента). Каждый массив содержит однородные сведения о некоторой совокупности объектов. Такими объектами могут быть: последовательности заработных плат по табельным номерам работников; перечень выпуска различного вида продукции по месяцам года; товары на складе по кодовым номерам и т.д. Обработка информационных массивов заключается: в пополнение массивов данных новыми сведениями, разнообразное изменение элементов массивов и вывод результатов обработки. Во всех ранее рассмотренных примерах использовались только простые переменные. В последующих задачах будут использоваться переменные с индексами, являющиеся элементами массива. Под массивом в программировании будем понимать упорядоченную конечную группу данных одного типа. Индекс указывает порядковый номер элемента массива. Он может быть числом или выражением целого типа. Количество элементов содержащихся в массиве называется его размерностью. В зависимости от числа индексов, массивы бывают одномерными, двумерными, и т. д. Наиболее распространенные алгоритмы обработки одномерных массивов: 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) определение общей и средней суммы оборота за месяц:
2) нахождение количества дней с оборотом, равным (£, ³, ¹, >, <) плану D:
3) определение максимального оборота предприятия за данный период и номера дня с максимальным оборотом:
4) 5% ежедневного оборота отчисляется в дополнительный фонд заработной платы. Организовать новый массив, содержащий информацию об ежедневном отчислении.
Для обработки массива, его необходимо ввести в память. При этом организуют цикл ввода, работающий столько раз, сколько элементов в массиве. В блок-схеме цикл ввода показан через блок модификации, где счётчиком цикла является переменная i (номер дня). Представим алгоритм определение общей и средней суммы оборота в виде блок-схемы (рис.10):
Рис. 10 Блок-схема обработки массива к примеру 7-1) Примечание. Блок-схема накопления произведения элементов массива имеет тот же вид, что на рис. 10. Но первоначальное значение произведения Р=1; формула накопления произведения имеет вид: P = P * A(i). Представим алгоритм нахождение количества дней с оборотом, равным плану D в виде блок-схемы (рис.11):
Рис. 11 Блок-схема обработки массива к примеру 7-2)
Рис. 12 Блок-схема обработки массива к примеру 7-3) Представим алгоритм организации нового массива в виде блок-схемы (рис.13):
Рис. 13 Блок-схема обработки массива к примеру 7-4) Примечание. В блок-схеме цикл вывода результативного массива реализуется через блок модификации аналогично циклу ввода. Пример 8. Имеются данные о продуктах на складе. Определить общий вес продуктов, срок хранения которых менее 1 месяца и вывести их список. Таблица 3 – Исходные данные для примера 8
Выполним построение математической модели и алгоритма решения функциональной задачи хранения продуктов на складе.
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. г) Система расчетных формул:
Представим алгоритм накопления общего веса продуктов в виде блок-схемы (рис.14):
Рис. 14 Блок-схема алгоритма к примеру 8 Алгоритмы сортировки, предназначенные для упорядочивания расположения элементов (по алфавиту, по убыванию или возрастанию значений), являются важнейшими среди алгоритмов обработки массивов. Достоинство упорядоченного массива состоит в значительном облегчении поиска нужного элемента по сравнению с неупорядоченным массивом. Методы сортировки можно подразделить на три группы: обменные сортировки, сортировки посредством выбора и сортировки вставками. Рассмотрим алгоритмы сортировки из каждой группы. При этом будем использовать массив вещественных чисел и выполнять сортировку по возрастанию значений элементов. Сортировка по убыванию производится аналогичным образом, отличия лишь в знаке операции отношения. Сортировка «пузырьком» (обменная) состоит в сравнении каждого элемента со следующим за ним стоящим элементом (xi и xi+1) и обмена (перестановки) их, если элементы стоят не в нужном порядке (допустим, xi > xi+1). После первого такого просмотра массива наибольший элемент переместится в нужную позицию (на последнее место в массиве). Затем подобная процедура выполняется для массива на один элемент короче, и т.д. На каждом просмотре новый элемент помещается в требуемую позицию, следовательно, для сортировки массива из n элементов нужно не более n-1 просмотра. Исходными данными являются: целочисленное значение n и элементы массива xi, i=1, 2,..., n; результат уже отсортированный массив x. Учтем с помощью переменной fl тот факт, что если на каком-то промежуточном этапе массив уже отсортирован, то при просмотре его элементов не происходит ни одной перестановки и дальнейшие просмотры не нужны. Если выполняется ветвь алгоритма, в которой происходит перестановка (обмен) элементов, то переменной fl присваивается значение 1. Представим этот алгоритм в виде блок-схемы (рис. 15). Сортировка посредством выбора состоитв последовательном выборе элементов массива и помещении их в соответствующие позиции. В ней наибольший элемент помещается в позицию n, следующий по величине элемент в позицию n-1 и т.д. Исходными данными являются: целочисленное значение n и элементы ai, 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 – сохраняет наименьший вес продукта на определённом этапе сортировки, простая переменная вещественного типа. г) Система расчетных формул:
наименьшим весом
Представим алгоритм сортировки методом вставки в виде блок-схемы (рис. 17): Рис. 17 Блок-схема алгоритма сортировки к примеру 9
|