Реализация итерационных вычислений (Контрольная работа № 1)

КОНТРОЛЬНАЯ РАБОТА № 1

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

1. Понятие алгоритма

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

1.  Дискретность – свойство, отражающее выполнение вычислительного процесса, задаваемого алгоритмом по шагам.

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

3.  Элементарность – свойство, согласно которому действие, которое выполняется на каждом шаге должно быть простым.

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

5.  Массовость – свойство, согласно которому алгоритм может быть применен к любой совокупности из допустимого множества исходных данных.

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

1.  Временная сложность – показатель, отражающий время выполнения алгоритма или количество шагов его выполнения.

2.  Емкостная сложность – показатель, по которому производят оценку количества данных, необходимых для выполнения алгоритма.

3.  Сложность описания – показатель, отражающий длину описания алгоритма, количество инструкций операторов.

Для представления алгоритма используют различные средства, в том числе граф-схемы алгоритмов, каждая из которых представляет собой граф. Понятие элементарного графа дополнено введением надстройки, которая задает вычисления, каждому из которых соответствует путь в этом графе и последовательность меток узлов, лежащих на этом пути. Узлы графа, с помощью введения типизации, интерпретируются как действия, а дуги задают порядок передачи управления. Для каждого алгоритма существует одна начальная дуга и одна или множество конечных. В табл.1 представлены типы узлов граф-схемы алгоритма в соответствии с ГОСТ 19.701-90 «Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения».

Таблица 1