Создание программы
В отличие от математики, где знание формул и теорем практически обеспечивает решение задач, в программировании нет такого аппарата, но зато существует ряд технологических приемов, направляющих ход Ваших мыслей при разработке и создании программы. Эти «рецепты» формировались долгие десятилетия сообществом программистов и пренебрегать ими все равно, что отправляться в бескрайние джунгли без проводника и карты.
Как писал Никлаус Вирт в своей статье «Разработка программы пошаговым усовершенствованием», опубликованной в журнале Communication of The ACM в 1971 г.: «Программирование обычно преподается на примерах. Опыт показывает, что успех курса программирования крайне зависит от выбора этих примеров. К сожалению, они слишком часто выбираются главным образом для того, чтобы продемонстрировать возможности самого языка. Вместо этого, основным критерием выбора должна быть их пригодность показать некоторые широко применяемые методы программирования. Кроме того, примеры программ обычно представляются как законченные «изделия», сопровождаемые объяснениями их цели и их лингвистических подробностей. Но активное программирование состоит из создания новых программ, а не из рассмотрения старых. Вследствие этих методов обучения, студент получает впечатление, что программирование заключается главным образом в овладении языком (со всеми особенностями и сложностями, настолько изобилующими в современных языках программирования) и надежды на интуицию, чтобы тем или иным способом преобразовать свои идеи в законченные программы. Очевидно, что курсы программирования должны преподавать методы дизайна и конструирования программ, а выбранные примеры должны быть такими, чтобы достаточно хорошо демонстрировать постепенное развитие».
Прежде, чем браться за создание программы Вы должны решить задачу в ее предметной области, т.е. представить ее в виде математических формул. Затем необходимо спроектировать структуры данных, которые необходимо обработать. И только после этого можно приниматься за создание алгоритма программы. Алгоритм – это точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи за конечное число шагов. Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность действий преобразования исходных данных в результатные.
Любой алгоритм, оформленный в виде программы для компьютера, состоит из двух важных разделов (частей): описания данных, с которыми оперирует программа, и описания действий, которые необходимо выполнить с этими данными. Причем, сначала, программист решает, какие действия он собирается совершить, а затем, проектирует структуры данных для решения решаемой задачи – а не наоборот!
При этом используется структурный подход, который начинается с нисходящей разработки (проектирования) программы методом пошаговой детализации с помощью псевдокода.
Нисходящее проектирование включает разбиение большой задачи на меньшие подзадачи, которые могут рассматриваться порознь и, в свою очередь, разбиваться на меньшие подзадачи до выяснения всех особенностей решаемой основной задачи.
Первым, кто ввел в практику принцип пошагового уточнения или детализации (step-wise refinement) как ключевого для систематического создания программ, был Никлаус Вирт, опубликовавший подробную статью с примером использования этого принципа в журнале Communications of ACM в 1971 г.
Основную идею нисходящего проектирования методом пошаговой детализации рассмотрим на примере какой-либо (произвольной) программы, с условным названием GLOP. Вначале попробуем представить, что у нас есть компьютер, который может сразу выполнить эту программу. Тогда мы можем просто написать команду
GLOP
и все готово! К сожалению, пока не имеется таких машин, которые по Вашему желанию выполняли бы любые действия. Поэтому нам придется разбивать задачу, а следовательно, и программу на более мелкие элементы. Как правило, выполнение программы подразумевает ввод необходимых данных, их обработку и вывод полученных результатов. Тогда мы можем переписать нашу программу GLOP в следующем виде (рис. 1):
При этом каждую строку нашей программы мы можем снова разбивать на более простые операции, до тех пор, пока Вы не сможете представить их в операторах имеющегося в Вашем распоряжении языка программирования (в нашем случае – пока – это Турбо Паскаль).
Промежуточной стадией между человеческим языком и исходным кодом программ и наиболее естественным средством для пошаговой детализации является псевдокод – компактный (зачастую неформальный) язык описания алгоритмов, использующий ключевые слова императивных языков программирования, но опускающий несущественные подробности и специфический синтаксис. Такими несущественными деталями могут быть описания переменных, системно-зависимый код и подпрограммы, требующие дальнейшей пошаговой детализации. Главная цель использования псевдокода – обеспечить программиста инструментом для формирования этапов разработки программы, в форме независимой от языка программирования, чтобы затем реализовать свои намерения на любом конкретном языке программирования. Псевдокод широко используется в учебниках и научно-технических публикациях, а также на начальных стадиях разработки компьютерных программ.
В отличие от стандартизации синтаксиса языков программирования, на синтаксис псевдокода обычно не устанавливается стандартов, так как последний непосредственно не компилируется в исполняемую программу, а только в операторы требуемого языка программирования и то – в голове самого программиста. Поэтому можно сказать, что обычно автор каждой публикации применяет свой оригинальный псевдокод. Однако чтобы быть максимально понятным читателям, авторы публикаций содержащих псевдокод, как правило, заимствуют нужные им конструкции из какого-либо языка программирования. Зачастую источником псевдокода служат несколько языков, и таким образом псевдокод часто не содержит специфических признаков конкретного языка программирования. Кроме того, математические выражения часто включаются в псевдокод в том виде, как их принято записывать в математике, а не в языках программирования, а некоторые фрагменты псевдокода могут быть фразами естественного языка (русского, английского и т. д.). Однако при этом для псевдокода используются конструкции некоторых языков программирования. Так, например, очень часто используется синтаксис, похожий на синтаксис языка Паскаль. Это объясняется тем, что Паскаль создавался как язык, ориентированный на задачи обучения программированию, и поэтому синтаксис этого языка особенно приспособлен для восприятия человеком. Но следует понимать, что псевдокод находится посередине между программистом и языками программирования. В идеале псевдокод должен в голове программиста компилироваться на любой язык программирования. Но главным здесь является удобство описания программистом своих намерений по реализации алгоритма! Особенно это важно для начинающих программистов, поскольку опытные программисты этапы «создания алгоритма решения задачи – псевдокода – текста программы» производят «в одно касание».
Таким образом, можно заключить, что псевдокод – это искусственный и неформальный язык, который помогает программисту выражать свои мысли при формулировании алгоритма программы для дальнейшего превращения в код на соответствующем языке программирования. Программы на псевдокоде не могут выполняться на компьютере. Их назначение – помочь программисту «обдумать программу». Тщательно подготовленная программа на псевдокоде может затем легко быть преобразована в программу на любом языке программирования.
Но уже на этапе написания псевдокода Вы должны уже мыслить категориями структурного программирования. То есть, с помощью псевдокода Вы описываете логическую структуру программы с помощью базовых структур: следование, развилка, цикл. Логической структурой программы называется форма ее представления в виде взаимосвязанных логических блоков (в структурном программировании – следование, развилка, цикл).
Прелесть псевдокода состоит в том, что, в совершенстве освоив его применение, Вы создаете псевдокод будущей программы «в уме», а затем используете свой мозг как препроцессор для «компиляции» в коды на необходимом языке программирования, а уже компилятор языка программирования превращает ее в машинные коды.
В классической работе Бома и Джакопини (опубликована в журнале Communications of ACM в мае 1966 г.) было показано, что для программы, в которой всякий модуль (независимая составная часть программы) проектировался с единственным входом и единственным выходом, а программа является множеством вложенных модулей, каждый из которых также имеет один вход и один выход, может быть реализована в языке программирования, включающем только одну неуправляющую и две основные управляющие конструкции. Фактическая реализация этих конструкций может быть различной в различных языках программирования. Принцип, изложенный в статье Бома и Джакопини, называемый «структурной теоремой» имеет фундаментальное значение и составляет основу реализации алгоритмов при проектировании Ваших структурных программ.
По Бому и Джакопини для построения логической структуры программы требуется три основных составляющих блока (рис. 1.2):
функциональный блок или линейная последовательность операторов (СЛЕДОВАНИЕ);
условный оператор (конструкция принятия двоичного или дихотомичного решения – РАЗВИЛКА);
конструкция обобщённого цикла (ЦИКЛ с параметром, с предусловием, с постусловием и т.д.).
Тогда для всякой программы, составленной из указанных конструкций, всегда может быть получено ещё и доказательство её правильности!
Первым инициатором структурного программирования был профессор Э. Дейкстра (Эйндховен), изложивший свои идеи в письме редактору Communication of ACM в марте 1968 г. В пользу этого подхода говорит такой факт: в 1969 г. на конференции по методам разработки программного обеспечения, организованных НАТО, Джон Арон из фирмы IBM впервые доложил об эксперименте, известном под названием «проект суперпрограммиста». В этом эксперименте одному программисту, доктору Харлану Миллсу, было предложено выполнить за шесть месяцев работу, представляющую, как оказалось, проект на 30 человеко-лет. Успех этого эксперимента побудил фирму IBM испробовать те же идеи в более крупной разработке – проекте информационно-поисковой системы для газеты Нью-Йорк Таймс. Так же как и предыдущем случае, основные усилия в этом проекте были посвящены поиску новых эффективных методов организации и управления разработкой, а также нисходящему проектированию и структурному программированию. Этот проект был весьма интересен тем, что он отличался сравнительно большим масштабом (около 83 000 операторов исходной программы), практическим характером (реальный заказчик платил реальные деньги за работающую систему) и успешной реализацией (производительность программистов оказалась примерно в пять раз выше производительности среднего программиста).
После этого был издан приказ, по которому все новые программы, создаваемые с участием 4 400 сотрудников Центра федеральных систем фирмы IBM, должны разрабатываться с применением методов структурного программирования. Для этого нужно было переучить примерно 2 600 программистов и их руководителей. Это потребовало 5 200 человеко-недель или 100 человеко-лет напряженных усилий. Все, кто сопротивлялся нововведению, были уволены…
ЛАБОРАТОРНАЯ РАБОТА № 1
Освоение технологии структурного программирования
при разработке и создании программы на языке Турбо Паскаль
для линейного вычислительного процесса
Цели работы:
1. Освоение нисходящей разработки (проектирования) программы методом пошаговой детализации с помощью псевдокода.
2. Освоение методов структурного программирования.
3. Овладение выразительными средствами графики языка ТП для повышения читаемости программы.
4. Овладение навыками введения в программу необходимого количества комментариев.
5. Освоение средств исследования программы.
6. Освоение методики тестирования программы.
Теоретические сведения
Линейным называется такой вычислительный процесс, при котором все этапы решения задачи выполняются в естественном порядке следования записи этих этапов.
Для линейных вычислительных процессов в структурном программировании логическая структура программы представляется набором базовых структур следование. Это самая важная из структур: она означает, что действия должны выполняться строго друг за другом (рис. 1.3).
Здесь каждый прямоугольник изображает либо порядок действий на первоначальном этапе пошаговой детализации, например, Ввести данные GLOP, Выполнить вычисления GLOP, Вывести результаты GLOP (рис.1.1), либо один оператор конкретного языка программирования, например, WriteLn, ReadLn и т.д. В дальнейшем Вы увидите, что структура следование, в свою очередь, может состоять из других базовых структур.
Самым основным, фундаментальным оператором языка ТП, который входит в структуру следование, является оператор присваивания. Он указывает, что вновь вычисленное значение необходимо присвоить некоей переменной. Оператор имеет такой вид:
<переменная> := <выражение>
Знак := называется знаком операции или просто операцией присваивания. Оператор «a := 5» произносится так: «текущее значение a заменяется значением 5», или «переменной a присвоить значение 5».
Теперь рассмотрим последовательно все этапы создания программы на конкретном примере.