Инструкция while
Цикл – это алгоритмическая структура в которой одни и те же инструкции выполняются периодически в зависимости от условия. В C++ используется несколько разновидностей циклов. Цикл while реализует алгоритмическую структуру цикл с предстусловием.
Синтаксис
while (условие) {
Тело цикла
}
Блок-схема
В этом цикле условие проверяется вначале. Пока условие имеет значение отличное от нуля или логическое выражение имеет значение true, то цикл делает шаг – выполняется некоторый набор инструкций (одна или более), называемый телом цикла. Шаги цикла будут выполняться до тех пор, пока позволяет условие. Если проверяемое условие ложно изначально, то инструкции, входящие в тело цикла, не выполняются, а выполняются инструкции находящиеся за циклом (после }). Иногда требуется организовать бесконечный цикл. Выход из такого цикла должен быть запрограммирован внутри тела цикла. “Бесконечный цикл” можно организовать следующим условием: while (true) {}.
Цикл while является универсальным циклом. В тоже время разработчик должен программировать изменение значений переменных в теле цикла так, чтобы эти изменения влияли на условие выхода из цикла. Неверно составленный программный код может привести к “зацикливанию” (т. е. невозможности выхода из цикла).
Рассмотрим пример.
Постановка задачи: Вывести n раз число k.
Для решения данной задачи нам необходимо использовать переменную-счетчик и определить её начальное значение, равное нулю, перед входом в цикл.
Программа 8.1
#include <iostream>
using namespace std;
int main() {
int n, k, i = 0;
cout << "n = "; cin >> n;
cout << "k = "; cin >> k;
while (i < n) {
++i;
cout << k << " ";
}
return 0;
}
Решение этой задачи можно реализовать иначе – без счетчика. В программе используется операция декремента в условии.
Программа 8.2
#include <iostream>
using namespace std;
int main() {
int n, k;
cout << "n = "; cin >> n;
cout << "k = "; cin >> k;
while (n--)
cout << k << " ";
return 0;
}
Накопители суммы и произведения
Часто требуется в цикле “накапливать” сумму или произведение. Для этого в программе используются переменные-накопители. Начальное значение этих переменных не должно влиять на конечный результат. Таким образом, для получения суммы начальное значение накопителя (обычно – s) должно быть равно нулю, а для произведения (обычно – p) – единице. Счетчик тоже, своего рода, накопитель, следовательно, перед циклом он всегда обнуляется.
Пример накопления произведения – это вычисление факториала числа. Факториал – величина, которая имеет очень быстрый рост. Поэтому, нужно предусмотреть переполнение соответствующего типа.
Программа 8.3 Вычислить факториал числа n, n! = 1 * 2 * 3 * ... * n.
#include <iostream>
using namespace std;
int main() {
int n, i = 0;
auto f = 1ull;
cout << "n = "; cin >> n;
while (i < n) {
++i;
f *= i;
}
cout << n << "! = " << f << endl;
return 0;
}
Данную задачу можно решить и другим способом, с помощью операции декремента:
Программа 8.4
#include <iostream>
using namespace std;
int main() {
int n;
auto f = 1ull;
cout << "n = "; cin >> n;
int i = n;
while (n > 0)
f *= n--;
cout << i << "! = " << f << endl;
return 0;
}
Пример накопления суммы – это задача на подсчет разрядов числа и определения их суммы. Работу программы можно ускорить, если использовать операцию побитового сдвига (подумайте как реализовать такое решение).
Программа 8.5 Дано натуральное n (> 0). Определить сумму цифр данного числа и их количество.
#include <iostream>
using namespace std;
int main() {
unsigned long long n;
int s = 0, i = 0;
cout << "n = "; cin >> n;
while (n > 0) {
++i;
s += n % 10;
n /= 10;
}
cout << "i = " << i
<< "\ns = " << s
<< endl;
return 0;
}
Инструкция do while
Алгоритмическую структуру “цикл с постусловием” в языке программирования C++ реализует инструкция цикла do while.
Блок-схема
Синтаксис
do {
Тело цикла
} while (условие)
Поскольку условие проверяется в конце цикла, то тело цикла (одна или более инструкций) будет выполнено хотя бы один раз. В этом существенное отличие инструкций while и do while.
Пока условие имеет значение, отличное от нуля или true выполняется тело цикла (это его отличает от соответствующего цикла в ЯП Pascal). Если проверяемое условие ложно изначально, то инструкции, входящие в тело цикла, будут выполнены один раз, затем произойдет выход из цикла и будут выполняться инструкции следующие за циклом.
Эту разновидность цикла удобно использовать, когда есть необходимость производить анализ входных данных. В общем случае, инструкции while и do while взаимозаменяемы.
Программа 8.6 Вывести n-первых четных положительных чисел (включая 0).
#include <iostream>
using namespace std;
int main() {
int n, i = 0;
cout << "n = "; cin >> n;
do {
cout << i++ * 2 << " ";
} while (i < n);
cout << endl;
return 0;
}
В математике известны сходящиеся ряды. Сумма членов ряда стремится к определенному значению на бесконечности (к пределу), например, сумма ряда 1 + 1/1! + 1/2! + 1/3! + ... равна числу е (Эйлера). Точность вычислений зависит от количества членов ряда. Этот ряд сходится довольно быстро. Определить количество членов ряда для получения итогового результата с точностью до 10-10.
Программа 8.7.1
#include <iostream>
#include <cmath>
using namespace std;
int main() {
const double eps = 1.0e-10;
double s = 2.0, s1, s2;
auto f = 1ull;
auto i = 2u;
do {
f *= i;
s1 = s;
s += 1/static_cast<double>(f);
s2 = s;
i++;
} while (fabs(s1 - s2) > eps);
cout.precision(11);
cout << "i = " << i
<< "\ns = " << s << endl;
return 0;
}
Вывод программы
i = 15 s = 2.7182818285
Однако данный алгоритм не является эффективным, поскольку мы производим сложные вычисления, связанные с вычислением факториала. На самом деле, алгоритм можно существенно ускорить и упростить, если использовать рекуррентную формулу для определения очередного слагаемого на каждом шаге цикла. Краткая математическая запись ряда для вычисления числа e и его рекуррентная формула имеют вид:
Рекуррентная формула позволяет избежать вычисления факториала числа (если ряд сходится медленно, то это, в добавок, может привести к переполнению). Таким образом, количество используемых арифметических операций становится меньше, а значит повышается эффективность как по времени, так и по памяти. Измененная программа будет иметь следующий вид:
Программа 8.7.2
#include <iostream>
#include <cmath>
using namespace std;
int main() {
const double eps = 1.0e-10;
double s = 1.0, s1, s2 = 1.0;
auto i = 1u;
do {
s1 = s;
s2 = s2/static_cast<double>(i);
s += s2;
i++;
} while (fabs(s1 - s) > eps);
cout.precision(11);
cout << "i = " << i
<< "\ns = " << s << endl;
return 0;
}
Инструкция if вложенная в цикл
В циклах очень часто приходится прибегать к использованию условной инструкции. Однако, если задачу всё же можно решить без if, то следует выбирать именно этот вариант, так как if увеличивает время выполнения и сложность алгоритма. Например, задачу (8.6) вывода четных чисел можно было бы решить с помощью if так:
while (i < n * 2) {
if (i % 2 == 0) cout << i << " ";
i++;
}
Примером использования условной инструкции являются задачи на анализ разрядов вводимых чисел. Например. Вводится последовательность из n (n > 0) натуральных чисел. Определить количество трехзначных чисел в данной последовательности оканчивающихся на 7.
Программа 8.8
#include <iostream>
using namespace std;
int main() {
int n, i = 0;
cout << "n = "; cin >> n;
do {
int d;
cin >> d;
if (d / 1000 == 0 &&
d / 100 != 0 &&
d % 10 == 7)
++i;
} while (--n);
cout << "i = " << i << endl;
return 0;
}
Инструкции break и continue
Инструкция break прерывает выполнение циклов while, do while (и for, который мы рассмотрим на следующем занятии) и передает управление выполнения программы инструкции, следующей за блоком. Это означает, что если используется структура вложенных циклов, то будет осуществлен выход только из вложенного цикла (если break будет выполнена в нем), внешний же цикл продолжит свою работу.
Программа 8.9 Дано натуральное число n. Определить, является ли оно простым.
#include <iostream>
using namespace std;
int main() {
int n, i = 2;
bool k = true;
cout << "n = "; cin >> n;
while (i <= n / 2) {
if (!(n % i)) {
k = false;
break;
}
i++;
}
cout << "Число "
<< n
<< (k ? " простое" : " не является простым");
return 0;
}
В отличие от break – continue прерывает выполнение только текущей итерации (то есть, выполнение инструкций тела цикла) и передает выполнение на вычисление условия. При этом инструкции, следующие за continue, игнорируются. Данная инструкция применяется не часто, но может быть использована для контроля состояния допустимости значения выражений в теле цикла. Особенность работы continue с циклом for мы рассмотрим на следующем уроке.
Следует сказать, что многие разработчики стараются не использовать в циклах эти инструкции. Однако последние повышают читаемость программы.
Например. Постановка задачи. Протабулировать значение функции f(x) = 2/x с шагом 1 на отрезке [-5, 5]
Программа 8.10
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
int i = -5;
while (i <= 5) {
if (i == 0) {
cout << "В точке 0 - не определена" << endl;
i += 1;
continue;
}
cout << setprecision(2)
<< "x = "
<< setw(2)
<< i
<< setw(10)
<< "f(x) = "
<< setw(5)
<< fixed
<< 2.0 / i
<< endl;
i += 1;
}
return 0;
}
Вложенные циклы
Когда на каждом шаге цикла требуется выполнять циклические операции применяется структура вложенных циклов, т.е. один цикл находится внутри другого цикла. Посмотрим пример такой программы. В этой программе вывод представлен в виде квадратной таблицы (матрицы).
Программа 8.11 Вывести таблицу Пифагора. Таблица Пифагора представляет собой матрицу в которой в первом столбце и первой строке числа от 1 до 9, а на пересечении строк и столбцов (элемент матрицы) произведение номера строки на номер столбца.
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
int i = 0;
while (++i < 10) {
int j = 0;
while (++j < 10) {
cout << i * j << setw(3);
}
cout << '\n';
}
return 0;
}
Вывод программы:
1 2 3 4 5 6 7 8 9 2 4 6 8 10 12 14 16 18 3 6 9 12 15 18 21 24 27 4 8 12 16 20 24 28 32 36 5 10 15 20 25 30 35 40 45 6 12 18 24 30 36 42 48 54 7 14 21 28 35 42 49 56 63 8 16 24 32 40 48 56 64 72 9 18 27 36 45 54 63 72 81
while не является идеальным инструментом для вывода матриц. Для этих целей лучше подходит цикл for, который мы рассмотрим на следующем уроке. Для того, чтобы сделать программу компактной, инкрементацию счетчика мы поместили в условие.Следует избегать слишком большой вложенности. Однако, даже при многократной вложенности, можно составить более эффективный алгоритм, в частности, в задачах перебора разрядов числа. Приведем пример такой задачи. Для определения времени выполнения алгоритма воспользуемся библиотекой chrono.
Программа 8.12 Среди трехзначных чисел вывести те числа, сумма разрядов которых равна k.
#include <chrono>
#include <iostream>
using namespace std;
using namespace chrono;
int main() {
int a = 1, k;
cout << "k = "; cin >> k;
auto start = system_clock::now();
while (a < 10) {
int b = 0;
while (b < 10) {
int c = 0;
while (c < 10) {
if (a + b + c == k)
cout << a * 100 + b * 10 + c << " ";
c++;
}
b++;
}
a++;
}
auto end = system_clock::now();
auto elapsed = end - start;
cout << "\n"
<< duration_cast<microseconds>(elapsed).count()
<< " мкс"
<< endl;
return 0;
}
k = 6 105 114 123 132 141 150 204 213 222 231 240 303 312 321 330 402 411 420 501 510 600 49 мкс
Аналог программы без вложенных while:
Программа 8.13
#include <chrono>
#include <iostream>
using namespace std;
using namespace chrono;
int main() {
int a = 100, k;
cout << "k = "; cin >> k;
auto start = system_clock::now();
while (a < 1000) {
if (a / 100 + a / 10 % 10 + a % 10 == k)
cout << a << " ";
a++;
}
auto end = system_clock::now();
auto elapsed = end - start;
cout << "\n"
<< duration_cast<microseconds>(elapsed).count()
<< " мкс"
<< endl;
return 0;
}
k = 6 105 114 123 132 141 150 204 213 222 231 240 303 312 321 330 402 411 420 501 510 600 76 мкс
Хотя результаты тестов с каждым запуском обеих программ будут различаться, тем не менее, программа 8.12 выполняется быстрее на большинстве тестов.
Ещё одним примером уместного применения вложенных циклов while является классический алгоритм разложения числа на простые множители.
Программа 8.14
#include <iostream>
using namespace std;
int main() {
unsigned n, i = 2;
cout << "n = "; cin >> n;
while (n > 1) {
while (n % i == 0) {
cout << i << " ";
n = n / i;
}
i++;
}
return 0;
}
Вопросы
1. Назовите отличия циклов while и do while. Можно ли заменить цикл while на do while? А наоборот?
2. Можно ли заменить инструкции break и continue на другие конструкции языка?
3. Как работает структура вложенных циклов в программе 8.12?
Практические задания
- Вывести на экран все целые степени числа
2от0доn. - Дано вещественное число
Aи целое числоN (> 0). НайтиAв степениN:AN = A·A· … ·A - Даны целые положительные числа
NиK. Найти сумму1K + 2K + … + NK. - Найдите среди трехзначных чисел такие, которые имеют максимальное число делителей.
