Структурное программирование сверху-вниз и правильность программ

Размещено на http://www.allbest.ru/

КАБАРДИНО-БАЛКАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМ. Х.М. БЕРБЕКОВА

ИНСТИТУТ ФИЗИКИ И МАТЕМАТИКИ

КАФЕДРА ИНФОРМАТИКИ И МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ

АВТОМАТИЗИРОВАННЫХ СИСТЕМ

КУРСОВАЯ РАБОТА

Структурное программирование сверху-вниз и правильность программ

Выполнил студент 4 курса отделения

«Прикладная математика и информатика»

очной формы обучения И.В. Петькин

Научный руководитель к.т.н., доцент И.И. Кузьменко

Пятигорск 2015



Содержание

структурный программирование метод проектирование

Введение

1. История методологии структурного программирования

2. Цель структурного программирования

3. Спагетти-код

4. Оператор GoTo

5. Теорема о структурном программировании

6. Принципы структурного программирования

7. Метод «сверху вниз»

8. Достоинства структурного программирования

9. Ясность и удобочитаемость программ

10. Двумерное структурное программирование

11. Практическое использование метода проектирования сверху вниз

12. Пример проектирования сверху вниз

Список использованной литературы



Введение

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

В соответствии с данной методологией любая программа строится без использования оператора GoTo из трёх базовых управляющих структур: последовательность, ветвление, цикл; кроме того, используются подпрограммы. При этом разработка программы ведётся пошагово, методом «сверху вниз».

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

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

По мнению Бертрана Мейера, «Революция во взглядах на программирование, начатая Дейкстрой, привела к движению, известному как структурное программирование, которое предложило систематический, рациональный подход к конструированию программ. Структурное программирование стало основой всего, что сделано в методологии программирования, включая и объектное программирование» [1].

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

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

Рассматриваемый подход иногда называют “иерархической декомпозицией” из-за ступенчатой природы процесса.



1. История методологии структурного программирования

Первоначально идея структурного программирования появилась на свет в связи с оператором GoTo и сомнениями в целесообразности его применения. Впервые подобные сомнения высказал Хайнц Земанек (Heinz Zemanek) на совещании по языку Алгол в начале 1959 года в Копенгагене. Однако это выступление не привлекло к себе внимания и не имело последствий. Эдсгер Дейкстра (Edsger Dijkstra) вспоминает: «До некоторой степени я виню себя за то, что в то время не смог оценить значимость этой идеи» [2].

Ситуация коренным образом изменилась через десять лет, когда в марте 1968 года Дейкстра опубликовал своё знаменитое письмо «Оператор Go To считается вредным» (Go To Statement Considered Harmful). Это поистине исторический документ, оказавший заметное влияние на дальнейшее развитие программирования.

Судьба самого документа интересна. Дело в том, что Дейкстра дал статье совсем другое название: «Доводы против оператора GO TO» (A Case against the GO TO Statement).

Однако в момент публикации произошло нечто непонятное - статья превратилась в «Письмо к редактору», причем прежнее название исчезло. Что произошло на самом деле? Дейкстра объяснил превращение статьи в письмо лишь много лет спустя, в 2001 году:

«Журнал Communications of the ACM опубликовал мой текст под названием «Оператор GOTO считается вредным». В последующие годы его часто цитировали. К сожалению, зачастую это делали люди, которые видели в нём не больше, чем сказано в заголовке. Как все это случилось? Я отправил статью под названием «Доводы против оператора GO TO». Чтобы ускорить публикацию, редактор превратил мою статью в «Письмо к редактору». При этом он придумал для статьи новое название, которое изобрел сам. Редактором был Никлаус Вирт».

2. Цель структурного программирования

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

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

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

3. Спагетти-код

Спагетти-код (spaghetti code) - плохо спроектированная, слабо структурированная, запутанная и трудная для понимания программа, содержащая много операторов GoTo (особенно переходов назад), исключений и других конструкций, ухудшающих структурированность [3]. Самый распространённый антипаттерн программирования.

Спагетти-код назван так потому, что ход выполнения программы похож на миску спагетти, то есть извилистый и запутанный. Иногда называется «кенгуру-код» (kangaroo code) из-за множества инструкций jump.

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

Спагетти-код может быть отлажен и работать правильно и с высокой производительностью, но он крайне сложен в сопровождении и развитии [8]. Доработка спагетти-кода для добавления новой функциональности иногда несет значительный потенциал внесения новых ошибок. По этой причине становится практически неизбежным рефакторинг (code refactoring) - главное лекарство от спагетти.

4. Оператор GoTo

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

Впервые эта точка зрения была отражена в статье Эдсгера Дейкстры «Оператор Go To считается вредным». Дейкстра заметил, что качество программного кода обратно пропорционально количеству операторов GoTo в нём. Статья приобрела широкую известность, в результате чего взгляды на использование оператора GoTo были существенно пересмотрены. В работе «Заметки по структурному программированию» Дейкстра обосновал тот факт, что для кода без GoTo намного легче проверить формальную корректность.

Код с GoTo трудно форматировать, так как он может нарушать иерархичность выполнения (парадигму структурного программирования) и потому отступы, призванные отображать структуру программы, не всегда могут быть выставлены правильно. Кроме того, оператор GoTo мешает оптимизации компиляторами управляющих структур [11].

Некоторые способы применения GoTo могут создавать проблемы с логикой исполнения программы:

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

• Передача управления внутрь тела цикла приводит к пропуску кода инициализации цикла или первоначальной проверки условия.

• Аналогично, передача управления внутрь процедуры или функции приводит к пропуску её начальной части, в которой производится инициализация (выделение памяти под локальные переменные).

Доводы против оператора GoTo оказались столь серьёзными, что в структурном программировании его стали рассматривать как крайне нежелательный. Это нашло отражение при проектировании новых языков программирования. Например, GoTo запрещён в Java и Ruby. В ряде современных языков он всё же оставлен из соображений эффективности в тех редких случаях, когда применение GoTo оправданно. Так, GoTo сохранился в Аде - одном из наиболее продуманных с точки зрения архитектуры языков за всю историю [12].

Однако в языках высокого уровня, где этот оператор сохранился, на его использование, как правило, накладываются жёсткие ограничения, препятствующие использованию наиболее опасных методов его применения: например, запрещается передавать управление извне цикла, процедуры или функции внутрь. Стандарт языка C++ запрещает обход инициализации переменной с помощью GoTo.

5. Теорема о структурном программировании

Теорему сформулировали и доказали итальянские математики Коррадо Бём (Corrado Bцhm) и Джузеппе Якопини (Giuseppe Jacopini). Они опубликовали её в 1965 году на итальянском языке и в 1966 году на английском [13]. Наряду с теоремой, в статье Бёма и Якопини описывались методы преобразования неструктурных алгоритмов в структурные на примере созданного Бёмом языка программирования P??. Язык P?? - первый полный по Тьюрингу язык программирования без оператора GoTo.

Теорема Бёма-Якопини написана сложным языком и в непривычных обозначениях. Если использовать современную терминологию и обозначения, она примет вид:

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

• последовательность - обозначается: f THEN g,

• ветвление - обозначается: IF p THEN f ELSE g,

• цикл - обозначается: WHILE p DO f,

где f, g - блок-схемы с одним входом и одним выходом,

р - условие, THEN, IF, ELSE, WHILE, DO - ключевые слова [14].

Пояснение. Формула f THEN g означает следующее: сначала выполняется программа f, затем выполняется программа g.

Как отмечает Харлан Миллс (Harlan Mills), данная теорема резко контрастирует с обычной (в 1960-1970 годы) практикой программирования, когда наблюдалось массовое использование операторов перехода GoTo [14].

Бём и Якопини не употребляли термин «структурное программирование». Тем не менее, доказанную ими теорему (и её последующие вариации у разных авторов) впоследствии стали называть «Теоремой о структурном программировании», «Структурной теоремой» (Structure theorem [14]), «Теоремой о структурировании» [15].

6. Принципы структурного программирования

Становление и развитие структурного программирования связано с именем Эдсгера Дейкстры [10].

Принцип 1. Следует отказаться от использования оператора безусловного перехода GoTo.

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

• Последовательность - однократное выполнение операций в том порядке, в котором они записаны в тексте программы. Бертран Мейер поясняет: «Последовательное соединение: используйте выход одного элемента как вход к другому, подобно тому, как электрики соединяют выход сопротивления со входом конденсатора» [17].

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

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

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

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

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

Бертран Мейер поясняет: «Преобразуйте элемент, возможно, с внутренними элементами, в подпрограмму, характеризуемую одним входом и одним выходом в потоке управления».

Принцип 5. Каждую логически законченную группу инструкций следует оформить как блок (block). Блоки являются основой структурного программирования.

Блок - это логически сгруппированная часть исходного кода, например, набор инструкций, записанных подряд в исходном коде программы. Понятие блок означает, что к блоку инструкций следует обращаться как к единой инструкции. Блоки служат для ограничения области видимости переменных и функций. Блоки могут быть пустыми или вложенными один в другой. Границы блока строго определены. Например, в if-инструкции блок ограничен кодом BEGIN..END (в языке Паскаль) или фигурными скобками {...} (в языке C) или отступами (в языке Питон).

Принцип 6. Все перечисленные конструкции должны иметь один вход и один выход.

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

Принцип 7. Разработка программы ведётся пошагово, методом «сверху вниз» (top-down method) [5].

7. Метод «сверху вниз»

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

Если говорить точнее, заглушка удовлетворяет требованиям интерфейса заменяемого фрагмента (модуля), но не выполняет его функций или выполняет их частично. Затем заглушки заменяются или дорабатываются до настоящих полнофункциональных фрагментов (модулей) в соответствии с планом программирования. На каждой стадии процесса реализации уже созданная программа должна правильно работать по отношению к более низкому уровню. Полученная программа проверяется и отлаживается [12].

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

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

При сопровождении и внесении изменений в программу выясняется, в какие именно процедуры нужно внести изменения. Они вносятся, не затрагивая части программы, непосредственно не связанные с ними. Это позволяет гарантировать, что при внесении изменений и исправлении ошибок не выйдет из строя какая-то часть программы, находящаяся в данный момент вне зоны внимания программиста [9].

Следует также учесть, что в «Предисловии» к книге «Структурное программирование» Хоар (Hoare) отмечает, что принципы структурного программирования в равной степени могут применяться при разработке программ как «сверху вниз», так и «снизу вверх».

8. Достоинства структурного программирования

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

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

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

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

9. Ясность и удобочитаемость программ

Структурное программирование значительно повышает ясность и удобочитаемость (readability) программ]. Эдвард Йордан (Edward Yourdon) поясняет:

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

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

Улучшение читабельности структурных программ объясняется тем, что отсутствие оператора GoTo позволяет читать программу сверху донизу без разрывов, вызванных передачами управления. В итоге можно сразу (одним взглядом) обнаружить условия, необходимые для модификации того или иного фрагмента программы.

10. Двумерное структурное программирование

Р-технология производства программ, или «технология двумерного программирования» была создана в Институте кибернетики имени В. М. Глушкова. Графическая система Р-технологии программирования закреплена в международном стандарте ISО 8631Н.

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

Методология двумерного структурного программирования существенно отличается от классического одномерного (текстового) структурного программирования.

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

С появлением компьютерной графики ситуация изменилась. Используя выразительные средства графики, появилась возможность видоизменить, развить и дополнить три типа базовых (текстовых) управляющих структурных конструкций, а также полностью отказаться от ключевых слов if, then, else, case, switch, break, while, do, repeat, until, for, foreach, continue, loop, exit, when, last и т. д. и заменить их на управляющую графику, то есть использовать двумерное структурное программирование.

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

11. Практическое использование метода проектирования сверху вниз

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

Однако в этой связи возникает фундаментальный вопрос: что же такое наиболее абстрактное описание системы? Ести спецификация написана правильно, то оно ясно определено; если же нет, то вопрос остается открытым и проектировщик вынужден строить дерево программы, не имея возможности найти вершину. Например, один из проектов операционной системы реального времени, выполненный, по словам проектировщика, с помощью метода сверху вниз, имел в качестве вершины структуру прерываний ЭВМ в реальном времени. Очевидно, что этот специальный аспект систем реального времени является вершиной не в большей степени, чем, скажем, задача обслуживания пользователей, решаемая операционной системой. Здесь только создается видимость проектирования сверху вниз, так как отсутствуют присущие ему черты. (Это не значит, что проект ошибочен, просто метод проектирования сверху вниз здесь ни при чем.)

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

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



12. Пример проектирования сверху вниз

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

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

Рассмотрим два варианта уточнения задачи:

Вариант 1. Поле коэффициентов - поле рациональных чисел. Элемент этого поля - либо целое число A, либо несократимая дробь вида A/B, где знаменатель B - натуральное число, а числитель A - целое число. Требуется найти точное решение системы.

Вариант 2. Поле коэффициентов - поле вещественных чисел. Элемент этого поля - число типа Real. Требуется найти приближенное решение системы с указанной точностью. В нашем случае имеют место следующие ограничения:

- коэффициенты уравнений системы - рациональные числа;

- необходимо получить точное решение системы в виде набора рациональных чисел;

- всегда существует единственное решение системы;

- количество уравнений системы и количество неизвестных совпадают.

На первом шаге уточняем задачу в виде:

Program LinearSystem;

Type Solution =...; LinSys =...;

Var S: LinSys; X: Solution; n: Integer;

Procedure SysInp(var A: LinSys);

Begin {ввод системы уравнений A}

End;

Procedure SysSol(A: LinSys; var Y: Solution);

Begin {решение Y системы уравнений A}

End;

Procedure SolOut(Y: Solution);

Begin {вывод решения Y}

End;

BEGIN {основная программа}

SysInp(S); SysSol(S, X); SolOut(X)

END. {конец программы LinearSystem}

На следующем шаге уточнения возникает проблема выбора метода решения и уточнения структуры данных задачи. Известным точным методом решения систем линейных уравнений является метод Гаусса последовательного исключения неизвестных. Основные шаги метода - выбор ведущего уравнения и ведущего неизвестного и исключение ведущего неизвестного из остальных уравнений системы. Учебники по линейной алгебре рекомендуют представлять данныe в виде n*(n+1) матрицы коэффициентов системы

x1 x2 . . . xn Cв. член

a11 a12 . . . a1n b1

a21 a22 . . . a2n b2

… … … … …

an1 an2 . . . ann bn

Поскольку параметр n зависит от задачи, для представления матрицы A в виде двумерного массива требуется резервировать память под массив некоторого наибольшего возможного размера Nmax, что приводит к неоправданным расходам оперативной памяти. Радикальное решение состоит в использовании динамических структур данных. Систему можно представить в виде списка уравнений, а каждое уравнение - списком слагаемых (членов уравнения):

LinSys = ^LS_Item; {список уравнений}

LS_Item = Record

LS_Mem: LinEqu; NextEqu: LinSys

End;

LinEqu = ^EquItem; {список членов уравнения}

EquItem = Record

EquMem: Monom; NextMem: LinEqu

End;

Компромиссное решение - динамическое резервирование памяти под массив A: LinSys = ^Array[1..Nmax, 1..Nmax] of Rational; {Rational - рациональные числа}

Выберем радикальный путь решения и уточним процедуры SysInp, SysSol, SolOut. Наш выбор определяет Solution как список рациональных чисел.

Procedure SysInp(var A: LinSys);

Var i: Integer; P: LinSys;

Begin {ввод системы уравнений A}

Read(n); S:= Nil;

For i:= 1 to n do

begin Nеw(P); P^.NextEqu:= S; S:= P;

{ввод i-того уравнения - списка P^.LS_Mem}

end

End;

Procedure SysSol(A: LinSys; var Y: Solution);

Begin {решение Y системы уравнений A}

For i:= 1 to n do

begin {прямой ход метода Гаусса - выбор уравнения, содержащего

ненулевой коэффициент при Xi в качестве ведущего;

-перестановка местами i-того и ведущего}

For j:= 1 to n do

If i <> j then - исключение Xi из j-того уравнения

end;

For i:= n downto 1 do {обратный ход метода Гаусса}-вычисление Xi;

End;

Procedure SolOut(Y: Solution);

Var i: Integer;

Begin {вывод решения Y}

For i:= 1 to n do {Вывод i-той компоненты решения}

Writeln(' Задача решена ')

End;

Следующее уточнение структуры данных состоит в определении типа Monom. Если мы решим продолжить тактику экономии памяти, можно не хранить члены уравнения вида Aij*Xi при Aij = 0. В этом случае члены уравнения представляются парой <коэффициент, номер неизвестного>: Monom = Record

Coef: Rational;

Unknown: Integer

End;

Для упрощения структуры данных изменим определение типа EquItem, исключив тип Monom:

EquItem = Record

Coef: Rational; Unknown: Integer; NextMem: LinEqu

End;

Теперь процедуру ввода уравнения реализуем как локальную в процедуре SysInp. Ввод уравнения - это ввод левой и правой частей уравнения, отделенных друг от друга вводом знака "=". Ввод левой части - повторение вводов членов уравнения, отделенное друг от друга вводом знака "+".

Procedure SysInp(var A: LinSys);

Var i: Integer; P: LinSys;

Procedure EquInp(Var E: LinEqu);

Var Q: LinEqu; Sign: Char;

Procedure MemInp(var R: LinEqu);

{ тело процедуры MemInp }

Begin Writeln('Ввод первого члена левой части'); MemInp(Q);

E:= Q; Write('Нажми = или +'); Sign:= ReadKey;

While Sign = '+' do

begin Writeln('Ввод следующего члена уравнения');

MemInp(Q^.NextMem);

Q:= Q^.NextMem; Write('Нажми = или +'); Sign:=ReadKey

end;

Writeln('Ввод свободного члена уравнения'); MemInp(Q^.NextMem);

Q:= Q^.NextMem;

Q^.NextMem:= Nil

End;{процедуры ввода уравнения}

Begin {ввод системы уравнений A}

Read(n); S:= Nil;

For i:= 1 to n do

begin Nеw(P); P^.NextEqu:= S; S:= P; EquInp(P^.LS_Mem}

end

End;

Раздел операторов процедуры SysInp приобрел законченный вид. Ввод члена уравнения оформим в виде процедуры MemInp, введя тип Rational, значениями которого являются рациональные числа. Введение численного типа Rational означает необходимость реализации набора процедур, обеспечивающих работу с рациональными числами. Поскольку тип Rational необходим для решения многих других задач, его следует оформить как модуль RAT и активизировать в программе директивой Uses. Принципы проектирования модуля мы рассмотрим ниже. Сейчас нам понадобятся только имена процедур ввода и вывода рациональных чисел - RatInp и RatPrint.

Procedure MemInp(var R: LinEqu);

Begin New(R);

With R^ do

begin RatInp(Coef);

If Sign <> '=' then Read(UnkNown) else UnkNown:= n + 1

end

End;

Наш алгоритм решения системы (процедура SysSol) превратит список уравнений в список пар вида «номер неизвестного, значение неизвестного». Поэтому для вывода решения системы нет необходимости формировать список X. Достаточно установить ссылку X типа LinSys на S и вывести значение X в требуемом виде. Это означает, что тип Solution можно исключить, сделав соответствующие изменения в заголовках процедур.

Procedure SysSol(A: LinSys; var Y: LinSys);

Procedure SolOut(Y: LinSys);

Уточним процедуру вывода решения:

Procedure SolOut(Y: LinSys);

Var i: Integer; P: LinSys;

Begin {вывод решения Y}

P:= Y;

For i:= 1 to n do

begin {Вывод i-той компоненты решения }

With P^, LS_Mem^ do

begin

Writeln('X[',i,'] = '); RatPrint(Coef)

end;

P:= P^.NextEqu

end;

Writeln(' Задача решена ')

End;

Мы закончили проектирование процедур ввода-вывода с точностью до средств модуля RAT. Продолжим уточнение основной процедуры программы - процедуры SysSol.

Procedure SysSol(A: LinSys; var Y:LinSys);

Var P, Q: LinSys; TempRef: LinEqu; i: Integer;

Begin {решение Y системы уравнений A} P:= A;

For i:= 1 to n do begin {прямой ход метода Гаусса}

{выбор ведущего уравнения} Q:= P;

While Q^.LS_Mem^.Unknown <> i do Q:= Q^.NextEqu;

{перестановка местами i-того и ведущего}

TempRef:= P^.LS_Mem; P^.LS_Mem:= Q^.LS_Mem;

Q^.LS_Mem:= TempRef; {исключение Xi из уравнений системы}

{1. нормализация ведущего уравнения}

{2. исключение Xi из верхней части системы}

{3. исключение Xi из нижней части системы}

P:= P^.NextEqu;

end;

Y:= A;

End;

Для выбора ведущего уравнения используется последовательный просмотр уравнений системы с помощью ссылки Q. Единственность решения системы гарантирует существование ведущего уравнения - уравнения с ненулевым коэффициентом при Xi. Перестановка уравнений осуществляется переброской ссылок P^.LS_Mem и Q^.LS_Mem. Основная часть алгоритма - исключение неизвестного Xi. Она состоит из шагов 1, 2, 3, выполняемых последовательно.

Шаг 1 - нормализация ведущего уравнения, т.е. деление всех членов уравнения на коэффициент при Xi.

Шаг 2 - исключение Xi из верхней части системы. j-е уравнение верхней части (j < i) имеет вид Xj + Aji1*Xi1 +... + Ajik*Xik = Bj, причем i1 >= i поскольку оно нормализовано и неизвестные Xk, k < i, исключены на предыдущих шагах основного цикла. Поэтому исключение осуществляется при i1 = i. Нужно домножить ведущее уравнение на Aji1 и вычесть его из j-того уравнения.

Шаг 3 - исключение Xi из нижней части системы. j-тое уравнение нижней части (j > i) имеет вид Aji1*Xi1 +... + Ajik*Xik = Bj, причем i1 >= i. Исключение осуществляется точно также, как и на шаге 2. Шаги 2 и 3 настолько схожи, что естественно было бы реализовать их одной и той же процедурой. Для этого необходимо всего лишь реализовать одинаковое представление уравнений из нижней и верхней частей системы, т.е. не хранить в списке уравнения верхней части системы соответствующий ведущий член Xj. Таким образом, на выходе шага 1 - процедуры нормализации мы должны получить "хвост" Aji1*Xi1 +... + Ajik*Xik = Bj нормализованного уравнения.

Основная часть алгоритма будет выглядеть так:

{исключение Xi из уравнений системы}

{нормализация i-того уравнения и получение "хвоста"}

EquNorm(P); Q:= A;

For j:= 1 to n do

begin If i<>j then If Q^.LS_Mem^.Unknown=i {исключение Xi из j-того

уравнения} then EquTrans(Q, P); Q:= Q^.NextEqu

end;

В нашей версии метода Гаусса та его часть, которую называют обратным ходом, совмещена с прямым ходом метода. Мы приводим матрицу системы сразу к диагональному виду. Процедура SysSol приобрела законченный вид. Осталось уточнить процедуры EquNorm(P) и EquTrans(Q, P), которые обрабатывают отдельные уравнения.

{нормализация уравнения и выделение "хвоста"}

Procedure EquNorm(var P: LinSys);

Var LCoef: Rational; TempRef:LinEqu;

Begin TempRef:= P^.LS_Mem; New(LCoef);

LCoef^:= TempRef^.Coef^; {ведущий коэффициент }

{установка ссылки на «хвост» уравнения}

P^.LS_Mem:= P^.LS_Mem^.NextMem;

Dispose(TempRef); {сборка мусора}

TempRef:= P^.LS_Mem; {инициализация цикла}

Repeat TempRef^.Coef:= DivRat(TempRef^.Coef, LCoef);

TempRef:= TempRef^.NextMem {следующий член}

until TempRef = Nil;

Dispose(LCoef)

End {процедуры нормализации};

Наиболее интересна с точки зрения техники программирования процедура EquTrans элементарного преобразования линейного уравнения E1 c с помощью ведущего уравнения E2. E1:= E1 - C*E2 Если бы уравнения были представлены массивами коэффициентов, это преобразование реализовалось бы с помощью одного арифметического цикла. В нашей же структуре данных необходимо реализовать преобразование списков. Пусть уравнения имеют вид E1 = A1*X + T1, E2 = A2*Y + T2, где A1*X, A2*Y - первые члены списков (головы), а T1 и T2 - хвосты списков. Возможны следующие случаи:

Случай 1. Неизвестные X и Y одинаковы. Тогда: Если A1 - C*A2 <> 0 то (A1*X + T1) - С*(A2*X + T2) = (A1-C*A2)*X + (T1 - C*T2) иначе (A1*X + T1) - С*(A2*X + T2) = (T1 - C*T2)

Случай 2. Номер X меньше, чем номер Y. Тогда: (A1*X + T1) - С*(A2*X + T2) = A1*X + (T1 - C*E2)

Случай 3. Номер X больше, чем номер Y. Тогда: (A1*X + T1) - С*(A2*X + T2) = (-C*A2)*Y + (E1 - C*T2)

В каждом из этих случаев правая часть соответствующего соотношения - равенства есть сумма (голова + хвост) результирующего уравнения, причем вычисление хвоста легко организовать с помощью рекурсии и чуть сложнее - итерации. Признак окончания вычислений - свободные члены в головах списков и отсутствие хвостов. Перед применением описанного алгоритма (процедура EquDiff) вычисляется множитель C и из преобразуемого уравнения удаляется первый член. Все вычисления сопровождаются "сборкой мусора" - освобождением памяти, занимаемой удаляемыми членами.

Procedure EquTrans(var Q: LinSys; P: LinSys);

Var LCoef: Rational; CurP, CurQ: LinEqu;

Procedure EquDiff(var RefQ, RefP: LinEqu; C: Rational);

Var NextP, NextQ: LinEqu; NextC: Rational; II,JJ: Integer;

Finish: Boolean; {Удаление члена уравнения с нулевым коэффициентом} Procedure MemDel(var RefQ: LinEqu);

Var TempRef: LinEqu;

Begin TempRef:= RefQ^.NextMem;

RefQ^.NextMem:= RefQ^.NextMem^.NextMem;

RefQ^.Coef:= TempRef^.Coef;

RefQ^.Unknown:= TempRef^.UnkNown;

Dispose(TempRef) {сборка мусора}

End {процедуры удаления члена уравнения}; {вставка члена уравнения} Procedure MemInc(var RefQ, RefP: LinEqu; C: Rational);

Var C0: Rational; TempRef: LinEqu;

Begin New(TempRef); TempRef^.Coef:= RefQ^.Coef;

RefQ^.Coef:= MinusRat(MultRat(RefP^.Coef, C));

TempRef^.Unknown:= RefQ^.UnkNown;

RefQ^.Unknown:= RefP^.Unknown;

TempRef^.NextMem:= RefQ^.NextMem;

RefQ^.NextMem:= TempRef; RefQ:= TempRef

End {процедуры вставки члена уравнения};

Begin NextQ:= RefQ; {указатели на голову списка} NextP:= RefP;

Finish:= False; {признак окончания вычислений} Repeat

II:= NextQ^.Unknown; {номера неизвестных}

JJ:= NextP^.Unknown; {случай 1 и случай окончания вычислений}

If II = JJ then

begin {вычисление коеффициента уравнения}

NextC:= SubRat(NextQ^.Coef, MultRat(NextP^.Coef, C));

If II = n + 1 then

begin NextQ^.Coef:= NextC; Finish:= True end

else {случай 1}

if NextC^.Num <> 0 then

begin NextQ^.Coef:= NextC; NextQ:= NextQ^.NextMem;

NextP:= NextP^.NextMem

end

else begin MemDel(NextQ); NextP:= NextP^.NextMem end

end

else if II < JJ then {случай 2} NextQ:= NextQ^.NextMem

else begin {случай 3} MemInc(NextQ, NextP, C); NextP:= NextP^.NextMem

end

until Finish

End {процедуры EquDiff преобразования уравнения};

Begin {подготовка к вызову процедуры EquDiff}

CurQ:= Q^.LS_Mem; СurP:= P^.LS_Mem;

New(LCoef); Lcoef^:=CurQ^.Coef^;

Q^.LS_Mem:=Q^.LS_Mem^.NextMem;

Dispose(CurQ); CurQ:= Q^.LS_Mem; EquDiff(CurQ, CurP, LCoef)

End {исключения неизвестного};

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

Список использованной литературы

1. Мейер Б. Почувствуй класс. Учимся программировать хорошо с объектами и контрактами. Пер. с англ. М.: Национальный открытый университет ИНТУИТ: БИНОМ. Лаборатория знаний, 2011. 775с. С. 208.

2. Дейкстра Э. Оператор GoTo считается вредным. Dijkstra E. Go To Statement Considered Harmful // Communications of the ACM, Volume 11, No. 3, March 1968, pp. 147-148.

3. Лингер Р., Миллс Х., Уитт Б. Теория и практика структурного программирования. Пер. с англ. М.: Мир, 1982. 406с. С. 7.

4. Дейкстра Э. Заметки по структурному программированию. // Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975. С. 7-97.

5. Бутаков Е. А. Методы создания качественного программного обеспечения ЭВМ. М.: Энергоатомиздат, 1984. 232с. С. 114.

6. Гласс Р. Руководство по надежному программированию. М.: Финансы и статистика, 1982. 256с. С. 84.

7. Хьюз Дж., Мичтом Дж. Структурный подход к программированию. М.: Мир, 1980. 278c. С. 29-71.

8. Вирт Н. Систематическое программирование. Введение. М.: Мир, 1977. 184с. С. 139-168.

9. Гласс Р. Руководство по надежному программированию. М.: Финансы и статистика, 1982. 256с. С. 83-87.

10. Лингер Р., Миллс Х., Уитт Б. Теория и практика структурного программирования. М.: Мир, 1982. 406с. С. 324-327.

11. Иванова Г.С., Ничушкина Т.Н. Проектирование программного обеспечения. Учебное пособие по выполнению и оформлению курсовых, дипломных и квалификационных работ. М.: Московский государственный технический университет им. Н.Э. Баумана. Факультет Информатики и систем управления, 2002. 74 с. С. 28-31.

12. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975. 247 c.

13. Хоор К. Предисловие // Дал У., Дейкстра Э., Хоор К. М.: Мир, 1975. 247 c. С. 6.

14. Йодан Э. Структурное проектирование и конструирование программ. Пер. с англ. М.: Мир, 1979. 415 с. С. 174.

15. Пышкин Е. В. Структурное проектирование: основание и развитие методов. С примерами на языке C++: Учеб. пособие. СПб.: Политехнический университет, 2005. 324 с.

Размещено на Allbest.ru

...