Алгоритмы структуры алгоритмов структурное программирование 10 класс семакин презентация

Структурированное программирование-это парадигма программирования. Направленная на повышение ясности. Качества и времени разработки компьютерной программы путем широкого использования структурированных конструкций потока управления. Таких как выбор (if/then/else) и повторение (while и for), блочные структурыи подпрограммы.

Он появился в конце 1950-х годов с появлением языков программирования ALGOL 58 и ALGOL 60[1], причем последний включал поддержку блочных структур. Факторов, влияющих на популярность и широкое распространение. Сначала в академических кругах и среди практиков. Включает открытие того. Что сейчас известно как

теорема структурированную программу в 1966 году[2] и в публикации влиятельной Edsger В. Дейкстра, который ввел термин

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

Элементы

Структуры управления

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

  • Обычно это выражается такими ключевыми словами. Как if..then..else..endif. Условный оператор должен иметь по крайней мере одно истинное условие. И каждое условие должно иметь одну точку выхода при макс.

  • Это обычно выражается такими ключевыми словами, какwhile,repeat, forили do..until. Часто рекомендуется. Чтобы каждый цикл имел только одну точку входа (и в оригинальном структурном программировании также только одну точку выхода. И несколько языков обеспечивают это).
  • Хотя на практике рекурсивные циклы аналогичны итеративным циклам. Они могут быть более эффективными с вычислительной точки зрения и по-разному реализованы в виде каскадного стека.

Подпрограммы

Подпрограммы; вызываемые единицы. Такие как процедуры, функции. Методы или подпрограммы. Используются для того. Чтобы на последовательность можно было ссылаться одним оператором.

Блоки

Блоки используются для того. Чтобы группы операторов обрабатывались. Как если бы они были одним оператором. Блочно-структурированные языки имеют синтаксис для включения структур некоторым формальным способом, например оператор if , заключенный в квадратные скобки , if..fiкак в ALGOL 68, или раздел кода. Заключенный в квадратные скобкиBEGIN..END, как в PL/I и Pascal, отступы пробелов. Как в Python, или фигурные скобки {...}C и многих более поздних языков.

Структурированные языки программирования

Структурированное программирование возможно на любом языке программирования. Хотя предпочтительнее использовать что-то вроде процедурного языка программирования. Некоторые из языков . Первоначально используемых для структурированного программирования , включают: ALGOL, Pascal, PL/I и Ada, но большинство новых процедурных языков программирования с тех пор включили функции. Поощряющие структурированное программирование. И иногда намеренно упускали функции – особенно GOTO – в попытке сделать неструктурированное программирование

более сложным. Структурированное программирование (иногда известное как модульноепрограммирование]) обеспечивает логическую структуру написанной программы. Чтобы сделать ее более эффективной и простой для понимания и изменения.

Теоретические основы

Теорема о структурированной программе обеспечивает теоретическую основу структурированного программирования. Он утверждает. Что для выражения любой вычислимой функции достаточно трех способов объединения программ—последовательности. Выбора и итерации . Это наблюдение не связано с движением структурированного программирования; эти структуры достаточны для описания цикла

команд центрального процессора, а также работы машины Тьюринга Следовательно. Процессор всегда выполняет Однако авторы обычно приписывают этот результат работе Бема и Якопини 1966 года. Возможно, потому, что Дейкстра сам цитировал эту работу[4]. Теорема о структурированной программе не описывает. Как написать и проанализировать хорошо структурированную программу. Эти вопросы рассматривались в конце 1960-х и начале 1970-х годов с большим вкладом Дейкстры, Роберта У. Флойд, Тони Хоар, Оле-Йохан Дальи Дэвид Грайс.

Дебаты

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

Нас преобразует махнул эту интересную новость под носом у неисправимый языка ассемблера программистов. Которые продолжали нестись вперед извилистой биты логики и говорит: ‘Я думаю. Не могу структура это.’ Ни доказательства по Бем и Jacopini. Ни наши неоднократные успехи на написание структурированного кода. Вывел их раньше. Чем они были готовы убедить самих себя.[5]

Дональд Кнут принял принцип. Согласно которому программы должны быть написаны с учетом доказуемости. Но он не согласился (и до сихпор не согласен) с отменой утверждения GOTO.

В своей статье 1974 года [6] он привел примеры, в которых. По его мнению. Прямой скачок приводит к более четкому и эффективному коду. Не жертвуя доказуемостью. Кнут предложил более слабое структурное ограничение: должно быть возможно нарисовать блок-схему программы все прямые ветви слева. Все обратные ветви справа. И ни одна ветвь не пересекает друг друга. Многие из тех. Кто хорошо разбирается в компиляторах и теории графов, выступали за то. Чтобы допускать только приводимые потоковые графы[когда они определяются как?].[кто?]

Теоретики структурированного программирования обрели главного союзника в 1970-х годах после

того, как исследователь IBM Харлан Миллс применил свою интерпретацию теории структурированного программирования к разработке системы индексации для исследовательского файла New York Times. Этот проект имел большой инженерный успех. И менеджеры других компаний цитировали его в поддержку принятия структурированного программирования. Хотя Дейкстра критиковал то. Как интерпретация Миллса отличалась от опубликованной работы.]

Еще в 1987 году можно было поставить вопрос о структурированном программировании в журнале по информатике. Фрэнк Рубин сделал это в том же году с открытым письмом под названием

[7] Последовали многочисленные возражения. В том числе ответ Дийкстры. Который резко критиковал как Рубина. Так и уступки. Сделанные другими писателями при ответе на него.

Результат

К концу 20-го века почти все компьютерщики были убеждены. Что полезно изучать и применять концепции структурированного программирования. Высокоуровневые языки программирования. В которых изначально отсутствовали структуры программирования . Такие как FORTRAN, COBOLи BASIC, теперь имеют их.

Общие отклонения

Хотя goto в настоящее время в значительной степени заменен структурированными конструкциями выбора (if/then/else) и повторения (while и for). Лишь немногие языки являются чисто структурированными.

Наиболее распространенным отклонением. Встречающимся во многих языках. Является использование оператора return для раннего выхода из подпрограммы. Это приводит к появлению нескольких точек выхода вместо одной точки выхода. Требуемой структурированным программированием. Существуют и другие конструкции для обработки случаев. Неудобных в чисто структурированном программировании.

Ранний выход

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

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

Несколько выходов могут возникать по разным причинам. Чаще всего либо из-за того. Что подпрограмме больше нечего делать (если она возвращает значение, она завершила вычисление), либо из-за

Наиболее распространенной проблемой при раннем выходе является то. Что операторы cleanup или final не выполняются – например. Выделенная память не освобождается или открытые файлы не закрываются. Что приводит к утечке памяти или утечке ресурсов. Это должно быть сделано на каждом возвратном сайте. Который хрупок и может легко привести к ошибкам. Например, в более поздней разработке оператор return может быть упущен разработчиком. И действие. Которое должно быть выполнено в конце подпрограммы (например,

оператор trace). Может быть выполнено не во всех случаях. Языки без оператора return, такие как стандартный Pascal и Seed7, нет этой проблемы.

Большинство современных языков обеспечивают языковую поддержку для предотвращения таких утечек; см. Подробное обсуждение в разделе управление ресурсами. Чаще всего это делается с помощью защиты от размотки. Которая гарантирует. Что определенный код гарантированно будет запущен при выходе из блока выполнения; это структурированная альтернатива наличию блока очистки и a

goto. Это чаще всего известно как try...finally,и считается частью обработки исключений. В случае введения нескольких returnоператоров try...finally, все без исключения могут выглядеть странно. Существуют различные методы инкапсуляции управления ресурсами. Альтернативный подход. Найденный в основном в C++. Заключается в том . Что Сбор ресурсов-это инициализация, которая использует обычное раскручивание стека (освобождение переменных) при выходе функции для вызова деструкторов локальных переменных для освобождения ресурсов.

Кент Бек, Мартин Фаулер и соавторы утверждали в своих

книгах по рефакторингу. Что вложенные условные выражения могут быть более трудными для понимания. Чем определенный тип более плоской структуры. Использующей несколько выходов, предикируемых защитными предложениями В их книге 2009 года прямо говорится. Что Ясность-это ключевой принцип: если метод яснее с одной точкой выхода. Используйте одну точку выхода; в противном случае не делайте этогоОни предлагают кулинарное решение для преобразования функции. Состоящей только из вложенных условных выражений. В последовательность охраняемых операторов return (или throw). За которыми следует один неохраняемый блок. Который должен содержать код для общего случая. В то время как охраняемые операторы должны иметь дело с менее распространенными (или с ошибками).

[9]Херб Саттер и Андрей Александреску также утверждают в своей книге 2004 C++ tips book. Что точка с одним выходом является устаревшим требованием.[10]

В своем учебнике 2004 года Дэвид Уотт пишет. Что Используя понятие структуры Теннента секвенсора Уотт единообразно описывает конструкции потока управления . Встречающиеся в современных языках программирования. И пытается объяснить. Почему определенные типы секвенсоров предпочтительнее других в контексте потоков управления с несколькими выходами.

Уотт пишет. Что неограниченные goto (jump sequencers) плохи. Потому что назначение прыжка не является самоочевидным для читателя программы. Пока читатель не найдет и не изучит фактическую метку или адрес. Который является целью прыжка. В противоположность этому. Уотт утверждает. Что концептуальное намерение возвратного секвенсора ясно из его собственного контекста. Без необходимости исследовать его назначение. Уотт пишет что существует класс секвенсоров известных как escape секвенсоры, определяемый как спагетти-код[11]

В противоположность вышесказанному,

Бертран Мейер написал в своем учебнике 2009 года. Что инструкции типа breakи continuegotoв овечьей шкуре[12]

Обработка исключений

Основываясь на ошибке кодирования в результате катастрофы Ariane 501, разработчик программного обеспечения Джим Бонанг утверждает. Что любые исключения. Выбрасываемые из функции. Нарушают парадигму единого выхода. И предлагает запретить все межпроцедурные исключения. Бонанг предлагает. Чтобы все C++. Соответствующие одному выходу. Были написаны в соответствии с:

bool MyCheck1() throw() { bool success = false; try { // Do something that may throw exceptions.

если (!MyCheck2()) { throw SomeInternalException(); } // Другой код. Аналогичный приведенному выше. success = true; } catch (...) { // Все исключения пойманы и зарегистрированы. } возвратный успех; }

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

Он отмечает. Что решения. Которые оборачивают исключения ради создания одного выхода. Имеют большую глубину вложенности и. Следовательно. Более трудны для понимания. И даже обвиняет тех. Кто предлагает применять такие решения к языкам программирования. Которые поддерживают исключения вовлечения в культовое мышление.[13]

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

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

На самом деле ненормальные ситуации. Представленные флагами состояния. По умолчанию игнорируются!Он отмечает. Что в отличие от тестирования флагов состояния исключения имеют противоположное поведение по умолчанию, вызывая завершение работы программы. Если только программист явно не имеет дело с исключением каким-либо образом, возможно. Добавляя код для преднамеренного его игнорирования. Основываясь на этих аргументах. Уотт приходит к выводу. Что секвенсоры перехода или escape-секвенсоры (обсуждавшиеся в предыдущем разделе) не так подходят. Как выделенный секвенсор исключений с семантикой. Описанной выше.

]

В учебнике Лаудена и Ламберта подчеркивается. Что обработка исключений отличается от структурированных программных конструкций. Таких как whileциклы. Потому что передача управления В тот момент. Когда передача действительно происходит. Может отсутствовать синтаксический признак того. Что управление действительно будет передано[15]. Профессор информатики Арвинд Кумар Бансал также отмечает. Что в языках. Реализующих обработку исключений. Даже такие управляющие структуры, как for, которые имеют свойство single-exit при отсутствии исключений. Больше не имеют его при наличии исключений. Потому что исключение может преждевременно вызвать ранний выход в любой части структуры управления; например , если

init()выбрасывает исключениеfor (init(); check(); increm()), то обычная точка выхода после check() не достигается.Ссылаясь на многочисленные предыдущие исследования других авторов (1999-2004) и свои собственные результаты. Уэстли Веймер и Джордж Некула писали. Что существенная проблема исключений заключается в том. Что они [17]:8:27

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

OpenMP. Различные параллельные конструкции из OpenMP. Например parallel do, не допускают ранних выходов изнутри наружу параллельной конструкции; это ограничение включает в себя все виды выходов. Начиная с breakисключений C++. Но все они разрешены внутри параллельной конструкции. Если цель перехода также находится внутри нее.]

Многократная запись

Чаще всего это только повторный входв корутину (или генератор/полукорутину). Где подпрограмма дает контроль (и. Возможно, значение). Но затем может быть возобновлена там. Где она остановилась. Существует ряд

распространенных применений такого программирования. Особенно для потоков (в частности. Ввод/вывод). Государственные машины и параллелизм. С точки зрения выполнения кода выход из сопрограммы ближе к структурированному программированию. Чем возврат из подпрограммы. Поскольку подпрограмма фактически не завершилась и будет продолжаться при повторном вызове – это не ранний выход. Однако сопрограммы означают. Что несколько подпрограмм имеют состояние выполнения. А не один стек вызовов подпрограмм. Иим образом. Вводят другую форму сложности.

Очень редко подпрограммы допускают вход в произвольную позицию подпрограммы. Так как в этом случае состояние программы (например. Значения переменных) неинициализировано или неоднозначно. И это очень похоже на goto.

Конечные автоматы

Некоторые программы. В частности парсеры и коммуникационные протоколы, имеют ряд состояний, которые следуют друг за другом таким образом. Что их нелегко свести к базовым структурам. И некоторые программисты реализуют изменения состояний с переходом в новое состояние. Этот тип переключения состояний часто используется в ядре Linux.]

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

Цитаты

  1. ^
  2. ^ Бом, Коррадо; Джузеппе Якопини (май 1966). (PDF). Коммуникации АСМ. 9 (5): 366–371. CiteSeerX 10.1.1.119.9119. doi:10.1145/355592.365646. S2CID 10236439. Архивировано (PDF) с оригинала на 2015-09-23.
  3. ^ Дейкстра, Э. У. (март 1968). Коммуникации АСМ. 11 (3): 147–148. doi:10.1145/362929.362947. ISSN 0001-0782. S2CID 17469809.
  4. ^ Plauger, P. J. (12 февраля 1993). Программирование нарочно. Очерки по проектированию программного

    обеспечения (1-е изд.). Прентис-Холл, стр. ISBN 978-0-13-721374-0.

  5. ^ Дональд Кнут — Структурированное программирование с операторами go to , архивированными 2013-10-23 на машине Wayback
  6. ^ Франк Рубин (март 1987). ГОТО считается вредным (PDF). Коммуникации АСМ. 30 (3): 195–196. doi:10.1145/214748.315722. S2CID 6853038. Архивировано из оригинала (PDF) на 2009-03-20.
  7. ^ Джей Филдс; Шейн Харви; Мартин Фаулер; Кент Бек (2009). Рефакторинг: Ruby Edition. Pearson Education. pp. 274-279. ISBN 978-0-321-60350-0.
  8. ^ Херб Саттер; Андрей Александреску (2004).

    Стандарты кодирования C++: 101 Правило. Руководство и лучшие практики. Образование Пирсона. ISBN 978-0-13-265442-5. Исторически сложилось так. Что некоторые стандарты кодирования требовали. Чтобы каждая функция имела ровно один выход. То есть один оператор return. Такое требование устарело в языках. Поддерживающих исключения и деструкторы. Где функции обычно имеют множество неявных выходов.

  9. ^ Дэвид Энтони Уотт; Уильям Финдли (2004). Концепции проектирования языка программирования. John Wiley & Sons. pp. 215-221. ISBN 978-0-470-85320-7.
  10. ^ Бертран Мейер (2009). Прикосновение класса: Обучение хорошо программировать с объектами и контрактами

    . Springer Science & Business Media. p. 189. ISBN 978-3-540-92144-8.

  11. ^ – Блог MVP Питера Ричи. Архивирован с оригинала на 2012-11-14годы . Проверено 2014-07-15.
  12. ^ Дэвид Энтони Уотт; Уильям Финдли (2004). Концепции проектирования языков программирования. John Wiley & Sons. pp. 221-222. ISBN 978-0-470-85320-7.
  13. ^ Кеннет К. Лауден; Кеннет А. Ламберт (2011). Языки программирования: Принципы и практика (3 изд.). Cengage Learning. p. 423. ISBN 978-1-111-52941-3.
  14. ^ Арвинд Кумар Бансал (2013). Введение в языки программирования

    . CRC Press. p. 135. ISBN 978-1-4665-6514-2.

  15. ^ Weimer, W & Necula. G. C. (2008). (PDF). ACM-транзакции на языках программирования и системах. 30 (2). Архивировано (PDF) с оригинала на 2015-09-23.
  16. ^ Рохит Чандра (2001). Параллельное программирование в OpenMP. Morgan Kaufmann. p. 45. ISBN 978-1-55860-671-5.

Источники

Внешние ссылки

  • BPStruct — Инструмент для структурирования параллельных систем (программ. Моделей процессов)
  • J. Darlinton; M. Ghanem; H. W. To (1993), In Programming Models for Massively Parallel Computers. IEEE Computer Society Press. 1993: 160-169, CiteSeerX 10.1.1.37.4610