2015-05-10
629
Среди этапов подготовки задач к автоматическому решению, ключевое место занимает этап построения собственно алгоритма. Любой начинающий программист в качестве основного элемента подготовки должен научиться строить алгоритмы решения. Как сказано выше, для построения алгоритмов решения вычислительных задач требуется по минимуму 5 типов элементарных операций. Опыт также показывает, что все многообразие вычислительных задач при их решении можно описать также ограниченным набором сочетаний этих элементарных предписаний в более крупные вычислительные структуры. Постепенно, расчленяя задачи на подзадачи, сводим их решение, в конечном счете, к некоторым типовым фрагментам алгоритмов (подобно тому как разбивая совершенно непохожие, сложные механизмы, мы обнаруживаем, что они состоят из одинаковых деталей и узлов, только по-разному соединенных). Из этого не следует, конечно, что процесс алгоритмизации не содержит в себе элементов творчества. Составление алгоритма - это такой же творческий процесс, как и конструирование механизма с заданными свойствами из заданного набора деталей. Очень важно "увидеть" место этих "деталей" в составе сложного "механизма", узнать в сложной ММ типовые фрагменты.
Можно указать 3 основных типа структур вычислительных схем, сочетая которые составляют алгоритмы любой сложности. Тип вычислительной схемы, или тип алгоритма, определяется исходя из порядка исполнения всех его предписаний при выполнении алгоритма по конкретным данным задачи. В соответствии с этим он получает и свое название.
1. Линейный тип алгоритма - это такая вычислительная структура, при которой все предписания выполняются в строго линейной последовательности друг за другом, как записаны; сам порядок исполнения называется естественным. В чистом виде линейные алгоритмы встречаются редко, они чрезвычайно просты. Но как фрагменты присутствуют почти во всех вычислительных схемах, так как именно на этих участках вводятся исходные данные, формируются и выходят на пользователя новые результаты (блок-ввода, блок-процесс, блок-печати). Примеры будут рассмотрены ниже.
2. Разветвляющийся тип алгоритма - эта такая вычислительная схема, которая содержит не одну, а несколько возможных ветвей решения по ММ; т.е. в структуре алгоритма есть хотя бы одна операция сравнения, порождающая 2 ветви последующего решения. Заранее нельзя сказать, какая ветвь алгоритма будет выполняться, все зависит от конкретных данных. Выбирается она автоматически, только в процессе исполнения алгоритма (остальные ветви для этого варианта данных останутся невостребованными). Тем труднее пользователю заранее (на этапе разработки) предусмотреть все возможные ветви решения и изобразить их, ничего не упустив. Примеры также будут рассматриваться ниже.
3. Циклический тип алгоритма - эта такая схема разветвленной структуры, в которой одна ветвь операции сравнения является обратной связью (ОС) на предыдущую часть алгоритма (т.е. идет назад). Таким образом, некоторая последовательность операций алгоритма будет выполняться многократно (т.е. в цикле), образуя тело цикла (тц). В крайнем случае, тело цикла может состоять всего из одной операции. Для того чтобы результаты всякий раз получались новые, необходимо алгоритмически предусмотреть три момента:
a) надо организовать данные для первого прохождения тела цикла;
b) после каждого выполнения тела цикла надо обновлять данные для очередного прохождения цикла;
c) надо управлять циклом, организовать условие выхода из цикла или его продолжения (ОС не должна охватывать указанные в пункте а операции!).
Варианты заданий
