Алгоритмы, структуры данных

       

Лирическое отступление


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

Это было нечто! Меня поразила сама возможность выполнять ряд простых шагов и гарантированно получать правильный результат.

Ну а уж потом были примеры из тригонометрии: четырехэтажные дроби с ужасным количеством синусов, косинусов и бесконечно длинными аргументами, которые путем небольшой игры ума сворачивались в робкое 1+sin(x), а то и просто в неприметную 1.

С тех самых пор я весьма неравнодушен к формальным преобразованиям и стараюсь найти им применение в программировании. И, вы знаете, иногда получается! :-)

Давным-давно, когда люди еще не придумали объектно-ориентированное программирование, модным направлением было программирование структурное. Шутки шутками, но в результате именно структурного подхода мы сейчас имеем Pascal и Delphi.

Почему я говорю то Паскаль, то Дельфи? Просто потому, что лингвистическая основа Delphi - это Object Pascal, сильно выросший из детских штанишек, но все же узнаваемый. И новые объектно-ориентированные возможности и замечательные библиотеки классов в совокупности с CASE-средствами так и не скрыли полностью длинные уши структурного языка (и это замечательно!). Они вылезают то здесь, то там, в отдельных процедурах, в обработчиках событий... :-)

Так вот, в те давние времена возникла следующая ситуация:

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

    (Особенно этим грешат процедуры, занимающиеся разного рода синтаксическим разбором.)

  • Стандартный Паскаль имеет очень ограниченное количество структурных инструкций ( if-then-else, while-do и т.д., вы это лучше меня знаете...)

  • А программу-то написать хочется! Что делать ?

  • А нельзя ли как-нибудь "втиснуть" этот наш премудрый алгоритм в куцый набор инструкций?
  • Можно! Причем используя вполне .


  • Вот этим мы сейчас и займемся.

    Но в начале - немного теории.





    Итак, структурное программирование учит нас, что есть 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 и прочих неприятностей.



    Содержание раздела