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

Страницы работы

11 страниц (Word-файл)

Фрагмент текста работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1

Символ

название

интерпретация

данные

данные, носитель данных неопределен

процесс

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

предопределенный процесс

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

Подготовка

модификация команды или группы команд с целью воздействия на некоторую последующую функцию

Решение

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

граница цикла

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

соединитель

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

терминатор

выход во внешнюю среду и вход из внешней среды (начало и конец программы)

линия

поток данных или управления; для направлений справа-налево и снизу-вверх добавляются стрелки

пунктирная линия

используется для обведения аннотируемого участка

комментарий

пояснительные записи и примечания

пропуск

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

Похожие материалы

Информация о работе