Полное построение алгоритма

ELSE

переход к следующему элементу

IF массив не кончился THEN

переход на проверку интервала

ELSE

печать сообщения, что все элементы входят в интервал

Конец

При записи на псевдокоде каждое отдельное предложение может начинается со звездочки (*). Алгоритм строится таким об­разом, что разбиение продолжается до тех пор, пока каждый шаг алгоритма не станет достаточно понятным.

Структурные диаграммы — могут использоваться в качестве структурных блок-схем, для показа межмодульных связей, для отображения структур данных и систем обработки данных. Су­ществуют следующие структурные диаграммы: диаграммы Насси — Шнейдермана, Варнье, Джексона, МЭСИД и др.

Рассмотрим пример использования диаграмм МЭСИД.

Задан одномерный массив из положительных и отрицатель­ных чисел. Требуется определить частное от деления суммы по­ложительных элементов на сумму отрицательных элементов это­го массива. Справа от диаграммы (рис. 1.16) приводятся соответ­ствующие операторы языка Visual Basic.

S1=0

S2=0

FOR I=1 TO N

IF A(I) < 0 THEN

S1=S1+A(I)

ELSE

S2=S2+A(I)

END IF

NEXT I

IF S1<> 0 THEN R=S2/S1

1.2.7. Базовые канонические структуры алгоритмов

Для реализации алгоритмов на ПЭВМ используется алго­ритмический язык — набор символов и правил образования и истолкования конструкций из этих символов для записи алго­ритмов.

Любую программу можно написать, используя комбинации трех базовых структур:

• следования или последовательности операторов;

• ветвления или условного оператора;

• повторения или оператора цикла.

Программа, составленная из канонических структур, называ­ется регулярной программой, т. е. имеющей один вход и один выход.

Алгоритмы и программы объединяются понятием математиче­ское обеспечение. В настоящее время затраты на математиче­ское обеспечение составляют примерно полторы стоимости ПЭВМ, и постоянно происходит дальнейшее относительное его удорожание.

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

Полное построение алгоритма

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

Полное построение алгоритма предусматривает выполнение следующих последовательно друг за другом этапов:

1) постановка задачи;

2) построение модели;

3) разработка алгоритма;

4) проверка правильности алгоритма;

5) реализация, т. е. программирование алгоритма;

6) анализ алгоритма и его сложности;

7) проверка (отладка) программы;

8) составление документации.

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

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

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

Обычно процесс точной формулировки задачи сводится к постановке правильных вопросов. Перечислим некоторые полез­ные вопросы для плохо сформулированных задач:

• Понятна ли терминология, используемая в предваритель­ной формулировке?

• Что дано? Что нужно найти?

• Как определить решение?

• Каких данных не хватает или, наоборот, все ли перечис­ленные в формулировке задачи данные используются?

• Какие есть ограничения на данные?

Возможны и другие вопросы, возникающие в зависимости от конкретной задачи.

Построение модели. Задача четко поставлена, теперь нужно сформулировать для нее математическую модель. Выбор модели существенно влияет на остальные этапы в процессе решения.

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

Приступая к разработке модели, следует задать, по крайней мере, два основных вопроса:

1. Какие математические структуры больше всего подходят
для задачи?

2. Существуют ли решенные аналогичные задачи?

Второй вопрос, возможно, самый полезный во всей матема­тической модели. В контексте моделирования он часто дает от­вет на первый вопрос. Действительно, большинство решаемых в математике задач, как правило, являются модификациями ранее решенных.

Сначала нужно рассмотреть первый вопрос. Мы должны описать математически, что мы знаем и что хотим найти.

Разработка алгоритма. Выбор метода разработки алгоритма зачастую сильно зависит от выбора модели и может в значитель­ной степени повлиять на эффективность алгоритма решения. Два различных алгоритма могут быть правильными, но очень сильно отличаться по эффективности.

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

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

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

Реализация алгоритма. Как только алгоритм выражен, допус­тим, в виде последовательности шагов, и мы убедились в его правильности, настает черед реализации алгоритма, т. е. написа­ния программы для компьютера.

При этом возникают следующие проблемы:

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

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

Чтобы сделать это, необходимо ответить, например, на такие вопросы:

• Каковы основные переменные?

• Каких они типов?

• Сколько нужно массивов и какой размерности?

• Какие нужны подпрограммы (возможно, уже записанные в памяти)?

• Каким языком программирования пользоваться?

Конкретная реализация может существенно влиять на требования к памяти и на скорость алгоритма.

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