Лекция 3
1. Оператор цикла с параметром
Многократно повторяющийся участок программы называется циклом. Одно повторение цикла называется итерацией. Операторы, выполняющиеся в цикле, называется телом цикла.
В языке С++ существует три типа циклов:
1) цикл с параметром;
2) цикл с предусловием;
3) цикл с постусловием.
Если цикл с параметром представить в общем виде, то он будет иметь следующий формат:
for (инициализация; выражение; модификации) оператор;
Инициализация – это действие, когда мы переменной присваиваем начальное значение, т. е. значение с которого наш цикл начинает работать. В скобках, где написано слово инициализация, можно задать тип переменной, которую будем инициализировать. Можно инициализировать сразу несколько переменных. В этом случае их надо перечислить через запятую.
Выражение определяет условие выполнения цикла: если его результат, приведенный к типу bool, равен true, цикл выполняется.
Модификация – это действие, которое осуществляется в процессе работы цикла. У нас имеется начальное значение, называемое инициализацией, и конечное значение, называемое выражением, а правило, по которому мы задаем, чтобы из начального условия прийти в конечное, называется модификацией. В части модификаций тоже можно написать несколько операторов через запятую.
Любая из частей может быть пропущена, но точки с запятой должны стоять на своих местах.
Оператор является телом цикла, т. е. одно действие, но с помощью цикла оно выполняется столько, сколько указано в цикле. Соответственно, если мы хотим задать группу операторов, то они помещаются в фигурные скобки.
Пример. Посчитать сумму чисел от 1 до 10.
#include <stdio. h>
#include <iostream>
using namespace std;
void main(){
int i, s=0,n;
cout <<"n=";
cin >>n;
for (i=1;i<=n;i++) s=s+i;
cout <<"s="<< s<<endl;
}
Пример. Вычислить сумму ряда S=1*2+2*4+3*8+4*16+…+n*2n
#include <iostream>
using namespace std;
void main()
{
int i, j,n, s;
cin >>n;
for (i=1,j=2,s=0;i<=n;i++,j=j*2)
s=s+i*j;
cout <<s;
}
2. Нахождение суммы ряда
Числовым рядом называется бесконечная сумма S некоторой последовательности.
S = a1+a2+a3+…+ai+… = 
С помощью разложения в числовой ряд можно вычислить многие из элементарных функций, например
,
при 
;
при 
.
Основная проблема при вычислении суммы числового ряда состоит в вычислении очередного члена последовательности. Можно выделить три подхода к решению этой проблемы:
1) использование формулы общего члена ряда;
2) использование рекуррентного соотношения;
3) смешанный подход, основанный на двух предыдущих.
Использование формулы общего члена ряда
Формула общего члена ряда это соотношение, с помощью которого можно вычислить очередной член ряда, используя его номер.
Так для ряда S = 2+4+6+8+10+… a1=2=2∙1, a2=4=2∙2, a3=6=2∙3, … ,
и, соответственно, формула общего члена: ai=2∙i, где i=1, 2, 3,… .
Данный метод для вычисления очередного члена ряда используется лишь в том случае, если формула является легко вычислимой.
Пример 2.1. Найти сумму ряда для первых N слагаемых.
Формула общего члена ряда:
ai=
, i=1, 2, 3,…
Поскольку эта формула легко вычислима, используем ее при составлении алгоритма.
#include <iostream>
using namespace std;
void main()
{
int i, n;
float s;
cin >>n;
for (i=1,s=0;i<=n;i++)
s=s+1/float(i);
cout <<s;
}
Использование рекуррентного соотношения
Понятие рекуррентной последовательности в курсе математики вводится так: пусть известно k чисел: а1, …, ak. Эти числа являются началом числовой последовательности. Следующие элементы этой последовательности вычисляются так:
ak+1 = F(a1, …, ak); ak+2 = F(a2, …, ak+1); ak+3 = F(a3, …, ak+2) …
Здесь F(…) – функция от k аргументов. Формула вида
ai = F(ai-k, …, ai-1)
называется рекуррентной формулой. Другими словами, рекуррентная последовательность – это бесконечный ряд чисел, каждое из которых, за исключением k начальных, вычисляется через предыдущие члены ряда.
Например, арифметическая и геометрическая прогрессии:
a1=1, a2=3, a3=5,… Рекуррентная формула: 
.
a1=1, a2=2, a3=4, … Рекуррентная формула: 
.
Глубина рекурсии в обоих случаях равна 1 (такую зависимость называют одношаговой рекурсией).
Числа Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Начиная с третьего элемента, каждое число равно сумме двух предыдущих, т. е. это рекуррентная последовательность с глубиной, равной 2. Рекуррентная формула для чисел последовательности Фибоначчи:
.
Для вывода рекуррентной формулы часто можно воспользоваться соотношением вида:
.
Получив f(i), мы по сути найдем основную часть рекуррентного соотношения, так как
.
Правда, при этом нельзя забывать о начальном условии, без которого рекуррентная формула не будет полной.
Определим рекуррентное соотношение для ряда: 
.
Положим
. Тогда
.
Получаем рекуррентное соотношение: 
.
Рекуррентное соотношение используется в тех случаях, когда следующий член ряда можно выразить через предыдущий (или предыдущие), а использование формулы общего члена приведет к появлению вложенных циклов, что сделает программу неэффективной.
Пример 2.2. Написать программу вычисления суммы N первых членов ряда 
. Выпишем члены ряда
.
Поскольку каждый член ряда может быть получен из предыдущего домножением на определенный множитель, а вычисление «в лоб» каждого члена ряда приведет к появлению вложенных циклов, эффективнее будет использовать рекуррентное соотношение. Выведем его
Полученное рекуррентное соотношение 
.
#include <iostream>
#include <iomanip>
using namespace std;
void main()
{
int i, n;
double x, a,s, b;
cin >>x>>n;
s=1;
a=1;
for (i=1;i<n;i++)// так как нумерация начинается с нуля, пишем i<n!!
{
a=-a*x*x/(2*i-1)/(2*i);
s=s+a;
}
cout <<setprecision(5)<<fixed<<s<<endl;
}
Одновременное использование формулы общего члена и рекуррентного соотношения
Оба рассмотренных выше способа: использование формулы общего члена и построение рекуррентного соотношения не исчерпывают всего многообразия числовых рядов. Может возникать ситуация, когда формула общего члена не является эффективно вычислимой и при этом невозможно построить рекуррентное соотношение. Часто такая ситуация находит свое разрешение, если каждый член ряда представить в виде произведения ai=bi∙ci и отдельно рассмотреть последовательности из bi и ci. При этом одна из последовательностей будет эффективно вычислима через общий член ряда, а другая через рекуррентное соотношение. Рассмотрим ряд 
. Формула общего члена 
. Представим ai=bi∙ci, bi=xi, 
. Последовательность из bi выражается рекуррентным соотношением 
, а последовательность из ci эффективно вычислима через формулу общего члена.
Если все три рассмотренных способа не позволят получить эффективное вычисление очередного члена ряда, тогда необходимо будет использовать механизм вложенных циклов.
3. Оператор цикла с предусловием
Цикл с предусловием реализует структурную схему, представленную на рисунке:
Формат оператора цикла с предусловием в С++:
while (<выражение>) <оператор>;
Выражение определяет условие повторения тела цикла, представленного простым или составным оператором. Тип выражения должен быть арифметическим или приводимым к нему. Выражение вычисляется перед каждой итерацией цикла.
Особенности цикла с предусловием:
1) В цикле с предусловием сначала вычисляется значение выражения – условия продолжения цикла. После чего, если условие было истинно (не равно нулю), выполняется тело цикла.
2) В теле цикла выполняется только один оператор. Если нужно выполнить несколько операторов, то используется составной оператор.
while (<выражение>)
{
<оператор 1>;
<оператор 2>;
...
<оператор n>;
}
3) Если при первой проверке значение выражения равно 0 (или false), цикл не выполнится ни разу, и управление передается оператору, следующему за телом цикла.
4) Условие в цикле whilе проверяется на один раз больше, по сравнению с числом повторений тела цикла.
5) Для избегания бесконечного выполнения в теле цикла должен быть оператор, влияющий на условие завершения цикла.
Пример 1. Найти сумму цифр произвольного целого числа с использованием цикла с предусловием.
#include "windows. h"
#include <iostream>
using namespace std;
void main()
{
setlocale (LC_ALL, "Russian")
int n, S;
cout<< "Введите целое число: ";
cin>>n;
n=abs(n);
S=0;
while (n)
{
S+=n%10; // n%10 – «выделяет» последнюю цифру числа
n/=10; ; // n/10 – «зачеркивает» последнюю цифру
}
cout<< "Сумма цифр числа: "<<S<<"\n" ;
}
Построим трассировочную таблицу для n=123.
Команда | n | S | Условие |
S=0 | 123 | 0 | |
n=abs(n) | 123 | ||
n<>0 | 123<>0? Да | ||
S+=n%10 | 0+3=3 | ||
n/=10 | 12 | ||
n<>0 | 12<>0? Да | ||
S+=n%10 | 3+2=5 | ||
n/=10 | 1 | ||
n<>0 | 1<>0? Да | ||
S+=n%10 | 5+1=6 | ||
n/=10 | 0 | ||
n<>0 | 0<>0? Нет |
Оператор цикла или один из операторов, составляющих тело цикла, обязательно должен изменить условие продолжения цикла. Особенность цикла с предусловием – тело цикла может не выполниться ни разу в случае, когда n=0.
Пример 2. Найти все делители целого положительного числа.
#include <iostream>
using namespace std;
void main()
{
int num;
cin>>num;
int half=num/2; // половина числа
int div=2; // кандидат на делитель
while (div <= half)
{
if (!(num%div)) cout<<div<<"\n";
div++;
}
}
Поиск наибольшего общего делителя
Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел. На английском языке «наибольший общий делитель» пишется «greatest common divisor», и распространённым его обозначением является gcd.
Наибольший общий делитель двух натуральных чисел — это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 32 и 24 имеются общие делители: 2, 4, 8. Наибольшим общим делителем является число 8. Это записывается так: НOД(32, 24) = 8.
Достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида.
Идея этого алгоритма основана на следующей формуле:
1) Если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма.
2) Заменить большее число разностью большего и меньшего из чисел;
3) Вернуться к выполнению п.1.
Рассмотрим этот алгоритм на примере М=32, N=24:
M | 32 | 8 | 8 | 8 |
N | 24 | 24 | 16 | 8 |
Получили: НОД(32, 24) = НОД(8, 24) = НОД(8, 16) = НОД(8, 8) = 8, что верно.
Программа нахождения НОД с использованием вычитания:
#include <iostream>
using namespace std;
void main()
{
int N, M;
cin>>N>>M;
/* НОД(M, N)=НОД(M-N, N), если M>N; НОД(M, N)=НОД(N, N-M), если M<N; НОД(M, M)=M */
while (M!=N)
if (M>N) M-=N;
else N-=M;
cout<< M<<"\n" ;
}
Модифицированные алгоритмы Евклида
Программу вычисления НОД можно составить иначе, если воспользоваться операцией mod – получением остатка от деления.
Вариант 1
Идея алгоритма исходит из справедливости следующих равенств:
Рассмотрим этот алгоритм на примере М=32, N=24:
M | 32 | 24 | 8 |
N | 24 | 8 | 0 |
Получили: НОД(32, 24) = НОД(24, 8) = НОД(8, 0) = 8.
Программа нахождения НОД с использованием операции остатка от деления:
#include <iostream>
using namespace std;
void main()
{
int N, M,R;
cin>>N>>M;
/* НОД(M, N)=НОД(N, M mod N), НОД(M,0)=M */
while (N!=0)
{
R=M % N;
M=N;
N=R;
}
cout<<M<<"\n" ;
}
Вариант 2
Напишем еще один модифицированный вариант алгоритма Евклида, использующий соотношения
Трассировка этого алгоритма на примере М=32, N=24:
M | 32 | 8 | 8 |
N | 24 | 24 | 0 |
Получили: НОД(32, 24) = НОД(8, 24) = НОД(8, 0) = 8.
Вариант программы:
#include <iostream>
using namespace std;
void main()
{
int N, M;
cin>>N>>M;
/* НОД(M, N)=НОД(M mod N, N), если M≥N; НОД(M, N)=НОД(M, N mod M), если M<N;
НОД(M,0)=НОД(0,N)=M+N */
while (N!=0 && M!=0)
if (M>N) M %=N;
else N%=M;
cout<< M+N<<"\n" ;
}
4. Оператор цикла с постусловием
Цикл с постусловием реализует структурную схему, изображенную на рисунке:
Формат оператора цикла с постусловием в С++:
do <тело цикла> while (<выражение>);
Или, если тело цикла состоит более чем из одного оператора, используется конструкция:
do
{
<Оператор 1>;
<Оператор 2>;
<Оператор N>;
}
while (<выражение >);
Особенности цикла с постусловием:
1) Сначала выполняется простой или составной оператор, составляющий тело цикла, а затем вычисляется выражение – условие продолжения цикла. Тип выражения должен быть арифметическим или приводимым к нему.
2) Если условие истинно (или значение выражения не равно 0), то тело цикла выполняется еще раз.
3) Цикл завершается, когда условие продолжения цикла будет равно false (или равно 0).
4) Условие в цикле do... whilе проверяется столько же раз больше, сколько и тела цикла.
5) Тело цикла выполнится минимум один раз.
6) Для избегания бесконечного выполнения в теле цикла должен быть оператор, влияющий на условие завершения цикла.
Пример 3. Найти сумму цифр произвольного целого числа с использованием цикла с предусловием.
#include <iostream>
using namespace std;
void main()
{
int n, S;
cin>>n;
n=abs(n);
S=0;
do
{
S+=n%10; // n%10 – «выделяет» последнюю цифру числа
n/=10; ; // n/10 – «зачеркивает» последнюю цифру
}
while (n);
cout<< S<<"\n" ;
}
Определение простоты числа
Простые числа – это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число. Примеры простых чисел: 2 , 3, 5, 7, 11, 13 … Единица имеет только один делитель – само себя и поэтому она не может относиться ни к простым, ни к составным числам.
Во все времена люди хотели найти как можно большее простое число. Пока люди считали только при помощи карандаша и бумаги, им нечасто удавалось обнаружить новые простые числа. До 1952 г. самое большое известное простое число состояло из 39 цифр. Теперь поиском все больших простых чисел занимаются компьютеры.
Пример 4. Определить, является ли натуральное число N простым с использованием цикла с постусловием.
Самый простой путь решения этой задачи – проверить, имеет ли данное число N (N>=2) делители в интервале [2; 
]. Здесь используется свойство: наименьшее число, на которое делится натуральное число N, не превышает целой части квадратного корня из числа N. Если делители есть, число N – составное, если – нет, то – простое. При реализации алгоритма разумно делать проверку на четность введенного числа, поскольку все четные числа делятся на 2 и являются составными числами, то, очевидно, что нет необходимости искать делители для этих чисел. Из четных чисел только число 2 является простым.
#include <iostream>
#include “windows. h”
using namespace std;
void main()
{
setlocale (LC_ALL, "Russian")
int N, i;
cout<< "Введите натуральное число: ";
cin>>N;
i=1;
do
i+=1;
while (i * i < N && N % i!= 0);
if (i * i < N) cout<< "Число "<<N<<" - составное \n";
else cout<< "Число "<<N<<" - простое\n";
}
Разложение числа на простые сомножители
Пример 5. Составить программу, печатающую разложение на простые множители заданного натурального числа N > 0 (другими словами, требуется печатать только простые числа и произведение напечатанных чисел должно быть равно N; если N = 1, печатать ничего не надо).
Алгоритм разложения натурального числа на простые множители: берем первое простое число - 2 и пробуем делить данное натуральное число на 2, если число делится на 2, тогда надо 2 записать, а число разделить на 2 и снова полученный результат пробуем делить на два, если делится, тогда повторяем процесс деления, если не делится, тогда надо пробовать делить на следующее простое число - 3 и так далее.
Например, число 360 можно разложить на следующие простые множи=222335.
Программа (вариант 1):
#include <iostream>
using namespace std;
void main()
{
int N, k,i;
cin>>N;
k=N;
/* инвариант: произведение напечатанных чисел и k равно N,
напечатаны только простые числа*/
while (k!= 1)
{
i = 2; // начинаем с первого простого числа - 2
/* инвариант: k не имеет делителей в интервале (1,i) */
while (k % i!= 0)
i += 1;
/* инвариант: i - наименьший делитель k, больший 1, следовательно, простой */
cout<< i<<" " ;
k /=i ; // делим число k на i
}
}
Предложенный варианты программ не является эффективными: он заставляет компьютер выполнять много лишних проверок на деление.
Более совершенный алгоритм:
Сначала находим все делители, равные 2. Для этого последовательно делим число 360 на 2.
После этого, полученный результат делим на нечетные числа, т. к. все остальные четные числа не являются простыми. Причем на каждое нечетное число делим до тех пор, пока такое деление будет возможным.
Делим на 3: 45:3 = 15, 15:3 = 5.
Делим на 5: 5:5 = 1.
Делим на 7, не делится, пробуем делить на следующее нечетное число.
Делим на 9, не делится, переходим к следующему нечетному числу.
Делим на 11, не делится, и так далее.
Также можно получить более эффективный алгоритм, если использовать тот факт, что составное число имеет делитель, не превосходящий квадратного корня из этого числа.
Для этого вместо i+=1; в варианте 2 программы можно написать следующий код:
if (i*i>N) i=N;
else i+=1;
