1626435694-d107b4090667f8488e7fa1ea1b3d0faa (844295), страница 31

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 31)

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

только составная часть в поисках лучших способов программирования. Мы не будем далее углубляться в общие рассуждения, а коротко рассмотрим одну из таких методик в интересах описания программ экономии памяти. 3 4.2. Структурированное программирование В конце 1975 г. в книжных магазинах появилась (и вскоре исчезла) книга У. Дала, Э. Дейкстры и К. Хоора «Структурное программированием Перевод названия не вполне точен: более правильно говорить «Структурированное программирование».

146 гл. 4. РБАлизлция Это ближе к английскому оригиналу «Я1гпс1пге«) ргоягашш(пя» и более точно отражает смысл: внесение структуры как в процесс программирования, так и в форму программы. В этой книге содержится основополагающая статья Дейкстры «Заметки по структурному программированиюм Он единодушно признается ученым, внесшим наибольший вклад в развитие и распространение структурированного программирования, хотя под другими нааваниями сходная методика развивалась и другими авторами, а ее математические основы были известны в алгебре рекурсивных функций уже давно, хотя и не использовались на практике. Считая знакомство с этой выдающейся работой необходимым каждому программисту, автор не будет повторять обоснований, а опишет (несколько упрощенно) методику структурированного программирования в применении к конструкциям алгола.

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

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

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

Конкатенация означает, что задача представляет собой последовательное решение двух задач: Х1, а аатем Х2. Этк две задачи образуют составной оператор илн блок, если задача Х1 вырабатывает некоторую новую информацию, воспринимаемую затем % «.Х СТРУКТУРИРОВАННОЕ ПРОГРАММИРОВАНИИ 447 задачей Х2. В этом случае перед задачей Х1 появляется описательная часть, в которой описываются новые величины, локальные в данном блоке.

При этом в голове у программиста происходит некоторая перестройка, которая заменяет сводное знание об Р Лй«Г / А 01ьсншы айни А 5нпиое ", 1 РЫВ«Е А7 А: «ач Рэс. 4А. Коваатенацня. исходной задаче «расчлененными знаниямиэ о задачах Х1 и Х2 (см. рис. 4.1). Объекты исходной задачи либо полностью, либо частично становятся глобальнымп объектами задач Х1 и Х2. При выборе имен для локальных величин, связывающих Х1 и Х2, необходимо следить, чтобы не произошло коллизий мея«ду этими именами и именами глобальных величии. Альтернатива означает, что задача представляет собой проверку некоторого условия В и, в зависимости от его истинности илн ложности, выполнения аадачи Х1 нли Х2 соответственно.

Таким обрааом, условие В вместе с задачами Х1 и Х2 образует условный оператор алгола (см. рис. 4.2). Локальные величины прн этом структурировании не воаникают. Задача Х2 может отсутствовать, что приводит к конструкции условного оператора без иначе. Итерация. означает, что задача представляет собой цикл по некоторому параметру « с условием повторения В (это может быть либо условие типа пока, либо ааголовок цикла типа арифметической прогрессии), в котором происходит циклическое выполнение задачи Х(~), образующей тело оператора цикла (рис. 4.3). Как видно, правила структурированного программирования очень просты.'Их смысл в том, что они не позволяют при построении программы сделать слишком большого шага, при этом структурные ограничения предотвращают появление сложных информационных зависимостей н запутанных передач управления (как ГЛ 4. РЕАЛИЗАЦИЯ 448 видно, переходы по метке при таком подходе вообще не возникают).

Не менее важным является постоянное «перетряхиваниеэ е ! днанае а паба» ! А дада«а А Е:::::3 дбненпнн задана А и набате 1 Х1 г даннных ' ~, а атбпне,1 днанае ~ аз«бане ' '- и -' Рис. 4.2. Альтернатива. дамен мба«е дейст А Люса ~ ~, а наФам н " --Жс2- е дна«не ", 1 а набате й ниязи 0писипаепаитнепета!; Вм с':-угловое-та3апт Я цала мбанаХ(п Обьеппы ьжана А Рис. 4.3.

Итерация. и «фильтрация» нашего знания об исходной задаче при его переносе на новые подзадачи. Кстати говоря, эта сопровождающая работа мысли стоит программисту больших усилий. Таким образом, структурирование не делает программирование проще, наоборот, опо даже становится еще более напряженным. Однако его систематический н дисциплинирующий характер вознаграждает программиста более достоверным и легче проверяемым результатом:. % 4.х стгуктугиРОВАннов ПРОГРАммигозлнин 149 В качестве предварительной демонстрации структурированного программирования мы возьмем построение программы, пожалуй, наиболее традиционного' примера алгоритма — нахождения наибольшего общего делителя двух положительных целых чисел. Автор проведет эту демонстрацию в несколько подчеркнутой манере, обращая внимание читателя на широту диапазона умственных усилий программиста — от общей идеи алгоритма до скрупулезного обсуждения способа перестановки двух значений.

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

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

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

В простых случаях при приближении к заключительному программированию мы будем иногда объединять неоколько структурирований в одну формулу. 150 ГЛ. 4. РЕАЛИЗАЦИЯ Нагон<ление наибольшего общего делителя прим Пусть х и у — заданные натуральные числа, а г — их наибольший общий делитель.

Мы будем строить программу как описание процедуры НОД, имеющей х, у и г своими формальными параметрами. Итак (1) проц НОД (х, у, г); знач х, у; цел х, у, г; ТЕЛО НОД прим ТЕЛО НОД /х, у, г/. Задача решается сведением ее к простейшей. Пусть ОСТ (А, В) — зто остаток от целого деления А на В. Если мы знаем, что ОСТ (у, х) = О, то тогда г = х. Если же х не делит у, то тогда, как известно НОД (х, у) = = НОД (ОСТ (у, х), х). Это соотношение позволяет нам редуцировать числа, вовлекаемые в рассмотрение, до тех пор пока, остаток не окажется равным нулю.

Характеристики

Список файлов книги