34663

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

Реферат

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

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

Русский

2013-09-08

41 KB

26 чел.

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

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

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

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

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

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


 

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

12267. Шолпан планетасы 1.29 MB
  Шолпанның бетін Жерден оптикалық құралмен бақылау қиын өйткені ол бұлтқа оранған. Сондықтан ғаламшардың физикалық сипаттары радиометод және ғарыштық зерттеулермен алынған. Шолпанның массасы Жердің 0815 массасына тең ал оның радиусы R = 6050км немесе Жердің 0950 р
12268. Қазақстанның ауылшаруашылығы кешенінің даму бағыттары 423.5 KB
  Кіріспе Ел экономикасының қуаттылығы оның қазба байлықтары мен минералдық ресурстар базасының көлеміне емес алысты аңғаратын экономикалық реформалар стратегиясының бәсекелестікке қабілетті жоғарғы технологиялық тауар мен сапалы қызмет жасауға жағдай туғызуға...
12269. Екі мәрте Социалистік Еңбек Ері Жазылбек Қуанышбаевтың туғанына – 110 жыл 54.5 KB
  Жаз дидарлы ата жайында айтсақ... Екі мәрте Социалистік Еңбек Ері Жазылбек Қуанышбаевтың туғанына – 110 жыл Даналар көп менің мына даламда Атағы аян осынау кең ғаламға. Дәріс алған табиғаттың өзінен Жүгінбеген қағаз бенен қаламға. ...
12270. Қазіргі Қазақстандағы аграрлық қатынастар және ауылдың әлеуметтік-экономикалық дамуы (1985-2006 жж.) 183 KB
  Автореферат диссертации Қазіргі Қазақстандағы аграрлық қатынастар және ауылдың әлеуметтікэкономикалық дамуы 19852006 жж. ИСИБАЕВА ЕЛИЗАВЕТА ИМАНҒАЛИҚЫЗЫ Қазіргі Қазақстандағы аграрлық қатынастар және ауылдың әлеуметтікэкономикалық дамуы 19852006 жж.07.00.02 – Отан тари
12271. Табиғатты аграрлық мақсатта пайдалану экономикасы 58.5 KB
  Табиғатты аграрлық мақсатта пайдалану экономикасы Жоспар Кіріспе 1.1. Аграрлық секторда топырақ ресурстарының маңызы. 1. 2. Экономика жағдайында жел және су эрозиялары. 1.3. Жерді рекультивациялау. Қорытынды Қолданылған әдебиеттер 1.1. Аграрлық се...
12272. Ыбырай Жақаев 66 KB
  Ыбырай Жақаев Ыбырай Жақаев Қазақ халқының бұрынғы қазіргі мемлекетіміздің тарихындағы ірі іргелі тұлғалардың бірі. Еңбек сүйгіштіктің адамдықтың адалдықтың азаматтықтың өлшемі. Мен таңғаламын: Ыбекең күріштен дүниежүзілік рекорд жасады. Ал көршілес Ақтөбе ...
12273. Ақша айналысы және ақша жүйесі 166.5 KB
  КУРСТЫҚ ЖҰМЫС Тақырыбы: Ақша айналысы және ақша жүйесі. Кіріспе Көптеген шетел басылымдарында ақша айналымы деген ұғым кездеспейді. 90 – жылдардың орта шеңіне дейін ТМД – мүше елдердің басылымдарында ақша айналысы деген ұғымдарға анықтама беріліп ол бір – бі
12274. Қазақстан Республикасындағы ақша жүйесі 260 KB
  Жоспар Кіріспе I. Ақшаның мәні мен қызметтері Ақшаның пайда болуы мен қажеттілігі Ақша түрлері Ақшаның қызметтері және экономикадағы рөлі мен қазіргі жағдайдағы дамуы II. Ақша айналысы 2.1. Ақша айналысы мен заңы 2.2. Ақшаның метеалды
12275. Ақша айналысының кұрылымы 148 KB
  Мазмұны Кіріспе 1.Ақша айналымының түсінігі және мәні 1.1 Ақша айналымы және ақша айналымының заңы 1.2 Қолма – қол және қолма – қол емес ақша айналымдары 2. Ақша айналысының кұрылымы 2.1 Ақша массасы және оның жылдамдығы 2.2 Ақша агрегаттар...