Жукова И.Г., Литовкин Д.В. (сост.) Технология программирования Методические указания
Подождите немного. Документ загружается.
Министерство образования Российской Федерации
Волгоградский государственный технический университет
Кафедра «Системы автоматизированного проектирования и
поискового конструирования»
ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ
Методические указания
Волгоград 2001
УДК
Технология программирования: Методические указания/ Сост. И.Г.
Жукова, Д.В. Литовкин; ВолгГТУ. – Волгоград, 2001. – 46 с.
Методические указания содержат основные теоретические сведения и
примеры проектирования одномодульных программ. Рекомендуются студентам
по направлению «Информатика и вычислительная техника» для подготовки к
практическим и лабораторным занятиям по курсу «Алгоритмические языки».
Таблиц:2. Библиогр.: 4 назв.
Рецензент В.В. Костерин
Печатается по решению редакционно-издательского совета
Волгоградского государственного технического университета
Волгоградский
государственный
технический
университет,
2001
Любая программа представляет собой последовательность операций,
понятных компьютеру. Количество операций, которые может выполнять
компьютер относительно невелико (не более 100), поэтому практически любая
программа содержит весь набор этих инструкций. Но откуда же тогда огромное
многообразие программ? Уникальность каждой программы определяется
последовательностью этих операций. Эта последовательность операций
называется алгоритмом.
Программа – это запись алгоритма решения задачи на языке
программирования высокого уровня или в машинных кодах.
На самом деле понятие алгоритм используется не только в
программировании. В широком смысле алгоритм – это предписание в виде
конечной последовательности дискретных шагов, которые задают процесс
преобразования исходной информации в результат.
Достаточно широко мы пользуемся алгоритмами в быту и на производстве –
это различные инструкции, правила и предписания. Например, правила
дорожного движения (“Переходя дорогу сначала посмотри налево. Если машин
нет, то иди. Дойдя до середины, посмотри направо. Если машин нет, то иди
дальше; иначе подожди когда проедут машины.”), инструкции по эксплуатации
бытовой технике, правила решения квадратного уравнения и т.д.
Пример:
Инструкция по кипячению воды в чайнике.
Главный вход: чайник без воды находится на полке. Конфорка выключена.
Вход: чайник без воды находится на полке.
Действие 1: Заполнение чайника водой.
Выход: чайник, заполненный до половины объема холодной водой,
находится на полке.
Вход: конфорка выключена.
Действие 2: Зажигание газовой горелки.
Выход: конфорка включена.
Вход: чайник, заполненный до половины объема холодной водой, находится
на полке. Конфорка включена.
Действие 3: Перемещение чайника с полки на конфорку.
Выход: чайник, заполненный до половины объема холодной водой,
находится на конфорке. Конфорка включена.
Вход: чайник, заполненный до половины объема холодной водой, находится
на конфорке. Конфорка включена.
Действие 4: Кипячение воды в чайнике.
Выход: чайник, заполненный до половины объема горячей водой, находится
на конфорке. Конфорка включена.
Вход: конфорка включена.
Действие 5: Выключение конфорки.
Выход: конфорка выключена.
Главный выход: чайник, заполненный кипятком до половины объема,
находится на газовой плите. Конфорка выключена.
Не любая последовательность операций или действий считается алгоритмом.
Алгоритм должен обладать массовостью, дискретностью, определенностью и
результативностью.
Массовость – применимость алгоритма ко всем задачам рассматриваемого
типа при любых исходных данных.
Дискретность – свойство алгоритма, означающее, что процесс
преобразования исходных данных в результат должен делиться на отдельные
законченные шаги. Каждый такой шаг должен использовать данные, полученные
на предыдущем шаге, и выдавать промежуточные результаты, которые будут
использоваться последующими шагами.
Определенность – свойство алгоритма, состоящее в том, что каждое
входящее в него действие должно быть строго определено и не допускать
различных толкований. Так же строго должен быть определен и порядок
(последовательность) выполнения отдельных действий.
Результативность – алгоритм всегда должен завершаться за конечное
число шагов, приводя к определенному результату.
Создание алгоритмов даже для сравнительно простых задач достаточно
сложное и трудоемкое дело. Поэтому для упрощения этого процесса используется
метод пошагового уточнения. Суть этого метода заключается в том, что
разработку алгоритма ведут от общего, поначалу неясного наброска к постепенно
детализируемой, прорабатываемой и уточняемой в отдельных элементах картине.
В общем случае этот метод включает следующие шаги:
1.KПостановка задачи.
2.KРазработка тестовых примеров.
3.KРазработка структура данных.
4.KСоставление алгоритма.
5.KТестирование алгоритма.
6.KКодирование алгоритма.
Рассмотрим каждый шаг в отдельности.
Постановка задачи. На этом этапе определяется что должен делать
алгоритм (или программа). Для этого удобно представить программу в виде
«черного ящика» (см. рис. 1). Модель «черного ящика» позволяет
сконцентрировать внимание на внешней спецификации программы, не
затрагивая ее реализацию.
Действие
входная
информация
выходная
информация
Рис. 1. Модель «черного ящика»
Чаще всего входной информацией для программ являются данные,
вводимые пользователем (например, числа, строки и даты), действия
пользователя (нажатие управляющих клавиш, перемещение курсора мыши и т.д.)
и файлы. Также входная информация может отсутствовать (например,
screenserver). В качестве выходной информации для программ могут выступать
данные, выводимые на экран, и файлы. Чаще всего главной функцией
программы является преобразование входной информации в выходную.
Пример.
Написать программу для расчета корней квадратного уравнения.
Постановка задачи:
Выходные данные: Корни квадратного уравнения (вещественные числа).
Варианты сообщений: «Корни квадратного уравнения x1= 34.7 и x2= 12»,
«Корень квадратного уравнения x= 13.6», «Нет корней квадратного уравнения».
Входные данные: Коэффициенты квадратного уравнения
a
,
b
и
c
.
Варианты сообщений: «Введите коэффициент a = », «Введите коэффициент b = »,
«Введите коэффициент c = »
Главная функция: Расчет корней квадратного уравнения
0
2
cxbxa
.
При постановке задачи следует добиваться полноты, непротиворечивости
и однозначности ее описания. Если не соблюдать эти требования, то созданная
программа может оказаться бесполезной для пользователя, т.к. не будет решать
весь класс задач или получаемые результаты не будут удовлетворять
пользователя.
Замечание 1. В постановке задачи сначала указывается выходная
информация, а затем только входная. Это объясняется тем, что нам важен
результат, а входные данные задают лишь ограничения на способ получения этого
результата. Кроме того один и тот же результат можно получить несколькими
способами, используя разные исходные данные.
Замечание 2.KПостановка задачи на первом шаге может быть определена
частично и уточнена на последующих шагах разработки программы. Это связано
с тем, что для уточнения внешней спецификации программы необходимо
рассмотреть различные варианты решения задачи.
KРазработка тестовых примеров. Основной задачей данного шага является
порождение идеи алгоритма, т.е. выделение основных шагов алгоритма без их
конечной детализации. При этом составляется два набора тестовых примеров:
набор тестов входных и выходных данных и набор обобщающих тестов.
Набор тестов входных и выходных данных. Этот набор тестов должен
выявить состав входной и выходной информации. В набор должны входить
тестовые примеры, разнородные по составу входной и выходной информации.
Включение «похожих» тестов не имеет смысла. Тесты создаются как для
правильных так и неправильных данных.
Пример.
Набор тестовых примеров входных и выходных данных:
1) a = 1, b= -11, c= 30 x1= 6, x2= 5
2) a = 1, b= -4, c= 4 x1= 2
3) a = 1, b= -2, c= 5 решений нет
Набор обобщающих тестов. Это набор тестовых данных, охватывающих
все возможные случаи вычислений. Здесь должны быть рассмотрены варианты
решения задачи в зависимости от различных исходных данных. При это должны
быть определены основные операции и промежуточные данные, получаемые при
вычислении. Кроме того при разработке тестовых примеров должна быть
определена структура данных программы (см. следующий пункт).
Пример.
Набор тестовых примеров входных и выходных данных:
1) a = 1, b= -11, c= 30 D = 1, так как D > 0 x1= 6, x2= 5
2) a = 1, b= -4, c= 4 D = 0, так как D = 0 x1= 2
3) a = 1, b= -2, c= 5 D = -15, так как D < 0 решений нет
Результатом этого шага должно стать понимание решения поставленной
задачи при различных исходных данных.
Разработка структуры данных. Для хранения исходных, промежуточных и
возможно результирующих данных необходимо иметь переменные. Состав
переменных, их тип и возможные значения определяется из тестовых примеров.
Кроме того структура данных может уточняться и/или изменяться при
составлении алгоритма. При описании переменных полезно использовать
следующую таблицу:
Имя Тип Описание
D вещественное
число
Дискриминант
… … …
При задании переменных необходимо следовать следующим правилам:
1.KИмя переменной должно быть мнемоническим, т.е. нести смысл. Лучше
всего если имя соответствует предметной области, в которой решается задача.
Например: a, b, c, D, x1, x2, x – стандартные обозначения переменных при
решении квадратных уравнений; Price, Total – цена и общая сумма при расчете за
покупку.
2.KНе используйте одну переменную для хранения разной по смыслу
информации. Например, использование переменной Var для расчета
дискриминанта и корней квадратного уравнения.
3.KСтарайтесь указывать тип переменной безотносительно к языку
программирования. Так как у каждого языка программирования свои типы
данных, а алгоритм по возможности должен быть универсальным.
4.KЕсли вы не можете придумать описание переменной, то скорее всего либо
вы не до конца представляете как работает алгоритм, либо переменная не нужна
вообще. Описания типа «вспомогательная переменная» или «переменная цикла»
не допускаются.
Пример:
Имя Тип Описание
a, b, c вещественное Коэффициенты квадратного уравнения
число
0
2
cxbxa
D вещественное
число
Дискриминант
x1, x2 вещественное
число
Корни квадратного уравнения
Составление алгоритма.
После определения идеи алгоритма ведется детальная проработка алгоритма
с целью его представления на языке высокого уровня. Для этого используется
подход пошагового уточнения, когда большая задача разбивается на ряд более
мелких подзадач. В свою очередь каждая подзадача разбивается еще на ряд
подзадач и т.д.. Этот процесс продолжается до тех пор пока подзадачу можно
будет представить на языке программирования. Такой процесс называют
декомпозицией задачи (см. рис. 2).
Задача
Подзадача 1 Подзадача N........................................
Подзадача 1.1 Подзадача 1.2 Подзадача 1.M......... Подзадача N.1 Подзадача N.M..........
шаг
детализации
Рис. 2. Декомпозиция задачи
Использование такого подхода позволяет упростить разработку алгоритма.
Это объясняется тем, что на верхних шагах декомпозиции мы не рассматриваем
реализацию нижних шагов и это позволяет абстрагироваться от проблем
реализации их на языке программирования. На нижних уровнях декомпозиции
задачи становятся такими простыми, что их легко реализовать на языке
программирования.
Таким образом программа сначала представляется как одно большое
действие (вспомним модель «черного ящика»). Затем она разбивается на ряд
более мелких действий и т.д. Для упрощения разработки алгоритма, а также для
большей понятности алгоритма каждое действие разбивается на
последовательность операций, которая имеет четко заданную структуру. Таким
образом алгоритмическая структура задает последовательность выполнения
операций. В табл. 1 показаны признаки использования той или иной
алгоритмической структуры, порядок представления действия в виде
алгоритмической структуры.