программирование тусур. Программирование учебное пособие. Учебное пособие Томск Эль Контент
 Скачать 0.93 Mb.
|
|
Глава 3. Процедурное программирование Рекомендуемая литература к главе 3 [1] Немнюгин С. А. Turbo Pascal / С. А. Немнюгин. — СПб. : Питер, 2001. — 496 г. [2] Фаронов В. В. Турбо Паскаль 7.0: Практика программирования / В. В. Фа- ронов. — М. : Нолидж, 2000. — 416 с. [3] Вирт Н. Алгоритмы + структуры данных = программы / Н. Вирт. — М. : Мир, 1985. — 405 с. Глава 4 ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ Технология программирования — это совокупность методов и средств разработ- ки (написания) программ и порядок применения этих методов и средств. На ранних этапах развития программирования, когда программы писались в ви- де последовательностей машинных команд, какая-либо технология программиро- вания отсутствовала. Первые шаги в разработке технологии состояли в представ- лении программы в виде последовательности операторов. Написанию последова- тельности машинных команд предшествовало составление операторной схемы, от- ражающей последовательность операторов и переходы между ними. Операторный подход позволил разработать первые программы для автоматизации составления программ — так называемые составляющие программы. С увеличением размеров программ стали выделять их обособленные части и оформлять их как подпрограммы. Часть таких подпрограмм объединялась в биб- лиотеки, из которых подпрограммы можно было включать в рабочие программы и затем вызывать из рабочих программ. Это положило начало процедурному про- граммированию. Следующим шагом в углублении структурирования программ ста- ло так называемое структурное программирование, при котором программа в целом и отдельные подпрограммы рассматривались как последовательности канониче- ских структур: линейных участков, циклов и разветвлений. Чтобы лучше понять идеи структурного программирования, надо предвари- тельно познакомиться с оператором перехода, присутствующем в любом проце- дурном языке, в том числе и в Паскале. 4.1 Оператор перехода Для программ в императивных (процедурных) языках при их выполнении характерно, вообще говоря, строго последовательное выполнение содержащихся в них операторов. Какой оператор в зависимости от обстоятельств должен выпол- няться в качестве следующего, управляется через специальные условия. Переход 68 Глава 4. Технология программирования от одного оператора к другому в процессе выполнения программы называется те- чением программы или управлением потоком. В языке для управления течением программы используются, прежде всего, условные операторы и циклы. В машин- ном языке для управления потоком используется команда перехода. С помощью этой команды и реализуются условные операторы и циклы. Но в языке Паскаль существует и прямой аналог команды перехода — оператор перехода. Отдельные операторы можно пометить с помощью меток. Благодаря этому может быть использован специальный оператор goto <метка> (называемый пе- реходом), так что в результате выполнения этого оператора выполнение программы продолжается с оператора, помеченного меткой <метка>. Все метки, используемые в программе (блоке), должны быть описаны в специ- альном разделе label. Метка представляет собой идентификатор или целое число от 1 до 9999. Пример label m,1,metka,56; Оператор, помеченный меткой, имеет вид <метка> : <оператор>; Циклы можно реализовать, используя условный оператор и оператор перехода. Например, цикл while <условие> do <оператор>; эквивалентен операторам: 2: if not <условие> then goto 1; <оператор>; goto 2; 1; Теперь, все что вы прочитали об использовании оператора перехо- да, можно забыть и никогда не применять в своих программах. 4.2 Структурное программирование Идеи структурного программирования появились после осознания факта: «Программы пишутся для людей, на машине они только обрабатываются». Трансляция и выполнение программы трудностей практически не вызывает. Проверку правильности программы, модификацию (исправления и изменения) при- ходится выполнять человеку. 4.2 Структурное программирование 69 Суть структурного программирования: «Программирование, ори- ентированное на общение с людьми, а не с машиной». Это и означает, что запись программы должна быть максимально удобной для ее восприятия и понимания людьми (в том числе и людьми, не являющимися ее авторами). Теорема Бёма-Якопини В 1966 году итальянские математики Коррадо Бём и Джузеппе Якопини в сво- ей статье [4] сформулировали и доказали теорему, согласно которой любой алго- ритм может быть преобразован к структурированному виду, то есть такому виду, когда ход его выполнения определяется только при помощи трёх структур управле- ния: последовательной, ветвления (условный оператор if then else) и циклов с предусловием (while). Публикация теоремы была толчком к началу дебатов о структурном програм- мировании. Спустя 2 года вышла статья Эдсгера Дейкстры [5], в которой он кри- тиковал использование оператора goto и высказывался в пользу улучшения стиля программного кода за счёт использования структур управления и отказа от других инструкций, управляющих ходом алгоритма. Оператор перехода теоретически избыточен и практически вреден. Использо- вание операторов перехода поощряет создание малопонятных и трудно модифи- цируемых программ, которые вызывают большие сложности при отладке и со- провождении. Естественный способ чтения и прослеживания работы программы «сверху вниз и слева направо», поэтому — «Программируйте без goto!». При этом программа предоставляется в виде иерархической структуры блоков. Для лучшего понимания программы предлагаются следующие особенности написания: • на строке не более одного оператора; • делайте отступы — они выделяют блоки, поясняют структуру программы. Рекомендации для отступов: а) S1; S2; S3; б) If B then S1 else S2; в) while B do S; г) repeat S untill B; 70 Глава 4. Технология программирования д) for i:=1 to n do S; Структурное программирование дает возможность читать и проверять про- грамму как последовательный текст, что повышает производительность труда про- граммистов при разработке и отладке программ. С целью повышения структурно- сти программы необходима большая независимость подпрограмм, подпрограммы должны связываться с вызывающими их программами только путем передачи им аргументов, использование в подпрограммах переменных, принадлежащих другим процедурам или главной программе, не желательно. 4.3 Решение задачи Большинство процессов разработки программного обеспечения — это процессы решения некоторых задач. Удачные решения сложных проблем проектирования обычно находят те студенты, которые сознательно или подсознательно применяют общие правила решения задач (табл. 4.1). Таблица 4.1 – Стратегия программирования Понимание задачи Начальное понимание задачи. Что является входными данными (или аргументами)? Что является выходны- ми данными (или результатами)? Что является спецификацией задачи? Имя программы или функции. Является ли постановка задачи удовле- творительной? Достаточная, или из- лишняя, или противоречивая? Есть ли специальные условия на входные и вы- ходные значения? Какие использовать вычислительные структуры и, следовательно, какие ис- пользовать типы? Можно ли задачу разбить на части? Может быть, следует начертить блок- схему или использовать псевдокод? Составьте план решения При разработке программы Вы долж- ны думать о связях между входом и выходом. Если нет непосредствен- ной связи, то Вы могли бы подумать о вспомогательных задачах, которые помогли бы найти решение. Встречались ли Вы с этой задачей ранее? Хотя бы в слегка измененной форме? Знаете ли Вы какую-нибудь задачу, связанную с этой? Знаете ли Вы какие-нибудь программы или функ- ции, которые могли быть полезны? продолжение на следующей странице 4.3 Решение задачи 71 Таблица 4.1 — Продолжение Рассмотрите спецификацию задачи. Попытайтесь найти знакомую задачу с той же или похожей формулировкой. Вы обнаружили задачу, связанную с вашей и уже решенную. Можете ли Вы использовать это? Можете ли Вы использовать ее результаты? Можете ли Вы использовать ее методы? Не сле- дует ли Вам внести некоторые вспомо- гательные части в вашу программу? Вы должны придумать для себя план, как решить задачу. Если Вы не можете решить пред- ложенную задачу, то попытайтесь решить задачу, связанную с искомой задачей. Можете ли Вы представить подобную задачу, но более легкую для решения? А более общую задачу? А может, более специализированную? Или аналогичную? Можете ли Вы решить часть задачи? Можете ли Вы получить что-нибудь полезное из входных данных? Какая информация помогла бы Вам вычис- лить выходные данные? Как можно изменить вход и выход, так чтобы они были как возможно близки друг к другу? Использовали ли Вы все входные данные? Использовали ли Вы специ- альные условия на входные данные? Взяли ли Вы в расчет все, что используется в спецификации задачи? Выполнение плана Переведите проект вашей программы в код на конкретном языке программи- рования. При написании программы будьте уве- рены, что Вы следуете своему плану. Уверены ли Вы, что каждый шаг дела- ет именно то, что он должен? продолжение на следующей странице 72 Глава 4. Технология программирования Таблица 4.1 — Продолжение Подумайте, как Вы можете записать программу на конкретном языке. Сле- дует ли Вам воспользоваться разбо- ром случаев? Должны ли Вы написать программу в виде последовательных шагов? Или Вам необходимо восполь- зоваться итерацией или рекурсией? Вы должны писать программу по эта- пам. Думайте, на какие различные слу- чаи можно разбить задачу; в частно- сти, есть ли различные случаи для входных величин? Можете ли Вы по- лучать результаты отдельно по частям и как вместе собрать эти части, чтобы получить окончательный результат? Вы можете свести решение Вашей задачи первоначально к решению с «меньшими» входными данными и воспользоваться полученным реше- нием для решения исходной задачи — т. е. воспользоваться рекурсией. Вам необходимо учитывать програм- мы, которые Вы уже писали до это- го, и знать встроенные функции языка или библиотеки. Ваш проект может потребовать у Вас решить более общую задачу или бо- лее специальную. Напишите решения для этих случаев. Они могут послу- жить путеводной нитью к нужному ре- шению или могут быть использованы в решении. Посмотрите на программы, которые Вы писали прежде. Можно ли их использовать? Или модифицировать? Могут ли они помочь Вам построить искомое решение? Взгляд назад — анализ решения Проверьте Ваше решение: как его можно улучшить? Можете ли Вы проверить работу про- граммы для какого-то множества аргу- ментов? Подумайте, как Вы написали бы эту программу, если бы начали решать за- дачу снова? Подумайте, как Вы можете использо- вать эту программу или этот метод для построения другой программы? 4.4 Разработка программы Не существует формального аппарата для получения нужного алгоритма, сле- довательно, разработка алгоритма (а значит, и программы) ведется методом «проб и ошибок». После создания (и во время создания) алгоритма необходима проверка алгоритма на правильность и анализ эффективности. Мы должны различать: 4.4 Разработка программы 73 • умение пользоваться алгоритмическим языком, т. е. кодирование (техниче- ский аспект); • умение программировать (проектировать программу). Типичное распределение стоимости затрат при создании про- граммного продукта: Программирование (кодирование) — 8% Проектирование — 17% Тестирование — 25% Сопровождение — 50% Этапы разработки: а) создание алгоритма, б) проектирование программы, в) кодирование, г) тестирование. С любого этапа возможен возврат к любому более раннему этапу. 4.4.1 Метод пошаговой детализации Также называется методом разработки «сверху-вниз», или методом «нисходяще- го проектирования». Этот метод считается наиболее эффективным при разработке программ. Он состоит из следующих этапов. А. В решаемой задаче выделяется небольшое число (3–5) подзадач (более про- стые самостоятельные задачи). В проектируемой программе намечается соответ- ствующее число блоков (подпрограмм) для решения подзадач. Для блоков определяются: • назначение; • порядок выполнения; • связь блоков по обрабатываемым данным. Важно определение функционального назначения блока (что вход и что выход, что он делает), как делает — не уточняется. Б. Общая схема программы составлена — проверяем правильность. В. Если отдельные подзадачи достаточно сложные, повторяем процедуру дета- лизации; выделяем новые подзадачи в данной подзадаче. Г. Кодируем. Наиболее типичные крупные блоки: 1. Задание исходных данных. Контроль правильности исходных данных. 2. Решение поставленной задачи. 3. Выдача результатов. 74 Глава 4. Технология программирования Особенности пошаговой детализации. На каждом шаге детализации (уточнения) принимается небольшое число решений. • Детализация блока проходит локально, независимо от ос- тальной программы. Проверка правильности блока может проходить независимо от правильности всей программы. • Проектирование программы не связано с тем языком, на котором ведется кодирование. • Блоки должны быть достаточно независимы друг от друга. Критерии проектирования (выбора) блоков: 1) сложность взаимодействия блока с другими блоками долж- на быть меньше сложности его внутренней структуры; 2) хороший блок снаружи проще, чем внутри; 3) хороший блок проще использовать, чем построить. При нисходящем проектировании сначала отлаживается главная программа, в которой вместо еще не написанных подпрограмм стоят «заглушки» («муляж» подпрограммы — вместо работы печатает только сообщение о своей работе). По мере детализации «заглушки» заменяются написанными подпрограммами, тем са- мым проверяется работа подпрограмм. Восходящее проектирование («снизу-вверх») — это когда сначала создаются подпрограммы, а только потом — сама программа. Практически при нисходящем проектировании может использоваться частично восходящее проектирование. 4.4.2 Способы фиксирования результатов проектирования Диаграммы управления потоком Графическое представление управления потоком выполняемых команд может быть дано с помощью так называемых диаграмм управления потоком (блок-схем). С математической точки зрения блок-схема есть ориентированный граф с различ- ными типами узлов, которые помечены определенными выражениями или опера- торами. Блок-схема для императивной программы может быть систематически выведе- на из программы. Условный оператор if C then S1 else S2 выражается с помощью следу- ющей блок-схемы (рис. 4.1): 4.4 Разработка программы 75 Рис. 4.1 – Блок-схема для условного оператора Операторы присваивания (и вызовы подпрограмм) записываются в прямоуголь- никах. Булевские выражения, управляющие потоком, записываются в ромбах. Последовательной композиции S1;S2 соответствует соединение блок-схем для S1 и S2 с помощью стрелки от S1 до S2 (рис. 4.2). Рис. 4.2 – Последовательное выполнение Оператору цикла while B do S соответствует блок-схема на рис. 4.3. Рис. 4.3 – Блок-схема для цикла while Блок-схемы особенно часто применялись в ранние годы программирования, так как с их помощью надеялись получить наглядное представление о структуре программы, точнее, о структуре потока программы. Однако и сейчас блок-схемы достаточно широко используются в очень прагматических областях программирования. Решающим для сегодняшнего, лишь спорадического, использования блок-схем является их фундаментальный недостаток: они содержат слишком мало структур и, в особенности, никаких графических изображений потоков данных. При более 76 Глава 4. Технология программирования сложных программах выясняется, что преимущества наглядного представления управления потоком тотчас теряются. Сначала описание алгоритма можно представлять, используя диаграмму управ- ления потоком, в укрупненном блочном виде. Блок обычно не элементарен, не сводится к одному оператору (его размеры неограниченны и выбираются произ- вольно). Другие блоки связаны с данным блоком только через точки входа и выхода. Поэтому если блок правильно решает задачу, т. е. всегда дает нужный результат, то его внутренняя структура несущественна для остальной части алгоритма. От- сутствие детального описания внутренней структуры блока не мешает пониманию того, как работает алгоритм в целом; важно лишь, чтобы было четко определено, какие блоки запускают данный блок в работу, где лежит его исходная информация, где будет записан результат и куда переходить после окончания его работы. Потом работа крупных блоков уточняется и заменяется соответствующими блок-схемами. После того, как получена достаточно подробная блок-схема программы, пи- шется код программы. Недостатки блок-схем при проектировании: • трудоемкость вычерчивания и перечерчивания при модификациях; • потеря наглядности при детализации. Специальный язык — псевдокод Правила обработки данных и условия не формализуются — запись на естествен- ном языке. В качестве языка проектирования можно использовать сам Паскаль, за- давая содержание еще не детализированных блоков в виде комментариев Паскаля. При детализации блоков комментарии следует оставлять. При хороших комментариях структур данных, алгоритма и слож- ных мест в структурированной программе нет необходимости в ни- какой другой документации! Пример Пример описания на псевдокоде алгоритма, распознающего, можно ли полу- чить последовательность знаков a из последовательности знаков b посредством вычеркивания некоторых знаков. if { a — пустая последовательность знаков} then {ответ= "да"} else if { b — пустая последовательность} then {ответ= "нет"} else begin {сравнить первый знак последовательности a с первым знаком последовательности b} if {знаки совпадают} 4.4 Разработка программы 77 then {надо снова применить тот же алгоритм к остатку последовательности a и остатку последовательности b} else {нужно снова применить тот же алгоритм к исходной последовательности a и остатку последовательности b} end; 4.4.3 Пример разработки Гипотеза Гольдбаха (1742 г., Гольдбах — академик С.-Петербургской академии наук): Любое четное число > 2 представимо в виде суммы двух простых чисел. Задача. Дано натуральное m. Проверить гипотезу Гольдбаха для всех четных чисел, меньших m. При проектировании программ будем использовать метод пошаговой детали- зации. В каждой версии программы внесенные изменения по сравнению с преды- дущей версией выделяются курсивом. • Вариант 1. var i,m: integer; begin writeln( 'Введите натуральное m'); readln(m); i:=2; while i i:=i+2 end; end. • Вариант 2. Вводим функцию gold в виде «заглушки» (пока она еще абсо- лютно ничего не делает). var i,m: integer; function gold(n:integer):boolean; {n удовлетворяет гипотезе Гольдбаха <=> значение функции — истина} begin end; begin writeln( 'Введите натуральное m'); readln(m); i:=2; while i |