while (условие продолжения)

Лекция 5

Организация циклов. Операторы цикла.

Цикл – многократно повторяющаяся группа действий. Для удобства пользователей в языке есть 3 разных оператора цикла.

Оператор цикла while.

while (выражение) оператор;

Читается так: пока истинно выражение выполнять оператор.

Оператор цикла do while.

do оператор; while (выражение);

do {оператор;… оператор;} while (выражение);

Читается так: выполнять оператор (последовательность операторов) пока истинно выражение.

Как правило, при организации цикла одного оператора цикла недостаточно,т.к. выражение содержит некоторые переменные, при входе в цикл while эти переменные должны иметь значение, а значит перед входом в цикл им должно быть присвоено начпальное значение.

Пример1. Последовательно вводятся целые неотрицательные числа. Определить их сумму, наименьшее из них.

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

Итак есть совокупность x₁, x₂, … x_k ,-1; -1 – это, например, признак конца этой группы. Задача содержит 3 основных элемента действий:

(1) получить очередной элемент x т.е. считать его из последовательности.

(2) проверить условие окончания: x=-1?

(3) обработка элемента последовательности: добавление к сумме и проверка на минимум.

Int main()

{

int x,s,min;

cin>>x; // начальные

// установки s=0; min=x;

while (x>=0) // проверка условия окончания

{//обработка элемента

s=s+x; //s+=x; действие накопления

if (x<min) min=x; // min на текущий момент

//получение нового элемента

сin>>x;

}

cout << “s=”<<s<<” min=”<<min<<endl;

return 0;

}

Выводы: использование циклического алгоритма включает два момента

1)повторяющуюся часть алгоритма;

Начальные установки, текстуально они располагаются до while, а продумываются после написания while.

Рекомендуется: если в цикле идёт накопление, то необходимо позаботиться о начальных установках: для суммы – 0 (либо другое нач. значение), для произведения – 1 (либо другое нач. значение , не 0), для минимума – либо первый элемент,либо максимальное допустимое значение для типа, для максимума – либо первый элемент,либо минимальное допустимое значение для типа.

Схемы циклов.

Цикл с предусловием Цикл с постусловием

ложь выход

ист.

ложь

выход

Различают два типа циклов: итерационные и циклы с параметром

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

Это циклы, в которых заранее неизвестно и не может быть вычислено количество повторений цикла.

Рассмотрим пример 2. Для заданного x найти сумму s(x)c заданной точностью ε, где =

Накопление суммы бесконечного числа слагаемых невозможно, поэтому здесь используется суммирование конечного числа слагаемых и доказанный в Мат. Анализе факт: если в бесконечной сумме слагаемые знакочередующиеся и стремятся к 0 с ростом n, то погрешность накопленной частичной суммы определяется модулем первого из отброшенных членов, т.е. если |a_n|<ε,то найденная сумма вычислена с нужной точностью. Опять те же 3 элемента действий:

Условие окончания: |a_n|<ε

Обработка очередного слагаемого : S=S+ a_n

Получение очередного слагаемого нельзя выполнять “в лоб” ,т.к. возведение х каждый раз в свою степень неэффективно, лучше домножать степень х предыдущего слагаемого на (-x²). Вычисление факториала как целого числа возможно только для 2n<=12(для int16)и как вещественного тоже по причине погрешности , возникающей из-за хранения не более 15-16 десятичных знаков (для double).Поэтому самое выгодное получать очередное слагаемое домножением предыдущего на некоторую величину w(обозначим её так).

Для хранения слагаемого можно использовать переменную a, т.е. получение очередного слагаемого a=a*w.

//summa.cpp

#include <iostream>

#include <cmath>

using namespace std;

//сумма бесконечного ряда

const double eps=1.0E-9;

int main ()

{double x,s,r,a;

int k,n;

cout<<"vvedite x\n";

cin>>x;

//начальные установки

s=0;

n=0; r=-x*x;

a=1;

while (fabs(a)>=eps) // проверка на конец

{//обработка слагаемого

s=s+a;

//получение нового слагаемого

n=n+1; k=2*n;

a=a*r/((k-1)*k);

}

cout <<s<<endl;// вывод результата

return 0;

}

Итерационные циклы встречаются в задачах:

=накопления суммы, произведения с заданной точностью(см.пример2) =обработки рекуррентной последовательности. Говорят: элементы x₀,x₁,…x_k-1,x_k,x_k+1,…x_n-1,x_n,… образуют рекуррентную последовательность,если задано к начальных элементов x₀,x₁,…x_k-1 ,а следующие вычисляются по формулам

x_k=φ(x₀,x₁,…x_k-1)

x_k+1=φ(x₁,…x_k-1,x_{k) ………….}и т.д.

Могут быть поставлены задачи, например:

=если последовательность сходится, то можно найти предел последовательности с заданной точностью ε;

=найти N-ый элемент такой последовательности;

= найти такой элемент последовательности, для которого выполняется некоторое условие;

Особенность такого алгоритма в том, что нельзя гарантировать возможность хранить все вычисляемые элементы посл-ти. Хранят минимум элементов т.е. к+1. Для них заводят к+1 рабочие переменные r₀,r₁,…r_k-1,r_k и в них хранят к предыдущих элементов и вычисленный к+1 элемент. Это окно r₀,r₁,…r_k-1,r_k в процессе вычислений как бы передвигают по последовательности.

Схема такого алгоритма:

// начальные установки

r1=x₀; r2=; … rk= x_k-1;

while (условие продолжения)

{r0=r1; r1=r2; ….rk_1=rk; rk₌φ(r₀,r₁,…r_{k_1});}

Замечание: r0 либо ничего не присваивается в нач. установках (если r0 не используется в условии), либо присваивается некоторое фиктивное значение, которое позволит войти в цикл первый раз.

Пример 3. Для заданных целых a и b найти с=nod(a,b).

=

nod(20,12)=nod(12,8)=nod(8,4)= nod(4,0)=4 Здесь строится последовательность a,b, и остатков , пока не получится остаток =0, т.е. нужны 3 рабочие переменные.

cin >> a>>b;

int r0,r1,r2;

r1=abs(a); r2=abs(b);

while (r2!=0) // while (r2)

{ r0=r1; r1=r2; r2=r0%r1; }

сout<<”nod(a,b)=”<<r1<<endl;

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

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

Оператор цикла for.

For (инициализация; выражение; модификации) оператор;

For (инициализация; выражение; модификации) {оператор;… оператор;}

Инициализация – Здесь объявляются переменные, используемые в цикле, в том числе и параметр цикла,далее им могут быть присвоены начальные значения. Всё это выполняется в начале цикла(НУ).

Выражение – задаёт условие выполнения цикла, значение выражения приводится к типу bool, если оно истинно, тело цикла выполняется,если ложно – происходит выход из цикла.

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

for (int i=n/2; i<5,i<10; i++) cout<<i<<" ";// проверка возможностей цикла for

i<5,i<10- работает последнее условие.

Примеры. 1. int m,s; //s- сумма цифр m

cin>>m; for(s=0 ;m>0; s+=m%10,m/=10); cout<<s;

2. int n,i,r0,r1,r2; //n-ое число Фибоначчи

cin>>n;

for( r1=1, r2=1, i=2; i<=n; i++, r0=r1, r1=r2, r2=r1+r0);

cout<<r2<<endl;

Замечание О выборе эталона цикла.

Дано: [a,b],N. Отрезок делится на N частей длины h, найти

s=f(a)+f(a+h)+…f(a+N*h); пусть f(x)=cos(x);

double s=0, a, b; int N;

cin>>a>>b>>N;

double x=a, h=(b-a)/N;

while (x<b){s+=cos(x);x+=h;} //Здесь параметр цикла вещест. типа!

Возможны разные результаты на разных компьютерах:

h-вещ.типа и его значение представлено с погрешностью ε.

Либо h+ε,либо h-ε,в конце эталон будет либо a+N*h+N*ε,

либо a+N*h-N*ε, в первом случае последнее слагаемое не вычисляется.

Замечание: Циклы while и for взаимозаменяемы.

b1;

while(b2)
{

оператор;…оператор; ≈ for ( b1; b2; b3){оператор;…оператор;}
B3;

}

Кратные циклы.

Цикл наз. простым, если он не содержит в себе других циклов, в противном случае цикл наз. кратным. Уровень кратности – уровень вложенности цикла.

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

Рекомендации:

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

Замечания об оптимизции циклов:

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

2. Понижать сложность операций, выполняющихся в цикле: можно вычислять двояко: либо sqrt(x), либо pow(x,0.5).Лучше первый способ, т.к. во втором случае работают exp(x) и ln(x).

Поиск по сайту: