Министерство финансов Российской Федерации

Всероссийская государственная налоговая академия

ИНФОРМАТИКА И ПРОГРАММИРОВАНИЕ

Бакалавры: 230700 "Прикладная информатика"

Язык программирования С++

Лабораторная работа № 08

ПРОГРАММИРОВАНИЕ ИТЕРАЦИОННЫХ ЦИКЛИЧЕСКИХ

ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

Автор профессор кафедры "Прикладной информатики в экономике"

кандидат технических наук Л.К. Кузнецов

10 апреля 2012 г.

Москва

ВГНА

2012

Лабораторная работа № 03

ПРОГРАММИРОВАНИЕ ИТЕРАЦИОННЫХ ЦИКЛИЧЕСКИХ

ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

Цель работы:

Ознакомиться:

• - с понятием итерационного циклического вычислительного процес­са (ЩВП);

• - с понятием ИЦВП с известным заранее и неизвестным заранее чис­лом циклов;

• с правилами (алгоритмами) накопления (вычисления) сумм и произ­ведений в цикле;

• с правилами вывода рекуррентных формул;

• с оператором цикла со спецификацией итерационного типа (типа условия);

Получить практические навыки:

• по накоплению сумм и произведений в цикле;

• по выводу рекуррентных формул;

• по программированию ИЦВП.

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

1. Изучить методику вывода рекуррентных соотношений.

2. Изучить алгоритмы рекуррентных вычислений.

1. Краткие теоретические сведения

Ниже приводятся минимальные сведения, необходимые только для вы­полнения лабораторной работы

1.1. Понятие ицвп

Итерация – результат многократного применения какой-либо математической операции. Пусть у = f(х), тогда последовательность f(х), f[f(х)], f{f[f(х)]} есть последовательность итераций функции f(х). В частности, если f(х) = ах, то эта последовательность записывается в виде ах, а²х, а³х, … , аⁿх. Число, показывающее, сколько раз применена операция, называется показателем итерации, процесс составления итерации – итерирование – находит многочисленные приложения в программировании циклических вычислительных процессов.

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

Примером ИЦВП является вычисление приближенного значения квадрат­ного корня из числа х по формуле Ньютона:

где У₀ – заданное начальное приближение корня.

Так как по формуле (8.1) можно при некотором k вычислить не точ­ное, а приближенное значение величины , то в условиях за­дачи необходимо указать величину , характеризующую требуемую точ­ность вычислений. Тогда определение корня состоит в многократном вы­числении (пересчете) по формуле (8.1), в правой части которой исполь­зуется предыдущее значение переменной y. Вычисление следует прекратить при достижении требуемой точности, то есть при выполнении ус­ловия

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

Рассмотренный выше итерационный вычислительный процесс можно представить в виде блок-схемы (рис. 8.1).

Рис.8.1. Блок-схема алгоритма вычисления квадратного корня по формуле Ньютона

Очевидно, что никаких изменений в структуре цикла при переходе от арифметических циклов, рассмотренных в предыдущей лабораторной рабо­те, к итерационным не происходит. Итерационный ЦВП состоит из тех же частей и строится по той же типовой блок-схеме, что и арифметический.

ИЦВП можно разделить на ЦВП, в которых число повторений цикла заранее известно, и на ЦВП, в которых число повторений цикла заранее неизвестно.

В ИЦВП, в которых число повторений цикла заранее известно, провер­ка окончания цикла происходит по специальной переменной – счетчику циклов. Например, при вычислении суммы вида

используется рекуррентная (итерационная) формула

для определения очередного k-го члена суммы через значение предыду­щего k-1 члена этой суммы. При этом число циклов, необходимое для вычисления суммы (8.3), известно заранее и равно n.

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

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

На языке С++ алгоритмы ИЦВП могут быть описаны с помощью уже рас­смотренных ранее операторов присваивания, перехода и условного опера­тора. Однако запись алгоритмов в этом случае получается сложной и излишне громоздкой. Поэтому в языке С++ для организации ИЦВП предус­мотрены специальные оператор цикла: оператор цикла с предусловием while и оператор цикла с постусловием do.. while (рас­смотрены в предыдущей работе).

Существует классический набор задач, при решении которых используются ИЦВП. Все эти задачи, помимо общего, что они итерационные, имеют свои особенности. В алгоритмах вычисления сумм, произведений, количеств, пределов, последовательностей особенностью является содержание тела цикла. При вычислении суммы к значению суммы многократно прибавляются новые значения слагаемых. При вычислении произведения значение многократно помножается на очередной сомножитель. При вычислении количеств значение счетчика увеличивается на 1. При вычислении предела или последовательности значение многократно вычисляется на базе предыдущего значения. Итоговое значение, кроме вычисления последовательностей, чаще единственное, так как все остальные вычисленные значения являются промежуточными. Управление циклами этого вида выполняется также с использованием управляющих переменных, которыми фактически служит номер вычисляемого значения (слагаемого, множителя, элемента последовательности). Если число повторений известно, цикл должен быть арифметическим. В задачах вычисления с указанной точностью цикл должен быть итерационным, так как заранее не может быть известно число повторений, которое понадобится, чтобы достичь заданной точности.

Организация ИЦВП чаще всего опирается на рекуррентные формулы. Рассмотрим применение рекурсии в алгоритмах вычисления сумм и про­изведений.