Алгоритмизация задач обработки массивов

Массивом называется упорядоченная совокупность элементов с одинаковыми свойствами. Любой массив характеризуется:

· именем;

· размерностью;

· типом элементов.

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

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

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

К основным видам задач обработки массивов относятся:

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

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

· поиск максимального (минимального) по значению элемента и определение его местоположения в массиве;

· упорядочение значений элементов в массиве.

Одномерный массив носит название вектора. Элементы одномерного массива имеют по одному индексу. Этот индекс соответствует номеру элемента в векторе.

Рассмотрим вектор A, состоящий из 7 элементов значениями: 30, 25, 18, 20, 7, 11, 9. Любой элемент этого вектора обозначается A(i), где i -индекс, 1 <= i <= 7.

При i=1 A(i) = 30 или A(1)= 30;

при i= 5 A (i) = 7 или A (5) = 7.

Элементы одномерного массива располагаются один за другим в последовательно расположенных байтах памяти. Рассмотрим типовые алгоритмы обработки одномерного массива на конкретных задачах.

Задача 5. Определить и вывести сумму значений элементов в числовом массиве A, содержащем 7 элементов.

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

Блоки 2, 3, 4 и 5 описывают циклический процесс ввода элементов одномерного массива в память. Блоки 7, 8, 9, 10 предназначены для организации цикла накопления суммы элементов массива “нарастающим итогом”. При решении задачи подсчета суммы значений элементов массива определяется “чистая“ область памяти, в которой должна накапливаться сумма (блок 6).

1 начало i=1 ввод A (i) i = i + 1

да

i £ 7

нет

S = 0

i = 1

да

S = S + A (i)

i = i + 1

да

i £ 7

нет

вывод

конец

Рис. 6.13. Блок-схема алгоритма решения задачи 5.

да

начало

ввод

i = 1

ввод

V (i)

i = i + 1

i £ n

нет

P = 1

k = 0

i = 1

да

V (i) < 0

i = i + 1

нет

i £ n

вывод

P, k

конец

P=P_*V(i) k = k +1

Рис. 6.14. Блок-схема алгоритма решения задачи 6.

В каждом из циклов выполняется последовательная обработка элементов массива, так как параметром цикла является индексированная переменная, принимающая значения от 1 до 7 с шагом +1.

Задача 6. Определить количество и произведение значений отрицательных элементов в векторе.

Как видно, постановка задачи дана в общем виде, размер массива не задан. Блок-схема алгоритма решения такой задачи приведена на рис.6.14. В блоке 2 осуществляется ввод количества элементов массива (в переменную n). Блоки 3, 4, 5, 6 описывают ввод в цикле n элементов массива с произвольно заданным именем V. В блоке 7 подготавливается область памяти для подсчета произведения значений элементов (p = 1), а в блоке 8 - для подсчета количества элементов (k=0). Блоки 9 - 14 организуют циклический процесс подсчета количества и произведения значений отрицательных элементов.

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

Задача 7. Упорядочить по возрастанию значений элементы числового массива A, содержащего 10 элементов.

Процесс упорядочивания информации по определенному признаку называется сортировкой. Цель сортировки – облегчение последующего поиска элементов. Существует много методов сортировки, соответственно и алгоритмов их реализации. Для решения задачи используем один из наиболее простых метод обменов (или пузырьковый метод). Данный метод основывается на сравнении пары соседних элементов. Если расположение элементов не удовлетворяет условиям сортировки, то их меняют местами. Сравнение и перестановки продолжаются до тех пор, пока не будут упорядочены все элементы. Определить, что элементы упорядочены можно фиксируя факт перестановки присваиванием некоторой переменной (n) значения, например true. До начала сравнения элементов эта переменная должна иметь другое значение, например false. Если после сравнения всех элементов, значение переменной остается равной false, то это означает, что все элементы упорядочены.

Блок-схема алгоритма решения задачи 7 приведена на рис. 6.15. Блоки 2, 3, 4 и 5 описывают циклический процесс ввода элементов одномерного массива в память. В блоке 6 переменной n присваивается значение false. Блоки с 7 по 12 предназначены для организации цикла, в котором выполняется парное сравнение элементов массива (блок 8). Так как условием является сравнение элемента с индексом i и элемента с индексом i+1, то индексированная переменная (параметр цикла) изменяет свое значение от 1 до 9 с шагом +1. Если условие выполнится хотя бы для одной пары элементов, то после операции обмена значениями двух элементов массива (блок 9), переменной n присваивается значение true (блок 10). Блок 11 является инвариантом цикла с постусловием. Если условие истинно, то выполняется тело цикла с постусловием (блоки с 6 по 12). Блоки 14,15,16 и 17 описывают циклический процесс вывода элементов одномерного массива.



Рис. 6.15. Блок-схема алгоритма решения задачи 7.

Двумерный массив носит название матрицы. Рассмотрим числовую матрицу B, состоящую из 4 строк и 3 столбцов (см. рис. 6.16).

3 2 8

1 6 9

1<= i<=4 10 4 7

5 2 1

1<=j<=3

Рис. 6.16. Пример числовой матрицы, состоящей из 4 строк и 3 столбцов.

Расположение элемента в двумерном массиве определяется номером строки и номером столбца, на пересечении которых находится этот элемент, поэтому каждый элемент матрицы имеет два индекса: первый индекс указывает на номер строки, а второй индекс показывает номер столбца.

Если номер строки обозначить буквой i, а номер столбца - буквой j, то для рассматриваемой нами матрицы B (см. рис. 6.16) будут справедливы следующие утверждения:

при i = 1 и j = 2 B(i,j)= 2; при i = 3 и j = 1 B(i,j)= 10 и т.д.

Рассмотрим типовые задачи обработки двумерных массивов.

Задача 8. Определить и вывести среднее арифметическое для элементов матрицы B, состоящей из 4 строк и 3 столбцов.

Среднее арифметическое представляет собой отношение суммы значений элементов к количеству этих элементов. Количество в данной задаче определять не нужно, т.к. оно известно (4 * 3), поэтому основная обработка сводится к определению суммы значений элементов.

Блок - схема алгоритма решения этой задачи приведена на рис.6.17.

На схеме хорошо видны два последовательно расположенных циклических участка: один - для организации ввода данных (блоки 2- 8), другой - для организации вычисления суммы значений элементов матрицы (блоки 10 -16).

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

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

Так на схеме (рис. 6.17) можно различить заголовок внешнего цикла c параметром i (блоки 2,7,8), тело внешнего цикла (блоки 3, 4, 5, 6), которое представляет собой внутренний цикл с параметром j со своим заголовком (блоки 3, 5, 6) и телом цикла (блок 4).

Задача 9. В произвольной матрице определить значение максимального элемента и его координаты (номер строки и номер столбца).

Для определения произвольной матрицы необходимо организовать по запросу ввод количества строк (n) и столбцов матрицы (k). Блок - схема алгоритма решения этой задачи показана на рис. 6.18.

Поиск максимального элемента выполним следующим образом. Запомним в качестве максимального (переменная М) первый элемент матрицы (блок 10) и сохраним значения его индексов (блоки 11 и 12). Затем с помощью вложенных циклов в блоках с 13 по 22 последовательно просматриваем элементы матрицы, сравнивая их с максимальным значением. Если очередной элемент A(i,j) больше ранее найденного максимального значения (переменная М), то сохраняем его (блок 16) и его индексы (блоки 17,18).

1 начало i=1 j = 1 ввод B (i, j) j = j + 1 да 6 j £ 3 7 нет i = i + 1 ДА i £ 4 9 нет S = 0 i = 1 j = 1 S = S + B (i,j) j = j + 1 да 14 j £ 3 нет i = i + 1 да 16 i £ 4 нет S = S/12 вывод S конец

Рис.6.17. Блок-схема алгоритма решения задачи 8.

1 начало ввод n, k i = 1 j = 1 ввод A (i, j) j = j + 1 да j £ k 8 нет i = i + 1 9 i £ n M = A (1,1) T = 1 L = 1 i = 1 j = 1 нет 15 да A (i, j) > M M = A (i, j) T = i L = j j = j + 1

14 15 19 да 20 j £ k 21 нет i = i + 1 да i £ n нет вывод M, T, L конец Рис. 6.18. Блок-схема алгоритма решения задачи 9.

Контрольные вопросы

1) Какие существуют этапы подготовки задач к решению на компьютере?

2) Что представляет собой этап постановки задачи?

3) Что представляет собой этап алгоритмизации?

4) Что представляет собой этап программирования?

5) Что представляет собой этап отладки программы?

6) Что такое алгоритм?

7) Откуда произошло слово «алгоритм»?

8) Какие основные свойства алгоритмов?

9) Какие способы изображения алгоритмов вам известны?

10) Что называется блок-схемой алгоритма?

11) Какие виды вычислительных процессов вам известны?

12) Какой вычислительный процесс называется линейным?

13) Какой вычислительный процесс называется ветвящимся?

14) Какой вычислительный процесс называется циклическим?

15) Какие виды циклов вам известны?

16) Что такое массив? Какие характеристики массива Вы знаете?

17) Что такое размерность массива?

18) В чем отличие двумерного массива от одномерного массива?

19) Какие типовые операции можно выполнять над элементами массива?

20) Что такое сортировка?

Тестовые задания

№	Задание	Варианты ответа
	Алгоритмическая конструкция какого типа изображена на фрагменте блок-схемы?	q циклическая q вспомогательная q линейная q ветвящаяся
	Алгоритмическая конструкция какого типа изображена на фрагменте блок-схемы?	q ветвящаяся q цикл с постусловием q линейная q цикл с предусловием
	Алгоритмическая конструкция какого типа изображена на фрагменте блок-схемы?	q ветвящаяся q цикл с постусловием q линейная q цикл с предусловием
	Определите значение целочисленной переменной z после выполнения следующего фрагмента алгоритма:	q 7 q 8 q 5 q 6
	Каким должно быть условие в блоке “решение”, чтобы после выполнения фрагмента алгоритма было найдено максимальное среди значений a, b, с?	q a < c q d > c q c > b q d < c
	Сколько раз в представленном фрагменте алгоритма выполнится тело цикла	q 0 раз q 1 раз q 2 раза q 2 раза
	Приведенный алгоритм	q считает количество положительных чисел q находит сумму всех отрицательных чисел q считает количество чисел q находит сумму положительных чисел
	Определите значение целочисленной переменной k после выполнения следующего фрагмента алгоритма:	q 10 q 20 q 21 q 25
	Элементы целочисленного массива А равны соответственно 4,1,5,3,2. Чему равно значение выражения: А(А(4))-А(А(5))	q 1 q 4 q -3 q -4
	Определите значение целочисленной переменной S после выполнения следующего фрагмента алгоритма:	q 0 q 9 q 12 q 21

Глава 7. Программирование на
объектно- ориентированном языке
VISUAL BASIC

Основные понятия объектно-ориентированного программирования

Объект -некая сущность, которая четко проявляет свое поведение и является представителем некоторого класса подобных себе объектов

Почти все, с чем производится работа в VISAUL BASIC, является объектами. Например, объектами являются: Форма, Командная кнопка, Текстовое поле и т. д.

Каждый объект характеризуется:

· свойствами;

· методами;

· событиями.

Свойство -это имеющий имя атрибут объекта. Свойства определяют характеристики объекта (цвет, положение на экране, состояние объекта).

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

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

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

Например, класс «Командная кнопка» содержит общее описание кнопок в окнах приложений.

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

Примеры событий:

· щелчок мыши по какому-либо объекту экранной формы;

· загрузка новой экранной формы;

· перемещение указателя мыши вдоль полосы прокрутки;

· нажатие какой-либо клавиши на клавиатуре.

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