Мисюткин. Методичка по алгоритмитизации

Подождите немного. Документ загружается.

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

Как уже отмечалось в разделе 5.3., очень часто информация

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

двумерные массивы (другое название, взятое из математики – матрицы).

Пример двумерного массива Z размерностью 3х4, состоящего из целых

чисел, изображен на рисунке.

Элементы такого массива имеют два

индекса, первый из которых означает номер

строки, в которой стоит элемент, а второй –

номер столбца.

Например, Z

означает число =77.

Таким образом, чтобы выбрать нужное

число из такого массива нужно задать значения двух его индексов.

Обработка таких массивов осуществляется с использованием циклов.

Но в этом случае циклов нужно 2: один – по изменению номера строки, а

второй – по изменению номера столбца. Причем один из этих циклов

находится внутри другого. Такие циклы называются вложенными.

t =0

i =1





tи

1



t =1

i = i+1

нетда

нет

t=1

Вывод "Массив

не упорядочен"

п"

Конец

нетда

К=0; t=0

Ввод N,

массива x

да

Вывод

массива x

5-7012712-477887-1556

строки

столбцы

Рис. 5.10. Схема алгоритма примера 5.5.

i=1

0



иNi

0

0

t=1

K=K+1

i=i+1

нет

да

К=0

Вывод

"отрицательн

ых чисел

нет"

Вывод К

да

нет

t=0

Вывод "нулей в

массиве нет"

Конец

да

нет

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

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

Внешний цикл начинает работу раньше, чем внутренний, и включает

последний целиком в свою рабочую часть.

6.1. Ввод-вывод двумерных массивов

Пусть требуется осуществить ввод значений двумерного массива Z,

состоящего из N строк и M столбцов (размерность NxM).

Решение. Сначала введем размерность массива: N и M.

Дальнейшие действия зависят от того, как будут вводиться элементы

массива: по строкам или по столбцам.

Построчный ввод матрицы более естественен - так нам ее удобнее

читать. В этом случае внешним циклом будет цикл по номеру строки i=1,2,

…,N, а внутренним - по номеру столбца j=1,1....,M. Такой ввод рассмотрен

на схеме (рис.6.1.). В случае ввода матрицы по столбцам, циклы меняются

местами.

Рис.6.1. Схема алгоритма ввода а) и вывода б) двумерного массива

В последующих примерах, чтобы сократить запись алгоритма будем

использовать для ввода и вывода матриц обозначения следующего вида:

Пример 6.1. Вычислить произведение элементов матрицы, не

принадлежащих интервалу (X,Y) и расположенных в столбцах с номерами

кратными 3.

Решение. Обозначим номер строки через i, а номер столбца – j .

Поскольку в вычислении произведения участвуют элементы (причем только

а)

Ввод

N,M

i=1

i≤N

j=1

j≤M

Ввод Z

j=j+1

i=i+1

нет

да

нет

да

i=1

i≤N

j=1

j≤M

Ввод Z

j=j+1

i=i+1

нет

да

нет

да

б)

Ввод N,M

матрицы Z

Вывод

матрицы

не принадлежащие (X,Y)) столбцов 3,6,…,M, оформим вложенные циклы

следующим образом:

- внешний – по номеру столбца: j=3,6,…,M;

- внутренний – по номеру строки: i=1,2,3,…,N.

Величина t позволяет судить о том, были в матрице элементы

принадлежащие (X,Y) (когда t=1) или нет (когда t=0).

Схема алгоритма приведена на рис. 6.2.

Пример 6.2. Определить количество строк матрицы, в которых

содержатся более трех положительных элементов.

Решение. Для подсчета количества введем две величины:

 k– количество положительных элементов в рассматриваемой

строке (каждый раз при переходе на новую строку k=0);

 k1 – количество строк, содержащих более трех элементов.

Вложенные циклы оформим здесь следующим образом:

 внешний – по номеру строки: i=1,2,3,...,N;

 внутренний – по номеру столбца: j=1,2,...,M.

Схема программы представлена на рис.6.3.

Рис.6.2. Схема алгоритма примера 6.1.

начало

Ввод X,Y,N,M,

матрицы Z

конец

P=1

t=0

j=3

j≤M

t=0

Вывод "чисел

не

принадлежащих

(x,y) нет"

Вывод

нет

да

i=1

i≤N

X≤Z

или

≥Y

P=P∙Zij

t=1

i=i+1

j=j+3

нет

да

нет

да

нет

да

Вывод

матрицы Z

Начало

Ввод N, M, матрицы Z

Вывод матрицы Z

k1=0

i=1

Ni 

k=0

j=1

Mj 

0

k=k+1

j=j+1

k>3

i=i+1

k1=k1+1

Вывод k1

Конец

Рис. 6.3. Схема алгоритма примера 6.2.

нет

да

ЛИТЕРАТУРА

1. Схемы алгоритмов, программ, данных и систем. Условные обозначения

и правила выполнения. ГОСТ 19.701 – 90 (ИСО 5807 – 85).

2. Мовшович С.М. Методы сортировки, м/у №1909, Гомель, ротапринт

ГГТУ, 1995.

3. Мовшович С.М. Основы алгоритмизации, м/у №1051, Гомель,

ротапринт ГГТУ, 1988

4. Светозарова Г.И. Алгоритмизация и основы программирования. – М:

В.ш., 1987.

ОГЛАВЛЕНИЕ

Введение.........................................................................................................................................3

1. Способы записи алгоритма...................................................................................................3

2. Типы алгоритмов...................................................................................................................8

3. Линейные алгоритмы............................................................................................................9

4. Разветвляющийся алгоритм................................................................................................10

5. Циклические алгоритмы.........................................................................................................12

5.1. Организация циклов с предусловием и постусловием.................................................12

5.2. Табуляция функции одной переменной.........................................................................14

5.3. Применение циклов в алгоритмах обработки массивов...............................................15

5.3.1. Ввод-вывод одномерных массивов..........................................................................17

5.3.2.Алгоритм нахождения суммы элементов одномерного массива...........................18

5.3.3. Алгоритм нахождения минимального или максимального элемента массива и

его порядкового номера......................................................................................................22

5.3.4. Алгоритм перестановки............................................................................................23

5.3.4. Алгоритм формирования нового массива из элементов имеющегося.................26

5.3.5. Поиск в упорядоченном массиве.............................................................................29

6. Алгоритмы обработки двумерных массивов........................................................................32