Название: Алгоритмы и программы (Афанасьева Т. В.)

Жанр: Информационные системы и технологии

Просмотров: 1327


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

 

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

Задача   поиска   значения   Х   в   упорядоченном   по   возрастанию значений     массиве A(1)<A(2)<,...,<A(n) формулируется следующим образом. Требуется выяснить, входит ли значение Х в этот упорядоченный массив, и если входит, то определить значение k, для которого А(k)=Х. Для такого типа задач применяется эффективный метод бинарного поиска, который также известен как метод деления пополам.

Сущность этого метода поиска заключается в последовательном определении номера S элемента, расположенного в точке деления упорядоченного массива пополам и сравнении искомого значения Х с этим элементом    массива    A(s).    Если    A(s)=Х,    то    поиск    заканчивается. В противном случае возможны две ситуации.

Если A(s)<Х, то все элементы, имеющие номера   с 1 по s, также будут меньше Х, если  A(s)>Х, то все элементы, имеющие номера с S по n, также  будут  больше  Х  в  силу  упорядоченности  массива  по возрастанию значений.

Поэтому для дальнейшего поиска половину значений массива можно исключить из рассмотрения. В первом случае – левую, во втором случае – правую половину. Рассмотрим пример. Допустим, что требуется определить, совпадает ли значение Х=12 с каким-либо элементом в упорядоченном массиве А и, если совпадает, то определить порядковый номер S этого элемента. Иллюстрация применения метода бинарного поиска для поиска элемента Х=12 в массиве (2, 3, 4, 6, 10, 12, 20, 30, 35, 45) приведена на рис. 23.

На рис. 22 представлен алгоритм, реализующий метод бинарного поиска в упорядоченном массиве.

 

НАЧАЛО Ввод N,X

A(1...N)

 

P=1, Q = N

В этом алгоритме Х – искомое значение, P, Q – номера первого и последнего элемента массива. S=(P+Q) DIV 2 – операция

деления нацело массива пополам. S – результат: номер совпавшего элемента массива

 

 

Р< Q

 

+

 

S=(P+Q) DIV 2

 

+

 

Значение не найдено

A(S)<X            P=S+1

 

 

Q=S+1

+

A(S)=X

 

Найдено

S

 

КОНЕЦ

 

 

Рис. 22. Алгоритм метода бинарного поиска

 

Искомый элемент Х=12.

Элементы массива для рассмотрения А (2, 3, 4, 6, 10, 12, 20, 30, 35, 45).

Номера элементов     1 2 3 4 5          6          7          8          9 10.

 

Первое бинарное деление массива : номер элемента S=5, А(5)=10 А(5)<Х,

исключаем левую половину массива из рассмотрения.

 

Элементы массива для рассмотрения А (12, 20, 30, 35, 45).

Номера элементов     6          7          8          9          10.

 

Второе бинарное деление массива: номер элемента S=8, А(8)=30 А(8)>Х,

исключаем правую половину массива из рассмотрения.

 

Элементы массива для рассмотрения А (12, 20).

Номера элементов     6          7

Третье деление S=6, А(6)=12 А(6)=Х, элемент Х=12 найден.

 

Рис. 23. Иллюстрация применения метода бинарного поиска

Задания для самостоятельного выполнения

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

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

 

1. В  одномерном  массиве  определить  первый  отрицательный  элемент и его номер.

2. Исключить из массива а1,…, аn первый отрицательный элемент.

3. Ввести        массив            a1,       a2,...,   a15.     Расположить  ненулевые      элементы по убыванию.

4. Ввести        массив            x1,x2,...,x20.    Элементы       на        нечетных        местах,

расположить в порядке возрастания, а на нечетных – в порядке убывания.

5. Ввести массив a1,a2,...,a15. Требуется упорядочить его по возрастанию абсолютных значений элементов.

6. Ввести        массив            x1,x2,...,x20.    Требуется       расположить  отрицательные элементы в порядке убывания.

7. Ввести  упорядоченный  по  неубыванию  массив

X (1)  X (2)  ...  X (n) .

Найти количество различных чисел среди элементов этого массива.

8. Ввести        два      упорядоченных          по        возрастанию  числовых        массива

X (1)  X (2)  ...  X (n)

и          Y (1)  Y (2)  ...  Y (m) .   Найти количество     общих

элементов в этих массивах, то есть количество К таких чисел X(i)=Y(j).

9. Известно,   что      некоторое       число  содержится    в          каждом           из        трех

целочисленных         неубывающих            массивов

X (1)  X (2)  ...  X (n) ,

Y(1)  Y(2)  ...  Y(m) и

Z (1)  Z (2)  ...  Z (k ) . Найти одно из этих чисел.

 

 

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

 

Двумерный    массив            –          это       структура        однотипных   элементов,

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

 

3          7 –1     0

4          2          6   1

9          5   12  4

6          22  31  1

 

Рис. 24. Пример двумерного массива

представление значений соответствует математическому понятию двумерного массива. Каждый элемент в двумерном массиве идентифицируется  номером  строки  и  номером столбца, на пересечении которых он расположен. Например,  в двумерном массиве А, изображенном на рис. 24, элемент со значением   5 расположен на пересечении третьей строки и второго столбца. Этот элемент будет  обозначаться как  А(3,  2).  А  элемент

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

В дальнейшем будем считать, что для двумерного массива A(N, М) в обозначении  элемента  А(i,  j)  первое  значение  i  соответствует  номеру строки и изменяется от 1 до N, а j – номеру столбца и изменяется от 1 до М. В отличие от одномерного массива, в котором использовался только один  номер  для  определения  местоположения  элемента  и  требовался только  один  цикл  для  ввода  элементов,  в   двумерном  массиве  для обработки элементов необходимы два вложенных друг в друга цикла. Внешний цикл предназначен для изменения номера строки i, а второй, внутренний,  –  для  изменения  номера  столбца    j  в  текущей  строке  i. На рис. 25 представлен простой алгоритм ввода элементов, построенный в виде структуры из вложенных циклов. В дальнейшем при рассмотрении алгоритмов обработки  элементов двумерного массива в целях сокращения их   размера   фрагмент   ввода   элементов   будем   заменять   отдельным блоком ввода.

НАЧАЛО

 

Введите М, N

 

I  = 1

 

J :=1

 

Введите  А(I,J)

 

 

 

 

J := J +1

 

 

 

J >M

 

+

 

I := I +1

 

I >N

 

+

 

КОНЕЦ

 

Рис. 25. Алгоритм ввода элементов двумерного массива

НАЧАЛО

 

Введите М, N,

А(1.. N, 1..М)

 

I  = 1

 

max : =A [1, 1]

 

J :=1

 

+

A [I, J]<max

 

max : =A [I, J]

 

J := J +1

 

J >M

 

+

 

I:= I +1

 

I >N

 

+

 

Вывод max

 

КОНЕЦ

 

Рис. 26. Алгоритм поиска максимального значения в двумерном массиве

 

Пример 13. Составить алгоритм поиска максимального значения в двумерном массиве.

Решение. Поиск максимального элемента в двумерном массиве осуществляется аналогично поиску в одномерном массиве. Отличие состоит в том, что для обработки двумерного массива используем два вложенных цикла. Обозначим максимальный элемент переменной МАХ. Значение этой переменной будет меняться на каждой итерации     цикла,     если     очередное     значение     элемента     массива     окажется больше МАХ (рис. 26).

Пример 14. Cоставить алгоритм вычисления количества нечетных элементов в каждой строке двумерного массива А(1.. N, 1..М).

Решение. Для определения нечетных элементов будем использовать проверку на нечетность A[I, J] mod 2  0, для подсчета количества нечетных значений – формулу

К=К+1 и вывод значения К столько раз, сколько строк в массиве. Алгоритм решения представлен на рис. 27.

 

НАЧАЛО

 

Введите М, N,

А(1.. N, 1..М)

 

I = 1

 

К = 0

 

J:=1

 

+

A[I, J] mod 2=0

 

К = К+1

 

J:= J +1

 

К = 0

 

J > M

 

 

 

I:= I +1

 

 

 

 
+

 

Вывод

К

 

I > N

+

 

КОНЕЦ

 

Рис. 27. Алгоритм вычисления в каждой строке двумерного массива количества нечетных элементов

Пример  15.  Составить  алгоритм  вычисления  суммы  элементов  двумерного массива А(1.. N, 1..М), расположенных выше главной диагонали.

НАЧАЛО

 

Введите М, N,

А(1.. N, 1..М)

 

I = 1

 

S = 0

 

J:= 1

 

+

I ≥ J

 

S=S+A[I, J]

 

J:= J +1

 

J > M

 

+

 

I:= I +1

 

I > N

 

+

 

Вывод S

 

КОНЕЦ

 

Рис. 28. Алгоритм вычисления суммы элементов двумерного массива,

расположенных выше главной диагонали

 

Решение. Рассмотрим алгоритмическое решение, представленное на рис. 28. Для определения условия расположения элементов выше главной диагонали рассмотрим двумерный массив в обобщенном виде на рис. 29. Обратим внимание на диагональные элементы: номер строки и номер столбца совпадают. Значит для определения элементов на главной диагонали достаточно использовать условие I = J, где I – номер строки, J – номер столбца.

Для определения элементов выше главной диагонали достаточно использовать условие I<J, ниже главной диагонали – I>J. По условию задачи требуется найти сумму

элементов   двумерного   массива   А(1..   N,   1..М),   расположенных   выше   главной диагонали, значит,   применим условие I<J, связывающее такие параметры элемента

массива  как номер строки I и номер столбца J.

А11   А12   А13

А21   А22   А23

А31   А32   А33

 

Рис. 29. Пример двумерного массива

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

 

 

Задания для самостоятельного выполнения

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

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

 

1. Ввести  двумерный массив  А(N,  M).  Составить визуальный алгоритм замены всех нулевых элементов на минимальный элемент.

2. Ввести  двумерный  массив  А(N,  N).  Составить  визуальный  алгоритм подсчета среднего арифметического значений двумерного массива. Найти отклонение от среднего у элементов первой строки.

3. Ввести  двумерный  массив  А(N,  N).  Составить  визуальный  алгоритм подсчета среднего арифметического значения двумерного массива. Вычислить  отклонение  от   среднего  для  всех  элементов  двумерного массива.

4. Ввести  двумерный  массив  А(N,  N).  Составить  визуальный  алгоритм замены всех отрицательных элементов    на среднее арифметическое значение элементов двумерного массива.

5. Составить визуальный алгоритм нахождения числа строк двумерного массива   А(N,   N),   количество   отрицательных   элементов   в   которых больше Р.

6. Ввести двумерный массив размером 7*4. Найти наибольший элемент двумерного массива. Удалить строку с максимальным элементом.

7. Ввести   двумерный   массив   размером   7*4.   Поменять   столбец   с максимальным элементом с первым столбцом двумерного массива.

8. Ввести двумерный массив размером 7*7. Найти максимальный элемент двумерного массива, расположенный ниже побочной диагонали.

9. Ввести двумерный массив размером 7*4. Найти наименьший элемент двумерного массива. Перенести строку, содержащую этот элемент в конец.

10. Ввести двумерный массив размером 7*4. Найти максимальный элемент двумерного массива. Поменять столбец, содержащий этот элемент с последним столбцом двумерного массива.

11. Ввести двумерный массив размером 6*4. Найти минимальный элемент двумерного массива. Переставляя  строки и столбцы, добиться того, чтобы элемент оказался в правом нижнем углу.

 

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

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

2. Чем массив отличается от последовательности значений?

3. Что определяет номер элемента массива?

4. Сформулируйте свойства массива.

5. Какие  типы  алгоритмических  структур  применяются  для  обработки массива?

6. Какие существуют способы обработки одномерного массива?

7. В чем заключается сортировка одномерного массива?

8. Опишите методы сортировки одномерного массива.

9. Приведите пример и алгоритм сортировки массива.

10. Опишите методы обработки упорядоченных массивов.

11. В чем заключается сущность метода двоичного поиска?

12. Чем двумерный массив отличается от одномерного?

13. Как осуществляется доступ к элементу двумерного массива?

14. Какие существуют способы обработки двумерного массива?