Козенко С.Л. Алгоритмизация инженерных задач

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

Для определения a

в формулу для общего члена подставим значе"

ние k = 1. Получим: a

= p

sin(x), отсюда S

= a

= p

sin(x).

Решение задачи приведено на рис. 2.1.

Рис. 2.1. Схема алгоритма вычисления значения суммы первых L из N членов

последовательности (пример 2.1)

В некоторых задачах рекуррентное соотношение целесообразно

найти только для некоторой компоненты общего члена последова"

тельности.

Пример 2.2

Составить схему алгоритма вычисления значения произведения

всех членов последовательности, общий член которой

(1)!

pk k

где k = 1..N, x = x

+(i–1)h, i = 1..M. Исходными являются значения

параметров: N, M, x

h, p.

Решение. Предварительно необходимо произвести преобразо"

вание: a

= 1+b

и рекуррентную формулу вывести для b

(1)(1)1

(11)!

(1)!

pk k p

pk k

ex k ex

kex

1 2

Таким образом, согласно (2.1),

. В этом случае

, a

= 1+b

Решение задачи приведено на рис. 2.2.

Рис. 2.2. Схема алгоритма вычисления значения произведения всех членов

последовательности (пример 2.2)

3. АЛГОРИТМЫ ОБРАБОТКИ МАССИВОВ ДАННЫХ

3.1. Общие понятия

Под массивом будем понимать некоторым образом организован"

ный набор данных (например, чисел), называемых элементами, или

компонентами, массива. Элементам массива приписывается общее

имя, при этом элементы имеют индексы, которые определяют место"

положение каждого элемента в массиве. Количество индексов, ис"

пользуемых для указания координат (положения) элемента в

массиве, зависит от размерности массива. Различают одномерные

(векторы в математике), двумерные (матрицы в математике или таб"

лицы) и многомерные массивы. В дальнейшем будем рассматривать

только одномерные и двумерные массивы.

Например,

A = { a

, ..., a

} –

одномерный массив (вектор) размерностью n,

11 12 13 1

21 22 23 2

1213

...

mmm mn

bbb b

–

двумерный массив (матрица) размерностью m´n (m – число строк, n –

число столбцов матрицы).

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

но в то же время упорядочены по индексам, что позволяет произво"

дить обработку массивов путем организации циклов по индексам.

Рассмотрим некоторые обобщенные схемы алгоритмов типовых

задач обработки массивов.

3.2. Поиск экстремальных элементов в массиве

К подобным задачам относятся задачи поиска максимальных и/

или минимальных элементов, а также некоторых функций от этих

элементов (например, максимального по модулю элемента) в масси"

вах различной размерности с указанием или без указания координат

этих элементов в массиве.

Пример 3.1

Составить схему алгоритма поиска экстремальных по модулю эле"

ментов в одномерном массиве A

Решение задачи приведено на рис. 3.1.

Рис. 3.1. Схема алгоритма решения примера 3.1

Пример 3.2

Составить схему алгоритма поиска экстремальных элементов и

их координат в двумерном массиве A

m´n

Решение задачи приведено на рис. 3.2.

Рис. 3.2. Схема алгоритма решения примера 3.2

Пример 3.3

Составить схему алгоритма поиска экстремальных элементов в k"й

строке (l"м столбце) матрицы A

m´n

. Значение k (или l) определено.

Решение. Для решения задачи можно воспользоваться схемой

алгоритма, приведенной на рис. 3.2. В этой схеме необходимо сде"

лать следующие изменения:

– удалить блоки 8, 9, 11, 12;

– в блоках 7, 10 вместо A

записать A

(для поиска экстремаль"

ных элементов в k"й строке) или A

(для поиска экстремальных эле"

ментов в l"м столбце);

– удалить блок 13 (для поиска экстремальных элементов в стро"

ке) или 14 (для поиска экстремальных элементов в столбце); в остав"

шемся блоке вместо 1 записать 2;

– в блоках 15, 16, 17, 18 заменить индекс i на k (для поиска экстре"

мальных элементов в строке) или j на l (для поиска экстремальных

элементов в столбце);

– удалить блоки 19, 20, 21, 22;

– удалить блок 23 (для поиска экстремальных элементов в столб"

це) или 24 (для поиска экстремальных элементов в строке);

– в блоке 25 убрать I

max

, J

max

, I

min

, J

min

3.3. Вычисление значения суммы (произведения)

элементов массива

Вычисление значения суммы (произведения) элементов массива

входит во многие задачи обработки массивов, а также в задачи ли"

нейной алгебры. Значение суммы S (произведения P) элементов мас"

сива находят с использованием рекуррентной зависимости (2.1) в

виде последовательного накопления частичных сумм (произведе"

ний) элементов массива. Все рассуждения аналогичны приведенным

в разд. 2. Различие состоит лишь в том, что начальное значение сум"

мы задается равным 0 (для произведения начальное значение задает"

ся равным 1).

Пример 3.4

Составить схему алгоритма вычисления значения суммы положи"

тельных элементов матрицы A

m´n.

Решение задачи приведено на рис. 3.3.

Пример 3.5.

Составить схему алгоритма вычисления значения произведения

всех элементов одномерного массива A

Решение. Для решения задачи можно воспользоваться схемой

алгоритма, приведенной на рис. 3.3. В этой схеме необходимо сде"

лать следующие изменения:

– удалить блоки 3, 5;

– в блоке 4 A

заменить на A

– в блоке 7 вместо S: = 0 записать P: = 1;

– удалить блоки 9, 10, 12;

– в блоке 11 вместо S: = S+A

записать P: = P*A

;

– в блоке 14 S заменить на P.

3.4. Сортировка (упорядочение) массива

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

одномерного) заключается в перестановке элементов массива в за"

Рис. 3.3. Схема алгоритма вычисления значения суммы положительных

элементов матрицы A

m´n

(пример 3.4)

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

элементов массива или значений функций от этих элементов. Суще"

ствуют несколько методов сортировки массивов. Рассмотрим два наи"

более применимых на практике метода сортировки: метод простого

выбора и метод «пузырька».

Сортировка методом простого выбора. Суть метода сводится к

тому, что в неупорядоченной последовательности находят экстре"

мальный по значению элемент, точнее его индекс. Найденный экст"

ремальный элемент переставляется с первым элементом неупорядо"

ченной последовательности, и поиск повторяется со следующего эле"

мента. Число шагов описанного процесса – n(n–1)/2, где n – число

элементов последовательности.

Главный недостаток метода – отсутствие признака окончания про"

цесса сортировки. Поэтому в случае, когда последовательность уже

упорядочена (изначально или по мере прохождения процесса сорти"

ровки), приходится выполнять все n(n–1)/2 шагов.

Пример 3.6

Составить схему алгоритма сортировки одномерного массива A

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

бора.

Решение задачи приведено на рис. 3.4.

Сортировка методом «пузырька». Суть метода состоит в следую"

щем. В ходе просмотра элементов неупорядоченной последователь"

ности сравниваются два соседних числа. Если эти числа расположе"

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

меняют местами. Затем переходят к следующей паре, в которой одно

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

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

ца последовательности в ее начало, что напоминает процесс обмен"

ного движения воздушных капель и жидкости в наклоненном пу"

зырьке (отсюда и название метода). Сортировка считается закончен"

ной, если в ходе просмотра элементов последовательности не была

произведена ни одна перестановка, иначе процесс повторяется.

По сравнению с методом простого выбора метод «пузырька» имеет

более быструю сходимость за счет наличия признака окончания про"

цесса сортировки, который показывает, были перестановки в парах

или нет.

Пример 3.7

Составить схему алгоритма сортировки одномерного массива A

порядке убывания значений элементов, используя метод «пузырька».

Решение задачи приведено на рис. 3.5.

Рис. 3.4. Схема алгоритма сортировки одномерного массива методом

простого выбора (пример 3.6)

Рис. 3.5. Схема алгоритма сортировки одномерного массива методом «пузырьC

ка» (пример 3.7)