Инструкция while
Цикл – это алгоритмическая структура в которой одни и те же инструкции выполняются периодически в зависимости от условия. В C++ используется несколько разновидностей циклов. Цикл while
реализует алгоритмическую структуру цикл с предстусловием.
while (условие) { Тело цикла }
В этом цикле условие проверяется вначале. Пока условие имеет значение отличное от нуля или логическое выражение имеет значение true
, то цикл делает шаг – выполняется некоторый набор инструкций (одна или более), называемый телом цикла. Шаги цикла будут выполняться до тех пор, пока позволяет условие. Если проверяемое условие ложно изначально, то инструкции, входящие в тело цикла, не выполняются, а выполняются инструкции находящиеся за циклом (после }
). Иногда требуется организовать бесконечный цикл. Выход из такого цикла должен быть запрограммирован внутри тела цикла. “Бесконечный цикл” можно организовать следующим условием: while (true) {}
.
Цикл while
является универсальным циклом. В тоже время разработчик должен программировать изменение значений переменных в теле цикла так, чтобы эти изменения влияли на условие выхода из цикла. Неверно составленный программный код может привести к “зацикливанию” (т. е. невозможности выхода из цикла).
Рассмотрим пример.
Постановка задачи: Вывести n
раз число k
.
Для решения данной задачи нам необходимо использовать переменную-счетчик и определить её начальное значение, равное нулю, перед входом в цикл.
#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; }
Решение этой задачи можно реализовать иначе – без счетчика. В программе используется операция декремента в условии.
#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
) – единице. Счетчик тоже, своего рода, накопитель, следовательно, перед циклом он всегда обнуляется.
Пример накопления произведения – это вычисление факториала числа. Факториал – величина, которая имеет очень быстрый рост. Поэтому, нужно предусмотреть переполнение соответствующего типа.
Вычислить факториал числа 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; }
Данную задачу можно решить и другим способом, с помощью операции декремента:
#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; }
Пример накопления суммы – это задача на подсчет разрядов числа и определения их суммы. Работу программы можно ускорить, если использовать операцию побитового сдвига (подумайте как реализовать такое решение).
Дано натуральное 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
взаимозаменяемы.
Вывести 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.
#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.0 / 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
и его рекуррентная формула имеют вид:
Рекуррентная формула позволяет избежать вычисления факториала числа (если ряд сходится медленно, то это, в добавок, может привести к переполнению). Таким образом, количество используемых арифметических операций становится меньше, а значит повышается эффективность как по времени, так и по памяти. Измененная программа будет иметь следующий вид:
#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 / i; s += s2; i++; } while (fabs(s1 - s) > eps); cout.precision(11); cout << "i = " << i << "\ns = " << s << endl; return 0; }
Инструкция if вложенная в цикл
В циклах очень часто приходится прибегать к использованию условной инструкции. Однако, если задачу всё же можно решить без if
, то следует выбирать именно этот вариант, так как if
увеличивает время выполнения и сложность алгоритма. Например, задачу (9.8.6) вывода четных чисел можно было бы решить с помощью if
так:
while (i < n * 2) { if (i % 2 == 0) cout << i << " "; i++; }
Примером использования условной инструкции являются задачи на анализ разрядов вводимых чисел. Например. Вводится последовательность из n (n > 0)
натуральных чисел. Определить количество трехзначных чисел в данной последовательности оканчивающихся на 7
.
#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
будет выполнена в нем), внешний же цикл продолжит свою работу.
Дано натуральное число 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]
#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; }
Вложенные циклы
Когда на каждом шаге цикла требуется выполнять циклические операции применяется структура вложенных циклов, т.е. один цикл находится внутри другого цикла. Посмотрим пример такой программы. В этой программе вывод представлен в виде квадратной таблицы (матрицы).
Вывести таблицу Пифагора. Таблица Пифагора представляет собой матрицу в которой в первом столбце и первой строке числа от 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
.
Среди трехзначных чисел вывести те числа, сумма разрядов которых равна 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
:
#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 мкс
Хотя результаты тестов с каждым запуском обеих программ будут различаться, тем не менее, программа cpp-10.12 выполняется быстрее на большинстве тестов.
Ещё одним примером уместного применения вложенных циклов while является классический алгоритм разложения числа на простые множители.
#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; }