34663

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

Реферат

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

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

Русский

2013-09-08

41 KB

29 чел.

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

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

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

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

Реальный вычислительный процесс всегда должен заканчиваться при конечном значении 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.

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


 

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

39507. ЭЛЕКТРОННОЕ СРЕДСТВО ОБУЧЕНИЯ И ТЕСТИРОВАНИЯ ПО ДИСЦИПЛИНЕ «ОСНОВЫ СОЦИАЛЬНО-ГУМАНИТАРНЫХ НАУК. ПОЛИТОЛОГИЯ» 219.28 KB
  Это задается следующими строками: int ocenka = 0; { AnsiString otvety= ; for int k = 0; k kolv; k { ocenka = ocenka kRight[k]; if kRight[k]==1 otvety = otvety IntToStrk1; } Загрузка вопросов в RadioGroup производится следующим образом: RadioGroup1 Items Clear; while j q ChildNodes Count { RadioGroup1 Items Addq ChildNodes Nodes[j] Text; j; } } if i = qw ChildNodes Count BitBtn3 Click; } ОБОСНОВАНИЕ ПРИЕМОВ ПРОГРАММИРОВАНИЯ ОС Windows XP Windows XP кодовое название при разработке Whistler;...
39508. Оценка размера вреда (ущерба) имуществу при наступлении страхового случая 1.22 MB
  Основные понятия и определения Оценка определение стоимости объекта оценки. Внутренняя оценка оценка проводимая самостоятельно юридическими и физическими лицами в том числе индивидуальными предпринимателями на основании собственного решения без привлечения исполнителя оценки. Результат внутренней оценки не может использоваться в случаях если в соответствии с законодательными актами оценка должна быть только независимой [3].
39509. Оценка размеров вреда при наступлении страховых случаев 3.44 MB
  В процессе работы выполнены следующие исследования: проанализировано существующее положение дел в области определения размера вреда в Республике Беларусь; сделан анализ зарубежной практики оценки имущества для целей возмещения убытков связанных с наступлением страховых случаев; разработаны предложения по определению размера вреда связанных с наступлением страховых случаев. Общие сведения об объекте оценки [1. Определение ориентировочных размеров убытков причиняемых полным разрушением капитального строения жилого дома в котором...
39511. Служебно-представительское здание в монолитном каркасе, расположенное в сейсмически активной зоне 1.37 MB
  Подбор сечения арматуры. Расчет поперечной арматуры. Стык осуществляемый путей сварки выпусков арматуры и укладки бетона в зоне соединения [4. Основные расчетные формулы Принимаем Полная высота плиты h=h0a=457514=5975 мм где а=10d 2=108 2=14 мм 10 мм защитный слой d=8 мм предполагаемый диаметр рабочей продольной арматуры Принимаем толщину плиты 100 мм.
39512. Спорткомплекс с залом площадью 730 м2 1.14 MB
  Организация строительного производства должна быть направлена на уменьшение сроков строительства при высоком качестве работ и минимальных затратах труда материальных ресурсов и денежных средств. Основными направлениями НТП в области строительства являются: концентрация предприятий в составе промышленных узлов в которых предусматривается комплексная переработка сырья без создания отвальных зон. Это создает условия для массового внедрения принципов поточного производства; снижение мощности строительства в области строительного...
39513. Семиэтажный жилой дом из монолитного железобетона 1.26 MB
  ПОПЕРЕЧНАЯ РАМА МОНОЛИТНОЕ ПЕРЕКРЫТИЕБАЛКА КОЛОННА РАСЧЕТ НАГРУЗКА ФУНДАМЕНТ РАСЧЁТНОЕ СЕЧЕНИЕ Объектом разработки является семиэтажный жилой дом из монолитного железобетона. Цель проекта разработка несущих конструкций. В процессе работы проектирования выполнены следующие исследования разработки: запроектированы и рассчитаны элементы монолитного каркаса перекрытие колонна фундамент.
39514. Крытая хоккейная площадка общей площадью 2800м2 178 KB
  Нагрузки и воздействия. Переходя с одного элемента на другой нагрузки и воздействия постоянно меняются принимая форму нормальных и поперечных сил изгибающих и крутящих моментов а в тесных рамках тонкостенных стержней преобразуются в изгибнокрутящие бимоменты или другие более сложные формы.85 Нагрузки и воздействия.1 Нагрузки и воздействия Место строительства г.
39515. Расчет и нормативные нагрузки на покрытие 1.88 MB
  В дипломном проекте определены расчетные и нормативные нагрузки на покрытие. Выполнен статический расчет несущих конструкций покрытия здания. Подобраны сечения колонны, поясов и раскосов ферм, которые обеспечивают их прочность, общую устойчивость, а также местную устойчивость элементов сечения. Запроектированы основные узлы крепления элементов.