4622

Структурная методология разработки программ

Практическая работа

Информатика, кибернетика и программирование

Введение К началу 70-х годов ХХ века, когда развитие языков программирования достигло достаточно высокого уровня, а создаваемые программные комплексы достигли достаточно внушительных размеров (сотни тысяч – миллионы команд), стало очевидно, что...

Русский

2012-11-23

436.5 KB

108 чел.

Введение

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

Исходя из этих проблем, ведущими программистами 70-х годов (Дейкстра, Вирт, Дал, Xoap, Йордан, Константин, Майерс и др.) были разработаны строгие правила ведения проектов, которые получили название структурной методологии.

Важным этапом в становлении этого подхода стали международные конференции по программированию, проведенные в 1968-69 годах. На второй из них Эдсгер Дейкстра впервые использовал термин «структурное программирование» и предложил принципиально новый способ создания программ. Он рассматривал программу как совокупность иерархических абстрактных уровней, которые позволяли:

  1.  четко структурировать программу, что улучшило ее понимание программистами;
  2.  выполнять доказательства ее корректности и тем самым повышать надежность функционирования программы;
  3.  сокращать сроки разработки программ.

Еще одним толчком к изменению способа программистского мышления стало опубликованное письмо Дейкстры редактору одного из научных издательств, которое было озаглавлено «Оператор GOTO нужно считать вредным». Это письмо вызвало острую полемику среди программистов того времени, но в итоге победило все-таки структурное мышление, которое, кроме Дейкстры, активно поддерживали профессор Цюрихского технического университета Вирт и профессор Оксфордского университета Xoap. Одним из результатов полемики было доказательство того, что любая программа может быть написана, используя только простую последовательность операторов, итеративную конструкцию типа while (пока) и конструкцию выбора case (выбор), а оператор goto (перейти к) не является необходимой управляющей конструкцией в структурном программировании. К сожалению, споры об операторе goto имели один отрицательный «побочный эффект» — довольно часто программирование без goto стало отождествляться со всем структурным программированием. Однако цели структурного программирования намного глобальнее и серьезнее.

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


1. ОСНОВЫ ТЕХНОЛОГИИ СТРУКТУРНОГО ПРОГРАММИРОВАНИЯ

Структурное программирование — методология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры блоков. Предложена в 70-х годах XX в. Э.Дейкстрой, разработана и дополнена Н.Виртом (рис. 1).

Эдсгер Вибе Дейкстра (1930 – 2002) — нидерландский учёный, идеи которого оказали влияние на развитие компьютерной индустрии. Известен как создатель алгоритма поиска кратчайшего пути на графе, один из основателей структурного программирования. В 1972 г. стал лауреатом премии Тьюринга.

Никлаус Вирт (1934) — швейцарский учёный, специалист в области информатики, один из известнейших теоретиков в области разработки языков программирования, профессор компьютерных наук, лауреат премии Тьюринга 1984 г. Ведущий разработчик языков программирования Паскаль, Модула-2, Оберон.

Рис. 1. Пионеры структурного программирования – Э.Дейкстра и Н.Вирт.

Методология структурного программирования появилась как следствие возрастания сложности решаемых на компьютерах задач, и соответственного усложнения программного обеспечения: в 70-е годы XX в. объёмы и сложность программ достигли такого уровня, что «интуитивная» (неструктурированная) разработка программ, которая была нормой в более раннее время, перестала удовлетворять потребностям практики. Программы становились слишком сложными, чтобы их можно было нормально сопровождать, поэтому потребовалась какая-то систематизация процесса разработки и структуры программ.

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

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

Типичными методами структурного программирования являются:

  •  нисходящее проектирование (проектирование сверху вниз);
  •  модульное (процедурное) программирование;
  •  структурное кодирование.

В соответствии с методологией структурного программирования:

1. Любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:

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

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

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

3. Разработка программы ведётся пошагово, методом «сверху вниз».

Сначала пишется текст основной программы, в котором, вместо каждого связного логического фрагмента текста, вставляется вызов подпрограммы, которая будет выполнять этот фрагмент. Вместо настоящих, работающих подпрограмм, в программу вставляются «заглушки», которые ничего не делают. Полученная программа проверяется и отлаживается. После того, как программист убедится, что подпрограммы вызываются в правильной последовательности (т.е. общая структура программы верна), подпрограммы-заглушки последовательно заменяются на реально работающие, причём разработка каждой подпрограммы ведётся тем же методом, что и основной программы. Разработка заканчивается тогда, когда не останется ни одной «заглушки», которая не была бы удалена. Такая последовательность гарантирует, что на каждом этапе разработки программист одновременно имеет дело с обозримым и понятным ему множеством фрагментов, и может быть уверен, что общая структура всех более высоких уровней программы верна. При сопровождении и внесении изменений в программу выясняется, в какие именно процедуры нужно внести изменения, и они вносятся, не затрагивая части программы, непосредственно не связанные с ними. Это позволяет гарантировать, что при внесении изменений и исправлении ошибок не выйдет из строя какая-то часть программы, находящаяся в данный момент вне зоны внимания программиста.

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

Методология структурной разработки программного обеспечения была признана «самой сильной формализацией 70-х годов». После этого слово «структурный» стало модным в отрасли, и его начали использовать везде, где надо и где не надо. Появились работы по «структурному проектированию», «структурному тестированию», «структурному дизайну» и т.д.

К достоинствам структурного программирования можно отнести следующее:

1. Структурное программирование позволяет значительно сократить число вариантов построения программы по одной и той же спецификации, что значительно снижает сложность программы и облегчает понимание её другими разработчиками.

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

3. Сильно упрощается процесс тестирования и отладки структурированных программ.

Рассмотрим более подробно основные методы структурного программирования.

1.1. Цели и принципы структурного программирования

Целями структурного программирования являются:

Обеспечение дисциплины программирования в процессе создания программных комплексов*.

Улучшение читабельность программы. Читабельность улучшается, если придерживаться следующих правил:

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

стремиться к локализации действия управляющих конструкций и использования структур данных;

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

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

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

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

Основные принципы структурного программирования сведены в табл. 1.

Таблица 1. Принципы структурного программирования

Принцип

Пояснение

Абстракция

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

Формальность

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

«Разделяй и властвуй»

Разделение программы на отдельные фрагменты (модули), которые просты по управлению и допускают независимую отладку и тестирование.

Иерархическое упорядочение

Структура разбиения на части не менее важна, чем сам факт такого разделения. Этот принцип выдвигает требование иерархического структурирования взаимосвязей между модулями программного комплекса, что облегчает достижение целей структурного программирования.

1.2. Нисходящее проектирование

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

Спецификация задачи является ее первичным проектом. От неё мы движемся к программе, постепенно уточняя описание.

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

Пример 1. В качестве примера рассмотрим проект одевания ребенка.

Решение:

1. Первичная цель:

Одеть.

2. Конкретизация цели на первом шаге:

Одеть нижнюю половину.

Одеть верхнюю половину.

2.1. Нижнюю половину можно одеть в два этапа:

Надеть брюки.

Надеть носки и ботинки.

2.2. Верхнюю половину можно также одеть в два этапа:

Надеть рубашку.

Надеть куртку.

3. Окончательный проект выглядит так:

Надеть брюки.

Надеть носки.

Надеть ботинки.

Надеть рубашку.

Надеть куртку.

Метод нисходящего проектирования предполагает последовательное разложение общей функции обработки данных на простые функциональные элементы («сверху-вниз»). В результате строится иерархическая схема – функциональная структура алгоритма (ФСА), отражающая состав и взаимоподчиненность отдельных функций (рис. 2).

Рис. 2. Функциональная структура приложения

Последовательность действий по разработке ФСА приложения следующая:

  1.  определяются цели автоматизации предметной области и их иерархия (цель-подцель);
  2.  устанавливается состав приложений (задач обработки), обеспечивающих реализацию поставленных целей;
  3.  уточняется характер взаимосвязи приложений и их основные характеристики (информация для решения задач, время и периодичность решения, условия выполнения и др.);
  4.  определяются необходимые для решения задач функции обработки данных;
  5.  выполняется декомпозиция функций обработки до необходимой структурной сложности, реализуемой предполагаемым инструментарием.

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

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

Функции ввода-вывода информации рекомендуется отделять от функций вычислительной или логической обработки данных.

По частоте использования функции обработки делятся на:

  •  однократно выполняемые;
  •  повторяющиеся.

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

1.3. Модульное программирование

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

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

В программировании под модулем понимается отдельная подпрограмма, а подпрограммы часто называются процедурами или процедурами-функциями. Поэтому модульное программирование еще называется процедурным.

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

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

Среди множества модулей различают:

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

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

Каждый модуль может оформляться как самостоятельно хранимый файл; для функционирования программного продукта необходимо наличие программных модулей в полном составе.

Модуль должен обладать следующими свойствами:

  •  один вход и один выход – на входе программный модуль получает определенный набор исходных данных, выполняет содержательную обработку и возвращает один набор результатных данных, т.е. реализуется стандартный принцип IPO (Input–Process–Output вход-процесс-выход);
  •  функциональная завершенность – модуль выполняет перечень регламентированных операций для реализации каждой отдельной функции в полном составе, достаточных для завершения начатой обработки;
  •  логическая независимость – результат работы программного модуля зависит только от исходных данных, но не зависит от работы других модулей;
  •  слабые информационные связи с другими программными модулями – обмен информацией между модулями должен быть по возможности минимизирован;
  •  обозримый по размеру и сложности программный код.

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

Модули содержат:

  •  определение доступных для обработки данных;
  •  операции обработки данных;
  •  схемы взаимосвязи с другими модулями.

Каждый модуль состоит из спецификации и тела. Спецификации определяют правила использования модуля, а тело – способ реализации процесса обработки.

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

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

  •  каждый модуль вызывается на выполнение вышестоящим модулем и, закончив работу, возвращает управление вызвавшему его модулю;
  •  принятие основных решений в алгоритме выносится на максимально «высокий» по иерархии уровень;
  •  для использования одной и той же функции в разных местах алгоритма создается один модуль, который вызывается на выполнение по мере необходимости.

В результате дальнейшей детализации алгоритма создается функционально-модульная схема (ФМС) алгоритма приложения, являющаяся основой для программирования (рис. 2).

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

Рис. 3. Функционально-модульная структура алгоритма приложения

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

  •  точки (момент, условие) начала диалога;
  •  инициатор диалога – человек или программный продукт;
  •  параметры и содержание диалога – сообщения, состав и структура меню, экранные формы и т.п.;
  •  реакция программного продукта на завершение диалога.

Для создания диалоговых процессов и интерфейса конечного пользователя наиболее подходят объектно-ориентированные инструментальные средства разработки программ.

Графический интерфейс пользователя (GUI, Graphics User Interface) является обязательным компонентом большинства современных программных продуктов, ориентированных на работу конечного пользователя.

1.4. Структурное кодирование

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

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

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

Свойство структурности операторов состоит в том, что каждый оператор имеет один вход и один выход. Программа, построенная из структурных операторов, называется структурированной.

Фундаментом структурного программирования является теорема о структурировании, сформулированная итальянскими математиками К.Бомом и Дж.Якопини в 1966 г.

Теорема устанавливает, что как бы сложна ни была задача, схему алгоритм ее решения (и, соответственно, программу) всегда можно представить в виде композиции трех типов вложенных блоков:

  •  следования (begin-endначало-конец),
  •  ветвления (if-then-else если-то-иначе),
  •  циклов с предусловием (while пока).

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

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

Виды основных управляющих структур алгоритма приведены на рис. 4.

1. Структура типа «следование» (рис. 4, а) – образуется последовательностью действий, S1, S2, …, Sn, следующих одно за другим:

выполнить S1;

выполнить S2;

выполнить Sn.

В линейном вычислительном процессе все операции выполняются последовательно в порядке их записи. Типовым примером такого процесса является стандартная вычислительная схема, состоящая из трех этапов:

  1.  ввод исходных данных;
  2.  вычисление по формулам;
  3.  вывод результата.

В языке Pascal такая структура заключается в операторные скобки Begin ... End:

Begin

 S1;

 S2;

 ...

 Sn;

End

2. Структура типа «ветвление» (ЕСЛИ – ТО – ИНАЧЕ) (рис. 4, б) – обеспечивает в зависимости от результата проверки условия Р, принимающего одно из двух логических значении Да (True) или Нет (False), выбор одного из альтернативных путей работы алгоритма:

если Р

  то выполнить S1

  иначе выполнить S2.

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

В языке Pascal такая структура имеет следующий формат:

If P 

 Then S1

 Else S2;

3. Структура типа «цикл с предусловием» (рис. 4, в) – обеспечивает многократное выполнение действия S в зависимости от того, какое значение принимает логическое условие Р:

до тех пор пока Р 

  выполнять S.

Выполнение цикла прекращается, когда условие Р не выполняется.

В языке Pascal такая структура имеет следующий формат:

While P Do

 S;

В расширенный комплект элементарных алгоритмических структур дополнительно входят следующие управляющие конструкции (рис. 5).

4. Структура типа «сокращенное ветвление» (ЕСЛИ – ТО) (рис. 5, а) – если результат проверки условия Р принимает значение Да (True), то выполняется действие S; в противном случае это действие пропускается и управление передается следующей структуре:

если Р

  то выполнить S1.

В языке Pascal такая структура имеет следующий формат:

If P 

 Then S;

5. Структура типа «выбор – иначе» (рис. 5, б) являются расширенным вариантом структуры типа ЕСЛИ – ТО – ИНАЧЕ. Здесь проверяемое условие Р может принимать не два логических значения, а несколько порядковых значений, например, 1, 2, …, n. Если Р = i, то будет выполняться действие Si. Если же значение Р будет выходить из диапазона допустимых значений, то выполняется действие S (в укороченном варианте «выбор» никакого действия не производится и управление передается к следующей структуре. В языке Pascal такая структура имеет следующий формат:

Case P Of

1: S1;

2: S2;

n: Sn

Else S

End;

6. Структура типа «цикл с постусловием» (рис. 5, в) – обеспечивает многократное выполнение действия S до тех пор, пока не выполняется условие Р.

В языке Pascal такая структура имеет следующий формат:

Repeat

S

Until P;

7. Структура типа «цикл с параметром» (рис. 5, г) – обеспечивает заранее определенное многократное выполнение действия S. При этом здесь последовательно выполняются следующие типовые операции:

  •  задание начального значения используемого параметра цикла (например, если переменной цикла является i, то ей присваивается значение i1, т.е. i:=i1);
  •  выполнение действий S, предусмотренных в теле цикла;
  •  изменение параметра цикла, который обеспечивает вычисление результата с новыми начальными данными (например, если параметр цикла i изменяется с шагом i3, i:=i i3);
  •  проверка текущего значения параметра цикла с заданным конечным значением (i<=i2);
  •  переход к повторению тела цикла, если параметр цикла не превысил конечного значения, иначе — выполнение следующих действий или вывод результата.

В языке Pascal такая структура имеет следующий формат:

For Переменная:=i1 To (Downto) i3 Do

 S;

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

Структурные операторы обычно применяются уже на ранних стадиях нисходящего проектирования программы.

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

Пример 2. Необходимо составить алгоритм нахождения значений функции:

при с = 2; а = 3,14 и значениях х = -3; -1.5; 0; 1.5; 3.

Решение. В данном примере х меняется от начального значение -3 до конечного значения +3 с шагом +1.5. Поэтому, если используется цикл с предусловием, то следует вначале присвоить x := -3, затем в теле цикла изменять текущее значение х на x := х + 1.5, а в предусловии проверять х ≤ 3. Как только это условие прекратит выполняться, следует выйти из цикла.

Схема алгоритма поставленной задачи показана на рис. 6.

Блоки 2-4 образуют линейную структуру (структуру следования). В этих блоках осуществляются действия, связанные с присвоением числовых значений переменным а, с и х. Причем х присваивается начальное значение -3.0, так как значение этой переменной будет циклически изменяться.

В блоке 5 проверяется условие окончания цикла по х. Если окажется, что условие x ≤ 3 не выполняется, то будет осуществлен выход из цикла и процесс вычислений закончится (управление передается на блок 14, означающий конец вычислений).

При выполнении условия x ≤ 3 осуществляется вход в тело цикла.

В блоке 6 вычисляется вспомогательная переменная z = c2x (она введена для того, чтобы не вычислять многократно выражение c2x).

Блоки 7 и 8 обеспечивают проверку заданных условий и в зависимости от того, выполняются они или нет, в блоках 9-11 осуществляется вычисление значения функции y по соответствующей формуле.

Блок 12 предназначен для обозначения вывода результатов: выводится текущее значение х и соответствующее ему значение y.

В блоке 13 осуществляется изменение значения переменной цикла х: к текущему значению прибавляется шаг изменения (в данном примере это 1.5). После этого действия управление передается к блоку 5 и цикл вновь повторяется, но с новым значением х.

Рис. 6. Схема алгоритма, использующая типовые (базовые) управляющие структуры

Задание № 1. Методом нисходящего проектирования составьте алгоритм проекта написания реферата.

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

при a = 3 и х = 2; 2.5; 3; 3.5; 4.

2. РАЗРАБОТКА АЛГОРИТМА МЕТОДОМ ПОШАГОВОЙ ДЕТАЛИЗАЦИИ

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

Пример 3. Разработать программу, которая с заданной точностью находит значение аргумента х по заданному значению функции у при известном значении n

где n > 1, х > 0. 

Решение. При n > 1 данная функция является монотонно возрастающей. Для нахождения значения х можно применить метод половинного деления, суть которого заключается в следующем. Вначале определяют отрезок [x1, х2] такой, что f(x1) ≤ уf(x2). Затем делят его пополам xt = (x1 + х2)/2 и определяют, в какой половине отрезка находится х, для чего сравнивают f(xt) и у. Полученный отрезок опять делят пополам и так до тех пор, пока разность x1 и x2 не станет меньше заданного значения .

Для разработки алгоритма программы используем метод пошаговой детализации. Будем представлять алгоритмы псевдокодом и в виде блок-схем. 

Шаг 1. Определяем общую структуру программы.

Программа

Ввести у, n,

Определить х

Вывести х, у

Конец.

Шаг 2. Детализируем операцию определения х. 

Определить х

Определить x1 такое, что f(x1) ≤ у

Определить х2 такое, что f(x2) ≥ у 

Определить х на интервале [x1, х2]

Все

Шаг 3. Детализируем операцию определения x1.

Значение x1 должно быть подобрано так, чтобы выполнялось условие f(x1) ≤ у. Известно, что х > 0, следовательно, можно взять некоторое значение х, например, x1 = 1, и последовательно уменьшая его, например в два раза, определить значение x1, удовлетворяющее данному условию. 

Определить x1

x1 := 1

цикл-пока f(x1) > у

x1 := x1/2

все-цикл

Все

 

Шаг 4. Детализируем операцию определения х2.

Значение х2 определяем аналогично x1, но исходное значение будем увеличивать в два раза.

Определить x2

x1 := 1

цикл-пока f(x2) < у

x1 := x1*2

все-цикл

Все

Шаг 5. Детализируем операцию определения х.

Определение х выполняется последовательным сокращением отрезка [x1, х2].

Определить x

цикл-пока x2 – x1 >

Сократить отрезок [x1, х2]

все-цикл

Все

Шаг 6. Детализируем операцию сокращения интервала определения х.

Сокращение отрезка достигается делением пополам и отбрасыванием половины, не удовлетворяющей условию f(x1) ≤ уf(x2).

Сократить интервал определения х:

xt := (x1 + х2)/2

если f(xt) > у 

то х2 := xt 

иначе x1 := xt 

все-если

Все

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

Программа:

Ввести у, n, eps

x1 := 1

цикл-пока f(x1) > у

x1 := x1/2

все-цикл

х2 := 1

цикл-пока f(x2) < у

х2 := х2*2

все-цикл

цикл-пока x2 – x1 > eps

xt := (x1 + х2)/2

если f(xt) > у 

то х2 := xt 

иначе x1 := xt 

все-если

все-цикл

Вывести xt, у

Конец.

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

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

ВЫВОДЫ

  1.  Структурное программирование — методология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры блоков. Предложена в 70-х годах XX в. Э.Дейкстрой, разработана и дополнена Н.Виртом. Типичными методами структурного программирования являются: нисходящее проектирование (проектирование сверху вниз); модульное (процедурное) программирование; структурное кодирование.
  2.  Целями структурного программирования являются: обеспечение дисциплины программирования, повышение эффективности и надежности программ, уменьшение времени и стоимости программной разработки. Основные принципы структурного программирования: абстракция, формальность, «разделяй и властвуй», иерархическое упорядочение.
  3.  Метод нисходящего проектирования предполагает последовательное разложение общей функции обработки данных на простые функциональные элементы («сверху-вниз»). Средства достижения целей на предыдущем уровне превращаются в цели на нижнем.
  4.  Структурное кодирование — это метод написания программ, имеющих определенную структуру. Он основан на использовании небольшого набора структурных операторов, правильность которых легко проанализировать и установить. При этом одни операторы состоят из других, вложенных в них.
  5.  Фундаментом структурного программирования является теорема о структурировании, сформулированная итальянскими математиками К.Бомом и Дж.Якопини в 1966 г. Теорема устанавливает, что как бы сложна ни была задача, схему алгоритм ее решения (и, соответственно, программу) всегда можно представить в виде композиции трех типов вложенных блоков: следования (begin-end – начало-конец), ветвления (if-then-else – если-то-иначе), циклов с предусловием (while – пока).

Контрольные вопросы

  1.  Какие существуют методы структурного программирования?
  2.  Какие цели преследует структурное программирование?
  3.  Какие цели преследует структурное программирование?
  4.  На каких принципах реализуется структурное программирование?
  5.  В чем заключается идея нисходящего проектирования алгоритма?
  6.  Что такое модульное программирование и какими свойствами должны обладать модули?
  7.  В чем заключается смысл структурного кодирования? Какие элементарные структуры образуют функционально-полную систему? Как они работают?
  8.  Какие дополнительные элементарные структуры используются в структурном кодировании? Как они работают?

Задание на самостоятельную работу

  1.  Изучить материал лекции, представленный в электронной форме.
  2.  Ответить на контрольные вопросы.
  3.  Разработайте алгоритм программы, определяющей первые 10 чисел последовательности Фибоначчи, которая формируется следующим образом:

F1 = F2 = 1, Fn = Fn–1 + Fn–2, где n > 2.

Алгоритм представьте в виде схемы и запишите псевдокодом.

* Э.Дейкстра дал следующее определение: «Структурное программирование – это дисциплина, которую программист навязывает сам себе».


Приложение 1

Приложение n

Функция 1

Функция 2

Функция m

Подф-ция 11

Подф-ция 1k

Подф-ция m1

одф-ция m2

Подф-ция mp

Цель 1

Подцель 11

Подцель 1s

Цель 2

Подцель 21

Подцель 2q

Второй уровень иерархии программы

Первый уровень иерархии программы

Головной модуль

(программа-сервер)

Модуль управления 1

(Управл. прогр. 1)

Модуль управления n

(Управл. прогр. n)

Модуль 1A

(подпрогр. 1А)

Модуль 1В

(подпрогр. 1В)

Модуль 1W

(подпрогр. 1W)

Модуль 0A

(подпрогр. 0А)

Модуль 0B

(подпрогр. 0B)

Модуль nA

(подпрогр. nА)

Модуль nB

(подпрогр. nB)

Модуль nW

(подпрогр. nW)

Третий уровень иерархии программы

Рис. 4. Базовые алгоритмические структуры:

а) следование (BeginEnd); б) ветвление (IfThenElse); в) цикл с предусловием (WhileDo)

Рис. 5. Дополнительные элементарные алгоритмические структуры:

а) сокращенное ветвление (IfThen); б) выбор – иначе (CaseOfElse);
в) цикл с постусловием (RepeatUntil); г) цикл с параметром (ForTo (Downto) – Do)

Начало

y := arctg(a)

y := 0.9*ex

y := 1.7*e-x

с := 2

а := 3.14

х := -3

х := х + 1.5

z := c2x

x ≤ 3?

z ≥ 1?

z < -1?

Останов

Вывод

x, y

Да

Да

Нет

Нет

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Да

Нет

Да

Нет

f(x2)<y

3

Опред. х2

1

х2 := 1

2

Все

5

х2 := х2*2

4

Сократить отрезок [х1, х2]

3

Да

Нет

x1x2>

2

Определить х

1

Все

4

xt := (x1+ x2)/2

2

х2 := xt

5

Да

Нет

f(x2)>y

3

Сокр. [x1, x2]

1

Все

6

х1 := xt

4

Программа

1

Ввести

y, n,

2

Да

Нет

f(x1)>y

4

х1 := 1

3

х1 := х1/2

5

Да

Нет

f(x1)<y

7

х2 := 1

6

х2 := х1*2

8

xt := (x1+ x2)/2

10

х2 := xt

Да

Нет

f(x2)>y

11

х1 := xt

12

Да

Нет

x1x2>

9

Конец

15

Вывести

x, y

14

9

8


 

А также другие работы, которые могут Вас заинтересовать

45674. Политическая и социальная реклама 36 KB
  Политическая и социальная реклама. Политическая реклама используется как инструмент пропаганды определенных политических идей партий деятелей и т. Как и коммерческая реклама реклама политическая благодаря своей многотиражности многообразию возможности повторения лаконизму и эмоциональности обладает значительными возможностями воздействия на массовое сознание. Политическая реклама не только оправдана – она крайне необходима в нашем обществе.
45675. Рекламный бюджет организации 33.5 KB
  Интуитивный метод Первый метод интуитивный. Метод остаточных средств Еще один метод близкий к интуитивному метод остаточных средств или все что нам по карману. Остаточный метод не учитывает того что на разных этапах развития перед компанией могут стоять разные цели и задачи на достижение которых может просто не хватить средств. Процент от продаж Третьим в рейтинге популярности рекламодателей идет метод определения рекламного бюджета как процента от объема продаж иногда как процента от выручки или товарооборота.
45677. Рекламный текст как коммуникативная единица. Специфика рекламной коммуникации. Методика анализа рекламного текста 41.5 KB
  Рекламный текст как коммуникативная единица. Методика анализа рекламного текста. Сегодня не существует единства понимания что есть рекламный текст. Под рекламным текстом чаще подразумевают только его вербальный компонент.
45678. Разработка концепции и идеи рекламной кампании. Оценка эффективности рекламной кампании 40.5 KB
  Информативная реклама: преобладает на основном этапе выведения товара на рынок когда стоит задача создания первичного спроса. Увещевательная реклама: приобретает особую значимость на этапе роста когда перед фирмой встает задача формирования избирательного спроса. Напоминающая реклама: чрезвычайно важна на этапе зрелости чтобы заставить потребителей вспомнить о товаре. импульсивная подача – СМИ используются периодически через равные интервалы независимо от времени года; неравномерные импульсы – реклама размещается через неравные интервалы...
45679. Рекламная кампания 61 KB
  Итак рекламную кампанию следует планировать в следующей последовательности: Анализ маркетинговой ситуации; Определение целей рекламы; Определение целевой аудитории; Составление сметы расходов на рекламу и контроль за ее выполнением; Выбор средств распространения рекламы; Составление рекламного сообщения или текста. Цель рекламы как правило сводится к тому чтобы убедить потенциальных покупателей в полезности товара и привести к мысли о необходимости купить его. Таким образом исследования играют роль основного рабочего...
45680. Расчет технологической карты на монтаж внутриквартального теплопровода из предварительно изолированных пенополиуретаном труб по грунту 2.88 MB
  Монтаж – это комплексный процесс механизированной сборки сооружений из готовых элементов заводского изготовления, а выполняемые при этом работы – монтажные. Широкое применение сборных конструкций ставит задачу предусмотреть при их проектировании возможность изготовления, транспортирования и монтажа наиболее просто с наименьшими затратами труда и материальных средств.
45681. Понятие коммуникации 31.5 KB
  Понятие коммуникации Коммуникация: Коммуникация – взаимодействие между людьми посредством знаков размещённых в презентационных репрезантационных технических средствах распространяемых по определённым каналам в соответствии с выбранным кодом. Коммуникация для нас – взаимодейсвие субъектсубъектного типа. Коммуникация будет таковой при условии что информации имеет смысл для обоих субъектов=субстанция информационной природы.
45682. Типология социальной коммуникации 40 KB
  Типология социальной коммуникации Социальная коммуникация – это процесс в котором участвуют как минимум 2 социальных субъекта причём наличествует как факт передачи так и факт приёма информации причём со стороны источника передача осуществляется интенционно намеренно вербально невербально а со стороны получателя происходит приём этой информации как в осозновании так и вне осозновании.Неполноценная вырожденная ком.Мин колво участников – 2 – полноценная социальная комм.Природа участников комм.