3.3 Разработка алгоритма

Next:3.4 Обоснование алгоритма
Up:3 Общие рекомендации по выполнению заданий
Previous:3.2 Выбор представления данных

3.3 Разработка алгоритма

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

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

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

1. Средства, предоставляемые тем языком, на котором алгоритм будет запрограммирован. Например, в языке Турбо Паскаль допускаются модули и средства объектно-ориентированного программирования, позволяющие естественным образом реализовывать абстрактные структуры данных, в то время как в стандарте языка Паскаль их нет. Таким образом, при использовании различных языков имеется возможность разрабатывать существенно различные алгоритмы.

2. Структура данных, на которые ориентирован алгоритм. Этот фактор оказывает исключительно большое влияние на эффективность разрабатываемого алгоритма. Подробно об этом будет рассказано ниже.

3. Приближенность представления вещественных чисел в памяти ЭВМ. Это требует, чтобы при разработке алгоритма всюду, где производится сравнение вещественных значений, использовался некоторый задаваемый программистом уровень точности. Игнорирование специфики машинной арифметики является распространенной студенческой ошибкой при разработке алгоритма. Например, проверку того, лежат ли три точки на одной прямой, студент программирует обычно следующим образом: в уравнение прямой, проходящей через две точки, он подставляет координаты третьей точки. Все точки лежат на одной прямой тогда и только тогда, когда в результате получается нуль. Однако, из-за неточности машинной арифметики при выполнении такой проверки на ЭВМ нуль почти никогда не будет получен, даже если теоретически названное свойство выполнено. Реально приходится считать свойство выполненным, когда полученный при подстановке результат по модулю меньше некоторого предусмотренного разработчиком малого числа, например $10^{-6}$ .