КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И ИНЖЕНЕРНОЙ КИБЕРНЕТИКИ

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

УФИМСКИЙ ГОСУДАРСТВЕННЫЙ НЕФТЯНОЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И ИНЖЕНЕРНОЙ КИБЕРНЕТИКИ

ОСНОВЫ АЛГОРИТМИЗАЦИИ

УФА 2000

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

Учебное пособие может быть использовано для студентов всех специальностей заочной формы обучения УГНТУ.

Составители: ИВАНОВ В.И., доцент,

МУХАМАДЕЕВ И.Г., доцент,

ИВАНОВА О.В., гр. ЭА-96-01

Рецензент: ХОРОБРОВ В.Р., доцент

Ó Уфимский государственный нефтяной

технический университет, 2000

ВВЕДЕНИЕ

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

1) постановка задачи (формализация задачи);

2) алгоритмическая часть (алгоритмизация);

3) программирование;

4) оценка и анализ полученных результатов (контрольный расчет).

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

Практика показывает, что адекватная формализация (математическое описание) достаточно сложных задач требует порядка 70% временных затрат для реализации задачи на компьютере.

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

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

Следующим этапом решения задачи на компьютере является собственно программирование. Для этой цели можно использовать алгоритмический язык высокого уровня, например, ПАСКАЛЬ.

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

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

АЛГОРИТМИЗАЦИЯ

Вначале рассмотрим два общих положения.

Первое

Существуют три основные (базовые) алгоритмические структуры:

1) линейная структура;

2) циклическая структура;

3) разветвленная структура.

Считается, что алгоритм любой степени сложности состоит из различных комбинаций упомянутых выше трех базовых структур

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

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

Рис.1

нет

a) цикл " до" б) цикл " пока" в) арифметический цикл

Рис.2

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

В алгоритмах разветвленной структуры вычислительный процесс формируется, как правило, в виде двух ветвей (путей) в соответствии с некоторым условием, которое может быть истинным (“да”) или ложным (“нет”). Варианты оформления алгоритмов разветвленной структуры приведены на рис. 3.

a) альтернатива б) обход б) коррекция

Рис.3

Второе

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

Пример 1

Необходимо вычислить максимальное значение переменных . Существует много различных способов решения данной задачи. Рассмотрим один из них с использованием дополнительной переменной . Алгоритм примера 1 показан на рис. 4.

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

1 шаг 2 шаг 3 шаг

Рис.4

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

Пример 3

Необходимо вычислить значение произведения (факториала) натурального ряда целых чисел от 1 до N.

Следовательно,

(4) ( 4 ) Схема алгоритма для вычисления факто-риала

показана на рис. 8.

Рис.8

Пример 4

Необходимо вычислить среднегеометрическое значение Q положитель-ных элементов вектора C = { }, . При формализации данной задачи приходим к следующему выражению:

, ( 5 )

где k – число положительных элементов < 0.

Эта задача может быть решена методом “сверху вниз”, как показано на рис. 9.

Рис. 9

Окончательная схема алгоритма решения данной задачи показана на рис. 10.

Рис.10

Пример 5

Дан вектор X = { }, i=1, 2, ..., N. Необходимо вычислить значение Р согласно следующему выражению:

P = _k. ( 6 )

Например, если N = 4 тогда

P =

Графическая схема алгоритма данной задачи представлена на рис. 11.

Рис.11

Пример 6

Дана матрица A = { }, i, j=1, 2, ..., N.

Необходимо вычислить элементы вектора X = { }, i = 1, 2, ..., N. Каждый элемент вектора вычисляется как произведение i-го столбца и главной диагонали матрицы A.

Например, пусть N = 3 и известны все элементы матрицы A

A = = .

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

Действительно,

- 2-ая строка (вектор),

- 3-ий столбец (вектор),

{ }_N - главная диагональ (вектор),

{ }_N - побочная диагональ (вектор).

В соответствии с условием задачи ( пример 6 ), элементы вектора x_i могут быть рассчитаны следующим образом:

для = * + * + * = _;

для = ;

для .

Формализация данной задачи приводит к следующему выражению:

, i = 1, 2, ..., N ( 8 )

Два варианта разработки алгоритма данной задачи показаны на рис. 13.

Рис.13

ТРАНСПОНИРОВАНИЕ МАТРИЦЫ

Транспонирование матрицы A ={ }_N_*_N предполагает перестановку в ней элементов строк и столбцов.

Например, A = , тогда A^T = . ( 16 )

Существуют два способа решения данной задачи:

1) с использованием новой матрицы A^T ={ }_N_*_N,

в этом случае для ;

2) путем перестановки в три шага соответствующих элементов в исходной матрице A (рис.18).

2-ой шаг

1-ый шаг 3-ий шаг

a_ij пустая ячейка b a_ji

Рис.18

Схемы алгоритмов транспонирования элементов матрицы для обоих способов показаны на рис. 19.

1) 2)

Рис. 19

Пример 7

Необходимо вычислить значение параметра Z в соответствии со следующим выражением:

Z = ( A - E ) * C1^IN* ( C2²- 1 ), ( 17 )

где A - исходная матрица, все элементы и размерность которой известны;

E – единичная матрица;

C1 – главная диагональ матрицы A;

C2 – побочная диагональ матрицы A.

Рассмотрим поэтапный процесс решения данной задачи.

1. Ввод размерности N и всех элементов матрицы ( ).

2. Вычисление единичной матрицы E ={ }_N_*_N.

3. Вычисление главной диагонали (вектор) ( ).

4. Вычисление побочной диагонали (вектор) ( ).

5. Инвертирование вектора C1: ( ).

6. Вычисление квадратной матрицы B=A-E.

7. Вычисление вектора D=B*C1^IN.

8. Вычисление значения F= C2*C2.

9. Вычисление значения K=F-1.

10. Вычисление вектора Z=D* K.

11. Вывод вектора Z ={ }_N.

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

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

1) предусмотреть комментарии к каждому пункту задачи;

2) организовать вывод значений рассчитанных параметров при выпол-нении каждого пункта задачи.

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

Первый шаг

Среди N-1 элементов вектора X (за исключением ) произведем поиск минимального элемента вектора и поменяем его местами с первым элементом, если значение < . В результате выполнения первого шага сортировки получим следующий вектор X =(-1, 4, 2, 3, 6, 0).

Второй шаг

Среди N-2 элементов вектора X (за исключением , ) произведем поиск минимального элемента вектора и поменяем его местами со вторым элементом, если значение < . В результате выполнения второго шага сортировки получим вектор X =(-1, 0, 2, 3, 6, 4).

Очевидно, после выполнения N-1 шага (в нашем примере после 5 шагов) получим окончательный упорядоченный вектор X =(-1, 0, 2, 3, 4, 6).

Алгоритм упорядочивания по возрастанию элементов вектора показан на рис. 22. Данный алгоритм пригоден для упорядочивания элементов вектора по убыванию с очевидной заменой знака " > " на знак " < " в блоке проверки условия (рис. 22).

Рассмотрим алгоритм сортировки элементов матрицы.

Дана матрица A ={ }_P*N. Необходимо упорядочить элементы столбцов матрицы А в порядке убывания. Алгоритм сортировки элементов матрицы для этого случая приведен на рис. 23.

Рис.22

Рис.23

......................

для = P_N ( )

Рис.24. Алгоритм вычисления полинома по схеме Горнера.

СОДЕРЖАНИЕ

введение..................... Ошибка! Закладка не определена.

АЛГОРИТМИЗАЦИЯ..... Ошибка! Закладка не определена.

1. ВЫЧИСЛЕНИЕ СУММЫ (СУММИРОВАНИЕ) ЭЛЕМЕНТОВ ВЕКТОРА 6

2. ВЫЧИСЛЕНИЕ ПРОИЗВЕДЕНИЯ ЭЛЕМЕНТОВ ВЕКТОРА........... 7

3. ВЫЧИСЛЕНИЕ ПРОИЗВЕДЕНИЯ ДВУХ ВЕКТОРОВ.................... 10

4. СУММИРОВАНИЕ (ВЫЧИТАНИЕ) МАТРИЦ................................. 12

5. ВЫЧИСЛЕНИЕ ПРОИЗВЕДЕНИЯ МАТРИЦ.................................... 13

6. ВЫЧИСЛЕНИЕ ПРОИЗВЕДЕНИЯ МАТРИЦЫ НА ВЕКТОР.......... 14

7. ВЫЧИСЛЕНИЕ ЕДИНИЧНОЙ МАТРИЦЫ....................................... 14

8. ТРАНСПОНИРОВАНИЕ МАТРИЦЫ................................................. 15

9. ИНВЕРТИРОВАНИЕ ЭЛЕМЕНТОВ ВЕКТОРА................................ 16

10. АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО (ИЛИ МИНИМАЛЬ-НОГО) ЭЛЕМЕНТА ВЕКТОРА...................................................................... 17

11. АЛГОРИТМ СОРТИРОВКИ (УПОРЯДОЧИВАНИЯ) ЭЛЕМЕНТОВ ВЕКТОРА ИЛИ МАТРИЦЫ.......................................................................................... 18

12. ВЫЧИСЛЕНИЕ ПОЛИНОМА ПО СХЕМЕ ГОРНЕРА.................... 20

13. ВЫЧИСЛЕНИЕ СУММЫ ЧЛЕНОВ РЯДА Ошибка! Закладка не определена.