Введение

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

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

1. Алгоритмизация вычислительных процессов

1.1. Основные этапы подготовки задачи к решению на ПЭВМ

Процесс подготовки задачи к решению на ПЭВМ состоит из следующих основных этапов:

−постановка задачи,

−математическое описание задачи (выбор или разработка математической модели),

−выбор и обоснование численного метода,

−алгоритмизация вычислительного процесса,

−составление программы и ее отладка.

Впроцессе подготовки задачи к решению на ПЭВМ некоторые этапы могут периодически повторяться (например, для уточнения метода решения или алгоритма).

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

5

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

Выбор и обоснование численного метода. Само по себе математическое описание в большинстве случаев трудно представить на языке вычислительной машины. Использование в этом случае конкретного численного метода приводит решение задачи к упорядоченной последовательности выполнения арифметических и логических операций. Если одна и та же задача может быть решена с помощью различных численных методов, то выбирают тот, который наилучшим образом удовлетворяет её основным требованиям с учётом требуемой точности, времени решения задачи на ПЭВМ, требуемых ресурсов ПЭВМ.

Алгоритмизация вычислительного процесса. На этом этапе составляется алго-

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

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

Алгоритмизации вычислительных процессов включает:

−определение структуры, типов и диапазонов допустимых значений исходных данных и результатов;

−выделение автономных этапов вычислительных процессов;

−формальное описание каждого этапа;

−определение, для каждого этапа, структуры и типов вспомогательных данных, используемых для реализации алгоритма;

−назначение порядка выполнения этапов вычислительного процесса;

−проверку результативности (правильности) выбранного алгоритма для допустимого набора исходных данных.

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

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

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

Далее по тексту используется следующая терминология:

6

−данное (данные) – информация, представленная в виде пригодном для обработки на ЭВМ (числа или наборы символов). Синонимы: переменная, операнд, величина;

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

−вычислительный процесс – совокупность операций над данными.

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

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

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

Формульно-словесный способ описания алгоритмов базируется на использовании математических символов и выражений (формул) в сочетании со словесным пояснением. Этот способ используется в специальной литературе (математика, физика и т.п.).

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

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

взависимости от характера описываемых операций.

Впроцессе разработки алгоритмов допускается неформальное их описание, но в сопроводительной документации к программе уместен только формальный, общепринятый способ описания алгоритмов в виде блок-схем. В этом случае используются предусмотренные ГОСТ 19.701-90 (ISO 5807-85) условные обозначения, часть которых приведена ниже.

Терминатор. Символ отображает начало, конец или прерывание выполнения программы.

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

Комментарий. Используется для пояснений содержимого отдельных этапов вычислительного процесса.

Процесс. Символ отображает обработку данных представленных в памяти ПЭВМ (расчет по формулам). Расчетную формулу можно записать внутри символа или в комментарии.

7

Данные. Ввод или вывод данных, носитель которых не определен.

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

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

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

При выполнении схем алгоритмов или программ следует придерживаться следующих правил:

−начало или конец алгоритма или программы изображается символом "терминатор", внутри которого можно записывать соответственно слова "начало", "конец" или отметить причину прерывания работы программы;

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

−символам блок-схемы можно присваивать идентификаторы (слова или числа), располагаемые слева над линией контура;

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

−блок-схему разрешается размещать на отдельных листах. Начало и конец разрываемых при этом соединяющих линий отмечаются символом «соединитель» с «комментарием». Внутри символов «соединитель» указываются идентификаторы символов (этапов вычислительного процесса) от которых и к которым соответственно передаётся управление;

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

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

При описании вычислительного процесса следует помнить, что при выполнении программы значение любого данного, введённое в память ЭВМ или полученное в процессе выполнения расчётов, сохраняется до окончания работы программы, если только оно не будет каким-либо образом переопределено. Переопределенное (новое) значение может

8

быть вычислено в процессе выполнения программы или введено пользователем в память ЭВМ. В этом случае прежнее значение переопределяемого данного будет потеряно.

1.3. Типовые структуры вычислительных процессов и их описание

В соответствии с характером действий вычислительного процесса его можно отнести к одному из трех типов:

−линейный вычислительный процесс;

−ветвящийся вычислительный процесс;

−циклический вычислительный процесс.

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

1.3.1. Линейный вычислительный процесс

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

Этот процесс характерен порядком выполнения этапов незави-		Начало
сящим от исходных данных и результатов промежуточных вычисле-
ний. Графически линейный вычислительный процесс изображается	Ввод
		x, a, b
на блок-схеме одним или несколькими (в зависимости от степени
детализации) символами.
В качестве примера линейного вычислительного процесса рас-		y=a+b x
смотрим блок-схему изображенную на рис. 1.1. Последовательно
	Вывод
выполняются следующие этапы: ввод значений аргумента x и коэф-		x, y
фициентов a, b; расчет значения функции по формуле y=a+bx; вы-
вод результата расчета (значения аргумента x и функции y). Блок-
		Конец
схема отражает строго оговоренную последовательность этапов, на-
рушение которой может привести к фатальному нарушению алго-	Рис.1.1. Линейный вы-
ритма. Не нарушая общую последовательность этапов можно дета-	числительный процесс
лизировать содержание отдельных этапов, т.е. сложные выражения

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

1.3.2. Ветвящиеся вычислительные процессы

Вычислительный процесс называется ветвящимся, если в зависимости от значений исходных данных или промежуточных результатов он реализуется по одному из нескольких, заранее предусмотренных (возможных) направлений, каждое из которых носит на-

звание ветви вычислений.

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

9

	При организации ветвящихся вычислительных процессов возможны две основные
	ситуации: ветвление по условию и ветвление по ключу.
	Ветвление по условию. В этом случае выбор ветви вычислений осуществляется по
	значениям промежуточного результата и чаще всего заранее неизвестно конкретное
	направление счета.
	На рис.1.2 приводится блок-схема алгоритма:
	y=cos(x) если x<π/4,				да
					(then)
	y=sin(x) если x≥π/4.		x < π / 4
	В случае, когда условия являются взаимоисключающи-		нет		y=cos(x)
	ми, можно сформулировать иначе:
			(else)
	если(if) x<π/4	тогда(then) y=cos(x)	y=sin(x)
		иначе(else) y=sin(x).
	При неоднократном использовании данного вычисли-		Рис.1.2 Ветвление по
	тельного процесса значения x могут варьироваться. Но каж-
			условию
	дый раз осуществляется проверка условия ветвления и выби-
	рается ветвь вычислений соответствующая текущему значе-
	нию x.
	Ветвление по ключу. В этом случае имеется набор вычислительных процедур, объ-
	единенных в один модуль. Каждой вычислительной процедуре назначается значение пе-
	ременной называемой ключом. Пользователь имеет возможность выбрать требуемую про-
	цедуру вычислений, задав значение оговоренной переменной (ключа).
	Например, имеется ряд функциональных зависимостей:		y=f1(x);		y=f2(x);
	y=f3(x); ...; y=fn(x), которым соответствует ряд зна-
	чений переменной k, которую будем называть ключом. При		k
	k=1 расчет производится по зависимости y=f1(x), при k=2 –		k=1
	по y=f2(x), при k=3 – по y=f3(x) и т.д.				y=f1(x)
	Таким образом, для выбора нужной ветви вычислитель-		k=2		y=f2(x)
	ного процесса пользователю необходимо указать конкретное
			k=n
	значение ключа (k).			y=fn(x)
	Графически структура такого линейного вычислительно-
	го процесса может быть изображена так, как это показано на		Рис.1.3 Ветвление по ключу
	рис.1.3.
	Чаще всего в качестве ключа используются переменные
	целого типа. Удобно в качестве значения ключа использовать номер расчетной зависимо-
	сти (как в рассмотренном примере).

1.3.3. Циклические вычислительные процессы

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

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

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

Проход цикла - однократное выполнение последовательности операций входящих в

цикл.

10

Принято выделять следующие типы циклов:

−цикл с подсчетом числа проходов (for);

−цикл с условием на входе (While);

−цикл с условием на выходе (Repeat - Until).

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

Цикл с подсчетом числа проходов. Называемый также циклом с параметром, чаще всего используется для обработки массивов. Под массивом понимается совокупность данных одного типа (элементов массива), объединенных под одним именем (именем массива). Чаще всего встречаются одномерные массивы (векторы). Положение элемента в массиве определяется его индексом. Например: обозначение x5 - указывает на пятый (считая

от начала массива) элемент массива с именем X-

а

б

Обычно нумерация элементов массива начинается

i = ib

с 1. Тогда максимальное значение индекса соответ-

i = ib, ie, 1

ствует количеству элементов в массиве. При обра-

да

ботке массивов в цикле с подсчетом числа прохо-

i > ie

yi=f(xi)

нет

дов параметр цикла используется в качестве ин-

Вывод

yi=f(xi)

декса элемента массива.

i, xi, yi

Вывод

Типичная структура такого цикла изображена

i, xi, yi

на рис.1.4а, где отражается циклический расчет

i

функции yi=f(xi), в котором параметр цикла i

изменяется от начального значения равного ib до

i=i+1

конечного значения ie, а приращение параметра

цикла равно 1.

Рис.1.4 Цикл c подсчетом числа проходов

До выполнения проходов цикла параметру

а – функциональная схема;

цикла назначается его начальное значение i=ib.

б – компактное описание.

Вцикл входят этапы:

−проверка условия завершения цикла;

−расчет значений функции yi по заданным значениям аргумента xi;

−вывод значений: индекса i, аргумента xi и функции yi;

−переопределение значения параметра цикла для перехода к следующему проходу i=i+1 т.е. значение параметра цикла увеличивается на величину приращения параметра цикла.

Вслучае, когда начальное значение параметра цикла больше конечного (is>ie) тело цикла не выполняется ни разу.

Для удобства составления блок-схем цикл с подсчетом числа проходов записывают в компактной форме (блок-схема на рис.1.4б).

Цикл с условием на входе. На рис.1.5а показана функциональная блок - схема цикла While. Проходы циклов подобного типа осуществляются только в том случае, если выполняется определенное заранее оговоренное условие. Иначе можно сказать, что проходы циклов будут проводиться пока выполняется это условие.

Рассмотрим вычисления функции y=f(x), когда значения аргумента x изменяются от минимального значения xmin до максимального - xmax с шагом ∆x. В данном случае аргумент x является параметром цикла по значению которого не только производится расчет функции y, но и проверяется условие выполнения цикла.

11

	При использовании цикла While необходимо до		а	б
	циклических вычислений задать начальное значение
			x=xmin	x=xmin
	параметра цикла x=xmin. Перед каждым проходом		нет	Цикл «While»
	цикла проверяется значение логического выражения
			x ≤ xmax	x ≤ xmax
	являющегося условием выполнения цикла (в данном	да		y=f(x)
	случае x≤xmax). Если это условие выполняется, то
			y=f(x)	Вывод
	затем выполняются операции, описанные в теле цик-	Вывод		x, y
	ла, если условие не выполняется, то операции в цик-
			x, y	x=x+∆x
	ле игнорируются и управление передается этапам ал-
	горитма следующим за циклом. Обратите внимание		x=x+∆x	Цикл «While»
	на организацию ветвления (на расположение then и
	else). Таким образом, если условие x≤xmax не выпол-		Рис.1.5 Цикл «While»
	няется, не будет ни одного прохода цикла.		а - функциональная схема;
	Операция переопределения параметра цикла		б - компактная схема.
	(аргумента x) x=x+∆x, проводится в конце тела цикла после проведения необходимых
	расчетов и вывода результатов. Следует помнить, что переопределенное значение x на ве-
	личину ∆x больше значения x, по которому рассчитывается и выводится значение функ-
	ции y.
	При описании вычислительных процессов с циклом While программами на алгорит-
	мических языках нельзя забывать о точности представления данных. Так при пониженной
	точности представления данных в ЭВМ полученное текущее значение x может отличаться
	от конечного значения xmax на достаточно малую величину. Если это значение меньше
	xmax ничего неприятного не произойдет и все необходимые значения аргумента x будут
	обработаны. Хуже если переопределенное значение x станет больше xmax. В этом случае
	не выполнится условие x≤xmax и значение x≈xmax обработано не будет даже если оно от-
	личается от xmax на величину крайне малую.
	На рис.1.5б приведена блок-схема вычислительного процесса соответствующая опе-
	ратору цикла While алгоритмического языка Pascal.

Цикл с условием на выходе. На рис.1.6 рассмотрено решение аналогичной задачи с
использованием цикла Repeat until (повторять до тех пор, пока не выполнится условие
выхода из цикла). Как и в цикле While необходимо до циклических вычислений выпол-
нить присвоение параметру цикла его начального				а		б
значения x=xmin.	Отличие заключается в организа-		x=xmin		x=xmin
ции проходов цикла. Если в цикле While использова-					Цикл
лось условие выполнения прохода цикла x≤xmax, то в			y=f(x)
					Repeat until
цикле Repeat until	используется условие выхода из		Вывод		y=f(x)
цикла x>xmax. Поэтому в цикле Repeat until должен
			x, y
выполниться хотя бы один проход.					Вывод
Проходы цикла Repeat until повторяются до тех			x=x+∆x		x, y
пор, пока условие x>xmax не выполнится. Как только
					x=x+∆x
условие x>xmax выполнится		- проходы цикла Repeat		да
			x>xmax
until прекращаются. Такая		организация выхода из			Repeat until
цикла позволяет завершить процесс циклических вы-			нет		x>xmax
числений в любом случае и получить результат для			Рис.1.6	Цикл	Repeat until
значения x равного xmax.
			а – функциональная схема;
Как и в случае с циклом While при описании			б – компактная схема.
вычислений с ограниченной точностью представле-

12