Построение алг_ функц_ задач

Федеральное агентство по образованию Волгоградский государственный архитектурно-строительный университет Кафедра информационных систем и математического моделирования

Построение алгоритмов функциональных задач в MathCAD и Excel

Методические указания к лабораторным работам по курсу «Информатика»

Волгоград 2011

2

Введение

Каждому человеку постоянно приходится сталкиваться с различными задачами (проблемами) и решать их различными возможными способами. Однако не все задачи равнозначны по своему характеру, сложности и важности их решения для человека. Например, некоторые задачи возникают достаточно часто, другие – достаточно редко, а некоторые вообще являются единичными или крайне редкими. Миллионы людей занимаются математическими расчетами в силу профессиональной или иной необходимости, не говоря уже об учебе. Ни одна серьезная разработка в любой отрасли науки и производства не обходится без трудоемких математических расчетов. Для их проведения используются программы, составленные с использованием конструкций языков высокого уровня (таких как BASIC, PASCAL, CИ и других). Однако разработка таких программ, особенно имеющих современный графический интерфейс требует и соответствующей подготовки в практике программирования и достаточно большого времени (и то и другое может отсутствовать у инженера или исследователя).

Широкую известность и заслуженную популярность еще в середине 80-х годов приобрели интегрированные системы для автоматизации математических расчетов класса MathCAD, разработанные фирмой MathSoft (США). По сей день они остаются единственными математическими пакетами, в которых описание решения математических задач дается с помощью привычных математических формул и знаков. Такой же вид имеют и результаты вычислений.

В последних версиях MathCAD пользователям предоставлена возможность составлять "собственные" программы-функции и использовать принципы модульного программирования для реализации оригинальных вычислительных алгоритмов пользователя. Однако в литературе эти новые возможности освещены весьма слабо. Поэтому в данных указаниях излагаются способы программирования различных алгоритмов с использованием конструкций пакета MathCAD 2000 Professional.

1. Понятие алгоритма, его свойства и способы описания

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

Термин "алгоритм" своим происхождением обязан имени узбекского математика Аль-Хорезми, который еще в IX веке сформулировал правила выполнения четырех арифметических действий. Появившееся несколько позже слово "алгорифм" связано с именем древнегреческого математика Евклида, назвавшего так сформулированные им правила нахождения наибольшего общего делителя двух чисел. В современной математике употребляется термин "алгоритм".

Умение решать задачи определенного типа, не обязательно математические всегда означает владение соответствующим алгоритмом.

Пример1: Алгоритм приготовления настойки шиповника или др. Столовую ложку семян измельчить

3

1.Залить стаканом кипятка

2.Кипятить на слабом огне 10 мин.

3.Охладить

4.Процедить

Пример2: Алгоритм вычисления х по формуле y = (5x − 2)x

1.Задать числовое значение х

2.Умножить х на 5, результат обозначить В1

3.Из В1 вычесть 2, результат обозначить В2

4.В2 умножить на х

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

Если алгоритм решаемой задачи разработан, то его можно решить любому исполнителю (в том числе ЭВМ), не знакомому с решаемой задачей, и, точно следуя правилам, исполнитель получит ее решение.

1.2. Свойства алгоритма

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

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

Результативность. Выполнение алгоритма должно приводить к конкретному результату (решению задачи), за конечное число шагов.

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

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

1.3. Способы описания алгоритма

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

-словесный;

-графический;

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

1.3.1. Словесный способ описания алгоритма

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

Рассмотрим в качестве примера словесной формы задания алгоритм нахождения действительных корней квадратного уравнения ax2+bx+c=0

1.Задать значения чисел а, в и с.

2.Вычислить значение D по формуле D=:b2-4ac

4

3.Если D ≥ 0, то перейти к п.4, иначе перейти к п.6.

4.Вычислить значения х1 и х2 по формулам х1=-2+D/2a, х2=-2+D/2a.

5.Решением задачи считать х1 и х2.

6.Решение задачи не существует, так как дискриминант отрицательный. Словесный способ описания алгоритма имеет ряд недостатков:

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

−запись алгоритма решения сложных задач громоздка и не наглядна, она плохо формализована и не может непосредственно вводится в ЭВМ.

1.3.2. Графический способ описания алгоритма

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

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

Блок − схема по своему существу является той же логической схемой алгоритма, однако способ ее изображения более нагляден и удобен.

Изобразим алгоритм нахождения действительных корней квадратного уравнения ax2+bx+c=0 графически, в виде блок схемы.

Начало

a, b, c

D=:b2-4ac

D≥0

да

X1=-2+D/2a нет

X2=-2-D/2a

X1, X2

2. Структурный подход к разработке алгоритмов.

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

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

2.1. Управляющая структура следования

5

-S1

S2

S3

обеспечивает естественную последовательность выполнения действий. Каждый прямоугольник содержит одно или несколько последовательно выполняемых действий S:

2.2. Управляющая структура разветвления

«Истинно»

«Ложно»

- обеспечивает выбор выполняемого действия S1

или S2 в зависимости от некоторого условия Р. Если

P

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

ется действие S1 в противном случае - S2.

S1

S2

P

«нет»

«да»

Частный случай разветвления, когда одна

S1

ветвь не содержит никаких действий. Ее называют

обход:

2.3. Управляющая структура повторения (цикл) предусматривает повторное выполнение действия S (тела цикла) до тех пор, пока некоторое условие имеет значение "истинно". Как только значение условия становится "ложно", прекращается выполнение действия S, и управление передается следующей структуре. Различают две разновидности структуры повторения.

.

Цикл с постусловием − "ДО".

Цикл "ДО" выполняет действие S хотя бы один раз, так как первая проверка условия выхода из цикла происходит тогда, когда тело цикла уже выполнено.

Цикл с предусловием или цикл "ПОКА"

Цикл "ПОКА" отличается от цикла тем, что проверка условия производится до выполнения тела цикла, и если при первой проверке условие выхода из цикла выполняется, то тело цикла не выполняется ни разу.

P«Ложно»

«Истинно»

S

S

«Истинно» P

«Ложно»

3.Примеры типовых структур алгоритмов.

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

3.1. Алгоритм линейной структуры.

Определение: линейным называется алгоритм, в котором действия выполняются

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

Начало

x

P=x·x

F=2·P+4·P·P+6

F

6

дусматривает использование только структуры "следование". Блок − схема такого вычислительного процесса − это последовательность блоков.

Пример 1. Составить схему алгоритма вычисления выражения F=2x4+4x2+6 при x=3.

В системе MathCAD этот алгоритм реализовывается следующим образом:

x:=3 P:= x·x F:=2·P2+6

F=348

3.2. Разветвляющийся алгоритм

Oпределение: Разветвляющимся называется алгоритм, если в зависимости от выполнения или невыполнения некоторых условий его реализация происходит по одному из заранее предусмотренных направлений.

Начало

f(x)=sin(x)

f(x)≥0 да

нет

f(x)=-f(x) f(x)=f(x)

f(x)

Разветвляющийся алгоритм предусматривает использование следующих структур: следование и ветвление.

Рассмотренный нами ранее алгоритм нахождения действительных корней уравнения является алгоритмом разветвляющейся структуры.

Пример 3: Задана синусоидальная функция f(x) = sin(x). Надо создать другую функцию z(x), совпадающую с заданной, если она положительна, и противоположную по знаку заданной, если она отрицательна. Блок-схема алгоритма приведена на рисунке.

В системе MathCAD разветвляющиеся структуры реализуются с помощью функции if, которая имеет следующий формат:

if ( условие, выражение 1, выражение 2)

эта функция возвращает значение выражения 1, если условие выполняется, или значение выражения 2, если условие не выполняется.

Наша блок — схема реализуется так: f(x) := sin(x)

z(x) := if ( f(x) > 0, f(x), -f(x))

Ввод символов условия (равно, не равно, больше, меньше, больше или равно,

меньше или равно) производится с палитры			Evaluation and Bolean Palette или Вид/
Панели инструментов /математика или нажатием следующих сочетаний клавиш:
	Условие	Ввод	Пояснение
	Е1 = Е2	Е1 Alt = E2	Равно
	Е1 ≠ Е2	Е1 Alt # E2	Не равно
	E1 > E2	E1 > E2	Больше
	E1 < E2	E1 < E2	Меньше
	E1 ≥ E2	E1 Alt ) E2	Больше или равно
	E1 ≤ E2	E1 Alt ( E2	Меньше или равно

7

Вид символов на экране и на принтере может отличаться от приведенного в таблице.

3.3. Алгоритм циклической структуры.

Определение. Циклическим называют алгоритм, в котором предусмотрено мно-

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

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

Число повторений цикла определяется при вычислении суммы элементов – числом слагаемых, при нахождении максимума из n – чисел – числом сравниваемых величин, при нахождении значения полинома – его степенью. Причем число повторений цикла известно до начала выполнения алгоритма и не зависит от самих величин, над которыми выполняются операции. В арифметических циклах используется специальный оператор цикла (параметр), который состоит из двух частей. Первая – это заголовок (начало) оператора цикла, вторая часть – это конец оператора цикла. Между ними располагается заданная последовательность операторов, которую нужно выполнить несколько раз.

Определение: Параметром цикла называется переменная, которая изменяет свои

значения от начального до конечного, через шаг. Изобразим структуру цикла в виде схемы:

	Задание начального
	параметра цикла
	I=Iнач
	Тело цикла
да	Изменение пара-
	метра цикла I=I+H
	Условие
	I≤Iкон
	нет

Для компактного изображения цикла на схеме можно использовать символ мо-

дификация

I=Iнач, Iкон,Н

Тело цикла

где: I − управляющая переменная цикла, Iнач− ее начальное значение, Iкон − конечное значение управляющая переменная цикла, Н− шаг, с которым изменяется управляющая переменная цикла, если Н = 1, то его опускают.

В блоке «задание начального параметра цикла» должны задаваться значения переменных, используемых в теле цикла (или в блоке проверки условия), так, чтобы при первом прохождении цикла получался правильный результат. Например, при вычислении суммы n слагаемых после первого прохождения цикла сумма S должна быть равна пер-

	8
вому слагаемому, а для этого в блоке «задание начального параметра цикла» нужно за-
дать S=0. Аналогично при вычислении произведения n сомножителей произведение Р
должно быть равно первому сомножителю после первого шага цикла, поэтому в блоке
«задание начального параметра цикла» нужно задать Р=1.
Начало	Рассмотрим это на примере составления
	алгоритма для вычисления суммы элементов
В, Si=0	строк матрицы В размером 3×3.
	Значение bi,j			вычисляется для каждого зна-
	чения каждой строки матрицы, сначала по
i=:1;3	внутреннему циклу – по j затем по внешнему –
	i.
j=:1;3	1	2	3	6
	B = 4	5	6	S = 15
	7	8	9	24
Si=:Si+Bi,j
S

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

				Допустим вектор yi =(1,2,3). На первом шаге бе-
S:=1				рется значение y1=1 и умножается на содержимое ячей-
				ки S, т.е. на 1, и помещается в эту же ячейку, на втором
i=:1;n				шаге берется значение y2=2, умножается опять на значе-
				ние, находящееся в ячейке S, полученный результат
				возвращается обратно (S2=1×2) и т.д. S3=2×3=6
S=:S yi

yi

В случае, когда управляющая переменная цикла изменяется от 1 до n с шагом 1, ее называют счетчиком, а организуемый при ее помощи цикл – циклом по счетчику. Цикл арифметического типа называют также циклом до.

			Циклы с конечным, но неопределенным заранее
	Начало	числом повторений называются итерационными. Ите-
		рация	— это результат повторного применения какой

	x, ξ	либо математической операции.
		Пример. Составить алгоритм вычисления суммы

n=0

a=1, y=1

n=n+1

a = ax n +1

да

y=y+a

a≥ξ

нет

y,n

членов ряда y =1+	x		+	x2	+ ... +	xn
	2!					(n +1)!
			3!

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

ξ.

a - очередной член ряда n- номер этого члена ряда тогда при n=0, a=2

n=1, a=x/2 n=2, a=x2/6 и т.д.

9

В системе MathCAD часто используются циклические вычисления. Например, необходимо вычислить некоторое число значений какой либо функции f(x). Циклические вычисления характерны и для итерационных и для рекуррентных методов (от латинского recurrens – возвращающийся). Рекуррентная - это формула, позволяющая вычислить (n+1)-й член последовательности через значения ее n – первых членов.

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

Имя переменной := Nнач..Nкон

Nнач − начальное значение переменной, Nкон − ее конечное значение.

Если Nнач< Nкон, то шаг изменения переменной равен +1, если Nнач< Nкон, то –1. Переменные такого типа в системе MathCAD называются переменными с заданными

пределами изменения. Шаг изменения можно задать любым, используя конструкцию:

Имя переменной := Nнач, Nслед..Nкон

где Nслед − следующий за Nнач значение переменной, шаг в этом случае равен

Nслед - Nнач.

Пример: k:=0,0.5..3 k=0,0.5, 1, 1.5,2,2.5,3. (записывается в столбик)

4.Примеры основных алгоритмов обработки массивов

Начало

n, p, q

ORIGIN

i=:1;n

xi=f(xi)

4.1. Ввод вектора

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

n := 4 p := 5 q := 6 ORIGIN := 1

xi	i := 1 . . n

xi := f(i)

Здесь xi − индексированная переменная, а справа выражение (формула, задающая значение хi в зависимости от индекса i).

4.2. Вложенные циклы

Определение. Если циклический алгоритм содержит в себе один или несколько других циклических алгоритмов,

Начало	то такой алгоритм называется алгоритмом с вложен-

n, p, q	ными циклами.
	4.3. Примеры вложенных циклов
ORIGIN	Ввод матрицы
i=:1;n	n : = 4	p : = 5	q : = 6
	ORIGIN : = 1
j=:1;n	i : = 1 . . n
	j : = 1 . . n
	A i,j : = f(i,j)
Bi,j=f(xi,j)	Пояснения аналогичны, что и при вводе вектора.
Bi,j

	10
1. Найти значение максимального элемен-
та вектора
MaxV1 := V1
i := 1 . . n
MaxV1:=if(MaxV1>Vi, MaxV1, Vi)
MaxV1 =.
Начало
V
MaxV1=V1
i=1,n
MaxV1≥Vi	да
нет
MaxV1=Vi	MaxV1=V1

MaxV1

2. Найти значение максимального эле-
мента матрицы
MaxA1 := A1,1
i := 1 . . n
j := 1 . . n
MaxA1:=if(MaxA1>Ai,j,MaxA1,Ai,j)
MaxA1 =
Начало
A
MaxA1=A1,1
i=1,n
j=1,n
MaxA1≥Ai,j	да
нет
MaxA1=Ai,j	MaxA1=A1

MaxA1

	3. Произведение матриц	Начало
	i := 1 . . n j := 1 . . n
	Ci,j = 0	A,B
	k := 1 . . n
		i=1,n
	Ci,j = Ci,j + Ai,k Bk,j
	C=	j=1,n
		Ci,j=0
	n	k=1,n
	Cij = ∑ Aik Bki
	k=1
		Ci,j=Ci,j+Ai,k·Bi,k
		C