Урок на тему "Алгоритмы обработки одномерных массивов"

Урок «Алгоритмы обработки одномерных массивов»

Для студентов СПО специальности 09.02.07 «Информационные системы и программирование», изучающих дисциплину «Основы алгоритмизации и программирования».

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

Классическим примером однородной структуры данных является массив.

Простейший массив похож на цепочку. Он состоит из фиксированного числа компонентов, следующих друг за другом. Все его компоненты относятся к одному типу данных. Этот тип данных называется типом компонента.

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

Е

К

А

Т

Е

Р

И

Н

А

    ИМЯ

                                            Рис. 1 Шаблон массива

Каждая буква помещается в отдельную клеточку. Заполнив такую форму, мы записали имя в массив, имеющий 9 компонент, каждый из которых есть буква. Если создать подобную структуру данных в оперативной памяти компьютера, то можно будет хранить и обрабатывать информационные объекты до 9 символов.

Дадим определение массива.                                                                            

Массив - упорядоченный набор фиксированного количества однотипных элементов данных, имеющих общее имя.

Перечислим основные признаки массива:

-          Массив является структурой, т.е. состоит из множества компонент и в каждый момент времени имеет несколько значений.

-          Массив является однородной структурой, т.е. содержит данные одного типа, например буквы, целые числа, текстовые строки и т.д.

-          Массив является упорядоченной структурой, т.е. данные в массиве хранятся не хаотично, а в установленном порядке.

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

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

 Для ссылки на отдельный элемент массива используется запись вида:

имя массива[индекс]

Например: A[1], Mas[10], Х[i]

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

Таким образом, массив определяется своим именем и имеет фиксированный размер, все его элементы упорядочены (пронумерованы). В нашем примере (рис. 1) массив имеет имя -  ИМЯ,  размер – 9 компонент, пронумеровать его элементы можно с помощью одного индекса от 1 до 9.

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

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

-          ввод массива (инициализация массива);

-          вывод массива;

-          арифметические действия, выполняемые над всеми элементами массива;

-          арифметические действия, выполняемые над определенной группой элементов массива;

-          поиск максимального или минимального элемента;

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

-          замена элементов;

-          вставка элемента;

-          удаление элемента;

-          поиск элемента по условию;

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

Пример 1.

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

Решение

Для хранения результата вычислений возьмем простую переменную Sum.

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

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

На каждой итерации второго цикла будем осуществлять проверку условия кратности элемента массива заданному числу, A[i] % k= =0 (остаток от деления на k должен быть равен 0). В зависимости от выполнения условия, будем производить вычисление суммы. Для проверки условия используем конструкцию Неполного ветвления.

На рис. 2 приведена блок-схема алгоритма.

                              Рис. 2 Блок-схема алгоритма

Пример 2.

Пользователь вводит значения одномерного массива заданной размерности. Рассмотрим алгоритм перестановки местами максимального и минимального элемента массива. Составить блок-схему алгоритма.

Решение

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

Для реализации алгоритма используем циклическую структуру. Поскольку количество повторов цикла  равно количеству элементов массива, то можно использовать конструкцию Цикла со счетчиком.

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

На каждой итерации второго цикла будем осуществлять одновременно поиск максимального и минимального элемента. В качестве начального значения максимума и минимума возьмем значение первого элемента массива A[0].

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

Последним действием будет обмен местами максимума и минимума. Этот обмен происходит в самом массиве, поэтому меняются местами элементы A[Nmax]  и A[Nmin]. Обмен реализуется переприсваиванием элементов, для этого используются копии этих элементов max  и min.

На рис. 3 приведена блок-схема алгоритма.

                                         Рис. 3 Блок-схема алгоритма

Пример 3.

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

Решение

Структура данных для хранения исходных элементов известна из условия задачи, это одномерный массив. Результатом выполнения алгоритма должен быть вывод текстовой строки "Да" или "Нет".

Для реализации алгоритма используем циклическую структуру.

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

Осуществляя поиск отрицательного элемента, мы не знаем, где он будет находиться, возможно, в начале массива, а может быть и в конце. Но, если мы встретим его, нет необходимости просматривать остальные элементы, можно закончить просмотр массива и выйти из цикла. Таким образом, так как количество повторов цикла заранее неизвестно, то можно использовать конструкцию цикла с условием, например, Цикл с предусловием. Условием выхода из цикла будет либо равенство флага 1 (элемент найден) либо достижение верхней границы массива (i=N), а элемент не был найден.

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

На рис. 4 приведена блок-схема алгоритма.

                                               Рис. 4 Блок-схема алгоритма

Контрольные вопросы для самоанализа материала.

1.              Обобщите понятие массива по следующему плану:

-        Назначение массива;

-        Краткая характеристика (определение);

-        Алгоритмические конструкции, применяемые при обработке массива;

-        Область применения;

-        Недостатки и преимущества использования для хранения данных.

2.              Сделайте выводы,  при решении каких задачах с массивами, следует использовать циклы с условиями, а в каких циклы с параметром? Аргументируйте свои выводы.

3.              Проанализируйте блок-схему предложенного алгоритма (рис. 5). Алгоритм формирует из двух заданных массивов Х(n) и У(n) размерности n - третий Z(n) такой же размерности, по правилу: большее из X[i] и Y[i] становится новым значением Z[i]:

a)  Опишите алгоритмические конструкции, использованные в данном алгоритме.

b)  Перечислите название и назначение каждого пронумерованного блока.

c)  Укажите  и аргументируйте ошибку в блок-схеме алгоритма.

Рис. 5 Ошибочная блок-схема алгоритма