Министерство образования Российской Федерации
Государственное образовательное учреждение
высшего профессионального образования
«Сибирский государственный индустриальный университет»
Кафедра автоматизированного электропривода
и промышленной электроники
АЛГОРИТМЫ И СПОСОБЫ ИХ ОПИСАНИЯ
Методические указания к выполнению
лабораторного практикума по дисциплинам
«Алгоритмы в электроприводе» (специальность 180400 «Электропривод
и автоматика промышленных установок и технологических комплексов»)
и «Алгоритмы электронных устройств» (специальность 200400
«Промышленная электроника») всех форм обучения
Новокузнецк
2004
Министерство образования Российской Федерации
Государственное образовательное учреждение
высшего профессионального образования
«Сибирский государственный индустриальный университет»
Кафедра автоматизированного электропривода
и промышленной электроники
АЛГОРИТМЫ И СПОСОБЫ ИХ ОПИСАНИЯ
Методические указания к выполнению
лабораторного практикума по дисциплинам
«Алгоритмы в электроприводе» (специальность 180400 «Электропривод
и автоматика промышленных установок и технологических комплексов»)
и «Алгоритмы электронных устройств» (специальность 200400
«Промышленная электроника») всех форм обучения
Новокузнецк
2004
УДК 62-82-52(075):681.51
Алгоритмы и способы их описания: Методические указания к выполнению лабораторного практикума по дисциплинам «Алгоритмы в электроприводе» (специальность 180400 «Электропривод и автоматика промышленных установок и технологических комплексов») и «Алгоритмы электронных устройств» (специальность 200400 «Промышленная электроника») всех форм обучения: Метод. указ./ Сост. , . – Новокузнецк: СибГИУ, 2004. – 20 с: ил.
Изложены свойства алгоритмов и способы их описания. Рассмотрена методика изучения способов описания алгоритмов. Приводятся пример, индивидуальные задания к выполнению лабораторного практикума, а также основные численные методы.
Предназначена для студентов специальностей 180400 «Электропривод и автоматика промышленных установок и технологических комплексов» и 200400 «Промышленная электроника» всех форм обучения
Рецензент – кафедра систем автоматизации Сибирского государственного индустриального университета (зав. кафедрой д. т.н., профессор ).
Печатается по решению редакционно-издательского совета университета.
Общие положения
Алгоритм – точное предписание, определяющее вычислительный процесс, ведущее от варьируемых начальных данных к искомому результату. Алгоритм должен содержать конечную последовательность шагов, однозначно определяющих процесс переработки исходных и промежуточных данных в искомый результат.
При составлении алгоритмов следует учитывать требования, выполнение которых приводит к формированию необходимых свойств.
1 СВОЙСТВА АЛГОРИТМОВ
Любой алгоритм должен обладать следующими свойствами.
Определенность – однозначная, исключающая произвольное толкование любого предписания и заданного порядка выполнения операций, реализация вычислительного процесса, предусмотренного алгоритмом. Для соблюдения данного свойства можно записывать алгоритм по пунктам, в порядке следования операций, которые необходимо выполнить для решения поставленной задачи.
Результативность – способность завершить вычислительный процесс, предусмотренный алгоритмом, через конечное число шагов и привести к выдаче результата или сообщения о невозможности решения задачи. Для соблюдения этого свойства при использовании циклов в процессе решения поставленной задачи необходимо задать условие выхода из цикла.
Массовость – возможность решения по одному и тому же алгоритму однотипных задач с различными исходными данными, что позволяет создавать типовые программы для задач с различными вариантами задания значений исходных данных. Организация возможности ввода начальных данных в процессе выполнения программы и указание границ множества их допустимых значений способствует формированию соответствующего свойства алгоритма.
Дискретность – возможность расчленения, предопределенного алгоритмом, вычислительного процесса на отдельные этапы и элементарные операции.
2 СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ
Различают пять способов описания алгоритмов:
словесный структурно стилизованный математический графический программныйРассмотрим каждый из них.
2.1 Словесный способ описания алгоритмов
При этом способе приводится описание последовательных этапов обработки данных, задаваемых произвольным изложением на естественном языке.
2.2 Математический способ описания алгоритмов
Способ написания алгоритма, использующий математический язык. При этом в качестве синтаксических конструкций применяются цифры десятичной системы счисления, знаки математических операций, специальные символы математики (например ∩, ∪, ∈, ∞), буквы латинского алфавита, круглые и квадратные скобки, знаки «система» и «матрица» и т. д.
2.3 Графический способ описания алгоритмов
Использует для изображения структур алгоритмов совокупность блочных символов, соединенных линиями передачи управления. Такое изображение называется методом блок-схем.
В схеме алгоритма каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа, называемого символом действия.
Форма символов приведена в ГОСТ 19.003 – 80. Правила составления схем – в ГОСТ 19.002 – 80.
Базовые управляющие конструкции приведены на рисунке 1.
Различают:
алгоритм линейной структуры, алгоритм разветвленной структуры, алгоритм циклической структуры, алгоритм со структурой вложенных циклов.
где b=1,5a ; h=0,25a ; d=0,5a
Рисунок 1 – Обозначение, размеры и наименование основных обязательных символов схем алгоритмов
2.4 Структурно стилизованный способ описания алгоритмов
Основан на стилизованном представлении предписаний, задаваемых путем ограниченного набора типовых синтаксических конструкций, представленных в понятном для разработчиков алгоритмов виде.
Разновидность этого способа – алгоритмический язык в русской нотации (АЯРН). Он включает в себя строчные и прописные буквы русского и латинского алфавитов, цифры десятичной системы счисления, специальные символы клавиатуры и символы математических операций. Его синтаксические конструкции имеют вид:
алг | если | лит (симв) | тип | лог |
арг | знач | нач | рез | запись |
вещ | и | не | таб | истина |
выбор | или | нц | то | ложь |
для | иначе | от | цел | массив |
до | кон | пока | шаг | множество |
идти к | кц | при | := | функция |
вывод | ввод | нпп | кпп |
Алгоритм, записанный на алгоритмическом языке, начинается с заголовка и затем содержит последовательно расположенные друг за другом операторы, образующие тело алгоритма. Тело заключается между словами нач и кон. Признаком заголовка алгоритма является ключевое слово алг, следом за которым указывают название алгоритма. За названием в круглых скобках приводится характеристика величин, используемых в алгоритме в качестве исходных данных и результатов решения задачи. После заголовка необходимо в круглых скобках, следующих за ключевыми словами, указать список переменных, соответствующих начальным данным, и список переменных, соответствующих искомому результату. Ключевым словом для списка начальных данных является арг, а для списка искомого результата – рез.
2.5 Программный способ описания алгоритмов
Написание алгоритма на любом языке, используемом в ЭВМ (например, на Basic, C, Pascal и др.). При этом необходимо придерживаться синтаксиса и правил записи, характерных именно для этого языка.
Пример: Составить алгоритм решения задачи по определению гипотенузы прямоугольного треугольника, если известны два его катета.
1 Словесное описание
Пусть заданы катеты А и В.
Находим квадрат первого катета А. Находим квадрат второго катета В. Находим сумму квадратов катетов А и В. Находим гипотенузу С прямоугольного треугольника как квадратный корень из суммы квадратов катетов А и В.2 Математическое описание
Дано: А, В
Найти: С
Решение: 
3 Графическое описание
4 Структурно–стилизованное описание
алг Нахождение гипотенузы прямоугольного треугольника, если известны два его катета (вещ А≥0, вещ В≥0)
арг (А, В)
рез (С)
нач
ввод (А, В)
если А<0 или В<0,
то вывод (Недопустимая операция);
иначе С=(А^2+B^2)^(1/2), вывод (С),
кон
5 Программное описание
#include<stdio. h>
#include<math. h>
#include<conio. h>
float a, b,c;
int i;
main()
{
clrscr();
M1:printf("\n\n Введите значения катетов прямоугольного треугольника\n\n");
scanf("\n\n%f%f",&a,&b);
if (a<0||b<0)
{
printf("\n\n\n Ошибка \n\n
Один или оба катета имеют отрицательные значения,\n что недопустимо. Для повторного расчета введите 1.\n Для выхода нажмите любую другую клавишу и ввод.\n");
scanf("%d",&i);
switch(i)
{
case 1:goto M1;
default:goto M2;
}
}
c=hypot(a, b);
printf("\n\n Гипотенуза С = %38.2f",c);
printf("\n\n Для выхода нажмите любую клавишу\n\n");
while(!kbhit());
M2:return(0);
}
После выполнения программы на экране монитора будет отображена следующая информация.
Введите значения катетов прямоугольного треугольника
1
-3
Ошибка
Один или оба катета имеют отрицательные значения,
что недопустимо. Для повторного расчета введите 1.
Для выхода нажмите любую другую клавишу и ввод.
1
Введите значения катетов прямоугольного треугольника
2
4
Гипотенуза С = 4.47
Для выхода нажмите любую клавишу
3 ПРОГРАММА РАБОТЫ
Внимательно изучить материал, изложенный в предыдущих разделах, при необходимости используя рекомендованную литературу. Выполнить рассмотренный пример. Составить алгоритм решения задачи согласно номеру варианта (см. приложение А), при необходимости, используя методы изложенные в приложении Б. При этом, следует использовать все рассмотренные выше способы описания алгоритмов. Особое внимание обратить на необходимость соблюдения правил, выполнение которых приводит к формированию требуемых свойств алгоритма. Также следует учитывать синтаксис каждого из способов представления алгоритма. Набрать полученную программу на ПЭВМ и выполнить. Проверить правильность работы. Результаты продемонстрировать преподавателю. Составить отчет о проделанной работе.
4 СОДЕРЖАНИЕ ОТЧЕТА
Отчет по лабораторной работе должен включать:
- титульный лист; цель работы, в которой указать для чего выполняется данная работа, и что она позволяет изучить; формулировка задания; описание алгоритма решения задачи заданным количеством способов; пример выполнения алгоритма, записанного программным способом и реализованного на ПЭВМ; выводы по работе, где указать, что и каким образом было достигнуто в процессе выполнения задания.
5 КОНТРОЛЬНЫЕ ВОПРОСЫ
Дайте определение алгоритма. Какие свойства алгоритмов Вы знаете? Как соблюдается свойство дискретности алгоритма? Какие способы описания алгоритмов Вы знаете? Какое(какие) из свойств при составлении алгоритмов можно не принимать во внимание? Чем структурно-стилизованное описание алгоритма отличается от словесного? Чем программное описание алгоритма отличается от математического? Каким образом формируются синтаксические конструкции для структурно-стилизованного способа описания алгоритма? Назовите преимущества и недостатки каждого из рассмотренных способов описания алгоритмов. Какие условные графические обозначение, применяемые в схемах алгоритмов, Вы знаете? Какой из способов описания алгоритмов требует (при прочих равных условиях) больших трудозатрат и почему?
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
лгоритмы и структуры данных: Пер. с англ./ Н. Вирт. – М.: Мир, 1989. – 360 с.: ил. Построение и анализ вычислительных алгоритмов/ и др. – М.: Мир, 1979. – 536 с.: ил. лгоритмы: построение и анализ: Пер. с англ./ Т. Кормен, Ч. Лейзерсон, Р. Ривест. – М.: МЦНМО, 1999. – 960 с: ил. Шоу. А, Гэннон Дж. Принципы разработки программного обеспечения: Пер. с англ./ М. Зелковиц, А. Шоу, Дж. Гэннон. – М.: Мир, 1982. – 386 с.: ил. , Программирование в среде Turbo Pascal 7.0 /, ; Под ред. – Киев: ВЕК+, 2000. – 464 с.: ил. C++: специальный справочник/ Б. Карпов, Т. Баранова. – СПб: Питер, 2001. – 480 с.: ил.
ПРИЛОЖЕНИЕ А
ОСНОВНЫЕ ЧИСЛЕННЫЕ МЕТОДЫ
Вычисление степенных многочленов и дробно – рациональных рядов
Для вычисления степенных многочленов и дробно – рациональных рядов P(z)=anzn+an-1zn-1+…+a1z+a0 применяется схема Горнера, которая имеет вид P(z)=(…(anz+an-1)z+ an-2)z+…+a1)z+a0, коэффициенты a0, a1, …,
an-1, an – действительные. При действительном аргументе z схема Горнера применяется непосредственно, при комплексном Z=A+jB=R⋅ejΘ – с применением операций умножения и сложения комплексных чисел:
Вычисление значения дробно – рациональной функции комплексного переменного
Вычисление 
производится вычислением комплексных значений многочленов A(z) и B(z) с последующим делением их по формуле деления комплексных чисел.
Вычисление ортогональных многочленов
Многочлен Чебышева.
Ортогональный многочлен Чебышева Tn(x)=w(x) является решением дифференциального уравнения второго порядка 
. Они могут вычисляться с помощью явного выражения 
или по рекуррентным формулам 
при T0(x)=1 и Т1(х)=х.
Многочлен Лежандра.
Ортогональный многочлен Лежандра Рn(x) является решением дифференциального уравнения 
и может вычисляться по рекуррентным формулам 
при i=1,2,…,n-1, Р0(x)=1 и Р1(х)=х.
Многочлен Лагерра.
Ортогональный многочлен Лагерра Ln(x) является решением дифференциального уравнения 
и может вычисляться по рекуррентным формулам 
при i=1,2,…,n-1, L0(x)=1 и L1(х)=1-х.
Многочлен Эрмита.
Ортогональный многочлен Эрмита Нn(x) является решением дифференциального уравнения 
и может вычисляться по рекуррентным формулам 
при i=1,2,…,n-1, Н0(x)=1 и Н1(х)=2х.
Операции с матрицами
Диагональная матрица является разновидностью квадратной матрицы вида 
.
Единичная матрица – разновидность диагональной матрицы, у которой aij=1 при i=j.
Нулевая матрица – очищенный массив, т. е. матрица, у которой все aij=0.
Операции с константами сводятся к сложению, вычитанию, умножению или делению элементов матрицы aij на константу Х.
Транспонированной матрицей AT называется квадратная матрица, у которой столбцы соответствуют строкам квадратной матрицы А, например: 
; 
.
Определитель квадратной матрицы А – число Δ, равное сумме n! членов (-1)ra1j1a2j2a3j3…anjn, каждый из которых соответствует одному из n! различных упорядоченных множеств j1, j2, …, jn, полученных r-парными перестановками элементов из множества 1,2,…, n.
Определитель матрицы малой размерности (2*2, 3*3, 4*4) целесообразно вычислять по формулам, например для матрицы 2*2: 
.
Обратной матрицей называется матрица А-1, произведение которой на заданную матрицу А дает единичную матрицу. В общем виде обратную матрицу можно вычислить по формуле 
.
Умножение матрицы А размерностью m×n и В с размерностью n×l выполняется по формуле 
, где j=1,2, …, l, k=1,2, …, m. Получаемая матрица имеет размерность С(m×l).
Умножение матрицы на вектор R{r1, r2, …, rm} выполняется по формуле 
, где i=1,2, …, m. В результате получаем вектор U={v1, v2, …, vm}.
Вычисление определителя матрицы произвольного размера n×n методом Гаусса с выбором главного элемента
Метод Гаусса основан на последовательном исключении неизвестных, т. е. приведении матрицы коэффициентов aij к треугольному виду. Для реализации этого метода выполняют следующие действия:
Определитель матрицы любого размера n×n вычисляются по методу Гаусса. Он сводится к преобразованию матрицы к треугольному виду с помощью следующих формул преобразования элементов матрицы А:
, где k=1,2,…,n-1 и 
.
Преобразование массива А производят в направлении расположения столбцов слева направо. Определитель вычисляется как произведение всех диагональных элементов. Необходимое условие для реализации простого метода Гаусса заключается в неравенстве элемента 
нулю на всех этапах преобразования.
Для повышения точности вычислений и исключения остановок ЭВМ в ходе вычислений применяют вариант метода Гаусса с выбором главного элемента по столбцу, строке или всей матрице. В последнем случае перед преобразованиями в матрице А выбирают наибольший по модулю (главный) элемент, допустим aij. Далее переставляют первую строку матрицы с i-ой строкой (выбор главного элемента по строке), а первый столбец переставляют с j-м (выбор главного элемента по столбцу). При каждой такой перестановке знак определителя меняется, поэтому результат нужно умножить на (-1)р, где р – число перестановок.
Порядок действий при нахождении определителя.
Найдем в матрице максимальный по модулю элемент и вынесем его из столбца (тем самым получим элемент матрицы равным 1). Умножим строку, в которой находится единичный элемент, на значение какого-либо элемента, располагающегося в столбце единичного элемента матрицы. Отнимем умноженную строку от строки, где находится элемент, на который умножали. Так этот элемент в преобразованной матрице будет равен нулю. Поделим умноженную строку на тот элемент, на который умножали, чтобы опять получить единичный элемент. Операции производятся и с остальными элементами столбца до тех пор, пока в столбце не останутся все нули и единичный элемент. Если будет выполнен пункт 5, то можно будет вычеркнуть столбец с нулями и строку, в которой находится единичный элемент. Тем самым получим матрицу на порядок ниже, чем исходная. Повторять пункты 1-6, пока размерность матрицы не станет равна 1. Произведение всех вынесенных элементов и будет равняться определителю данной матрицы.Пример:
И так далее до приведения матрицы к единичной размерности.
Решение систем линейных уравнений
Системы из n линейных уравнений вида:
a11x1+a12x2+...+a1nxn=b1
a21x1+a22x2+...+a2nxn=b2
.......................................
an1x1+an2x2+...+annxn=bn
решаются точными и итерационными методами. Точные методы дают точное решение за конечное число операций, если все они вычислялись без погрешности. Число операций у итерационных методов зависит от заданной погрешности вычислений.
Метод Гаусса решения систем линейных уравнений.
Метод Гаусса или метод последовательного исключения неизвестных основан на приведении матрицы коэффициентов к треугольному виду.
При решении поставленной задачи сначала проводят прямой ход исключения переменных путем преобразования коэффициентов по формулам:
где i=1,2,…,n-1; j=i+1,2,…,n; k=i+1,2,…,i+n
В конце этих преобразований получают Xn=bn/ann.
Затем организуют обратный ход (последовательное нахождение Xn-1, Xn-2, …, X2, X1), проводя вычисления по формулам:
h=bi, h=h-xjajj,
где i=n-1, n-2, …, 2, 1;
j=i+1, i+2, …, n;
xi=h/aii
В результате получают массив X(I) неизвестных х.
Метод вращения решения систем линейных уравнений.
Метод вращения является разновидностью метода Гаусса, обладающий повышенной устойчивостью к «провалам» промежуточных вычислений.
Этот метод обеспечивает приведение исходной матрицы к системе с правой треугольной матрицей. Для этого вычисляют;
причем если aii=aki=0, то Mki=1 и Lki=0. После этого проводят преобразования системы по формулам:
где i=1, 2, …, n+1; j=i+1, i+2, …, n; yi и yk – левые части, bi и bk – правые части i-го и k-го уравнений соответственно.
После n(n-1)/2 шагов приходим к системе с верхней треугольной матрицей. Затем осуществляют обратное преобразование:
где m=n, n-1, …, 1.
ПРИЛОЖЕНИЕ Б
Варианты индивидуальных заданий
1. Определить квадрант нахождения точки по заданным её координатам, которые заранее неизвестны.
2. Вычислить наименьшее целое К>0, при котором значение функции 
становится меньше а.
3. Выявить в целочисленном массиве из 50 элементов элементы, значения которых кратны 3.
4. Выделить и записать подряд положительные элементы массива Х = {Х1, Х2, …, Х100} в массив Y, а отрицательные – в массив Z.
5. Вычислить определенный интеграл 
по формуле прямоугольников при изменении аргумента с шагом h=(b-a)/n, где n – заданное число шагов интегрирования.
6. Вычислить среднее геометрического положительных элементов массива Х = {Х1, Х2, …, Х100}: (для 2-х чисел – 
).
7. Вычислить сумму членов бесконечного ряда 
.
8. Вычислить значения полинома n-ной степени y=a1xn+a2xn-1+…+anx+an+1.
9. Найти наибольшее значение функции 
при изменении аргумента х от 0 до а с шагом h.
10. Найти наименьший элемент массива x[1:50] и его порядковый номер.
11. Выполнить транспонирование матрицы.
12. Вычислить определитель квадратной матрицы по методу Гаусса.
13. Вычислить определитель квадратной матрицы по методу Гаусса с выбором главного элемента по строке.
14. Вычислить определитель квадратной матрицы по методу Гаусса с выбором главного элемента по столбцу.
15. Выполнить обращение матрицы А(2×2).
16. Выполнить обращение матрицы А(3×3).
17. Выполнить умножение двух матриц одного размера.
18. Выполнить умножение двух матриц А(n×l) и В(m×n).
19. Выполнить умножение матрицы на вектор.
Найти положительные значения корней квадратного уравнения при изменении коэффициента –10<a<10 с шагом +5. Вычислить многочлен степени n при комплексном значении аргумента. Найти значение дробно-рациональной функции комплексного переменного. Вычислить ортогональный многочлен Чебышева. Вычислить ортогональный многочлен Лежандра. Вычислить ортогональный многочлен Лагерра. Вычислить ортогональный многочлен Эрмита. Найти решение системы из 3 уравнений методом Гаусса. Найти решение системы из 3 уравнений методом вращения. Выполнить сортировку элементов массива Х = {Х1, Х2, …, Х20} по возрастанию. Выполнить сортировку элементов массива Х = {Х1, Х2, …, Х20} по убыванию.Составители:
Татьяна Вениаминовна Богдановская
Денис Сергеевич Лемешевский
АЛГОРИТМЫ И СПОСОБЫ ИХ ОПИСАНИЯ
Методические указания к выполнению
лабораторного практикума по дисциплинам
«Алгоритмы в электроприводе» (специальность 180400 «Электропривод
и автоматика промышленных установок и технологических комплексов»)
и «Алгоритмы электронных устройств» (специальность 200400
«Промышленная электроника») всех форм обучения
Утверждены на заседании кафедры автоматизированного
электропривода и промышленной электроники
«13» февраля 2004 г., протокол № 88,
и одобрены редакционной комиссией факультета автоматики,
информатики и электромеханики
Изд. лиц. № Подписано в печать
Формат бумаги 60х84 1/16. Бумага писчая. Печать офсетная.
Усл. печ. л. Уч.-изд. л. Тираж 60 экз. Заказ
Сибирский государственный индустриальный университет
654007, 2
Издательский центр СибГИУ
