§ 8.7. Программирование разветвляющихся алгоритмов

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

Алгоритмическая конструкция “ветвление”

Из жизненного опыта нам известно, что даже элементарные бытовые действия мы выполняем после определенных размышлений.
1234x600
Аналогичным образом, требуется прерывать линейное выполнение алгоритма для того, чтобы принять решение в каком направлении выполнять дальнейшие вычисления. В этом случае применяется специальная алгоритмическая конструкция, которая называется “ветвлением“. Ветвление обеспечивает выполнение одной или более инструкций алгоритма, при условии истинности некоторого логического выражения. В виде блок-схемы эта конструкция изображается в следующем виде:

Здесь изображена так называемая полная форма ветвления, которая предполагает две ветви: на истину и ложь. Но существует и другой тип ветвления называемый “неполным ветвлением“. Такая форма ветвления содержит только одну ветвь инструкций, которые будут выполнены, если условие принимает значение “истинно”.

Пример реализации программы с ветвлением в виде блок-схемы приведен ниже.
Задача 1. Даны два числа A и B. Вывести большее из них.

Поскольку ветвление предполагает максимум два пути решения, то часто приходится вставлять одно ветвление внутрь другого, то есть применять вложенные ветвления. Частным случаем вложенного ветвления является переключатель (switch-case). Пример задачи, которая может быть решена с помощью переключателя.
Задача 2. Дано числовое представление дня недели: 0 – воскресенье, 1 – понедельник, 2 – вторник и т. д. Вывести, соответствующее ему, текстовое значение.

Переключатель (switch) работает следующим образом. Выражению-селектор в заголовке switch передается значение целочисленного объекта. Это значение по очередности сопоставляется со всеми значениями блоков case переключателя. Если значение какого-либо блока case окажется равным значению селектора, то выполняется инструкция этого блока и выход из switch. В противном случае (если будут пропущены все блоки case), выполняется блок по умолчанию (default), а если и он отсутствует, то switch передает управление в программу.
В различных языках программирования ветвления реализованы похожим образом, в виде инструкции управления if - else или swith - case (для переключателя).

Условная инструкция

Синтаксис условной инструкции выглядит следующим образом:

if (выражение_1)
{
    // Инструкции_1, если выражение в условии
    // принимает значение "истинно" или не равно 0 
}
[else
{
    // Инструкции_2, если выражение в условии
    // принимает значение "ложь" или равно 0   
}]

Часть синтаксиса, выделенная квадратными скобками, является необязательной. Если эту часть опустить, то ветвление будет неполным. Как мы уже сказали ранее, в качестве логического выражения может выступать любое арифметическое выражение, которое возвращает числовое значение (целое или действительное). Если логическое выражение_1 возвращает значение true (или оно не нулевое), то выполняется инструкция или группа инструкций (блок) в следующей строке (Инструкции_1). Если значение логического выражения_1 будет вычислено как false (или будет равно 0), то программа перейдет к вычислению блока Инструкции_2 после else.
Если в блоке более одной инструкции, то эта группа инструкций называется составной и должна обязательно заключаться в фигурные скобки.
Фигурные скобки в C++ определяют область видимости данных. Те данные, которые определяются внутри фигурных скобок будут недоступными вне этих скобок. Например:
Программа 8.7.1

#include <iostream>

int main() {
    if (true) {
    	int x = 12;
    }
    cout << x << endl;
    return 0;
}

Такая программа содержит одну ошибку (попытка использования неопределенного объекта) и одно предупреждение (переменная x не используется). Иными словами, переменная x, объявленная в блоке if, не видна вне этого блока.
Для более компактного оформления программного кода мы будем использовать следующий стиль написания инструкции if (стиль Java):

if (...) {
    //...
} else {
    //...
}

Для хорошей читаемости программного кода принято блок выделять отступом (в отличие от python, в C++ отступы не являются частью синтаксиса). Размер отступа, традиционно, принимается равным 4 пробелам или однократной табуляции.

Среды программирования автоматически добавляют отступ при переходе к блоку (после нажатия на Enter), а его величина устанавливается в настройках этой среды.

Приведем несколько примеров в которых задача решается с помощью ветвления. Начнем с неполного ветвления.
Задача 3. Определить является ли число N кратным числу K.

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

int main() {
    int N, K;
    cout << "N = "; cin >> N;
    cout << "K = "; cin >> K;
	if (N % K == 0)
		cout << N << " кратно "
			 << K << endl;
    return 0;
}

Блок-схема

Задача 1 может быть реализована следующим образом

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

int main() {
    int x, y;
    cout << "x = "; cin >> x;
    cout << "y = "; cin >> y;
	if (x > y)
		cout << x;
	else
		cout << y;
	cout << endl;
    return 0;
}

Задача 4. Составьте программу в которой черепаха рисует красный круг по часовой стрелке, а любого другого цвета (заданным в виде строки) – против часовой.

Программа 8.7.4
import turtle as t
t.reset()
C = input('Введите цвет круга: ')
t.begin_fill()
t.color(C, C)
if C == 'red':
    t.circle(-200)
else:
    t.circle(200)
t.end_fill()
t.mainloop()

Решим ещё одну задачу.
Задача 5. Даны три переменных целого типа a, b и c. Определить и вывести максимальное из трех значений.

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

int main() {
    int a, b, c;
    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;
    cout << "c = "; cin >> c;
    int max = a; // Предположим, что max -> a
	if (b > max)
		max = b; // тогда max -> b
	if (c > max)
		max = c; // тогда max -> c
	cout << max << endl;
    return 0;
}

Блок-схема

Идея алгоритма заключается в следующем. Предположим, что переменная a содержит максимальное значение, тогда остается сравнить max со значениями других переменных. В итоге, переменная max будет содержать максимальное значение.

Вложенные инструкции if

В тех случаях, когда в программе двух ветвей условной инструкции недостаточно, прибегают к вложенным ветвлениям. Вложенное ветвление реализуется условной инструкцией, которая в одной (или в обеих) из ветвей содержит другую условную инструкцию. Приведем пример.
Задача 6. Дана точка A с координатами (x;y). Определить, какой координатной четверти принадлежит т. A.

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

int main() {
    double x, y;
    cout << "x = "; cin >> x;
    cout << "y = "; cin >> y;
    cout << "Точка находится ";
    if (x > 0)
        if (y > 0)
            cout << "в I четверти.";
        else
            cout << "в IV четверти.";
    else
        if (y > 0)
            cout << "во II четверти.";
        else
            cout << "в III четверти.";
    cout << endl;
    return 0;
}

Блок-схема

Обратите внимание, что блок вложенной инструкции if (англ. – nested conditional) содержит дополнительный отступ. Эту программу можно оформить иначе, с помощью логической операции and.

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

int main() {
    double x, y;
    cout << "x = "; cin >> x;
    cout << "y = "; cin >> y;
    cout << "Точка находится ";
    if (x > 0 && y > 0)
		cout << "в I";
    else if (x < 0 && y > 0)
		cout << "в II";
    else if (x < 0 && y < 0)
		cout << "в III";
    else
		cout << "в IV";
    cout << " четверти." << endl;
    return 0;
}

Задача 5 могла быть реализована подобным образом, но, в таком случае, код станет очень громоздким и будет восприниматься плохо. Глубина вложенности одной условной инструкции в другую не имеет границ. Но, не взирая на то, что наличие отступов делает программный код понятным, слишком большая глубина вложенности значительно усложняет его чтение, поэтому ее величина редко бывает более 4. Большую глубину вложенности можно избежать использованием логических операций или разбиением вложенной структуры на несколько последовательных условных инструкций, как в задании ниже.
Задача 7. Даны три целых числа. Найти количество положительных чисел в исходном наборе.

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

int main() {
    int a, b, c;
    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;
    cout << "c = "; cin >> c;
    int i = 0;    
    if (a > 0) ++i;
    if (b > 0) ++i;
    if (c > 0) ++i;
    if (i) 
        cout << "Количество положительных "
                "чисел равно " << i << endl;
    if (!i) 
        cout << "Положительных чисел - нет!" << endl; 
    return 0;
}

Обсуждение. Если счетчик i не изменит своего значения после прохождения каскада инструкций if, то его значение так и останется нулевым. Результат операции !itrue, если значение i == 0 (логическое отрицание). (Блок-схема аналогична заданию 5).
Рассмотрим классический пример вложенных if – нахождение корней квадратного уравнения.
Задача 8. Даны коэффициенты a, b и c. Найдите вещественные корни квадратного уравнения, если вещественных корней нет – сообщите об этом.

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

int main() {
    double a, b, c, x1, x2;
    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;
    cout << "c = "; cin >> c;
    double d = b * b - 4 * a * c;
    if (d > 0) {
        x1 = (-b - sqrt(d))/2/a;
        x2 = (-b + sqrt(d))/2/a;
        cout << "x1 = "   << x1
             << "\nx2 = " << x2
             << endl;
    } else {
        if (d < 0) {
            x1 = -b/2/a;
            cout << "x = " 
                 << x1 
                 << endl;
        } else {
            cout << "Уравнение не имеет корней."
                 << endl;
        }
    }
    return 0;
}

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

Переключатель. switch-case

В некоторых случаях многократную вложенность условных инструкций можно заменить на еще одну её форму: switch-case. С помощью этой формы в C++ реализуется алгоритмическая структура переключатель (switch).
Стнтаксис переключателя таков:

switch (expr) { 
    case const_expr1 : statement1; break;
    case const_expr2 : statement2; break;
    // ...
    case const_exprN : statementN; break;
    [default: default_statement;]
}

Решим задачу 2 с помощью программы.

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

int main() {
    int d;
    cout << "d = "; cin >> d;
    switch (d) {
    case 0:
		cout << "Воскресенье"; break;
	case 1:
		cout << "Понедельник"; break;
	case 2:
		cout << "Вторник"; break;
	case 3:
		cout << "Среда"; break;
	case 4:
		cout << "Четверг"; break;
	case 5:
		cout << "Пятница"; break;
	default: // По умолчанию
		cout << "Суббота";
	}
    return 0;
}

При проектировании графических интерфейсов переключатель идеально соответствует элементу “радиокнопка” (от англ. radio button).

Тип enum (перечисление)

Перечисление является особым типом, значение которого ограничено диапазоном значений, которые могут принимать множество явно именованных констант (называемых – «счетчики»). Значения констант являются значениями целочисленного типа. Перечисление определяется с использованием следующего синтаксиса:

enum name {enumerator1 = constexpr , enumerator2 = constexpr , ... };
enum name : type { enumerator1 = constexpr , enumerator2 = constexpr , ... }; 

Вы спросите: “Какое отношение имеют перечисления к условной инструкции?”. Самое что ни на есть прямое! Дело в том, что перечисления очень часто обрабатываются с помощью инструкции switch. Приведем пример программы.
Задача 9. Семь цветов пронумерованы числами от 1 до 7. Требуется, по введенному номеру, определить шестнадцатеричный код этого цвета.

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

int main() {
    enum Color {aqua, black, blue, gray, green, red, yellow};
    int r;
    cout << "1. aqua,\n"
            "2. black,\n"
            "3. blue,\n"
            "4. gray,\n"
            "5. green,\n"
            "6. red,\n"
            "7. yellow\n"
            "Введите номер именованного значения цвета: ";
    cin >> r;
    cout << "Код цвета в 16-ричном представлении: ";
    switch (r - 1) {
        case aqua   : cout << "#00FFFF" << endl; break;
        case black  : cout << "#000000" << endl; break;
        case blue   : cout << "#0000FF" << endl; break;
        case gray   : cout << "#808080" << endl; break;
        case green  : cout << "#008000" << endl; break;
        case red    : cout << "#FF0000" << endl; break;
        case yellow : cout << "#008000" << endl; break;
        default : cout << "В наборе нет цвета"
                          " с таким именем!" << endl;
    }
    return 0;
}

Вывод

1. aqua,
2. black,
3. blue,
4. gray,
5. green,
6. red,
7. yellow
Введите номер именованного значения цвета: 5
Код цвета в 16-ричном представлении: #008000

Каждый счетчик связан со значением предыдущего счетчика. Когда в списке счетчиков предусмотрены инициализаторы, то значения счетчиков определяются ими. Если первый cчетчик не имеет инициализатора, то его соответствующее значение равно нулю. Для любого другого счетчика, определение которого не имеет инициализатора, соответствующее значение представляет собой значение предыдущего счетчика плюс один. Для следующего перечисления:

enum Test {a, b, c = 10, d, e = 1, f, g = f + c};

Значения счетчиков будут равны: a == 0, b == 1, c == 10, d == 11, e == 1, f == 2, g == 12

Тернарная операция

Условная инструкция не единственный способ реализации ветвлений в C++. Во многих языках существует единственная операция, которая называется – тернарная (или условное выражение). Такое название она имеет потому, что в этой операции участвуют три операнда. Синтаксис тернарной операции таков:

<логическое_выражение> ? <выражение_1> : <выражение_2>

Тернарная операция вычисляет выражение_1, если логическое_выражение вычисляется как true. Иначе вычисляется выражение_2. “В чем же разница по сравнению с условной инструкцией?” – спросите вы. Разница заключается в том, что тернарная операция может быть частью выражения с присваиванием, а условная инструкция – нет. Приведем примеры использования тернарной операции.

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

int main() {
    int x;
    cout << "x = "; cin >> x;
    x = !(x % 2) ? 3 : 2;
    cout << x << endl;
    cout << (!(x % 2) ? "even" : "odd");
    return 0;
}

Вывод

x = 5
2
even

Тернарная операция может сделать код очень лаконичным, но нужно быть внимательным, чтобы не допустить ошибки. Если тернарная операция входит в более сложное выражение, то, ввиду старшинства арифметических операций, её следует заключать в круглые скобки. Например, в этом коде:

x = 10 + (!(y % 2) ? 2 : 1);

если бы не было скобок, то, при нечетном y, значение x было бы не 11, а 2.

Приложение

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

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


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