Алгодром

05. Метод последовательного уточнения

СНИЗУ ВВЕРХ
|
СВЕРХУ ВНИЗ (Метод Последовательного Уточнения)
|
ПРИМЕР РЕШЕНИЯ ЗАДАЧИ
|
ЗАМЕЧАНИЯ

Снизу вверх

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

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

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

Сверху вниз (МПУ)

В трудных случаях программа составляется в обратном порядке - сверху вниз.

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

На следующем этапе можно переходить к уточнению отдельных пунктов общего плана, т.е. к написанию вспомогательных алгоритмов. Здесь можно применить тот же прием: сразу приступать к сотавлению процедуры, заменяя все предписания, которых нет в СКИ, вызовами новых вспомогательных алгоритмов.

Понятно, что на каждом этапе придется последовательно уточнять пункты плана возникшего на предыдущем уровне. И так до тех пор, пока на самом нижнем уровне не получатся процедуры, состоящие только из команд, входящих в СКИ. Это и есть метод последовательного уточнения.

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

Итак, метод последовательного уточнения состоит в следующем:

Пример решения задачи

Если суть метода понятна, можно попробовать решить ЗАДАЧУ:

Составить программу для исполнителя Чертежник, которая рисует такую картинку:

Для ее РЕШЕНИЯ мы применим метод последовательного уточнения, независимо от того, кажется ли задача Вам трудной или нет. (Чтобы сосредоточиться на принципиальных идеях, мы опускаем некоторые технические детали, как например размер поля.)
Итак, согласно технологии пректирования программ "сверху-вниз", начинаем с главного алгоритма или общего плана решения.

Одна из возможных идей: рисовать эту картинку "по рядам" , т.е. Чертежник должен нарисовать четыре ряда по пять "елей" в каждом, делая каждый раз между рядами переход от "конца" очередного ряда к "началу" следующего.

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

Переходим к уточнению пунктов нашего плана, т.е. к написанию вспомогательных алгоритмов 1-го уровня — процедур, вызываемых в основном алгоритме: подход, ряд, переход.
Попробуем, например, уточнить пункт ряд.И опять, не будем стремиться объяснить все до конца, а ограничимся только минимальным набором принимаемых решений:
Для рисования одного ряда необходимо нарисовать пять елей, перемещая исполнителя (делая сдвиг) после каждой из них к следующей.
Записываем сказанное в виде
вспомогательного алгоритма:
Неудивительно, что применив наш метод при составлении алгоритма ряд, мы получили две новые подзадачи: ель и сдвиг. Другими словами: пытаясь дать определение того, что такое "ряд", мы вынуждены были использовать два новых для исполнителя термина "ель" и "сдвиг", которые в свою очередь нуждаются в определениях.

Прежде чем продолжить, попробуйте ответить на следующие вопросы:

  • если количество нуждающихся в решении подзадач растет, каковы наши шансы в обозримом будущем завершить решение исходной задачи?
  • можно ли в данный момент, не уточнив до конца пункт ряд, заняться вспомогательным алгоритмом переход?
  • что следует сделать раньше: "нарисовать", наконец, поточнее елочку (вместо бесформенного пятна) или расcчитать сдвиг?
Продолжая процесс последовательного (постепенного) уточнения, попробуем написать вспомогательный алгоритм 2-го уровня ель.

Если очередная подзадача оказывается достаточно простой, мы можем, не прибегая к дальнейшей декомпозиции, решить ее сразу. Для этого надо в соответствующем алгоритме использовать только команды из СКИ (не прибегая к вызовам еще не написанных вспомогательных алгоритмов).
Наверное, так можно поступить
по отношению к процедуре ель:
(Напомним, что, как было сказано в начале, мы не станем отвлекаться на проблемы, связанные с вычислениями).
Дальнейшее уточнение этого алгоритма уже не требутся, т.к. все используемые команды "понятны" исполнителю.
Аналогичным образом можно уточнить все остальные алгоритмы и, тем самым, завершить решение задачи.

Замечания

Теперь Вы можете
посмотреть в целом на получившееся решение
  
самостоятельно повторить основные этапы решения

И в заключение два замечания:

  1. Можно ли было решать эту же задачу, проектируя алгоритм по технологии "снизу-вверх"?
      Если у Вас достаточно
        опыта и интуиции, чтобы сразу безошибочно угадать, какие вспомогательные алгоритмы могут пригодиться,
        умения правильно их написать ,
        способностей верно организовать их вызовы в главном алгоритме,
        терпения и навыков, наконец, чтобы отладить получившуюся программу, т.е. найти и исправить все неизбежные ошибки,
      то Вам — можно.

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

СНИЗУ ВВЕРХ
|
СВЕРХУ ВНИЗ (Метод Последовательного Уточнения)
|
ПРИМЕР РЕШЕНИЯ ЗАДАЧИ
|
ЗАМЕЧАНИЯ