Иванова Г.С. - Основы программирования

Введение

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

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

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

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

Кроме объектного подхода для работы в Delphi необходимо иметь пред­ ставление об основных отличиях Delphi Pascal и визуальных средах, исполь­ зующих принцип событийного программирования. Этот материал добавлен во второе издание учебника в виде приложений 4 и 5.

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

Часть 1. ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОЦЕДУРНОЕ ПРОГРАММИРОВАНИЕ

1. ЭТАПЫ СОЗДАНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

в процессе разработки программ с использованием процедурного подхода можно выделить следующие этапы:

• постановка задачи - определение требований к программному продукту;

•анализ - осуществление формальной постановки задачи и определение методов

еерешения;

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

•реализация - QQC^dibntHWQ программы на выбранном языке программирования, ее тестирование и отладка.

•модификация - выпуск новых версий программного продукта.

1.1. Постановка задачи

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

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

12

у.	Этапы создания программного обеспечения
Исходные	^+-ibP	Результаты
данные		(перечень,
(перечень,	Программа	характеристики,
характеристики,		способ
способ	Операцион ая система	представления)
представления)

Сбой Технические средства

Сбой энергоснабжения

Рис. 1.1. Факторы, определяющие параметры разрабатываемого программного обеспечения

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

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

Врезультате согласования между заказчиком и исполнителем всех пере­ численных вопросов составляют техническое задание в соответствии с ГОСТ 19.201-78, которое служит основанием для дальнейшей работы.

1.2.Анализ, формальная постановка и выбор метода решения

На данном этапе по результатам анализа условия задачи выбирают мате­ матические абстракции, адекватно, т.е. с требуемой точностью и полнотой, представляющие исходные данные и результаты, строят модель задачи и оп­ ределяют метод преобразования исходных данных в результат (метод реше­ ния задачи).

Пример 1.1. Разработать программу, которая по заданным длинам сто­ рон прямоугольника определяет его площадь.

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

13

Часть I. Основы алгоритмизации и процедурное программирование

S = а X Ь,

где S ~ площадь; а, b - длины сторон.

Результат получают перемножением аргументов.

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

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

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

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

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

1.3. Проектирование

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

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

14

/. Этапы создания программного обеспечения

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

Различают последовательности действий (вычислений) линейной, раз­ ветвленной и циклической структуры.

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

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

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

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

• циклические процессы, для которых количество повторений извест­ но ~ счетные циклы или циклы с заданным количеством повторений',

•циклические процессы, завершающиеся по достижении или наруше­ нии некоторых условий - итерационные циклы;

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

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

На изображение схем алгоритмов существует ГОСТ 19.701-90, согласно которому каждой группе действий ставится в соответствие блок особой фор­ мы. Некоторые часто используемые обозначения приведены в табл. 1.1.

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

В случае, когда схема алгоритма не умещается на листе, используют со­ единители. При переходе на другой лист или получении управления с друго-

15

	Часть L Основы		алгоритмизации				и процедурное программирование
								Т а б л и ц а 1.1
	Название блока			Обозначение				Назначение блока
1								Начало, завершение программы
I			(		Действие	J
								или подпрограммы
I	Терминатор
i
j								Обработка данных (вычисления,
'	Процесс				Действие
								пересылки и т. п.)
	Данные		/		Данные	/		Операции ввода-вывода
	Решение				Условие^			Ветвления, выбор, итерационные
								и поисковые циклы
	Подготовка		/действияЧ				i	Счетные циклы
	Граница цикла				Начало			Любые циклы
					Конец 1	\
к--
	Предопределенный				Имя			Вызов процедур
	процесс
	Соединитель							Маркировка разрывов линий
		::;{				I		•
{	Комментарий				Комментарий			Пояснения к операциям

i

го листа в комментарии указывается номер листа, например «с листа 3» «на лист 1».

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

•следование - обозначает последовательное выполнение действий (рис. 1.2, а);

•ветвление - соответствует выбору одного из двух вариантов действий (рис. 1.2,6);

•цикЛ'Пока - определяет повторение действий, пока не будет нарушено условие, выполнение которого проверяется в начале цикла (рис. 1.2, в).

16

	/. Эт<ты создант программного обеспечения
Действие 1	«^-Л'словиГ--^		нет
I	Действие 1	Действие 2
Действие 2

"Е

Рис. 1.2. Базовые алгоритмические структуры: следование (а), ветвление (б) и цикл-пока (в)

Помимо базовых структур используют три дополнительные структуры, производные от базовых:

•выбор - выбор одного варианта из нескольких в зависимости от значения некоторой величины (рис. 1.3, а);

•цикл'до ~ повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле (рис. 1.3, в);

•цикл с заданным числом повторений {счетный цикл) - повторение некоторых действий указанное число раз (рис. 1.3, д).

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

Перечисленные структуры были положены в основу структурного про­ граммирования - технологии, которая представляет собой набор рекоменда­ ций по уменьшению количества ошибок в программах [4, 8]. В том случае, если в схеме алгоритма отсутствуют другие варианты передачи управления, алгоритм называют структурным^ подчеркивая, что он построен с учетом рекомендаций структурного программирования.

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

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

Для каждой структуры используют свою форму описания. В литературе были предложены несколько вариантов форм псевдокодов. Один из вариан­ тов приведен в табл. 1.2.

Пример L2, Разработать алгоритм определения наибольшего общего делителя двух натуральных чисел.

17

Часть I. Основы алгоритмизации и процедурное программирование

Действие

нет _ Условие

да

i=nl,n2,h

Т

Действие

ИЗ

Действие 1	нет
Действие 2	Действие 3
	П"

Действие

>словие^ "^ да

Действие

1=п1

нет

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

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

18

	/. Этапы создания программного обеспечения
				Т а б л и ц а 1.2
Структура	Псевдокод		...Структура.	Псевдокод
Следование	<действие 1>		Выбор	Выбор <код>
	<действие 2>			<код1>: <действие 1>
				<код2>: <действие 2>
				Все-выбор
Ветвление	Если <условие>		j Цикл с	Для <индекс> =
	то	<действие 1>	! заданным	<n>,<k>,<h>
	иначе	<действие2>	количеством	<действие>
	Все-если		[^повторений	Все-цикл
Цикл-пока	Цикл'пока <условие>		' Цикл-до	Выполнять
	<действие>		|	<действие>
	Все-цикл		1	_Др.?УСлр1ие>

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

)	А	В	б)	А	В
	225	125		13	4
225-125 = 100		125		13-4=9	4
	100	25-100 = 25		9-4=5	4
100-25 = 75		25		5-4=1	4
75-25	= 50	25		1	4-1=3
50-25	= 25	25		1	3-1 =2
				1	2-1=1

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

В основе алгоритма лежит циклический процесс, количество повторе­ ний которого заранее не известно (итерационный). Условие выхода из цик­ ла - получение одинаковых чисел. Поскольку нельзя исключить, что пользо­ ватель введет равные числа, npoBcpiQ' будем осуществлять на входе в цикл, т.е. имеет смысл использовать цикл-пока. Если числа не равны, то при каж­ дом проходе цикла одно из чисел (большее) должно заменяться разностью большего и меньшего. Для реализации этой замены потребуется описать оба варианта, т.е. использовать ветвление с проверкой, какое из чисел больше. После выхода из цикла можно выводить пользователю любое из двух полу­ ченных чисел, так как они равны между собой.

19

Часть I. Основы алгоритмизации и процедурное программирова

На рис. 1.4 показана схема алгоритма, а ниже приведено его описание на псевдокоде.

			Алгоритм Евклида:
				Ввести А,В
				цикл-пока А ^ В
				если А > В
				то	А := А - В
				иначе В := В - А
		нет		все-если
				все-цикл
	А:=А-В	В:=В-А		Вывести А
			Конец алгоритма.
			Алгоритмы простых программ разраба­
	Вывод	/	тывают,	продумывая		последовательность
			действий для решения некоторой задачи, как
	/
			это было выполнено в примере. Для разра­
	( Конец	J	ботки алгоритмов более сложных программ
			целесообразно использовать метод пошаго­
	Рис. 1.4. Схема алгоритма		вой детализации (см. параграф				1.6). Парал­
			лельно с	разработкой		алгоритма	уточняют
	Евклида
			диапазон	изменения, точность и структурьг

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

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

1.4. Реализация

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

20