34663

Итерационные алгоритмы

Реферат

Информатика, кибернетика и программирование

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

Русский

2013-09-08

41 KB

24 чел.

Итерационные алгоритмы.

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

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

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

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

Вот некоторые общие примеры, используемые на практике:

1. абсолютное изменение параметра на соседних шагах итерационного процесса:

2. относительное изменение на соседних шагах

Здесь - наперед заданное малое значение, определяющая точность нахождения решения.

В реализации конкретных численных методов возможно применение специфических критериев или комбинации нескольких критериев.

Пример. Составить алгоритм вычисления бесконечной суммы 

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

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

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

Решая эту задачу "в лоб" путем вычисления на каждом i-ом шаге частичной суммы

S:=S + ((-1)**(i-1)) * (x**i) / i ,

мы получим очень неэффективный алгоритм, требующий выполнения большого числа операций. Гораздо лучше организовать вычисления следующим образом: если обозначить числитель какого-либо слагаемого буквой р, то у следующего слагаемого числитель будет равен -р*х (знак минус обеспечивает чередование знаков слагаемых), а само слагаемое m будет равно p/i, где i - номер слагаемого.

Сравните эти два подхода по числу операций.


Алгоритм на языке Паскаль

Блок-схема алгоритма

program Summa;

var e, m, p : real;

   i : integer;

   дано | 0 < x < 1

   надо | S = x - x**2/2 + x**3/3 - ...

Begin

 write(‘Введите x : ’);

 readln(x);

 write(‘Введите e : ’);

 readln(e);

 S := 0;

 i := 1;

  m := 1;

 p := -1

  while abs(m)>e do

 begin

   p:=-p*x; {p – числитель очередного слагаемого}

   m:=p/i; {m - очередное слагаемое}

   S:=S+m; {S - частичная сумма}

   inc(i); {i – номер очередного слагаемого}

  end;

 Write(s);

 readln;

End.

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


 

А также другие работы, которые могут Вас заинтересовать

32654. Место и роль управления проектами в современной теории управления. Сущность проектного и процессного подходов 35 KB
  Роль управления проектами в современном мире. Эти средства активно применяются не только для управления федеральными проектами и программами но и для осуществления управленческих функций внутри правительственного аппарата. В России же где организационная система и методы управления гораздо слабее чем на Западе эффект от внедрения УП окажется еще более значительным.
32655. Основные признаки, понятия и характеристики проекта 30 KB
  Основные признаки понятия и характеристики проекта. Но цели проекта ограничены во времени. При успешном завершении проекта целевая установка данная руководителю проекта заказчиком отпадает. Признак изменения Этот признак является наиболее важной характеристикой проекта так как осуществление проекта всегда несет изменения вещественной системы или предметной области в которой реализуется проект.
32656. Особенности управления программами и портфелями проектов 40.5 KB
  Особенности управления программами и портфелями проектов. При определенных условиях множество взаимосвязанных проектов объединяются в программу. Программа может быть сформулирована в терминах проектов и представлена как совокупность проектов объединенных общей целью выделенными ресурсами временем на ее выполнение технологией организацией и др. В дальнейшем мы будем рассматривать программы как совокупность проектов.
32657. Классификация проектов и программ 28 KB
  в которых осуществляется проект: социальные проекты экономические проекты организационные проекты технические проекты смешанные проекты. Сложные проекты включающие подпроекты и элементы различных типов проектов. Вид проекта: По характеру предметной области проекта: учебнообразовательные проекты; проекты исследования и развития; инновационные проекты.; инвестиционные проекты.
32658. Понятие о декомпозиции работ по проекту. Критерии выбора эффективной декомпозиции работ 46 KB
  Понятие о декомпозиции работ по проекту. Критерии выбора эффективной декомпозиции работ. Структура разбиения декомпозиции работ WBS Work Brekdown Structure иерархическая структура последовательной декомпозиции проекта на подпроекты пакеты работ различного уровня пакеты детальных работ. СРР является базовым средством для создания системы управления проектом так как позволяет решать проблемы организации работ распределения ответственности оценки стоимости создания системы отчетности эффективно поддерживать процедуры сбора...
32659. Типы структурных моделей проекта 202 KB
  Типы структурных моделей проекта. Типы структурных моделей проектов Типы структурных моделей проекта. Структурная модель проекта и принцип структуризации широко используются для построена и других структурных моделей применяемых в управлении проектом. Отметим наиболее существенные из них: Дерево целей и результатов первая по времени разработки структурная модель декомпозиции цели проекта на составные части.
32660. Жизненные циклы проекта и продукта 26.5 KB
  Жизненные циклы проекта и продукта. Жизненный цикл проекта совокупность последовательных фаз развития проекта и изобразить его концептуальную схему. Наиболее традиционным является разбиение проекта на четыре крупных этапа: определение проекта концепция разработка реализация и завершение. Определение проекта по существу подразумевает функцию выбора проекта.
32661. Участники проекта и их роль в обеспечении успеха проекта 31 KB
  Участники проекта и их роль в обеспечении успеха проекта. В настоящем разделе работы рассматривается состав участников проекта их роли и взаимосвязи распределение функций и ответственности. Главный участник Заказчик будущий владелец и пользователь результатов проекта. При этом заказчиком может быть как одна единственная организация так и несколько организаций объединивших свои усилия интересы и капиталы для реализации проекта и использования его результатов.
32662. Окружающая среда проекта 28 KB
  Окружающая среда проекта. Окружение проекта Каждый проект нужно рассматривать а также управлять им учитывая окружение в котором он существует. Окружающая среда проекта это совокупность внешних и внутренних в отношении проекта факторов влияющих на достижение результатов проекта. В данном разделе необходимо проанализировать факторы ближнего и дальнего окружения проекта которые могут оказать влияние на реализацию проекта.