IT_04_11

11

4 Теоретические сведения

4.1 Общие сведения о алгоритме

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

Алгоритм характеризуется следующими свойствами:

а) однозначностью - исключение возможности произвольного толкования любого из предписаний;

б) результативностью - реализация вычислительного процесса должна привести к получению результата или сообщению о невозможности получения результата;

в) массовостью - обеспечение возможности использования алгоритма для составления программ решения задач для различных вариантов задания значений исходных данных;

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

Различают следующие способы описания алгоритмов:

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

языке псевдокода (например, АЯРН - алгоритмический язык в русской нотации); в) графический, когда алгоритм изображается в виде схем, состоящих из

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

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

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

-исходные данные;

-промежуточные результаты;

-результаты вычислений;

-правило начала;

-правило непосредственной переработки;

-правило окончания;

-правило извлечения результатов расчета.

При разработке алгоритма используют следующие методы:

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

-метод подъема, при этом задается начальное предположение варианта

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

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

4.2 Графические изображения схем алгоритмов и программ.

Ниже приводятся изображения символов схемы программы по ГОСТ 19.701-90. Различает следующие разновидности схем алгоритмов:

1)схема данных, которая отображает путь данных при решении задач и определяют этапы обработки, а также различные применяемые носители данных;

2)схема программ - отображает последовательность операций в программе;

3)схема работы системы - отображает управление операциями и поток данных в системе;

4)схема взаимодействия программ - отображает путь активации программ и взаимодействий с соответствующими данными;

5)схема ресурсов системы - отображает конфигурацию блоков данных и обрабатывающих блоков, которая требуется для решения задачи или набора задач.

12

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

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

2)линейных символов, указывающих поток управления;

3)специальных символов, используемых для облегчения работы со схемой. 4.2.1 Символ «Процесс» Он предназначен для изображения вычислительного действия или

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

Рисунок 4.1 4.2.2 Символ «Решение».

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

Рисунок 4.2 4.2.3 Символ «Терминатор».

Рисунок 4.3 4.2.4 Символ «Данные (ввод/вывод)»

Рисунок 4.4 4.2.5 Символ предопределенного процесса (вызова подпрограммы)

Рисунок 4.5 4.2.6 Символ «Подготовка (модификация)»

Рисунок 4.6 4.2.7 Символы «Границы цикла»

Рисунок 4.7 4.2.8 Символ «Соединитель»

Рисунок 4.8 4.2.9 Символ «Комментария»

Рисунок 4.9

13

4.3 Разновидности структур алгоритмов

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

-композиция (линейная последовательность операций);

-выбор (алгоритм ветвления):

-итерация (циклические структуры).

4.3.1 Структура линейного алгоритма

Операция 1

Операция 2

Операция 3

Рисунок 4.10 Композиция описывает процесс, в котором операции выполняются

последовательно в порядке, их записи.

4.3.2 Структура алгоритма выбора При выборе предусмотрено несколько направлений передачи управления в

зависимости от заданного условия.

При наличии двух направлений выбора структура имеет следующий вид:

Да			Нет
		Условие
Вариант 1			Вариант 2

Рисунок 4.11 При наличии большего числа вариантов выбора структура имеет вид

Условие

1

Вариант 1

2

Вариант 2

n

Вариант n

Рисунок 4.12 4.3.3 Структуры циклических алгоритмов

Имеется два варианта итераций:

14

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

2)цикл с пост условием, когда сначала выполняется тело цикла, а затем происходит проверка условия выхода из цикла.

Блок схема алгоритма цикла с предусловием имеет вид:

Нет

Условие

Да

Тело цикла

Рисунок 4.13 Перед выполнением цикла производится определение начальных значений

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

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

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

Цикл с постусловием имеет следующую структуру рисунка 4.14

Тело цикла

Нет условие

Да

Рисунок 4.14 - Алгоритм цикла с постусловием Отличие структуры цикла с постусловием в том, что проверка условия для

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

Условие

Тело цикла

Тело цикла

Условие

а) б) Рисунок 4.15

Если необходимо выполнить заданное число итераций тела цикла, то тогда структура обозначается с учетом символа «Модификация».

Число итераций

Тело цикла

Рисунок 4.16

15

4.4 Правила построения схем программ

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

1)символ предназначен для графической идентификации функции, которую он отображает, независимо от текста внутри этого символа;

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

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

4)минимальное количество текста, необходимого для понимания функции данного символа, следует помещать внутри данного символа. Текст для чтения

должен		записываться слева	направо и сверху вниз независимо от направления
потока. Если объем текста,			помещаемого внутри символа, превышает его размеры,
следует		использовать символ	комментария. Если использование символов комментария
может	запутать или разрушить ход			схемы, текст следует помещать на отдельном
листе	и	давать перекрестную	ссылку	на символ;

5)в схемах может использоваться идентификатор символов. Это связанный с данным символом идентификатор, который определяет символ для использования в справочных целях в других элементах документации (например, в листинге программы). Идентификатор символа должен располагаться слева над символом;

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

7) в схемах работы системы символы, отображающие носители данных, во многих случаях представляют способы ввода-вывода. Для использования в качестве ссылки на документацию текст на схеме для символов, отображающих способы вывода, должен размещаться справа над символом, а текст для символов, отображающих способы ввода — справа под символом;

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

сполосой;

9)потоки данных или потоки управления в схемах показываются линиями. Направление потока слева направо и сверху вниз считается стандартным;

10) две или более входящие линии могут объединяться	в одну исходящую
линию. Если две или более линии объединяются в одну линию,	место объединения
должно быть смещено;

11)линии в схемах должны подходить к символу либо слева, либо сверху, а исходить либо справа, либо снизу. Они должны быть направлены к центру символа;

12)при необходимости линии в схемах следует разрывать для избежания излишних пересечений или слишком длинных линий, а также, если схема состоит из нескольких страниц. Соединитель в начале разрыва называется внешним соединителем, а соединитель в конце разрыва — внутренним соединителем;

13)ссылки к страницам могут быть приведены совместно с символом комментария для их соединителей.

4.5 Алгоритмизация задач лабораторной работы

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

16

Начало

Ввод A

Ввод B

	Расчет C
Да			Нет
	С<0

Ввод значения переменной A по запросу с клавиатуры

Ввод значения переменной B после запроса с клавиатуры

Расчет значения выражения переменной C

D=A*B-С2						D=С*B-A2
										Вывод значения переменной C
			C
										условия на экран
										Вывод значения переменной D
			D
										результата на экран
			Конец

Рисунок 4.17 - Пример схемы программы задачи №1 Схема алгоритма второй задачи №2 содержит структуры композиции и итерации.

Начало

Ввод

Xn

Ввод по запросу начального

значения аргумента

Xk

Ввод по запросу конечного

Ввод

значения аргумента

Hx

Ввод по запросу значения шага

Ввод

изменения аргумента

Начало цикла расчета функции с

Цикл пока

X>Xk

постусловием

Расчет значения выражения

Расчет

Y

переменной Y

Вывод экран текущих значений

X, Y

переменных аргумента и функции

Наращивание текущего значения

X = X + Hx

переменной аргументов

Выход из цикла расчета значений

Конец цикла

функций

Конец

Рисунок 4.18 – Пример схемы алгоритма задачи №2

17

4.6 Базовые типы данных языка С++

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

1)простые (скалярные) типы, не имеющие внутренней структуры, описывающие одно значение данных;

2)составные (структурированные) типы, имеющие некоторую внутреннюю структуру, описывающие некоторый комплекс единых данных.

В языке C имеется пять базовых (фундаментальных) типов данных:

1)символьный char – определяет символы текста;

2)целочисленный int – определяет целые численные значения;

3)вещественный с одинарной точностью float – определяет численные значения с дробной частью обычной точности представления;

4)	вещественный с двойной точностью double – определяет численные
значения с дробной частью высокой точности представления;
5)	тип void, который может иметь три назначения:

;указание о невозвращении значения функцией;

;указание о неполучении параметров функции;

;создание нетипизированных указателей.

Четыре первых базовых типа данных могут иметь модификаторы, которые

уточняют параметры типа данных:
1) signed	–	тип,	учитывающий	знак	(возможность	использования
отрицательных значений);

2)unsigned – тип данных, учитывающий только положительные значения, не учитывающие знак;

3)long – обозначение типа длинного размера в байтах, использующийся для увеличения диапазона возможных значений;

4) short – обозначение типа короткого размера в байтах,	имеющего
небольшой диапазон возможных значений.
В языке С нет явного обозначения логического типа данных. Вместо него
используется тип int, нулевое значение которого соответствует	ложному

утверждению, а ненулевое – истинному. В языке С++ имеется явно заданный логический тип данных bool, истинное значение соответствует константе true, а

ложное – false.

4.7 Переменные языка С++

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

тип_данных_переменной имя_переменной; Примеры объявления переменных

int I;	//	объявление	целочисленной переменной I
float X;	//	объявление	вещественной переменной X

Имя переменной должно начинаться с символа латинского алфавита или символа подчеркивания (_) и может включать далее и цифры. В языках программирования С и С++ различаются прописные и строчные символы: x и X – это две разные переменные.

Если объявляется несколько переменных одного типа, то возможна сокращенная

форма записи, использующая		формат:
тип_данных имя_первой_переменной, имя_второй_переменной, …;
int i, j, k;	//	объявление трех целочисленных переменных
В языках С и С++ при объявлении переменных можно присвоить начальные
значения (провести	инициализацию переменных), так как считается, что по
умолчанию переменная имеет		нулевое значение. Формат инициализации имеет вид:

тип_данных имя_переменной = начальное значение; Примеры объявления переменных:

18

double z=1.5e-5; // инициализация переменной значением 1.5·10-5 int i=10, j=-100; // инициализация двух целых переменных

4.7 Операторы языка С++

4.7.1 Математические и логические операции Таблица 4.1 – Арифметические операции в языке С++

Символ	Выполняемая операция
+	Плюс, унарный и бинарный
-	Минус, унарный и бинарный
*	Умножение
/	Деление
%	Получение остатка целочисленного деления
++	Унарная инкрементация (увеличение на 1)
--	Унарная декрементация (уменьшение на 1)

В таблице Таблица 4.1 указаны арифметические операции языка С++. Целое деление дает целый результат (7/2 = 3). Над целыми может выполняться операция %

получения остатка (7%2 = 1). В			Таблица		4.2	представлены операторы			С++,
используемые для управления логикой выполнения.
Таблица 4.2 – Логические операторы и сравнения в языке С++
Назначение			Операция				Обозначение
			Меньше				<
Операторы сравнения			Больше				>
			Меньше или равно				<=
			Больше или равно				>=
Операторы равенства			Равно				==
			Не равно				!=
			Отрицание				!
Логические операторы			Логическое И				&&
			Логическое ИЛИ				||
Важно не	путать операторы			равенства		и присваивания,		например,
a==b – это проверка	на равенство, т.е.			если	a и	b равны то выражение		даст	true

(истина), в противном случае – false (ложь), а в выражении a=b переменная a станет равна b.

4.7.2 Операция присваивания

Оператор присваивания в классическом случае обозначается символом = и имеет формат

переменная = расчетное_выражение; При этом сначала рассчитывается выражение, стоящее справа от =, которое

впоследствии присваивается переменной, стоящей в левой части.

В языке C++ имеется операция присваивания вместо оператора присваивания. Это позволяет выполнять присваивание внутри других выражений, например:

x=sqrt(a=3*x)

Допустимо множественное присваивание в формате

Переменная_1 = переменная_2 = ... = переменная_N = выражение; Пример множественного присваивания

a=b=c=10; // присвоение 10 сначала c, потом b, а затем a.

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

Например, x*=4 означает x=x*4.

19

Таблица 4.3 – Операторы присваивания языка С++

Обозначение	Описание
=	Присваивание
*=	Присвоить произведение
/=	Присвоить частное
%=	Присвоить остаток
+=	Присвоить сумму
-=	Присвоить разность
<<=	Присвоить сдвиг влево
>>=	Присвоить сдвиг вправо
&=	Присвоить поразрядное И
^=	Присвоить поразрядное исключающее ИЛИ
\!=	Присвоить поразрядное ИЛИ

4.7.3 Оператор выражения
Выражением	называется	последовательность	операций,	операндов	и

пунктуаторов (разделителей), задающих определенное вычисление. Например: a = b*3+c;

cout << "press Enter"; sin(2*x+1);

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

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

4.7.4 Составной оператор

Составной оператор –			это блок, ограниченный фигурными скобками. Составной
оператор позволяет рассматривать				несколько операторов как один.
{	a=b+2;	//	начало составного оператора
	b++;
}		//	конец	составного оператора

4.8 Операторы программирования переходов

Данная группа операторов используется для программирования алгоритмов ветвления и выбора. Имеется три условных оператора: if, switch и ?.

4.8.1 Условный оператор if.

Синтаксис описания оператора условного перехода if имеет вид:

if (выражение_условия) выражение_альтернативы_Да; else выражение_альтернативы_Нет;

При использовании if следует обратить внимание на следующее:

а) часть оператора else не является обязательной, допустимо использовать оператор if в виде:

if (выражение_условия) оператор_Да;

В этом случае оператор_Да выполняется если выражение истинно, в противном случае пропускается оператор_Да и выполняется следующий оператор;

б) если необходимо выполнить более одного оператора, то следует использовать составной оператор.

Условие в операторе if должно быть заключено в круглые скобки.

4.8.2 Оператор выбора switch.

20

Оператор switch производит сопоставление значения с множеством констант и передает управление на блок операторов, отмеченных искомым значением. Пример:

switch (i)		// Проверка условия по значению переменной X
{	case 1:		cout << “Один”;	// Вывод сообщения
			break;	// Окончание switch
	case 2:		cout << “Два”;	// Вывод сообщения
			break;	// Окончание switch
	default:		cout << “Другие числа”;	// Вывод сообщения
			break;	// Окончание switch

}// Конец оператора switch

Операторы break применяются для выхода из оператора switch. Константы в вариантах case должны быть различными, и если проверяемое значение не совпадает ни с одной из констант, выбирается вариант default, не являющийся обязательным.

4.8.3 Оператор ?

В С имеется компактное представление логического перехода, которое используется вместо конструкции if-else – оператор ?. Синтаксис оператора:

выражение_условия ? выражение_ДА : выражение_НЕТ ;

Сначала вычисляется выражение условия. Если оно истинно, то выполняется выражение_ДА, если не выполняется – выражение_НЕТ.

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

#include <iostream.h> #include <conio.h> int X,Y;

int main()

{cout << "\nВведите X и Y"; cin >> X >> Y;

if(X>Y) cout << "\nX>Y";

else cout << "\nX<Y";

getch();
return	0;
}// конец примера
Пример с	использованием	оператора ?:
#include	<iostream.h>	// модуль потоков cin и cout
#include	<conio.h>	// модуль с функцией getch()

int X,Y;	// объявление глобальных целочисленных переменных
int main()		// головная функция
{ cout << "\nВведите X и Y";		// вывод сообщения
cin >>	X >> Y;	// ввод с клавиатуры X и Y
(X>Y)?	cout << "\nX>Y": cout << "\nX<Y";
getch();
return	0;
}// конец примера

4.9 Операторы итераций (циклов)

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

1)цикл с предусловием;

2)цикл с постусловием;

3)цикл с заданным числом итераций.

4.9.1 Оператор цикла с предусловием while.

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