Реализация алгоритмов линейных процессов

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

Линейные алгоритмы в блок-схеме изобра- жаются с помощью управляющей структуры «Сле- дование» (рис. 8) – последовательностью блоков, размещаемых сверху вниз. Действия С1 и С2 вы- полняются друг за другом. Под действиями С1 и С2 понимаются, как правило операции присваивания, записываемые в виде: А:= В, где А – имя вычис- ляемой переменной, В – выражение. Справа от знака присваивания используются константы и перемен- ные, причем значения переменных должны быть определены до выполнения этого блока, т. е. долж- ны быть введены, либо вычислены ранее. Кроме этого, в одном вычислительном блоке не рекомен-

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

Знак := означает присваивание, т. е. «вычислить» значение переменной, стоящей в левой части операции присваивания и запомнить в соответствующей ячейке памяти. Перечислим правила использования и выполнения операции присваивания.

Слева от знака присваивания записывается имя вычисляемой переменной, значение этой переменной к моменту выполнения операции присваивания мо- жет быть неизвестно. Если же до выполнения операции эта переменная имела значение, то оно безвозвратно теряется.

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

Тип переменной в левой части операции присваивания должен соответст- вовать типу выражения, записанного в правой части.

При выполнении операции присваивания вычисляется значение выраже- ния, вычисленное значение заносится в переменную, записанную в левой части, предыдущее ее значение «стирается».

В выражении могут использоваться условные обозначения стандартных функций, встроенных в современные языки программирования. В рамках дан- ного пособия мы будем использовать обозначения следующих функций: триго- нометрические, такие как SIN(x), COS(x), TG(x) и др.; математические – SQRT(x) – квадратный корень из числа х, LN(x) – натуральный логарифм числа х; числовые: ABS(a) – модуль числа а, MOD (a,b) – остаток от деления числа a на число b, DIV (a,b) – целая часть от деления числа a на число b.

Приведем примеры записи операции присваивания.

Арифметические: A:=2/5; A:=X; Sum:=X+Z; D:=A/(x+y); y=SIN(x); Ost:=MOD(a,2).

Логические: R:=‘TRUE’; F:=‘FALSE’; FLAG:=a>b.

Строковые: S:= ‘Здравствуйте’

Рассмотрим на примере последовательности нескольких операций при- сваивания, как переменные получают новые значения. В табл. 2 приведены примеры последовательности операций присваивания и значений переменных, которые они принимают после выполнения операции присваивания.

Таблица 2

 

Номер примера	Последовательность операций присваивания	Значения переменных
1	a:= 5; b:= 3; b:= a	a = 5, b = 5
2	a:= 5; b:= 3; a:= a + b; b:= a – b; a:= a – b	a = 3, b = 5
3	a:= 5; b:= 3; r:= a; b:= a; a:= r	a = 3, b = 5

 

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

Задача 3.

На плоскости заданы две точки А и В. Пусть через точку В проведена окружность с центром в точке А. Определить длину окружности и площадь круга.

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

 

Исходные данные:   XA, YA – координаты точки А;

XB, YB – координаты точки B.

Выходные данные:  S – площадь круга;

L – длина окружности.

Рабочие переменные:

 

R – радиус;

Pi – константа 3.1416.

Формулы, рассчитывающие результаты:

;

L= 2·Pi·R; S = Pi·R·R.

Очевидно, что эту задачу можно решить с помощью линейного алгорит- ма. Блок-схема 2 и программа Krug описывают алгоритм решения поставлен- ной задачи по построенной математической модели.

Комментарии к алгоритму. В начале алгоритма используются операции вывода для ведения диалога с пользователем, т. е. для вывода на экран приглаше- ния для ввода исходных данных. После ввода исходных данных задается значение переменной Pi – арифметическое значение числа «пи». Далее по известной фор- муле вычисляется радиус окружности. В следующем блоке блок-схемы вычисля- ются значения длины окружности и площади круга. Два последних действия за- писаны в отдельном блоке от предыдущего действия в связи с тем, что в них ис- пользуются результаты предыдущих вычислений. После того, как искомые значе- ния вычислены, они выводятся на экран (принтер) с помощью операции «вывод».

 

 

НАЧАЛО

ВЕЩЕСТВЕННОЕ XA, YA, XB, YB,Pi, R, L,S

ВЫВОД                               “Введите

координаты точки А” ВВОД XA, YA

ВЫВОД                               “Введите

координаты точки B”

 

ВВОД XB, YB

 

Pi:= 3,1416

Pi:= 3,1416

 

 

R:= SQRT((XB-XA)**2+(YB-YA)**2)

 

 

L:= 2*Pi*R S:= Pi*R**2

 

 

ВЫВОД “L=”,L,”S=”,S

 

 

 

Блок-схема 2

КОНЕЦ.

 

 

Программа Krug

 

 

Задача 4.

Группа студентов сдавала экзамен. Известно общее количество чело- век и количество студентов, сдавших экзамен на «отлично», «хоро- шо», «удовлетворительно». Определить средний балл и качество зна- ний сдавших экзамен и процент не сдавших экзамен.

Примечание. Качество знаний рассчитывается как процент студентов, сдавших экзамен на «отлично» и «хорошо», от количества всех сдавших экзамен.

 

Запишем математическую модель задачи.

Исходные данные:   N – общее количество студентов;

X – количество студентов, сдавших на «5»; Y – количество студентов, сдавших на «4»;

Z – количество студентов, сдавших на «3».

Выходные данные:  SR – средний балл;

K – качество знаний;

PR – процент не сдавших.

Рабочие переменные:

B=X+Y+Z – общее количество сдавших; C=X+Y – количество сдавших на «4 и 5»; A=N-B – количество не сдавших.

Формулы, рассчитывающие результаты:

SR = (5X + 4Y + 3Z) / B; K = (C·100) / B;

PR = (A·100) / N.

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

НАЧАЛО

ЦЕЛОЕ N, X, Y, Z, B, C, A

ВЕЩЕСТВЕННОЕ SR, K, PR

ВВОД N, X, Y, Z B:=X+Y+Z

C:=X+Y A:=N-B

 

SR:=(5*X+4*Y+3*Z)/B K:=(C*100)/B PR:=(A*100)/N

 

ВЫВОД SR, K, PR

 

 

 

 

Блок-схема 3

КОНЕЦ.

 

 

Программа Exam