Программирование циклических алгоритмов


Инструкция while

Цикл – это алгоритмическая структура в которой одни и те же инструкции выполняются периодически в зависимости от условия. В C++ используется несколько разновидностей циклов. Цикл while реализует алгоритмическую структуру цикл с предстусловием.

Синтаксис
while (условие) {
    Тело цикла
}
Блок-схема

15
В этом цикле условие проверяется вначале. Пока выражение (или логическое выражение) в условии имеет значение отличное от нуля (или логическое выражение имеет значение true), то цикл делает шаг – выполняется некоторый набор инструкций (одна или более), называемый телом цикла. Шаги цикла будут выполняться до тех пор, пока значение логического выражения в условии не станет равным false или (если это не логическое выражение) равным нулю. Если проверяемое условие ложно изначально, то инструкции, входящие в тело цикла, не выполняются, а управление передается на инструкции находящиеся за циклом (т. е. после }). Иногда требуется организовать бесконечный цикл. Выход из такого цикла должен быть запрограммирован внутри тела цикла. “Бесконечный цикл” можно организовать следующим условием: while (true) {}.
Цикл while является универсальным циклом. От разработчика требуется программировать изменение значений переменных в теле цикла так, чтобы эти изменения влияли на условие выхода из цикла. Неверно составленный программный код может привести к “зацикливанию” (т. е. невозможности выхода из цикла).
Рассмотрим пример на этот тип цикла.
Постановка задачи: Вывести n раз число k.
Для решения данной задачи нам необходимо использовать переменную-счетчик и определить её начальное значение, равное нулю, перед входом в цикл.

Программа 8.5.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.5.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) – единице. Счетчик тоже, своего рода, накопитель, следовательно, перед циклом он всегда обнуляется.

Задача учебника. Даны целые x и y. Не используя операции деления получить частное q и остаток r от деления числа x на число y.

Программа 8.5.3
#include <iostream>
using namespace std;

int main() {
    int n, k;
    cout << "x = "; cin >> x;
    cout << "y = "; cin >> y;
    int r = x;
    int q = 0;
    while (r >= y) {
        r = r - y; // или r -= y
        q = q + 1; // или q++
    }
    cout << "Частное q = " << q
         << "\nОстаток r = " << r
         << endl;
    return 0;
}

Рассмотрим пример в котором используется накопление произведения. Постановка задачи: дано целое n. Вычислить факториал числа n, n! = 1 * 2 * 3 * ... * n (n < 20). Факториал – величина, которая имеет очень быстрый рост. Поэтому, нужно предусмотреть переполнение типа. Будем использовать максимально широкий целый тип (unsigned long long).

Программа 8.5.4
#include <iostream>
using namespace std;

int main() {
    int n, i = 0;
    unsigned long long f = 1;
    cout << "n = "; cin >> n;
    while (i < n) {
        ++i;
        f *= i;
    }
    cout << n << "! = " << f << endl;
    return 0;
}

Пример накопления суммы – это задача на подсчет разрядов числа и определения их суммы. Постановка задачи: Дано натуральное n (> 0). Определить сумму цифр данного числа и их количество.

Программа 8.5.5
#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 = s + n % 10; // или s += n % 10
        n = n / 10; // или n /= 10
    }
    cout << "i = "   << i
         << "\ns = " << s 
         << endl;
    return 0;
}

Инструкция do while

Алгоритмическую структуру “цикл с постусловием” в языке программирования C++ реализует инструкция цикла do while.

Блок-схема

16

Синтаксис
do {
    Тело цикла
} while (условие)

Поскольку условие проверяется в конце цикла, то тело цикла (одна или более инструкций) будет выполнено хотя бы один раз. В этом существенное отличие инструкций while и do while.
Пока логическое выражение в условии имеет значение, отличное от нуля или true выполняется тело цикла (это его отличает от соответствующего цикла в ЯП Pascal). Если проверяемое условие ложно изначально, то инструкции, входящие в тело цикла, будут выполнены один раз, затем произойдет выход из цикла и будут выполняться инструкции следующие за циклом.
Эту разновидность цикла удобно использовать, когда есть необходимость производить анализ входных данных. В общем случае, инструкции while и do while взаимозаменяемы.
(Наглядность задачи учебеника под вопросом, поэтому заменяем на другой пример).
Постановка задачи: Вывести n-первых четных положительных чисел (включая 0).

Программа 8.5.6
#include <iostream>
using namespace std;

int main() {
    int n, i = 0;
    cout << "n = "; cin >> n;
    do {
        cout << i * 2 << " ";
        ++i;
    } while (i < n);
    return 0;
}

Инструкция if в теле цикла

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

    while (i <= n * 2) {
        if (i % 2 == 0) cout << i << " ";
        i++;
    }

Примером использования условной инструкции являются задачи на анализ разрядов вводимых чисел. Например. Вводится последовательность из n (n > 0) натуральных чисел. Определить количество трехзначных чисел в данной последовательности оканчивающихся на 7 (типичная задача ОГЭ).

Программа 8.5.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 and // and можно заменить на &&
			d / 100  != 0 and
			d % 10 == 7)
			++i;
	} while (--n);
	cout << "i = " << i << endl;
	return 0;
}

Обсуждение. Логическая операция and (“И”) требует истинности всех трех операндов. Подробнее об этой операции мы будем говорить в следующем учебном году.

Инструкции break и continue

Инструкция break прерывает выполнение циклов while, do whilefor, который мы рассмотрим ниже) и передает управление выполнения программы инструкции, следующей за блоком. Это означает, что если используется структура вложенных циклов, то будет осуществлен выход только из вложенного цикла (если break будет выполнена в нем), внешний же цикл продолжит свою работу. Например.
Постановка задачи: Дано натуральное число n. Определить, является ли оно простым.

Программа 8.5.8
#include <iostream>
using namespace std;

int main() {
	int n, i = 2;
	bool f = true;
	cout << "n = "; cin >> n;
	while (i <= n / 2) {
		if (!(n % i)) {
			f = false;
			break;
		}
		i++;
	}
	if (k)
		cout << "Число " << n << " простое" << endl;
	else
		cout << "Число " << n << " не является простым" << endl;
	return 0;
}

Обсуждение. Условие основано на том факте, что если не будут найдены делители до n / 2, то число является простым. Если же будет найден делитель, то нужно немедленно прервать выполнение цикла.
В отличие от breakcontinue прерывает выполнение только текущей итерации (то есть, выполнение инструкций тела цикла) и передает выполнение на вычисление условия. При этом инструкции, следующие за continue, игнорируются. Данная инструкция применяется не часто, но может быть использована для контроля состояния допустимости значения выражений в теле цикла.
Следует сказать, что многие разработчики стараются не использовать в циклах эти инструкции. Однако последние повышают читаемость программы.
Например. Постановка задачи. Протабулировать значение функции f(x) = 2/x с шагом 1 на отрезке [-5, 5]

Программа 8.5.9
#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++;
	}
	return 0;
}

Инструкция for

Инструкция for реализует алгоритмическую структуру цикл с параметром (или цикл со счетчиком). Цикл for применяется в том случае, когда в программе, прежде выполнения инструкций тела цикла, становится известным (или заранее определено) количество шагов этого цикла. В блок-схеме инструкция for изображается следующим образом:

Синтаксис:
for (инициализация; условие; модификация) {
    Тело цикла;
}

Цикл работает следующим образом:

  1. В начале происходит инициализация переменной-счетчика. Инициализация производится единожды, до выполнения цикла.
  2. Затем проверяется выражение-условие: если выражение имеет значение true, будет выполняться тело цикла.
  3. После выполнения инструкций тела цикла производится модификация (изменение) величины счетчика; обычно для этого используются операции инкремента или декремента.
Примечание: в C++ является правилом создавать определение переменной-счетчика в заголовке цикла. Но это не обязательно. Однако использование описания переменной-счетчика в заголовке цикла приводит к описанию локальной переменной (см. ниже), уничтожаемой автоматически при завершении работы цикла. Поэтому, без крайней необходимости, описание переменной-счетчика вне цикла for производить не следует.

Например. Постановка задачи: Вывести натуральные числа от 1 до n.

Программа 8.5.10
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
	int n;
	cout << "n = "; cin >> n;
	for (int i = 1; i <= n; i++)
		cout << i << setw(3); 
	return 0;
}

Пример учебника. Постановка задачи: Дано целое n и действительное a. Вычислить an (целую степень действительного числа).

Программа 8.5.11
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
	int n;
	double a, p = 1.;
	cout << "n = "; cin >> n;
	cout << "a = "; cin >> a;
	for (int i = 0; i < n; ++i)
		p *= a;
	cout << "a в степени n = " << p << endl; 
	return 0;
}

Если в теле цикла более чем одна инструкция, то инструкции тела цикла необходимо заключать в фигурные скобки (блок).
В процессе работы цикла for не рекомендуется изменять значение счетчика в теле цикла. Такую программу будет сложно читать (и часто это будет приводить к ошибкам), но сами изменяемые значения счетчика, использовать можно. Рассмотрим пример. Постановка задачи: Дано натуральное число N. Вывести все делители этого числа.

Программа 8.5.12
#include <iostream>
using namespace std;

int main() {
	int N;
	cout << "N = "; cin >> N;
	for (int i = 2; i <= N / 2; i++) {
		if (N % i == 0)
			cout << i << " ";
	}
	return 0;
}
N = 16000
2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 320 400 500 640 800 1000 1600 2000 3200 4000 8000 

Область видимости данных

Мы уже знакомы с понятием составной инструкции (блоком), заключенной в фигурные скобки. Фигурные скобки определяют не только блок, но также и область видимости (англ. scope) переменных объявляемых внутри этого блока (включая заголовок цикла). Если попытаться получить доступ к счетчику вне тела цикла, то программа выдаст ошибку. Переменная i (например, в программе 8.5.12) является локальной переменной цикла – её видимость определяют { }. После завершения работы цикла переменная i, объявленная в заголовке, уничтожается и получить значение i (вне цикла) станет невозможным.

Примечание. Как мы уже сказали, переменная-счетчик не обязательно должна быть локальной. Если есть необходимость, то переменная-счетчик может быть объявлена вне цикла. В этом случае спецификатор типа (например, int) не используется. Тип данных счетчика может быть любой из арифметических типов, но чаще всего – это int.

Если переменная определена как локальная, но не была произведена инициализация этой переменной, то её значение неопределено и обращение к ее значению будет считаться ошибкой. Попытка изменить значения локальных переменных вне блока приведет к ошибке, но внутри блока можно получать и изменять значения всех объектов определенных вне блока (за исключением других локальных объектов). Более подробно локальную и глобальную видимость переменных мы обсудим в следующем учебном году.
(Составьте программы раздела 3.5.4 на С++ самостоятельно).

Примеры решения задач
Вопросы
Темы сообщений
Задания А
Задания Б
Задания С
Ссылки
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (2 оценок, среднее: 5,00 из 5)
Загрузка...

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Print Friendly, PDF & Email

Обсуждение закрыто.