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

Содержание

Введение

Глава 1 принципы структурной алгоритмизации

Глава 2  Требования и преимущества структурной алгоритмизации

Глава  3 Базовый набор структур для построения алгоритма

3.1  Линейные и разветвляющиеся  структуры

3.2 Ветвящейся структурой

3.3  Организация циклических  структур алгоритма

Заключение

Библиографический список

 

 

 

 

 

 

 

 

 

Введение

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

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

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

 

Глава 1 ПРИНЦАПЫ СТРУКТУРНОЙ АЛГОРИТМИЗАЦИИ

Английский математик Чарлз Бэббидж (Charles Babbage, 1792-1871) выдвинул идею создания программно-управляемой счетной машины, имеющей арифметическое устройство, устройство управления, ввода и печати.

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

Одновременно с английским ученым работала леди Ада Лавлейс (Ada Byron, Countess of Lovelace, 1815-1852 гг.), дочь известного английского поэта лорда Байрона. Она разработала первые программы для машины, заложила многие идеи и ввела ряд понятий и терминов, сохранившихся до настоящего времени. Именно ее многие считают первым программистом в мире. В ее честь один из процедурных языков программирования, разработанный в США в 1969 г. был так и назван — АДА.

Свое понятие программистской  деятельности ввели инженеры, обслуживающие  цифровой компьютер «Марк-1» в  Гарвардском университете (1944 г.). При  написании программ для вычисления артиллерийских баллистических таблиц впервые стали применять многократно  используемые последовательности —  подпрограммы. Устранение неисправности, вызванной попаданием мотылька (bug —  насекомое) в электрические цепи машины, привело к появлению понятия  «отладка» (debugging), которое используется сейчас для обозначения поиска неисправностей в компьютере и его программном обеспечении. Впервые была предложена программа- компоновщик как вспомогательное средство для создания других программ из нескольких различных подпрограмм ... и т.д.

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

Значительный вклад в  теорию программирования внес научный  сотрудник фирмы «Барроуз» (Burroughs), голландский ученый Эдсгер Дийкстра. В 1968 г. в работе под названием  «Заметки по структурному программированию»  он доказал, что большинство программ неоправданно сложны из-за отсутствия в них четкой математической структуры. По мнению Дийкстры, использование  трех типов управляющих структур — простой последовательности, альтернативы и повторения — позволило бы программистам обходиться без операторов безусловного перехода (goto) и тем самым преодолеть сложность и запутанность программ, добиться простоты их модификации. Проверку программ Дийкстра предложил производить математическими методами, а не просто тестированием, которое, по его мнению, может показать лишь наличие ошибок, а не их отсутствие.

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

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

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

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

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

Структурная алгоритмизация основывается на двух принципах:

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

Можно перечислить основные свойства и достоинства структурного программирования:

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

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

1. Начало.

2. Список данных: данные: тип; … ; данные: тип.

3. Ввод (исходные данные).

4. Вывод (исходные данные).

5. Обработка результатов испытаний.

6. Оценка надежности двигательной  установки.   

7. Выбор оптимальных параметров.

8. Вывод (результат).

9. Конец.

Затем следует определить, какие из использованных нами конструкций  «понятны» компьютеру, имеющемуся в  нашем распоряжении. Дело в том, что  алгоритм может быть реализован в  компьютере, если он содержит только элементарные предписания и структуры, входящие в базовый набор (о них речь пойдет ниже). Элементарными, т.е. не требующими детализации, мы будем считать следующие предписания или операции: Начало; Конец; Список данных; Ввод; Вывод; вычислительные операции, реализуемые операторами присваивания (:=). Сложные конструкции, которые компьютер не может реализовать сразу, разбиваются на более простые. Например, предписание 5 для рассматриваемого алгоритма может быть записано так:

5.1.  Начало 5.

5.2.  Операции, раскрывающие смысл обработки результатов.                                                                        

5.N. Конец 5.

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

Предписания 1 — 4 и 8 — 9, как правило, присутствуют в каждом алгоритме, разрабатываемом методом структурной алгоритмизации.

 

Глава 2 ТРЕБОВАНИЯ  И ПРЕИМУЩЕСТВА   СТРУКТУРНОЙ АЛГОРИТМИЗАЦИИ

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

Структурная алгоритмизация основывается на двух принципах:

1. последовательная детализация «сверху-вниз»
2. ограниченность базового набора структур для построения алгоритмов любой степени сложности.

Из принципов вытекают требования структурного программирования:

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

 

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

Можно перечислить основные свойства и достоинства структурного программирования:

1. Возможность преодоления барьера с ложности программ.
2. Возможность демонстрации правильности программ на различных этапах решения задачи.

 

 

 

Глава 3 БАЗОВЫЙ НАБОР СТРУКТУР ДЛЯ

ПОСТРОЕНИЯ АЛГОРИТМА

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

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

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

3.1 Линейные и разветвляющиеся структуры

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

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

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

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

X:=A;

которая читается следующим  образом: «Переменной X присвоить значение, равное результату, полученному при  вычислении по формуле A». В этом предписании: X — переменная; A — может быть любым, сколь угодно сложной математической формулой. В процессе выполнения этого  предписания компьютером A вычисляется, и результат вычисления присваивается  содержимому ячейки памяти (помещается в эту ячейку), отведенной для  хранения переменной X. При этом переменная X теряет свое предыдущее значение и  приобретает новое. Таким образом, символ «:=» употребляется как  предписание «присвоить». Как следствие  этого, бессмысленное, с точки зрения алгебры, выражение: