§ 8.9. Условная инструкция в цикле

Школьный курс python
Содержание

Для чего это нужно?

Циклы, которые мы рассмотрели в предыдущем уроке, либо обрабатывают изменяющиеся данные в самом цикле, либо обрабатывают входные данные. Однако часто приходится проверять состояние входных данных или выполнять некоторые действия в зависимости от значения некоторых данных на текущем шаге цикла. Поэтому неизбежно приходится применять условную инструкцию или условное выражение в теле цикла. Но нужно иметь ввиду, что некоторые алгоритмы можно запрограммировать и без использования условной инструкции в цикле, а сама условная инструкция увеличивает сложность алгоритма и время его выполнения. Например.
Задача 1. На отрезке от a до b (где a < b, натуральные числа) получить сумму четных чисел.

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

int main() {
	int a, b, s = 0;
    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;
    while (a <= b) {
        if (a % 2 == 0 )
			s += a;
		++a;
    }
    cout << "sum = " << s 
         << endl;        
    return 0;
}

Но использование условной инструкции можно избежать, если проверить какое значение имеет a: четное или нечетное?

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

int main() {
	int a, b, s = 0;
    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;
    a += a % 2 ? 1 : 0;
    while (a <= b) {
        s += a;
		a += 2;
    }
    cout << "sum = " << s 
         << endl;        
    return 0;
}

На больших отрезках программа 8.9.2 будет работать ощутимо быстрее.

Эти программы приведены в качестве простого примера, но не для образца! То есть, и программа 8.9.2 не является эффективной! В этой задаче можно обойтись и без цикла, если понять, что, на самом деле, ряд четных чисел (как и нечетных) есть прогрессия с шагом 2. Таким образом, достаточно проверить концы отрезка, чтобы выполнить вычисления по известной формуле для определения суммы n-членов арифметической прогрессии.

Анализ входных данных

Тем не менее, использование условной инструкции не избежать, если речь идет об анализе входных данных. Рассмотрим несколько типичных задач.
Задача 2. Дано целое число n. Определить каких цифр в числе больше четных или нечетных?

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

int main() {
	unsigned long long n;
	int even = 0, odd = 0;
    cout << "n = "; cin >> n;
    while (n != 0) {
        if (n % 10 % 2 == 0)
			++even;
		else
			++odd;
		n /= 10;
    }
    cout << "Больше "
		 << (even > odd ? "четных." : "нечетных.") 
		 << endl;
    return 0;
}

Блок-схема

В задаче №20.2 ОГЭ проверяется умение выпускника составлять алгоритмы по этой теме. Решим задачу демоверсии ОГЭ-2021.
Задача 3. Напишите программу, которая в последовательности натуральных чисел определяет количество чисел, кратных 4, но не кратных 7. Программа получает на вход количество чисел в последовательности, а затем сами числа. В последовательности всегда имеется число, кратное 4 и не кратное 7. Количество чисел не превышает 1000. Введённые числа не превышают 30'000. Программа должна вывести одно число: количество чисел, кратных 4, но не кратных 7.

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

int main() {
	int n, i = 0, j = 0;
    cout << "n = "; cin >> n;
    while (i < n) {
        int d; 
        cin >> d;
        if (!(d % 4) && (d % 7))
			j++;
		i++;
    }
    cout << j << endl;
    return 0;
}

Разновидностью задач такого типа является поиск максимального (или минимального) элемента в последовательности. Мы воспользуемся генератором случайных чисел для получения чисел такой последовательности.
Чтобы найти максимальный элемент последовательности определим переменную, начальное значение которой должно быть меньше любого элемента в этой последовательности. Эта переменная сравнивается со всеми членами последовательности и постепенно приобретает значение максимального элемента. Напротив, если мы осуществляем поиск минимального элемента, то значение переменной сравнения должно быть больше любого элемента последовательности.
Задача 4. Вводится последовательность из n (n < 100) случайных целых чисел (0 < d <= 1000). Определите в этой последовательности максимальный и минимальный элемент.

Программа 8.9.5
#include <iostream>
#include <random>
#include <chrono>
using namespace std;
using namespace chrono; 

int main() {
	// Получаем системный момент времени
    long long seed = system_clock::now().time_since_epoch().count();
	// Подключаем процессор случайных чисел
    default_random_engine rnd(seed);
    // Определяем распределение и указываем диапазон
    uniform_int_distribution<int> uid(1, 1000);   
	int n, i = 0, max = 0, min = 1001;
    cout << "n = "; cin >> n;
    while (i < n) {
        int d = uid(rnd);
        cout << d << endl;
        if (d < min) min = d;
        if (d > max) max = d;
		i++;
    }
    cout << "max = "   << max
		 << "\nmin = " << min
		 << endl;
    return 0;
}

Возможный вывод

n = 10
484
715
431
966
394
750
123
367
50
271
max = 966 
min = 50

Инструкция break

Инструкция break прерывает выполнение цикла (как while, так и for) и передает управление программой инструкции, следующей за блоком цикла. Инструкции, которые находятся в теле цикла после инструкции break будут пропущены и выполняться не будут.
Инструкция break всегда находится в одной из ветвей условной инструкции и служит для того, чтобы цикл не выполнял шаги, которые уже не смогут изменить полученные результаты или это уже не имеет никакого значения для решения задачи.
Задача 5. Дано целое n. Определить существует ли разряд равный k в числе n.

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

int main() {
	unsigned long long n;
	unsigned k;
	bool f = false; // Предположим, что такой цифры нет
    cout << "n = "; cin >> n;
    cout << "k = "; cin >> k;
    while (n != 0) {
        if (n % 10 == k) {
			f = true; 
			break; // Если нашли, то выходим
		}
        n /= 10;
    }
    if (f)
		cout << "Цифра " << k << " есть";
	else
		cout << "Цифры " << k << " нет";
	cout << " в этом числе" << endl;
    return 0;
}

Вывод

n = 123456
k = 9
Цифры 9 нет в этом числе

Инструкция continue

Также как и break, инструкция continue всегда находится в одной из ветвей условной инструкции, но служит для досрочного завершения только текущего шага цикла, после чего передает выполнение на условие. При этом, инструкции, следующие за continue до конца блока, игнорируются.

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

Данная инструкция применяется не часто, но может быть использована, например, для контроля допустимости значений при вычислении выражений в теле цикла. Например.
Задача 6. Требуется вывести значения функции f(x) = 1/x с шагом 0,1 (протабулировать) на отрезке от -1,0 до 1,0. Значение x == 0, в котором функция не определена, должно быть пропущено.

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

int main() {
	double i = -1.0;
    while (i <= 1.0) {
        if (i > -0.09 && i < +0.09) {
			i += 0.1;
			continue;	
		}
        cout << "i = "
			 << fixed << showpos
			 << setprecision(17) << i
			 << "\t" << setw(8) 
			 << setprecision(4) << 1 / i
			 << endl;
		i += 0.1;
    }   
    return 0;
}

Вывод

i = -1.00000000000000000	1/x =  -1.0000
i = -0.90000000000000002	1/x =  -1.1111
i = -0.80000000000000004	1/x =  -1.2500
i = -0.70000000000000007	1/x =  -1.4286
i = -0.60000000000000009	1/x =  -1.6667
i = -0.50000000000000011	1/x =  -2.0000
i = -0.40000000000000013	1/x =  -2.5000
i = -0.30000000000000016	1/x =  -3.3333
i = -0.20000000000000015	1/x =  -5.0000
i = -0.10000000000000014	1/x = -10.0000
i = +0.09999999999999987	1/x = +10.0000
i = +0.19999999999999987	1/x =  +5.0000
i = +0.29999999999999988	1/x =  +3.3333
i = +0.39999999999999991	1/x =  +2.5000
i = +0.49999999999999989	1/x =  +2.0000
i = +0.59999999999999987	1/x =  +1.6667
i = +0.69999999999999984	1/x =  +1.4286
i = +0.79999999999999982	1/x =  +1.2500
i = +0.89999999999999980	1/x =  +1.1111
i = +0.99999999999999978	1/x =  +1.0000

Обратите внимание, что для действительных чисел, ввиду потери точности при вычислениях (что наглядно демонстрируется выводом), невозможно осуществить сравнение с действительным 0.0. Возможно лишь установить некоторый малый промежуток для области определения функции, в которой её значение м. б. не определено.
Вернемся к предыдущему уроку, к программе вычисления факториала (8.8.4). Итак, заведомо известно, что пользователю нельзя вводить число n > 20. Но нельзя вводить и отрицательные числа. К тому же, 0! = 1. Проконтролируем в программе, что вводит пользователь и вернем его на ввод, если введенные данные не допустимы в данной программе.

Программа 8.9.8
#include <iostream>
using namespace std;
 
int main() {
    int n, i = 0;
    unsigned long long f = 1;
    cout << "n = "; cin >> n;
    while (i < n || n < 0) { // Запустим в цикл, если n < 0
		if (n > 20 || n < 0) {
			cout << "Введите корректное значение n = ";
			cin >> n;
			continue; 
		}
        ++i;       
        f *= i; 
    }
    if (!n)
		cout << 0 << "! = " << 1 << endl;
	else
		cout << n << "! = " << f << endl;
    return 0;
}
Существует мнение, что инструкции break и continue являются избыточными в программировании и многие разработчики стараются не использовать эти инструкции, так как вполне можно обойтись и без них. Однако, последние повышают читаемость программы.

Классические целочисленные алгоритмы

Условная инструкция в цикле используется в некоторых классических алгоритмах.

Разложение числа на простые множители

Задача 7. Дано целое n. Разложить число n на простые множители.

Программа 8.9.9
#include <iostream>
using namespace std;
 
int main() {
    unsigned i = 2;
    unsigned long long n, m;
    cout << "n = "; cin >> n;
    m = n;
    while (i < m / 2) {
		if (n % i == 0) {
			cout << i << " ";
			n /= i;
		}
		else
			++i; 
    }
    if (m == n)
		cout << "Это простое число" << endl;
    return 0;
}

Вывод

n = 777
3 7 37
------------
n = 2021
43 47
------------
n = 101
Это простое число

Блок-схема

Идея алгоритма заключается в следующем. Будем перебирать все возможные делители числа n в цикле до значения n / 2, начиная с 2. Если делитель найден, то будем делить это число на этот делитель, пока будет позволять условие (остаток == 0), и выводить этот делитель. Это и будет набор простых множителей. (В математических терминах такой процесс называется факторизацией).
Нужно предусмотреть и такой вариант, когда n является простым числом. Для этого, значение n сохраняется в переменной m. Помимо этого, пременная m нужна для того, чтобы зафиксировать значение n / 2, так как n, в цикле, изменяет свое значение.

Перебор делителей

Этот алгоритм предназначен для проверки: является ли данное число простым или нет (тест на простоту). Фактически, данный алгоритм является модификацией предыдущего.
Задача 8. Дано целое n. Определить, является ли число n простым.

Программа 8.9.10
#include <iostream>
using namespace std;
 
int main() {
    unsigned i = 2;
    unsigned long long n;
    bool f = true;
    cout << "n = "; cin >> n;
    while (i <= n / 2) {
		if (n % i == 0) { // Если нашли делитель,
			f = false;    // то это число не является простым
			break;        // Выходим досрочно
		}
		else              // Иначе переходим к следующему
			++i;          // возможному делителю
    }
    cout << "Число " << (f? "простое" : "составное") << endl;
    return 0;
}

Вывод

n = 114
Число составное
------------
n = 113
Число простое

Блок-схема

Идея алгоритма заключается в простом переборе всех возможных делителей. При этом, достаточно проверить все возможные делители от 2 до n / 2. Количество шагов можно сократить, если проверять до sqrt(n). Если найден делитель, то осуществляется досрочный выход из цикла и объявляется, что это число не является простым. Данный алгоритм имеет большую вычислительную сложность, поэтому не применяется для определения простоты больших чисел.

Можно повысить эффективность этого алгоритма, если пропустить делители кратные двум (кроме 2) и кратные трем (кроме 3).
Алгоритм Евклида

Задача 9. Даны два целых числа a и b. Определить наибольший общий делитель этих двух чисел с помощью алгоритма Евклида.

Программа 8.9.11
#include <iostream>
using namespace std;
 
int main() {
    unsigned long long a1, b1;
    cout << "a = "; cin >> a1;
    cout << "b = "; cin >> b1;
    auto a2 = a1; 
    auto b2 = b1;
    //============= НОД1 ====================
    while (a1 != b1) {
		if (a1 > b1) 
			a1 -= b1;
		else 
			b1 -= a1; 
    }
    cout << "НОД1(a, b) = " << a1 << endl;
    //============= НОД2 ====================
    while (b2) {
		a2 %= b2;
		auto buf = a2;
		a2 = b2;
		b2 = buf;
	}
	cout << "НОД2(a, b) = " << a2 << endl;
    return 0;
}
a = 120
b = 45
НОД1(a, b) = 15
НОД2(a, b) = 15

Блок-схема (НОД1)

Идея алгоритма Евклида - нахождения наибольшего общего делителя (НОД) для двух целых чисел (a и b, при a >= b), основана на следующем утверждении, что НОД(a, b) = НОД(a - b, b). Таким образом, можно организовать цикл в котором большее число мы будем заменять разностью большего и меньшего до тех пор, пока значение одного из чисел не станет равными нулю. Разность на последнем шаге цикла и будет определять НОД этих двух чисел. Существует и второй, более быстрый, способ. Вместо того, чтобы производить вычитания, мы будем получать остаток от деления a на b, что существенно сокращает объем вычислений. Он основан на утверждениях, что, если a = b⋅q + r, тогда НОД (a, b) = НОД (b, r) и НОД(r, 0) = r, для любого ненулевого r. При таком подходе, условная инструкция в теле цикла не используется. Её заменяет простой обмен значениями между двумя переменными. Оба этих способа мы реализовали в одной программе 8.9.11, для сравнения. Существуют и другие реализации этого известного алгоритма, например, рекурсивная реализация, бинарный алгоритм Евклида, расширенный алгоритм Евклида и др.

Приложение

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

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


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