Особенности итерационного вычислительного процесса. Структура (шаги) итерационного процесса.

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

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

Структура итерационного процесса

В блоке 1 задаются начальные значения переменных, точность, с которой должно быть найдено решение (ЗНЗ).

Блок 2 (подготовительный этап) предназначен для выполнения некоторых вспомогательных операций по подготовке первой итерации. Этот блок в некоторых задачах может отсутствовать (ПЭ).

Блок 3 (или несколько блоков) реализуют вычисления, необходимые для выполнения итерации (РВ).

В блоке 4 выполняются действия для подготовки следующей итерации (ПСИ).

В блоке 5 (вычисление погрешности) определяется, насколько найденное решение отличается от эталонного или полученного на предыдущей итерации (ВП).

Блок 6 предназначен для проверки условия окончания итерации.

Например: определение факториала может быть записано таким образом

Если n=0 n! =1

n>0 n! = n* (n-1)*(n-2) …1.

Видно, что алгоритм требует явного повторения вычислений.

Рекурсивный вычислительный процесс

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

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

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

 Если процедура Р содержит явное обращение к самой себе, то она называется прямо рекурсивной; если Р содержит обращение к процедуре Q , которая содержит (прямо или косвенно) обращение к Р, то Р называется косвенно рекурсивной.

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

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

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

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

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

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

Постфиксная, префиксная, инфиксная записи представления выражений и их особенности.