Перечислим теперь основные п р и н ц и п ы и м е т о д ы структур- ного программирования. Вы говорите, что я повторяюсь. Но я повторю. Т.С.Эллиот ┌────────────────────────────────────────┐ I. │ Как можно меньше переходов GOTO ! │ └────────────────────────────────────────┘ Э. Дейкстра выразил это таким образом: "Уже давно было замечено, что квалификация программистов является убывающей функцией от плотности пред- ложений GOTO в создаваемых ими программах". Причина этого заключается в том, что основные конструкции структурного программирования гораздо более лаконичны и просты, чем их аналоги на неструктурном языке программирова- ния, например MSX-BASIC. Отсюда сразу следует, что программы, написанные на MSX-BASIC, будут насыщены предложениями GOTO (написанными как явно,так и неявно!). Четыре предложения структурного программирования на приведенной ниже схеме в той или иной форме используются во многих языках программирования (приведены примеры конструкций языка программирования TURBO Pascal). ┌────────────────────┬─────────────────────┬───────────────────────────┐ │ Предложения │ Неформальное │ Соответствующая последо- │ │ структурного │ описание │ вательность операторов │ │ программирования │ │ на языке MSX-BASIC │ │────────────────────┼─────────────────────┼───────────────────────────│ │ │ Если условие истинно│ │ │ │ выполнить предложе-│ │ │IF C THEN S1 ELSE S2│ ние S1; │ IF C THEN S1 ELSE S2 │ │ │ в противном случае │ │ │ │ выполнить предложе-│ │ │ │ ние S2 │ │ │────────────────────┼─────────────────────┼───────────────────────────│ │ │ Повторить предложе-│ │ │ │ ние S, пока условие │ GOTO n │ │ WHILE C DO S │ С останется истинным│ m: S │ │ │ (0 или более раз) │ n: IF C THEN GOTO m │ │ │ │ │ │────────────────────┼─────────────────────┼───────────────────────────│ │ │ Повторять последова-│ │ │ │ тельность S (один │ │ │ REPEAT S UNTIL C │ или более раз) до │ m: S │ │ │ тех пор, пока усло-│ IF NOT C THEN GOTO m │ │ │ вие С не станет ис-│ │ │ │ тинным │ │ │────────────────────┼─────────────────────┼───────────────────────────│ │ │ Выполнить предложе-│ │ │ CASE K OF │ ние Si(только, если │ ON K GOTO N1,N2,...,Nm:│ │ 1: S1 │ значение K=i,причем │ GOTO s │ │ 2: S2 │ i равно либо 1, │ N1:S1:GOTO s │ │ ··· │ либо 2, │ N2:S2:GOTO s │ │ m: Sm │ ··· │ ··· │ │ │ либо m │ Nm:Sm │ │ │ (выбор по значению) │ ··· │ │ │ │ s:... │ └────────────────────┴─────────────────────┴───────────────────────────┘ Обратим Ваше внимание на то, что при программировании конструкций структурного программирования на языке MSX-BASIC невозможно обойтись без оператора GOTO, с помощью которого осуществляется переход на ту или иную ветвь условной конструкции. Однако следует иметь в виду, что оператор GOTO используется только для передачи управления в н у т р и конструк- ции, что не противоречит идеям структурного программирования. Дейкстра продолжает: "Я пришел к убеждению, что предложение GOTO долж- но быть устранено из всех языков программирования "высокого уровня" (т.е. отовсюду, за исключением, возможно, простых машинных кодов)". ┌──────────────────────────────────────────────────────────────────────┐ │ Однако сейчас стало ясным, что программирование без оператора GOTO- │ │ это еще не структурное программирование. Можно написать программу │ │ без оператора перехода, логическая структура которой тем не менее │ │ будет неудачной. И, наоборот, существуют ситуации, в которых пере- │ │ ход является лаконичным, простым и ясным средством, в то время как │ │ другие подходы сравнительно неудачны │ └──────────────────────────────────────────────────────────────────────┘ Например, правила структурного программирования часто предписывают по- вторять одинаковые фрагменты программы в разных участках модуля, чтобы из- бавиться от употребления оператора GOTO. В этом случае "лекарство хуже болезни", т.к. дублирование резко увеличивает возможность внесения ошибок при изменении модуля в будущем. Д.Кнут в работе [70] показал, что можно говорить о структурном прог- раммировании и при использовании оператора GOTO!Структурное программирова- ние на языках FORTRAN или BASIC возможно, хотя с большими трудностями и некоторыми нежелательными последствиями. Так, например, Чармонмен и Ведже- нер [72] показали,что можно сделать программу на языке FORTRAN похожей на структурную! II. Другой метод улучшения качества программирования заключается в при- менении н и с х о д я щ е г о п р о е к т и р о в а н и я, ("top-down programming" - "программирование "сверху-вниз""). ┌───────────────────────────────────────────────────────────────┐ │ Оператор GOSUB является о с н о в н ы м инструментом │ │ с т р у к т у р н о г о программирования. │ └───────────────────────────────────────────────────────────────┘ В методе нисходящего проектирования Вы вначале пишете основную програм- му, используя оператор GOSUB для вызова подпрограмм,причем в качестве под- программ вначале Вы вводите "заглушки" вида: PRINT "Вызвали подпрограмму номер ...":RETURN Затем, будучи уверенным в правильности логического построения основной программы, Вы детально "расписываете" каждую подпрограмму, вызывая по ме- ре необходимости подпрограммы более низкого уровня. Этот последовательный процесс продолжается, пока программа не будет завершена и проверена. При другом методе - в о с х о д я щ е м п р о е к т и р о в а н и и (программировании "снизу-вверх") - Вы вначале пишете подпрограммы нижнего уровня и тщательно их тестируете и отлаживаете. Далее Вы добавляете под- программы более высокого уровня, которые вызывают подпрограммы нижнего уровня, и так до тех пор, пока Вы не достигнете программы самого верхнего уровня. Метод проектирования "снизу-вверх" пригоден при наличии больших библиотек стандартных подпрограмм. Учтите, что иногда лучшим является гибрид двух методов. Однако в обо- их случаях каждая подпрограмма должна быть небольшой, так, чтобы можно бы- ло охватить одним взглядом всю ее логику (для персональных компьютеров же- лательно, чтобы и основная программа,и подпрограммы ц е л и к о м поме- щались в пределах 20÷30 строк экрана дисплея!) Всякий велосипедист хорошо знает, что ехать сверху вниз быстрее и удоб- нее, чем снизу вверх. В программировании дело обстоит примерно так же: "сверху-вниз" писать программы удобнее потому,что при таком методе мы точ- но знаем, какие подпрограммы описывать. Но есть у этого метода и недостаток: на верхнем уровне не всегда видно, куда спускаться, то есть как разделить решение задачи на такие части, каж- дую из которых было бы легко описать отдельной процедурой. У опытных про- граммистов вырабатывается своеобразное чутье: они сразу видят, какие нуж- ны процедуры, а новичкам иногда приходится туго. Метод "снизу-вверх", хотя и требует большого труда, бывает очень поле- зен на первых порах. Пусть даже половину составленных Вами подпрограмм придется потом "выбросить", но зато Вы хорошо почувствуете, какие подпро- граммы для исходной задачи необходимы. Да и отлаживать каждую написанную подпрограмму можно сразу: ведь все, что "под ней", уже описано (а обычно и отлажено). Словом, любишь кататься "сверху вниз" - люби и саночки во- зить (в обратном направлении). Опытные программисты иногда применяют ме- тод "снизу-вверх" для того, чтобы заранее заготовить для новой задачи на- бор подпрограмм, которые могут понадобиться в различных случаях. Так что "возить саночки" приходится не только новичкам! III. Структурное программирование до сих пор было у нас представлено как свойство или оценка о к о н ч а т е л ь н о г о текста программы. Необходимо добавить еще один ключевой момент - методологию, или особеннос- ти мыслительного процесса, управляющего процессом получения структурной программы. Этот мыслительный процесс называется п о ш а г о в о й д е - т а л и з а ц и е й и был первоначально предложен Э.Дейкстрой [73], а затем улучшен Н.Виртом [74]. ┌──────────────────────────────────────────────────────────────────┐ │ Пошаговая детализация представляет собой простой процесс, │ │ предполагающий первоначальное выражение логики программы в │ │ терминах гипотетического языка "очень высокого уровня" с │ │ последующей детализацией каждого предложения в терминах язы- │ │ ка более низкого уровня, до тех пор,пока, наконец, не будет │ │ достигнут уровень используемого языка программирования. │ └──────────────────────────────────────────────────────────────────┘ Причем на протяжении всего процесса логика выражается основными конст- рукциями структурного программирования. В методе пошаговой детализации можно выделить следующие существенные этапы [8]: 1. На уровне 1 создается общее описание программы в целом.Определяются основные логические шаги, требуемые для решения задачи, даже если пока не- известно, как их выполнить. Эти логические шаги могут отражать различные физические шаги решения или могут быть удобными групповыми именами для тех действий, выполнение которых представляется довольно смутно. Последо- вательности шагов, требуемых для решения задачи, записываются на обычном языке или на п с е в д о к о д е (см. ниже). 2. На уровне 2 в общих терминах детализируется описание шагов, введен- ных на этапе 1).В детализированное описание может входить обозначение цик- лических структур,в то время как действия внутри циклов могут по-прежнему оставаться неясными. Таким образом, выполняются только общие эскизы слож- ных действий. 3. На этом и последующих уровнях в виде последовательных итераций про- изводятся те же действия, что описаны на этапе 2). При каждой новой ите- рации уточняются детали, оставшиеся неясными после предыдущих итераций, и создаются более определенные описания. По мере выполнения итераций неопре- деленные детали становятся все проще и проще, так что на каком-то этапе могут быть полностью описаны. 4. Разработка завершена: в модульном виде получено описание требуемой программы. Перевод этого описания в программу на конкретном языке програм- мирования должен быть достаточно простой задачей. П с е в д о к о д включает в себя наборы фраз для написания таких групп операторов: последовательность, выбор, итерация, - дополняемых текс- том на обычном языке. Псевдокод не имеет строгого определения, поэтому Вы всегда можете сконструировать свой с о б с т в е н н ы й п с е в д о - к о д, используя, например, конструкции школьного алгоритмического языка: если , пока , для , выбор , а также комментарии, формулы и словесное опи- ──── ──── ─── ───── сание действий и процессов. В описание процессов могут входить и такие операторы конкретного языка программирования (например, BASIC), как INPUT, PRINT, READ и присваивания, но не операторы п е р е х о д а или другие средства передачи управления, применение которых должно ограничиваться реализацией трех указанных выше типов структур на заключительном этапе процесса проектирования. Концепцию псевдокода легче всего уяснить на примере. Пусть требуется определить наибольшее значение в некотором наборе дан- ных и вывести эти данные, поделенные на наибольшее значение. Скажем, если данные представляют собой последовательность чисел 4., 2.51, 10.0, -5.0, 7.5 , то вывод должен выглядеть следующим образом: 0.40, 0.251, 1.00, -0.5, 0.75 . Первый уровень разработки ясен: У р о в е н ь 1: ──────────────── 1) ввести данные; 2) найти максимум введенных данных; 3) вывести результаты. Д е т а л и з а ц и я 1.1. В в о д д а н н ы х можно детализировать ────────────────────────── на псевдокоде следующим образом: 1) определить количество чисел; 2) пока не все элементы введены, прочитать и запомнить значение элемен- та; 3) конец цикла. Это описание можно перевести на язык MSX-BASIC следующим образом: 100 INPUT"Укажите количество элементов";N 110 FOR I=1 TO N:INPUT A(I):NEXT I Д е т а л и з а ц и я 1.2. О т ы с к а н и е м а к с и м у м а мож- ────────────────────────── но детализировать следующим образом: 1) выбрать в качестве максимума первый элемент данных; 2) пробежать все введенные значения, заменяя текущий максимум на оче- редное значение, если оно не превысило его. Д е т а л и з а ц и я 1.3. В ы в о д р е з у л ь т а т о в можно ────────────────────────── детализировать следующим образом: 1) пока не все результаты выведены; 2) ВЫВОД значение очередного элемента, поделенное на максимум; 3) конец цикла. Это описание можно немедленно перевести на MSX-BASIC следующим образом: 300 FOR I=1 TO N:PRINT A(I)/M:NEXT I У р о в е н ь 2. ──────────────── Он включает в себя три детализованные выше части, из которых только детализация (1.2) требует дополнительного внимания. Ее можно детализиро- вать на псевдокоде следующим образом: 1) положить М, равное первому элементу данных; 2) пока не все элементы просмотрены; 3) если М<текущий элемент, то M = текущий элемент; 4) конец цикла. Это описание можно перевести на MSX-BASIC следующим образом: 200 M=A(1) 210 FOR I=1 TO N 220 IF M