- •Содержание
- •Введение
- •1 Рабочая программа по дисциплине «информатика»
- •Раздел 2. Алгоритмизация и программирование
- •2 Основы алгоритмизации
- •2.1 Основные этапы подготовки и решения задачи на компьютере
- •2.2 Постановка задачи. Разработка математической модели
- •2.3 Алгоритм и его свойства
- •2.4 Форма записи алгоритма на естественном языке
- •2.5 Графическая форма записи алгоритма
- •2.6 Типовые вычислительные процессы и структуры алгоритмов
- •2.6.1 Линейный вычислительный процесс
- •2.6.2 Разветвляющийся вычислительный процесс
- •2.6.3 Циклический вычислительный процесс
- •2.6.4 Алгоритмы обработки одномерных информационных массивов
- •2.6.5 Алгоритмы обработки двумерных информационных массивов
- •3 Язык программирования vba
- •3.1 Элементы языка
- •3.2 Программирование алгоритмов линейной структуры
- •3.3 Программирование алгоритмов разветвленной структуры
- •3.4 Программирование алгоритмов циклической структуры
- •3.5 Организация программ обработки одномерных массивов
- •3.6 Организация программ обработки двумерных массивов
- •4 Контрольная работа и методические указания по её выполнению
- •4.1 Выбор варианта
- •4.2 Задание 1. Варианты задач
- •4.3 Задание 2. Варианты задач
- •4.4 Задание 3. Теоретический вопрос
- •4.5 Методические указания по выполнению контрольной работы
- •4.5.1 Пример выполнения задания 1
- •4.5.2 Пример выполнения задания 2
- •4.5.3 Пример выполнения задания 3
- •Вопросы для подготовки к экзамену
- •Программирование алгоритмов циклической структуры.
- •Литература
- •Указатель
- •650992, Г. Кемерово, пр. Кузнецкий, 39. Тел. 25-75-00.
2.6.4 Алгоритмы обработки одномерных информационных массивов
Информационный массив с позиции логической структуры, отображающей состояние экономической системы, представляет собой набор данных (документов) одной формы (одного названия) со всеми их значениями либо сочетание таких наборов данных, относящихся к одной функциональной задаче.
При решении функциональных задач управления по планированию, учету, анализу и регулированию хозяйственной и коммерческой деятельности предприятия в памяти компьютера создаются информационные массивы - упорядоченные последовательности элементов одного типа, обращение к которым осуществляется при помощи его имени и индекса (т.е. порядкового номера элемента).
Каждый массив содержит однородные сведения о некоторой совокупности объектов. Такими объектами могут быть: последовательности заработных плат по табельным номерам работников; перечень выпуска различного вида продукции по месяцам года; товары на складе по кодовым номерам и т.д.
Обработка информационных массивов заключается: в пополнение массивов данных новыми сведениями, разнообразное изменение элементов массивов и вывод результатов обработки.
Во всех ранее рассмотренных примерах использовались только простые переменные. В последующих задачах будут использоваться переменные с индексами, являющиеся элементами массива.
Под массивом в программировании будем понимать упорядоченную конечную группу данных одного типа. Индекс указывает порядковый номер элемента массива. Он может быть числом или выражением целого типа. Количество элементов содержащихся в массиве называется его размерностью. В зависимости от числа индексов, массивы бывают одномерными, двумерными, и т. д.
Наиболее распространенные алгоритмы обработки одномерных массивов:
-
нахождение суммы, произведения, среднего значения;
-
нахождение суммы или количества элементов массива, удовлетворяющих некоторым условиям;
-
нахождение минимального (максимального) элемента массива и его номера;
-
создание нового массива из элементов имеющегося;
-
сортировка элементов массива.
Выполним построение математической модели и указанных выше алгоритмов 1) – 4) функциональной задачи денежного оборота торговой фирмы.
Пример 7. Имеются данные о ежедневном обороте торговой фирмы в течение месяца, т.е. одномерный массив, содержащий 30 элементов, A(30):
№ дня |
1 |
2 |
3 |
. . . |
30 |
Оборот |
124 |
120 |
50 |
. . . |
63 |
а) Обозначение переменных:
А(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 |
Наименование |
Вес, кг |
Срок хранения, дни |
1 |
Картофель |
200 |
3 |
2 |
Сахар |
500 |
7 |
3 |
Мука |
1500 |
60 |
4 |
Хлеб |
150 |
1 |
5 |
Крахмал |
200 |
90 |
6 |
Конфеты |
300 |
10 |
7 |
Печенье |
100 |
30 |
8 |
Вафли |
20 |
7 |
Выполним построение математической модели и алгоритма решения функциональной задачи хранения продуктов на складе.
а) Обозначения переменных:
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
Алгоритмы сортировки, предназначенные для упорядочивания расположения элементов (по алфавиту, по убыванию или возрастанию значений), являются важнейшими среди алгоритмов обработки массивов. Достоинство упорядоченного массива состоит в значительном облегчении поиска нужного элемента по сравнению с неупорядоченным массивом. Методы сортировки можно подразделить на три группы: обменные сортировки, сортировки посредством выбора и сортировки вставками.
Рассмотрим алгоритмы сортировки из каждой группы. При этом будем использовать массив вещественных чисел и выполнять сортировку по возрастанию значений элементов. Сортировка по убыванию производится аналогичным образом, отличия лишь в знаке операции отношения.
Сортировка «пузырьком» (обменная) состоит в сравнении каждого элемента со следующим за ним стоящим элементом (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 – сохраняет наименьший вес продукта на определённом этапе сортировки, простая переменная вещественного типа.
г) Система расчетных формул:
-
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