4843

Основы алгоритмизации. Основные аспекты алгоритмизации

Книга

Информатика, кибернетика и программирование

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

Русский

2012-11-27

306 KB

43 чел.

Введение

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

  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

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

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

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

Очевидно,

         (1) ( 1 )

Алгоритм суммирования элемен-тов вектора приведен на рис. 5.

Отметим, что начальное значение суммы .

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

Рис.5

Пример 2

Необходимо вычислить средне- арифметическое значение  четных по номеру элементов вектора X = {},   i=1, 2, ..., N.

     ( 2 )

Алгоритм примера 2 показан на рис. 6.

Рис.6

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

Очевидно,

     ( 3 )

Алгоритм для вычисления произведения элементов вектора приведен на рис. 7.

Отметим, что начальное значение произве-дения  = 1.

Рис.7

Пример 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

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

    Даны два вектора A = {ai} и B = {bi},

i=1, 2, ..., N . Отметим, что размер обоих векторов равен N, а результатом произве-дения двух векторов будет число

   C = A * B  =    (7)

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

Рис. 12

Пример 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), элементы вектора xi могут быть рассчитаны следующим образом:

для  =*+*+*=;

для  =;

для  .

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

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

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

Рис.13

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

Данные действия над двумя матрицами A и B могут быть произведены, если размерности обоих матриц равны, предположим (M*N). Результатом сумми-рования (вычитания) будет матрица C такой же размерности  (M*N).

C = A + B =

+= , ( 9 )

,  i = 1, 2, . . . ,M;

                        j = 1, 2, . . . , N.        ( 10 )

Рис. 14

Алгоритм суммирования матриц показан на рис. 14.

Алгоритм вычитания матриц  аналогичен рассмотренному, за исключе-нием  очевидной замены знака " + " на "  ".

5. ВычислениЕ произведения матриц

Даны две прямоугольные матрицы A={}N*M  и  B={}M*K .

В результате вычисления произведения матриц A и B получим прямоугольную матрицу C={ }N*K , в которой число строк равно числу строк матрицы A  (т.e. N), а число столбцов - числу столбцов матрицы B (т.e. K). Отметим, что число столбцов матрицы A равно числу строк матрицы B  (т.e. M).

Например,

C = A*B =*= ( 11 )

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

           ( 12 )

для   

   Алгоритм для вычисления произведения двух прямоуголь-ных матриц показан на рис. 15.

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

Рис.15

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

Даны прямоугольная матрица A={}N*M   и   вектор B={}M .

В результате вычисления произведения матрицы A и вектора B получим вектор C , в котором число элементов равно числу строк матрицы A (т.е. N). Отметим, что число элементов вектора B равно числу столбцов матрицы A (т.e. M).

Например,      C = A*B =

*= ( 13 )

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

        ( 14 )

для  

   Алгоритм вычисления произве-дения матрицы на вектор показан на рис. 16.

Рис.16

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

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

E={}N*N= ,    ( 15 )

        для  

    Алгоритм  вычисления единич-ной матрицы приведен на рис. 17.

Рис. 17

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

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

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

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

  1.  с использованием  новой матрицы AT={}N*N   ,

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

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

2-ой шаг

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

aij пустая ячейка b aji

Рис.18

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

                                  1)                                                                  2)

Рис. 19

9.  инвертирование элементов вектора

Инвертирование вектора X={}N означает перечисление элементов вектора в обратном порядке. Например, если  X=(0, -3, 2, 6),   тогда  XIN =  (6, 2, -3, 0) .

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

1) с использованием нового вектора XIN={}N     ,

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

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

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

1)     2)

Рис. 20

Рассмотрим более сложную задачу.

Пример 7

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

Z = ( A - E ) * C1IN * ( C22 - 1 ) , ( 17 )

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

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

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

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

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

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

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

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

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

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

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

Вычисление вектора D=B*C1IN.

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

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

  1.  Вычисление вектора Z=D*K.
  2.  Вывод вектора Z={}N.

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

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

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

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

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

10. АЛГОРИТМ поиска МАКСИМАЛЬНОГО ( ИЛИ МИНИМАЛЬ-НОГО ) элемента  ВЕКТОРА

Дан вектор X={}N .

Необходимо найти элемент вектора Х , имеющий максимальное значение. Например,   пусть   X =  (3, 4, 2, -1, 6, 0).   Очевидно,    что    M(max) == 6;  L (порядковый номер максимального элемента)=5.

Процедура поиска максимального элемента вектора следующая: предположим, что максимальным является первый элемент, т.e. M=a1, L=1.

Затем каждый элемент ,   сравнивается со значением M, и если значение некоторого текущего элемента  больше M, тогда M принимает новое значение  с запоминанием его порядкового номе-ра L = i.

Алгоритм поиска максимального элемента вектора показан на рис. 21.

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

Рис. 21

11. алгоритм сортировки (упорядочивания) элементов вектора или матрицы

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

Рассмотрим алгоритм сортировки (упорядочивания) элементов вектора, когда значение каждого последующего элемента вектора больше предыдущего. Например, пусть исходный вектор X={}6=(3, 4, 2, -1, 6, 0), тогда в результате сортировки получим вектор X=(-1, 0, 2, 3, 4, 6).

Существуют различные способы решения данной задачи. Рассмотрим один из них.

Процедура сортировки элементов вектора X по возрастанию их значений следующая.

Первый шаг

Среди 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

12. вычисление полинома по схеме горнера

Дан полином PN(x)  порядка N.

y = PN(x)= ( 18 )

Порядок N, значение аргумента  и коэффициенты  () известны. Поставим задачу разработки эффективной схемы вычисления полинома y = PN().

Представим уравнение (18) в следующем виде:

( 19 )

Очевидно, уравнение Горнера (19) предполагает меньший объем арифметических операций, чем исходное уравнение (18).

Рассмотрим следующую процедуру вычисления полинома с использованием рекуррентной формулы  (рис. 24):

,

для        . ( 20 )

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

для   

для   ( 21 )

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

для  =PN()

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

13. ВЫЧИСЛЕНИЕ  СУММЫ  ЧЛЕНОВ  РЯДА

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

,   ( 22 )

где   - общий член ряда.

Очевидно, сумма членов ряда S может быть вычислена только при конечном (заданном) числе членов ряда, предположим NZ = 10, или условием окончания вычислений может быть неравенство вида , где  достаточно малая величина, предположим  или . (Известно, что в сходящихся рядах , т.e. значение модуля каждого последующего члена ряда меньше предыдущего).

Приведем рекуррентную формулу для вычисления значения текущего члена ряда:

, где - рекуррентный множитель. ( 23 )

Для нашего примера  (уравнение 22)

M==. (24)

Покажем схему алгоритма вычисления суммы членов ряда на рис. 25.

Рис.25


 

А также другие работы, которые могут Вас заинтересовать

32568. Программаторы 43.12 KB
  Программаторы – это устройства, предназначенные для ввода управляющих программ, их редактирования и отладки, параметрирования системы
32569. Программно-математическое обеспечение (ПМО) контроллеров 248.4 KB
  Алгоритм программы Монитор Прикладное промышленное программное обеспечение Прикладное программное обеспечение рассмотрим на примере SIMTIC Soft фирмы Siemens – это система тесно связанных инструментальных средств для программирования и обслуживания систем автоматизации SIMTIC S7 C7 а также систем компьютерного управления SIMTIC WinC. Интегрирование всех пакетов программ в единый интерфейс позволяет существенно повысить эффективность использования промышленного программного обеспечения SIMTIC и использовать однородные операции на всех...
32570. АСУ ТП на базе промышленных сетей 218.52 KB
  В условиях бурно растущего производства микропроцессорных устройств альтернативным решением стали цифровые промышленные сети Fieldbus состоящие из многих узлов обмен между которыми производится цифровым способом. Использование промышленной сети позволяет расположить узлы в качестве которых выступают контроллеры и интеллектуальные устройства вводавывода максимально приближенно к оконечным устройствам датчикам и исполнительным механизмам благодаря чему длина аналоговых линий сокращается до минимума. Каждый узел промышленной сети...
32571. Общие сведения о ТСА. Основные понятия и определения 15.82 KB
  Основные понятия и определения Целью курса Технические средства автоматизации ТСА является изучение элементной базы систем автоматического управления технологическими процессами. Элемент устройство – конструктивно законченное техническое изделие предназначенное для выполнения определённых функций в системах автоматизации измерение передача сигнала хранение информации ее обработка выработка команд управления и т. Система автоматического управления САУ – совокупность технических устройств и программнотехнических средств...
32572. Тенденции развития ТСА 29.04 KB
  Увеличение функциональных возможностей ТСА: – в функции управлении от простейшего пуска останова и автоматического реверса к цикловому и числовому программному и адаптивному управлению; – в функции сигнализации от простейших лампочек до текстовых и графических дисплеев; – в функции диагностики от индикации обрыва цепи до программного тестирования всей системы автоматики; – в функции связи с другими системами от проводной связи до сетевых промышленных средств.
32573. Классификация ТСА по функциональному назначению в САУ 51.78 KB
  Классификация ТСА по функциональному назначению в САУ: СУ – система управления; ОУ – объект управления; КС – каналы связи; ЗУ – задающие устройства; УПИ – устройства переработки информации; УсПУ – усилительнопреобразовательные устройства; УОИ – устройства отображения информации; ИМ – исполнительные механизмы; РО – рабочие органы; КУ – контрольные устройства; Д – датчики; ВП – вторичные преобразователи.
32574. Основные принципы построения ТСА 15.47 KB
  Удовлетворение потребностей столь различных по качеству и сложности СУ в средствах автоматизации при их индивидуальной разработке и изготовлении сделало бы проблему автоматизации необозримой а номенклатуру приборов и устройств автоматики практически беспредельной. [24] В конце 50х годов в СССР была сформулирована проблема создания единой для всей страны Государственной Системы промышленных Приборов и средств автоматизации ГСП – представляющей рационально организованную совокупность приборов и устройств удовлетворяющих принципам типизации...
32575. Государственная система промышленных приборов и средств автоматизации (ГСП) 14.22 KB
  ГСП имеет единые параметры входных и выходных сигналов а также унифицированные габаритные присоединительные размеры. По принадлежности к ГСП приборы и устройства подразделяются на три группы: системные отвечающие всем без исключения требованиям ГСП; локального применения по назначению техническим и эксплуатационным характеристикам и конструктивным особенностям отвечающие требованиям ГСП но не предназначенные для совместной работы в системах автоматического контроля регулирования и управления с другими изделиями ГСП и не...