Структурное программирование: основные принципы. Принципы структурного программирования Что является характерными чертами структурного программирования
Структурное программирование – это проектирование, написание и тестирование программы в соответствии с жестким соблюдением определенных правил.
Основная цель структурного программирования – повышение производительности программистов. Другими целями являются:
– избавиться от плохой структуры программы;
– создавать программы и документацию к ним, которые можно было бы понимать, сопровождать и модифицировать без участия авторов (стоимость сопровождения и модификации, как правило, в 3-5 раз больше стоимости разработки).
Структурное программирование (или метод пошаговой детализации) включает:
1. Метод нисходящего проектирования. Его еще называют методом «сверху вниз» или «от общего к частному». Он предполагает разбиение задачи на несколько более простых частей или подзадач. Их выделяют таким образом, чтобы проектирование подзадач было независимым. При этом составляют план решения всей задачи, пунктами которого и являются выделенные части. План записывают графически в виде функциональной схемы (схемы иерархии, подчинения), где определяют головную и подчиненные подзадачи и связи между ними, т.е. интерфейс. Здесь же устанавливается, какие начальные данные (или значения) получает каждая подзадача для правильного функционирования и какие результаты она выдает. Затем производят детализацию каждой подзадачи. Число шагов детализации может быть произвольным. Детализацию продолжают до тех пор, пока не станет ясно, как программировать данный фрагмент алгоритма.
2. Структурное программирование. Реализация идеи структурного программирования основывается на том факте, что правильная программа любой сложности может быть представлена логической структурой, представляющей собой композицию трех базовых (логических или управляющих) структур, определяющих правила обработки данных: следования (линейная), разветвления (условного перехода) и повторения (цикла).
3. Сквозной структурный контроль. Он представляет собой регулярные проверки и согласования результатов работы исполнителей - программистов различных структур. Его необходимость определяется желанием разработчиков снизить стоимость разрабатываемых программ. Обязательным условием этого является раннее обнаружение и исправление возникающих ошибок и не состыковок.
Таким образом, метод составления алгоритма и программы именуемый «сверху вниз» или «от общего к частному» состоит в сведении сформулированной задачи к последовательности более простых подзадач, легче поддающихся обработке в отдельности, чем целиком исходная программа. Последовательное выделение из исходной задачи все более простых подзадач обеспечивает представление алгоритма решения исходной задачи как композиции алгоритмов выделенных подзадач.
Вместе взятые (выделенные) алгоритмы подзадач образуют систему, управление которой должен взять на себя алгоритм-диспетчер. Его называют главным (или головным), а все остальные подчиненными. Схему, отображающую уровень и взаимосвязь, взаимодействие алгоритмов, как головного, так и подчиненных, называют функциональной схемой – это схема иерархии алгоритмов.
Подчиненный алгоритм должен иметь один вход и один выход. Для него необходимо задать цель и определить множество допустимых входных значений (формальных параметров-значений), возможные собственные (локальные, внутренние) объекты и возможные побочные (волновые) эффекты (выход параметров за область допустимых значений, изменение значений параметров, в частности, получение результатов и/или вывод данных). Таким образом, подчиненный алгоритм – это элемент функциональной схемы алгоритма, реализующий одну самостоятельную подзадачу.
Часть алгоритма, организованная как простое действие, т.е. имеющая один вход и один выход, называется функциональным блоком.
Один вход означает, что выполнение данной части всегда начинается с одного и того же действия. Один выход означает, что после завершения данной части алгоритма всегда начинает выполняться одно и то же действие.
Функциональный блок алгоритма относится к простому типу блоков.
Поскольку алгоритм определяет порядок обработки данных, он должен содержать, с одной стороны, действия по обработке, а с другой стороны, порядок их следования, называемый потоком управления. Поток управления может обладать следующими свойствами:
1) выполняется каждый блок;
2) каждый блок выполняется не более одного раза.
При структурной организации алгоритма можно выделить три типа потоков управления.
Поток управления, в котором выполняются оба указанных свойства, называется линейным.
 |
Очевидно, что несколько блоков, связанных линейным потоком, могут быть объединены в один функциональный блок.
2. Ветвящийся поток управления. В этом типе выполняется свойство (2), а свойство (1) не выполняется.
Данный тип потока управления организует выполнение одного из двух функциональных блоков в зависимости от проверяемого логического условия.
3. Циклический поток управления. Он организует многократное повторение функционального блока, пока логическое условие его выполнения остается истинным.
В данном типе потока управления выполняется свойство (1), но не выполняется свойство (2).
 |
Если алгоритм представляет собой комбинацию трех рассмотренных типов потоков управления (базовых алгоритмических структур), то его называют структурным алгоритмом.
Структурные алгоритмы обладают рядом преимуществ по сравнению с неструктурными алгоритмами:
1. понятность и простота восприятия алгоритма;
2. проверяемость (для проверки любой из основных структур достаточно убедиться в правильности входящих в нее функциональных блоков);
3. модифицируемость.
Структурная теорема : любой алгоритм может быть сведен к структурному алгоритму.
Значение структурной теоремы для практики программирования состоит в том, что на ее основе разработан и широко используется структурный метод программирования. Основой метода является использование принципа модульности построения сложных программ. При этом каждый программный модуль организуется в виде стандартного функционального блока (строится из трех базовых структур) и выполняет лишь одну функцию по обработке данных. Модули обладают определенной автономностью, что позволяет их отладку (поиск и устранение ошибок) вести независимо от остальной программы и обеспечивает относительно простую модифицируемость как отдельного модуля, так и программы в целом. Эффективность структурного программирования особенно заметна при разработке сложных программ – модульный принцип позволяет разбить общую задачу на составные и относительно автономные части, каждая из которых может создаваться и отлаживаться независимо. Безусловно, такое разбиение требует согласования входных и выходных параметров модулей.
Исходя из структурного подхода к разработке алгоритма, типовыми этапами этого процесса являются:
1. Описание общего замысла алгоритма;
2. Формализация задачи;
3. Разработка обобщенной схемы алгоритма;
4. Разработка отдельных блоков алгоритма;
5. Стыковка блоков;
6. Определение возможности использования стандартных блоков;
7. Разработка блоков логического контроля;
8. Оптимизация схемы алгоритма;
9. Уточнение параметров;
10. Оценка машинного ресурса.
Структурное программирование - это определенные общие принципы и правила проектирования, разработки и оформления программ с целью облегчения процессов их создания и тестирования, повышения производительности труда программистов и улучшения читабельности результирующей программы. Структура программы и алгоритм решения задачи должны быть легкими для понимания, простыми для доказательства правильности и удобными для модификации. По своей сути структурный подход есть отказ от беспорядочного стиля в алгоритмизации и программировании (в частности, отказ от оператора goto) и определение ограниченного числа стандартных приемов построения легко читаемых алгоритмов и программ с ясно выраженной структурой, что особенно важно при разработке больших программных систем.
Опыт применения методов структурного программирования при разработке, например, ряда сложных операционных систем показывает, что правильность логической структуры системы в этом случае легко поддается доказательству, а сама система допускает достаточно полное тестирование. Уменьшение трудностей отладки и тестирования программ приводит к увеличению производительности труда программистов, поскольку на тестирование программы тратится от трети до половины времени ее разработки. Производительность труда программиста обычно измеряется числом отлаженных операторов, которые он может написать за день. Приближенные оценки показывают, что применение методов структурного программирования позволяет увеличить это число в 5-6 раз. Также нужно сказать, что структурное программирование предполагает определенную организацию самого процесса программирования и определенную технологию проектирования программ, что также положительно влияет на производительность труда программистов.
Основы структурного программирования. Теоретическим фундаментом структурного программирования является теорема о структурировании , из которой следует, что алгоритм (программа) решения любой практически вычислимой задачи может быть представлен с использованием трех элементарных базисных управляющих структур: структуры следования (последовательности); структуры ветвления, структуры цикла, изображенных на рис. 6.5-6.7 соответственно, где Р - условие, S - оператор.
Структура следования представляет собой естественный ход выполнения алгоритма - любую последовательность операторов, выполняющихся друг за другом (см. рис. 6.5). В языке программирования это соответствует последовательности операторов ввода, вывода и операторов присваивания.
Представляет фактор принятия решения, включает проверку некоторого логического условия Р и, в зависимости от результатов этой проверки, выполнение оператора S1 либо оператора S2. В языках программирования (например, Pascal) реализуется оператором if Р then SI else S2 (см. рис. 6.6).
Структура цикла (цикла с предусловием) представляет фактор повторяемости вычислений, обеспечивает многократное повторение выполнения оператора S, пока выполняется (истинно) логическое
Рис. 6.5. Структура следования
Рис. 6.6.
условие Р. В языках программирования (например, Pascal) реализуется оператором while Р do S (см. рис. 6.7).
Базисный набор управляющих структур является функционально полным, т.е. с его помощью можно создать любой сколь угодно сложный алгоритм, однако с целью создания более компактных и наглядных алгоритмов и программ используются дополнительные управляющие структуры: структура сокращенного ветвления; структура варианта или многоальтернативного выбора; структура цикла с параметром; структура цикла с постусловием. В разных языках программирования реализация базовых управляющих структур может быть различной, например в языке Pascal реализованы все предлагаемые структуры.
Любая программа может быть построена посредством композиции базисных структур: либо путем их последовательного соединения - образования последовательных конструкций, либо путем их вложения друг в друга - образования вложенных конструкций.
Каждая из структур может рассматриваться как один функциональный блок с одним входом и одним выходом. Блоки S, SI, S2, входящие в состав базисных управляющих структур, сами могут быть одной из них, поэтому возможны вложенные конструкции. Однако, какова бы ни была степень и глубина «вложенности», важно, что любая конструкция в конечном итоге имеет один вход и один выход. Следовательно, любую сложную структуру можно рассматривать как «черный ящик» с одним входом и одним выходом. Таким образом, можно ввести преобразование любой структуры в функциональный блок. Тогда всякий алгоритм, составленный из стандартных структур, поддается последовательному преобразованию к единственному функциональному блоку, и эта последовательность преобразований может быть использована как средство понимания алгоритма и доказательства его правильности. Обратная последовательность преобразований может быть использована в процессе проектирования алгоритма с постепенным раскрытием единственного функционального блока в сложную структуру основных элементов.
Для структурирования и понимания больших по объему программ используются также дополнительные структурные средства, которые поддерживают модульный принцип разработки ПС: это подпрограммы и модули. Использование аппарата подпрограмм (процедур и функций) - это возможность выделять в самостоятельные программные единицы со своими входными и выходными данными отдельные (часто повторяющиеся) участки кода для последующего многократного вызова их из различных точек программы и других подпрограмм. Модуль представляет собой автономно компилируемую библиотеку описаний типов, данных, процедур и функций, что позволяет группировать описания данных и подпрограмм по их функциям и назначению согласно одному из основных принципов структурного программирования - разбиения больших задач на подзадачи.
Методика разработки программ. Распространены две методики (стратегии) разработки программ, относящиеся к структурному программированию: программирование «сверху вниз»; программирование «снизу вверх».
Программирование «сверху вниз», или нисходящее проектирование программ , - это методика разработки программ, при которой разработка начинается с определения целей решения проблемы, после чего идет последовательная детализация, заканчивающаяся детальной программой. Сначала выделяется несколько самых глобальных задач, решение которых может быть представлено в общей структуре функционально независимыми блоками. Разработку логической структуры каждого такого блока и ее модификацию можно осуществлять независимо от остальных блоков. На этом первом этапе проекта раскрываются наиболее важные и существенные связи, определяется функциональное назначение каждого блока, его входные и выходные данные. На последующих этапах проектирования уточняется (детализируется) логическая структура отдельных функциональных блоков общей схемы, что также может осуществляться в несколько этапов детализации вплоть до простейших инструкций. На каждом этапе проекта выполняются многократные проверки и исправления.
Подобный подход является достаточно рациональным, позволяет значительно ускорить процесс разработки сложных программных проектов и в значительной мере избежать ошибочных решений. Кроме того, появляется возможность некоторые подпрограммы (модули) не реализовывать сразу, а временно отложить их разработку, пока не будут закончены другие части. Например, если имеется необходимость вычисления сложной математической функции, то выделяется отдельная подпрограмма такого вычисления, реализуется временно одним оператором, который просто присваивает нужное значение. Когда все приложение будет написано и отлажено, можно приступить к реализации этой сложной функции.
Программирование «снизу вверх», или восходящее проектирование программ, - это методика разработки программ, начинающаяся с разработки подпрограмм (процедур, функций), в то время когда проработка общей схемы не закончилась. Такая методика является менее предпочтительной по сравнению с нисходящим проектированием, так как часто приводит к нежелательным результатам, переписыванию кода и увеличению времени разработки. Ее использование может быть целесообразным, когда новый проект использует известные частные решения.
Общие принципы разработки программных проектов. Использование технологии структурного программирования при разработке серьезных программных проектов основано на следующих принципах:
- программирование должно осуществляться «сверху вниз»;
- весь проект должен быть разбит на модули/подпрограммы с одним входом и одним выходом;
- любая подпрограмма должна допускать только три основные структуры: последовательное выполнение операторов, ветвление и цикл;
- недопустим оператор безусловной передачи управления goto;
- документация должна создаваться одновременно с программированием, частично в виде комментариев к программе. Применение принципов и методов структурного программирования позволяет повысить надежность программ (благодаря хорошему структурированию при проектировании программа легко поддается тестированию и отладке) и их эффективность (структурирование программы позволяет легко находить и корректировать ошибки, а отдельные подпрограммы можно переделывать/модифицировать независимо от других), уменьшить время и стоимость программной разработки, улучшить читабельность программ.
Первые программы состояли из нескольких десятков - сотен машинных команд. Программные комплексы и информационные системы включали в себя от нескольких десятков тысяч до миллионов операторов на языках высокого уровня. По мере увеличения объема программных средств на первое место по влиянию на скорость их разработки вышел процесс отладки, т.е. обнаружение и исправление допущенных ошибок. Практика показала, что написать более-менее большую программу без ошибок практически невозможно. Более того, даже во время эксплуатации готовых программ обнаруживаются пропущенные при отладке ошибки. Ошибки делятся на несколько категорий.
Самая простая - синтаксические ошибки. Они связаны с неверным написанием конструкций языка и обнаруживаются сразу, в тот момент, когда компилятор пытается перевести программу на машинный язык
Если исправлены все синтаксические ошибки и ошибки компоновки, то программа начинает выполняться (стадия Run). Однако эта стадия может быть прервана недопустимой операцией (например, делением на ноль), и в этом случае говорят об ошибках времени выполнения {RunTime Errors). Либо программа досчитала до конца, но полученные результаты оказываются неверными. Вызвать это могут ошибки алгоритма, либо ошибки организации межмодульных связей, ошибки преобразования типов данных, либо простые описки (например, пропущен ноль при записи числа 100 и программа использовала в вычислениях 10).
Ошибки времени выполнения обнаруживаются решением серии тестовых примеров {прогонка программы), результат для которых известен заранее. Как правило, время, затраченное на поиск подобных ошибок, существенно превышает время написания самой программы и исправления синтаксических ошибок. Развитие концепции программирования тесно связано с проблемой снижения брака при написании программы.Разрабатываются теоретические основы структурного программирования, теория доказательства правильности программы, доказательное программирование.
Концепция структурного программирования предполагает такой научно обоснованный подход к построению программы и к возможностям языка программирования, при котором будет существенно снижен объем возможных ошибок. Существенное развитие концепции достигнуто в языке структурного программирования Pascal . Суть структурного программирования состоит в том, что данные представляют собой, прежде всего, абстракции реальных объектов и формулируются предпочтительно как абстрактные структуры, которые могут не иметь конкретной реализации в языке программирования. В процессе конструирования программы представление данных постепенно уточняется вслед за уточнением алгоритма.
Язык структурного программирования должен предоставлять возможность конструирования собственных типов данных. На низшем уровне стоят предопределенные в языке фундаментальные структуры (например: скалярные типы, запись, массив и множество). Из фундаментальных структур, как из молекул, строят усложненные структуры. Переменные фундаментальной структуры могут менять только значение, сохраняя тип или множество допустимых значений и занимаемый ими размер. Усложненные структуры характеризуются изменением не только значения, но и самой формы представления, составом входящих в них фундаментальных структур. Динамическое управление памятью реализуется на уровне указателей, и динамические данные объединяются в древовидную структуру (деревья).
Кроме того, предъявляются определенные требования к типизации данных, за счет чего тип любого выражения или переменной можно определить без необходимости проведения вычислений, т.е. на стадии трансляции. При этом можно избежать большого количества трудно находимых ошибок времени выполнения за счет выявления их на стадии трансляции программы.
Концепция структурного программирования предполагает не только использование специальных языков и применения определенного стиля программирования. В первую очередь это - философия программирования, которая затрагивает и такой аспект, как методика обученияпрограммистов.
Отмечается, что программирование представляет собой обширную и разнообразную деятельность, часто требующей сложной умственной работы. Неверно считать, что программирование можно свести к использованию готовых рецептов, основанных на систематическом описании простейших блоков. У учеников необходимо развивать способность творчески мыслить, и здесь чрезвычайно важна роль учителя, показывающего, как он делает то-то и то-то. Творчество не подвластно канонам, методикам и технологиям. В качестве метода обучения принимается тщательный выбор и рассмотрение характерных примеров. Необходимо рассматривать сложные и длинные программы, какие часто и встречаются на практике и лучше всего подходят для выявления того неуловимого, но важного свойства, которое называется стилем программирования. Разбор длинных программ служит упражнением в искусстве их чтения, которое не менее важно, чем умение писать программы.Контрольные вопросы и задачи
5.1. Назовите и кратко охарактеризуйте части команды программы.
5.2. Основой для программы функционирования УОДИ является ____ ; дайте его определение.
5.3. Что понимается под программированием в кодах?
5.4. Что Вы знаете о языке ассемблер?
5.5. Какие языки программирования называют машинно-независи-мыми?
5.6. Каким образом осуществляется «перевод» программы, написанной на алгоритмическом языке в объектный код, понятный компьютеру?
5.7. Что понимается под модульным программированием и отдельным модулем?
5.8. Что Вы знаете о структурном программировании?
Структурное программирование - одно из крупнейших достижений в технологии программирования. Хотя самое общее и довольно смутное представление о структурном программировании имеется почти у всех, общепринятого четкого его определения нет. Структурное програм мирование ставит своей целью писать программы минимальной сложности, заставить программиста мыслить ясно, облегчить восприятие программы.
Текст программы должен быть таким, чтобы его можно было читать «сверху - вниз». Неограниченное использование операторов безусловного перехода (GO TO ) нарушает это условие, поэтому структурное программирование часто называют программированием без GO ТО.
Можно привести примеры программ, которые не содержат GO TO , и аккуратно расположены лесенкой в соответствии с уровнем вложенности операторов, но совершенно непонятны и бывают другие программы, содержащие GO TO и все же понятны. Так что наличие или отсутствие GO TO - плохой показатель качества программы (иллюстрации в Д. Кнут). И все же: наиболее трудно контролируемым и потенциально неустойчивым является оператор безусловного перехода - GO TO .
Структура тела модулей и используемые базовые конструкции програм мирования должны быть потенциально устойчивыми к аппаратурным сбоям, искажениям исходных данных и к ошибкам в программах.
Любую программу можно синтезировать на основе элементарных базовых конструкций трех типов:
1. Простая последовательность. 2. Условия (альтернативы).
3. Повторение (циклы, итерации). Возможны один из двух или оба вида:
Делать «пока» Делать «пока не»
4. Можно добавить четвертую конструкцию - выбор (переключатель).
Блоки определяются рекурсивно: прямоугольники изображают вложенные строительные блоки, используемые вместо прямоугольника.
Перечисленные элементарные конструкции, например, в языке Паскаль реализованы так:
Условный оператор IF лог. выр . THEN оператор 1 ELSE оператор2 ;
IF лог. выражение THEN оператор ;
Повторение (циклы, итерации)
а) Делать «пока» WHILE условие продолжения DO оператор ;
б) Делать «пока не» REPEAT оператор UNTIL условие завершения ;
в) Цикл с перебором FOR К:=В1 ТО В2 DO оператор ;
FOR K:=B2 DOWNTO B1 DO оператор ;
Выбор (переключатель) CASE условие OF
N1, ... Nk : оператор 1 ;
Ni , ... Nm : оператор п ;
END ;
В языке FoxBASE эти конструкции реализованы в виде:
Условный оператор IF лог. выражение
операторы1
[ ELSE
операторы2 ]
ENDIF
Цикл DO WHILE выражение
операторы
ENDDO
Выбор (переключатель) DO CASE
CASE лог . выражение 1
операторы
CASE лог. выражение2
Операторы
CASE лог. Выражение п
Операторы
ENDCASE
Каждая структура характеризуется единственной точкой передачи управления в структуру (единственный вход) и единственной точкой выхода из структуры.
Эти конструкции имеют систематизирующее и дисциплинирующее значение. Простота исходных конструкций структурного программирования предотвращает появление сложных информационных связей и запуганных передач управления.
При повышении структурированности модулей снижается сложность программ, возрастает их наглядность, что способствует сокращению числа ошибок. Однако за повышение качества программ приходится расплачиваться дополнительной памятью и временем их реализации на ЭВМ.
Структурность программы зависит от используемого языка программирования. Современные программные средства разработки программ являются «наилучшими» языками структурного программирования. Из распространенных языков программирования самыми подходящими считаются Паскаль, Basic , FoxBASE . Структурное программирование, например, на языке Ассемблер почти невозможно. Сам факт использования языка Ассемблера указывает на то, что программа написана в основном в терминах машинного языка.
Структурное программирование ориентировано на общение с людьми, а не с машиной, способствует написанию программ, представляющих собой простое и ясное решение задачи.
Важно, чтобы программист, еще только приступая к программированию логики, мыслил в терминах основных базовых структурных конструкций.
Позиция в отношении оператора GO TO должна быть следующей: избегать использование GO TO всюду, где это возможно, но не ценой ясности программ. Часто оказывается целесообразным использовать GO TO для выхода из цикла или модуля, для перехода в конструкции ON (например, в языке Basic ) или во избежание слишком большой глубины вложенности развилок, тем более что переход осуществляется на последующие (расположенные ниже) операторы программы, и структурная программа продолжает оставаться легко читаемой сверху вниз. Наихудшим применением оператора GO TO считается передача управления на оператор, расположенный выше (раньше) в тексте программы.
Кроме того, чтобы облегчить чтение программы, ее текст необходимо разбить физически на части, добавляя пустые строки между разделами, подразделениями. Текст программы должен быть написан с правильными сдвигами, так что разрывы в последовательности выполнения легко прослеживаются. Одноцелевые выполняемые предложения каждого модуля должны умещаться на одной странице печатающего устройства.
Структурное программирование
Практика программирования показала необходимость научно обоснованной методологии разработки и документирования алгоритмов и программ. Эта методология должна касаться анализа исходной задачи, разделения ее на достаточно самостоятельные части и программирования этих частей по возможности независимо друг от друга. Такой методологией, зародившейся в начале 70-х годов и получившей в последнее время широкое распространение, является структурное программирование. По своей сути оно воплощает принципы системного подхода в процессе создания и эксплуатации программного обеспечения ЭВМ.
На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.
C труктурное программирование воплощает принципы системного подхода в процессе создания и эксплуатации программного обеспечения ЭВМ. В основу структурного программирования положены следующие достаточно простые положения:
алгоритм и программа должны составляться поэтапно (по шагам).
сложная задача должна разбиваться на достаточно простые части, каждая из которых имеет один вход и один выход.
логика алгоритма и программы должна опираться на минимальное число достаточно простых базовых управляющих структур.
Структурное программирование иногда называют еще "программированием без GO TO". Рекомендуется избегать употребления оператора перехода всюду, где это возможно, но чтобы это не приводило к слишком громоздким структурированным программам.
К полезным случаям использования оператора перехода можно отнести выход из цикла или процедуры по особому условию, "досрочно" прекращающего работу данного цикла или данной процедуры, т.е. завершающего работу некоторой структурной единицы (обобщенного оператора) и тем самым лишь локально нарушающего структурированность программы.
Фундаментом структурного программирования является теорема о структурировании . Эта теорема устанавливает, что, как бы сложна ни была задача, схема соответствующей программы всегда может быть представлена с использованием ограниченного числа элементарных управляющих структур. Базовыми элементарными структурами являются структуры: следование, ветвление и повторение (цикл), любой алгоритм может быть реализован в виде композиции этих трех конструкций.
Первая (а ) структура - тип последовательность (или просто последовательность), вторая (б ) – структура выбора (ветвление), третья (в ) – структура цикла с предусловием.
При словесной записи алгоритма указанные структуры имеют соответственно следующий смысл:
«выполнить
;
выполнить
»,
если
,
то выполнить
,
иначе выполнить
»,
«до
тех пор, пока
,
выполнять
»,
где
-
условие;
,
,
-
действия.
Применительно
к языку Паскаль, в котором наиболее
полно нашли свое отражение идеи
структурного программирования,
целесообразно при проектировании
алгоритмов дополнительно использовать
еще четыре элементарные структуры:
сокращенную запись разветвления (рис.
16,
);
структуру варианта (рис. 16,
);
структуру повторения или цикла с
параметром (рис. 16,
);
структуру цикла с постусловием (рис. 6,
).
Каждая из этих структур имеет один вход
и один выход.
Ветвящимся (разветвляющимся) называется вычислительный процесс, в котором происходит выбор одного из возможных вариантов вычислений в зависимости от проверки заданных условий.
В зависимости от типа и числа проверяемых условий различают:
Ветвление с простым условием (условие - выражение отношения);
Ветвление с составным условием (условие - логическое выражение);
Сложное ветвление (несколько условий).
Вариант вычислений, определяемый в результате проверки условия, называется ветвью .
Циклическим называется процесс многократного повторения некоторого участка вычислений при изменении хотя бы одной из входящих в него величин.
Повторяющийся участок вычисления называется циклом . Операции, осуществляемые в цикле, составляют тело цикла.
Величина, изменяющая своё значение от цикла к циклу, называется параметром цикла.
Зависимость, связывающая текущее и предыдущее значения параметра цикла, определяет закон изменения параметра цикла. Зависимость, предписывающая повторение цикла, либо выход из него, называется условием повторения цикла.
Полный однократный проход цикла от начала до конца называется итерацией.
Все циклические процессы по признаку определения количества повторений (М) разделяются на два класса.
Арифметическим называется циклический процесс, число повторений в котором может быть определено заранее, т.е. не зависит от результатов счёта в теле цикла.
Итерационным является циклический процесс, число повторений в котором зависит от результатов вычислений в теле цикла и не может быть определено заранее.
Независимо от того, к какому классу относится вычислительный процесс, каждый из них содержит обязательные элементы:
вход в цикл (формирование начального значения параметра цикла);
вычисления в теле цикла (расчёт текущего значения функций, формирования нового значения параметра цикла, а также вспомогательные операции);
выход из цикла (проверка условия, определяющего повторение вычислений, либо их прекращение).
В соответствии с видом задания (изменения) параметра цикла арифметические циклы подразделяются на:
циклы с аналитическим изменением параметра;
циклы с табличным заданием параметра.
Выполнение арифметических циклов, т.е. многократное вычисление значений функции при изменяющихся значениях аргумента, называется табуляцией функции .
Распространены две методики (стратегии) разработки программ , относящиеся к структурному программированию:
– программирование «сверху вниз»;
– программирование «снизу вверх».
Программирование «сверху вниз», или нисходящее программирование – это методика разработки программ, при которой разработка начинается с определения целей решения проблемы, после чего идет последовательная детализация, заканчивающаяся детальной программой.
Такой подход удобен тем, что позволяет человеку постоянно мыслить на предметном уровне, не опускаясь до конкретных операторов и переменных. Кроме того, появляется возможность некоторые подпрограммы не реализовывать сразу, а временно откладывать, пока не будут закончены другие части.
Программирование «снизу вверх», или восходящее программирование – это методика разработки программ, начинающаяся с разработки подпрограмм (процедур, функций), в то время когда проработка общей схемы не закончилась.
Такая методика является менее предпочтительной по сравнению с нисходящим программированием, так как часто приводит к нежелательным результатам, переделкам и увеличению времени разработки.
Подпрограммы бывают двух видов – процедуры и функции. Процедура просто выполняет группу операторов, а функция вдобавок вычисляет некоторое значение и передает его обратно в главную программу. Это значение имеет определенный тип. Данные передаются подпрограмме в виде параметров или аргументов, которые обычно описываются в ее заголовке так же, как переменные. Подпрограммы вызываются, как правило, путем простой записи их названия с нужными параметрами.
Подпрограммы могут быть вложенными – допускается вызов подпрограммы не только из главной программ, но и из любых других программ.
В некоторых языках программирования допускается вызов подпрограммы из себя самой. Такой прием называется рекурсией и опасен тем, что может привести к зацикливанию – бесконечному самовызову.
Достоинства структурного программирования:
– повышается надежность программ (благодаря хорошему структурированию при проектировании, программа легко поддается тестированию и не создает проблем при отладке);
– повышается эффективность программ (структурирование программы позволяет легко находить и корректировать ошибки, а отдельные подпрограммы можно переделывать (модифицировать) независимо от других);
– уменьшается время и стоимость программной разработки;
– улучшается читабельность программ.
Предпрограммная подготовка задачи
На ЭВМ могут решаться задачи различного характера, например: научно-инженерные; разработки системного программного обеспечения; обучения; управления производственными процессами и т. д. В процессе подготовки и решения на ЭВМ научно-инженерных задач можно выделить следующие этапы:
1. постановка задачи;
2. формирование математической модели задачи;
3. выбор и обоснование метода решения;
4. алгоритмизация вычислительного процесса;
5. программирование;
6. отладка и тестирование программы;
7. решение задачи на ЭВМ и анализ результатов;
8. сопровождение программы.
В задачах другого класса некоторые этапы могут отсутствовать, например, в задачах разработки системного программного обеспечения отсутствует математическое описание. Перечисленные этапы связаны друг с другом. Для уменьшения числа подобных изменений необходимо на каждом этапе по возможности учитывать требования, предъявляемые последующими этапами
Постановка задачи - этап словесной формулировки, определяющий цель решения, исходные данные, основные закономерности, условия и ограничения применения этих закономерностей. Анализируются характер и сущность всех величин, используемых в задаче, и определяются условия, при которых она решается.
Постановка задачи должна отвечать следующим требованиям:
Четкая формулировка цели с указанием вида и характеристик конечных результатов;
Представление значений и размерностей исходных данных;
Определение всех возможных вариантов решения, условий выбора каждого;
Обозначения границы применимости и действия в случае выхода за них.
Формирование математической модели задачи - этап перевода словесной постановки задачи в совокупность математических зависимостей, описывающих исходные данные и вычисления промежуточных и конечных результатов.
Математическая модель формируется с определенной точностью, допущениями и ограничениями. При этом в зависимости от специфики решаемой задачи могут быть использованы различные разделы математики и других дисциплин.
Математическая модель должна удовлетворять по крайней мере двум требованиям: реалистичности и реализуемости. Под реалистичностью понимается правильное отражение моделью наиболее существенных черт исследуемого явления. Реализуемость достигается разумной абстракцией, отвлечением от второстепенных деталей, чтобы свести задачу к проблеме с известным решением. Условием реализуемости является возможность практического выполнения необходимых вычислений за отведенное время при доступных затратах требуемых ресурсов.
Полученная математическая модель должна отвечать следующим требованиям:
Вначале составляется модель исходных данных, затем - расчетные зависимости;
В модели исходных данных не изменяются размерности данных и не используются никакие математические операции;
Обозначение всех входящих в зависимости величин именами, определяющими их суть;
Указание размерностей всех используемых величин для контроля и дальнейшей модернизации решения;
Выбор и обоснование метода решения - этап разработки или выбора из уже имеющихся метода решения, в том числе выбор стандартных структур вычислительных процессов (линейной, ветвящейся, циклической). Критерии выбора определяются математической моделью решения (предыдущий этап), требованиями к универсальности метода и точности результата, ограничениями технического и программного обеспечении. При обосновании выбора метода необходимо учитывать различные факторы и условия, точность вычислений, время решения задачи на ЭВМ, требуемый объем памяти и другие. Здесь следует указать альтернативные методы и аргументы сделанного выбора.
Алгоритмизация вычислительного процесса - этап разработки совокупности предписаний, однозначно определяющих последовательность преобразования исходных данных в конечные результаты. На данном этапе составляется алгоритм решения задачи согласно действиям, задаваемым выбранным методом решения. Процесс обработки данных разбивается на отдельные относительно самостоятельные блоки, и устанавливается последовательность выполнения блоков. Разрабатывается блок-схема алгоритма.
Программирование. При составлении программы алгоритм решения задачи переводится на конкретный язык программирования. Для программирования обычно используются языки высокого уровня, поэтому составленная программа требует перевода ее на машинный язык ЭВМ. После такого перевода выполняется уже соответствующая машинная программа.
1. Программа должна быть универсальной, то есть не зависящей от конкретного набора данных. Например, если количество обрабатываемых данных может меняться, то следует предусмотреть хранение максимально возможного их количества. Универсальная программа должна уметь обрабатывать ошибки, которые могут возникнуть в процессе обработки информации.
2. Вместо констант 1 лучше использовать переменные 2 . Если в программе используются константы, то при их изменении нужно изменять в исходной программе каждый оператор 3 , содержащий прежнюю константу. Эта процедура отнимает много времени и часто вызывает ошибки. В программе следует предусмотреть контроль вводимых данных (в частности, программа не должна выполняться, если данные выходят за пределы допустимого диапазона).
3. Некоторые простые приемы позволяют повысить эффективность программы (то есть уменьшить количество выполняемых операций и время работы программы). К таким приемам относится:
Использование операции умножения вместо возведения в степень;
Если некоторое арифметическое выражение встречается в вычислениях несколько раз, то его следует вычислить заранее и хранить в памяти ЭВМ, а по мере необходимости использовать;
При организации циклов в качестве границ индексов 4 использовать переменные, а не выражения, которые вычислялись бы при каждом прохождении цикла;
Особое внимание обратить на организацию циклов, убрав из них все повторяющиеся с одинаковыми данными вычисления и выполняя их до входа в цикл.
4. Программа должна содержать комментарии, позволяющие легко проследить за логической взаимосвязью и функциями отдельных ее частей.
При написании программы следует структурировать ее текст так, чтобы она хорошо читалась. В частности, в программе должно быть хорошо видно, где начинается и где заканчивается цикл.
Отладка программы – процесс выявления и исправления синтаксических и логических ошибок в программе. Суть отладки заключается в том, что выбирается некоторый набор исходных данных, называемый тестовым набором (тестом), и задача с этим набором решается дважды: один раз – исполнением программы, второй раз – каким-либо иным способом, исходя из условия задачи, так сказать, «вручную». При совпадении результатов алгоритм считается верным. В качестве тестового набора можно выбрать любые данные, которые позволяют:
Обеспечить проверку выполнения всех операций алгоритма;
Свести количество вычислений к минимуму.
В ходе синтаксического контроля программы транслятором выявляются конструкции и сочетания символов, недопустимые с точки зрения правил их построения или написания, принятых в данном языке. Сообщения об ошибках ЭВМ выдает программисту, при этом вид и форма выдачи подобных сообщений зависят от вида языка и версии используемого транслятора.
После устранения синтаксических ошибок проверяется логика работы программы в процессе ее выполнения с конкретными исходными данными. Для этого используются специальные методы, например, в программе выбираются контрольные точки, для которых вручную рассчитываются промежуточные результаты. Эти результаты сверяются со значениями, получаемыми ЭВМ в данных точках при выполнении отлаживаемой программы. Кроме того, для поиска ошибок могут быть использованы отладчики, выполняющие специальные действия на этапе отладки, например, удаление, замена или вставка отдельных операторов или целых фрагментов программы, вывод или изменение значений заданных переменных.
Тестирование - это испытание, проверка правильности работы программы в целом, либо её составных частей.
Отладка и тестирование (англ. test - испытание) - это два четко различимых и непохожих друг на друга этапа:
При отладке происходит локализация и устранение синтаксических ошибок и явных ошибок кодирования;
В процессе же тестирования проверяется работоспособность программы, не содержащей явных ошибок.
Тестирование устанавливает факт наличия ошибок, а отладка выясняет ее причину. В современных программных системах (Turbo Basic, Turbo Pascal, Turbo C и др.) отладка осуществляется часто с использованием специальных программных средств, называемых отладчиками. Эти средства позволяют исследовать внутреннее поведение программы.
Программа-отладчик обычно обеспечивает следующие возможности:
Пошаговое исполнение программы с остановкой после каждой команды (оператора);
Просмотр текущего значения любой переменной или нахождение значения любого выражения, в том числе, с использованием стандартных функций; при необходимости можно установить новое значение переменной;
Установку в программе "контрольных точек", т.е. точек, в которых программа временно прекращает свое выполнение, так что можно оценить промежуточные результаты, и др.
При отладке программ важно помнить следующее:
В начале процесса отладки надо использовать простые тестовые данные;
Возникающие затруднения следует четко разделять и устранять строго поочередно;
Как бы ни была тщательно отлажена программа, решающим этапом, устанавливающим ее пригодность для работы, является контроль программы по результатам ее выполнения на системе тестов.
Для реализации метода тестов должны быть изготовлены или заранее известны эталонные результаты. Вычислять эталонные результаты нужно обязательно до, а не после получения машинных результатов. В противном случае имеется опасность невольной подгонки вычисляемых значений под желаемые, полученные ранее на машине.
Тестовые данные должны обеспечить проверку всех возможных условий возникновения ошибок:
Должна быть испытана каждая ветвь алгоритма;
Очередной тестовый прогон должен контролировать то, что еще не было проверено на предыдущих прогонах;
Первый тест должен быть максимально прост, чтобы проверить, работает ли программа вообще;
Арифметические операции в тестах должны предельно упрощаться для уменьшения объема вычислений;
Количества элементов последовательностей, точность для итерационных вычислений, количество проходов цикла в тестовых примерах должны задаваться из соображений сокращения объема вычислений;
Минимизация вычислений не должна снижать надежности контроля;
Тестирование должно быть целенаправленным и систематизированным, так как случайный выбор исходных данных привел бы к трудностям в определении ручным способом ожидаемых результатов; кроме того, при случайном выборе тестовых данных могут оказаться непроверенными многие ситуации;
Усложнение тестовых данных должно происходить постепенно.
Процесс тестирования можно разделить на три этапа.
1. Проверка в нормальных условиях. Предполагает тестирование на основе данных, которые характерны для реальных условий функционирования программы.
2. Проверка в экстремальных условиях. Тестовые данные включают граничные значения области изменения входных переменных, которые должны восприниматься программой как правильные данные. Типичными примерами таких значений являются очень маленькие или очень большие числа и отсутствие данных. Еще один тип экстремальных условий - это граничные объемы данных, когда массивы состоят из слишком малого или слишком большого числа элементов.
3. Проверка в исключительных ситуациях. Проводится с использованием данных, значения которых лежат за пределами допустимой области изменений. Известно, что все программы разрабатываются в расчете на обработку какого-то ограниченного набора данных. Поэтому важно получить ответ на следующие вопросы:
Что произойдет, если программе, не рассчитанной на обработку отрицательных и нулевых значений переменных, в результате какой-либо ошибки придется иметь дело как раз с такими данными?
Как будет вести себя программа, работающая с массивами, если количество их элементов превысит величину, указанную в объявлении массива?
Что произойдет, если числа будут слишком малыми или слишком большими?
Наихудшая ситуация складывается тогда, когда программа воспринимает неверные данные как правильные и выдает неверный, но правдоподобный результат.
Программа должна сама отвергать любые данные, которые она не в состоянии обрабатывать правильно.
Решение задачи на ЭВМ и анализ результатов. После отладки программы ее можно использовать для решения прикладной задачи. При этом обычно выполняется многократное решение задачи на ЭВМ для различных наборов исходных данных. Получаемые результаты интерпретируются и анализируются специалистом или пользователем, поставившим задачу.
Сопровождение программы:
Разработанная программа длительного использования устанавливается на ЭВМ, как правило, в виде готовой к выполнению машинной программы. К программе прилагается документация, включая инструкцию для пользователя. Так как при установке программы на диск для ее последующего использования помимо файлов с исполняемым кодом устанавливаются различные вспомогательные программы (утилиты, справочники, настройщики и т. д.), а также необходимые для работы программ разного рода файлы с текстовой, графической, звуковой и другой информацией.
Доработка программы для решения конкретных задач;
Составление документации к решенной задаче, математической модели, алгоритму, программе по их использованию.
1Конста́нта в программировании - способ адресования данных, изменение которых рассматриваемой программой не предполагается или запрещается.
2 Переме́нная в императивном программировании - поименованная, либо адресуемая иным способом область памяти, адрес которой можно использовать для осуществления доступа к данным. Данные, находящиеся в переменной (то есть по данному адресу памяти), называются значением этой переменной.
В других парадигмах программирования, например, в функциональной и логической, понятие переменной оказывается несколько иным. В таких языках переменная определяется как имя, с которым может быть связано значение, или даже как место (location) для хранения значения.
3 Инструкция или оператор (англ. statement) - наименьшая автономная часть языка программирования; команда. Программа обычно представляет собой последовательность инструкций.
Многие языки (например, Си) различают инструкцию и определение. Различие в том, что инструкция исполняет код, а определение создаёт идентификатор (то есть можно рассматривать определение как инструкцию присваивания).
Ниже приведены основные общие инструкции императивных языков программирования.
4 Индекс в языках программирования - элемент перечислимого множества, который указывает на конкретный элемент массива, обычно является неотрицательным скалярным целым числом.
Есть три способа, как элементы массива могут быть проиндексированы целыми неотрицательными числами:
первый элемент массива имеет индекс 0;
первый элемент массива имеет индекс 1;
n («индекс началом с n»)
базисный индекс массива может быть свободно выбран. Обычно языки программирования, позволяющие «индекс началом с n», разрешают также в качестве индекса массива выбирать отрицательные значения, а также и другие скалярные типы данных, как перечисления или символы.
Массив может иметь несколько измерений, таким образом обычная практика обращаться к массиву, используя несколько индексов. Например к двумерному массиву с тремя строками и четырьмя столбцами можно было бы обратиться к элементу в 2-ом ряду и 4-ой столбце с помощью выражения: (в языке в котором приоритет у строки) и (в языке в котором приоритет у столбца) в случае индексом с началом с нуля. Таким образом два индекса используются для двумерных массивов, три - для трехмерного массива, и n - для n-мерного массива.
