Лирическое отступление
Однажды, еще в школе, на уроке алгебры, я в первый раз услышал о существовании формальных преобразований. Помнится это были (a+b) 2.
Это было нечто! Меня поразила сама возможность выполнять ряд простых шагов и гарантированно получать правильный результат.
Ну а уж потом были примеры из тригонометрии: четырехэтажные дроби с ужасным количеством синусов, косинусов и бесконечно длинными аргументами, которые путем небольшой игры ума сворачивались в робкое 1+sin(x), а то и просто в неприметную 1.
С тех самых пор я весьма неравнодушен к формальным преобразованиям и стараюсь найти им применение в программировании. И, вы знаете, иногда получается! :-)
Давным-давно, когда люди еще не придумали объектно-ориентированное программирование, модным направлением было программирование структурное. Шутки шутками, но в результате именно структурного подхода мы сейчас имеем Pascal и Delphi.
Почему я говорю то Паскаль, то Дельфи? Просто потому, что лингвистическая основа Delphi - это Object Pascal, сильно выросший из детских штанишек, но все же узнаваемый. И новые объектно-ориентированные возможности и замечательные библиотеки классов в совокупности с CASE-средствами так и не скрыли полностью длинные уши структурного языка (и это замечательно!). Они вылезают то здесь, то там, в отдельных процедурах, в обработчиках событий... :-)
Так вот, в те давние времена возникла следующая ситуация:
(Особенно этим грешат процедуры, занимающиеся разного рода синтаксическим разбором.)
Но в начале - немного теории.
|
Итак, структурное программирование учит нас, что есть 5 основных конструкций, из которых как из кубиков строится любая процедура: | ||||
 |
 |
 |
 |
 |
| SEQUENCE | IF-THEN-ELSE | WHILE-DO | REPEAT-UNTIL | CASE |
|
Историческая справка для любознательных. По этому поводу тоже было немало дебатов: сколько же структур действительно основных, а какие следует считать производными. Левые радикалы даже дошли до того, что основных структур только две: SEQUENCE и WHILE, а все остальные можно построить из них. Самое смешное, что это действительно так. Правда, размер текста программы при этом распухает неимоверно, но это уже детали... :-) |
А вот в этом как раз может помочь наша рабочая лошадка - непотопляемая конструкция REPEAT-CASE. При умелом применении эта нехитрая пара команд может "переварить" алгоритм любой сложности и запутанности. Главное, чтобы ВЫ четко представляли что делаете.
Однако хватит нам ходить вокруг да около, не пора ли заняться делом?
Предположим, у нас есть алгоритм следующего вида: |
Хитрый ли он? Да нет, конечно! Если приглядеться, он легко разбивается на 3 вложенные стандартные структуры:  |
|
Так что мы с легкой душой можем воплотить его в программе вроде такой: repeat while C1 do B1; if C2 then B2 else B3; until C3; И все! Очень красиво и компактно, спасибо большое дедушке Вирту. Как было бы хорошо, если бы в жизни нам попадались только такие алгоритмы. Однако в таком случае, вам незачем было бы читать эту статью! :-) |
А что вы скажете на это: |
Выглядит вроде просто, это мы мигом! Гмм.. да.. пробуем и так и эдак - в стандартный Паскаль это явно не укладывается. Можно, конечно, попытаться "расшить" процедурные блоки B1 и B3 или применить GOTO или EXIT из цикла. Но все это, согласитесь, выглядит как-то жалко и самодеятельно. Опять же надо каждый раз думать где разомкнуть цикл... И вот тут-то появляемся мы, (на белом коне !-) с нашей универсальной отмычкой по имени REPEAT-CASE. |
Теперь мы можем выполнить несколько чисто формальных шагов:
- Выделяем в нашем алгоритме фрагменты, которые хорошо укладываются в структурную модель (если такие есть). В нашем случае такой фрагмент только один: B2 + C2, т.е. последовательность из блока и условия.
( Если вы считаете, что фрагмент можно взять несколько шире и включить в него C1+B2+C2, я с вами соглашусь, но см.)
- Вне этих фрагментов ставим жирные точки в следующих местах:
- на входе в модуль (обозначим ее 1)
- на выходе модуля (обозначим 0)
- на входах и выходах всех фрагментов, что мы нашли
- во всех местах, где есть пересечение линий на блок-схеме
Скорее всего, многие точки просто сольются - пусть, мы будем считать их за одну. Например, у нас точка 1 на входе модуля совпадает с точкой пересечения линий входящей и от B3.
- Пронумеруем оставшиеся точки произвольно.
мы еще поговорим о том, что могут на самом деле означать эти номера. В нашем примере получается 4 точки от 0 до 3. - Теперь мы готовы перейти к модели конечного автомата и написать-таки нашу программу.
- Представьте, что есть некий блок, который может находиться в одном из 4 состояний. И есть набор действий, в результате которых блок переходит из одного состояния в другое.
- Для отображения этого самого состояния, заведем в программе некоторую переменную, скажем, State. А внутри веток CASE будем изменять ее состояние.
- Пишем нашу программу: var State:integer; begin State:=1; {для любого алгоритма} repeat case State of ... end; until State=0; {тоже для любого алгоритма} end;
- Теперь пропишем ветки CASE. Не забудьте в конце каждой ветки уточнить состояние: case State of 1: begin B1; if C1 then State:=2 else State:=3 end; 2: begin B2; if C2 then State:=0 else State:=3 end; 3: begin B3; State:=1 end; end;
- Все! Программа готова. Идите и попробуйте, она работает. И с точки зрения логики Паскаля все безупречно - никаких тебе GOTO и прочих неприятностей.
