Print bookPrint book

§ 3. Основные алгоритмические конструкции

Алгоритмические конструкции

Как вам уже известно из курса информатики, любой алгоритм может быть записан с использованием трех базовых алгоритмических конструкций: следование, цикл и ветвление (пример 3.1).

Команды, составляющие алгоритмическую конструкцию следование, выполняются последовательно, друг за другом, в том порядке, в котором они записаны. Команды цикла и ветвления управляют порядком выполнения других команд в программе и относятся к командам управления (управляющим конструкциями).

Алгоритмическая конструкция ветвления обеспечивает выполнение одной или другой последовательности команд в зависимости от истинности или ложности некоторого условия. Оператор ветвления — команда, реализующая алгоритмическую конструкцию ветвления на языке программирования.

Алгоритмическая конструкция повторение (цикл) представляет собой последовательность действий, выполняемых многократно. Саму последовательность называют телом цикла. Оператор цикла — это команда, реализующая алгоритмическую конструкцию повторения на языке программирования.

Существуют разные возможности управлять тем, сколько раз будет повторяться тело цикла. Может быть задано условие продолжения или окончания работы цикла, а также число повторений тела цикла. В зависимости от этого выделяют цикл с предусловием, цикл с постусловием и цикл с параметром.

Существуют разные возможности управлять тем, сколько раз будет повторяться тело цикла. Может быть задано условие продолжения или окончания работы цикла, а также число повторений тела цикла. Выделяют следующие циклы: цикл с предусловием, цикл с постусловием и цикл с параметром. Выбор цикла зависит от задачи. Во многих случаях циклы взаимозаменяемы. При выборе цикла можно ориентироваться на следующее:

  • цикл с параметром используется тогда, когда известно количество повторений;
  • цикл с предусловием используется в том случае, когда известно условие продолжения работы;
  • цикл с постусловием используется тогда, когда тело цикла должно быть выполнено хотя бы один раз.

Пример 3.1 Блок-схемы алгоритмических конструкций.

Следование

Ветвление

Цикл

  • Цикл с параметром (значение параметра изменяется от 1 до N):

  • Цикл с предусловием:

  • Цикл с постусловием:

Кроме блок-схем, для графического представления алгоритмов используют структурограммы (NS-диаграммы, диаграммы Насси — Шнейдермана).

Примеры структурограмм

Команда ветвления:

Команда цикла с предусловием:

Site: Профильное обучение
Course: Информатика. 10 класс (Повышенный уровень)
Book: § 3. Основные алгоритмические конструкции
Printed by: Guest user
Date: Thursday, 13 June 2024, 6:02 PM

3.1. Алгоритмические конструкции

Как вам уже известно из курса информатики, любой алгоритм может быть записан с использованием трех базовых алгоритмических конструкций: следование, цикл и ветвление (пример 3.1).

Команды, составляющие алгоритмическую конструкцию следование, выполняются последовательно, друг за другом, в том порядке, в котором они записаны. Команды цикла и ветвления управляют порядком выполнения других команд в программе и относятся к командам управления (управляющим конструкциями).

Алгоритмическая конструкция ветвления обеспечивает выполнение одной или другой последовательности команд в зависимости от истинности или ложности некоторого условия. Оператор ветвления — команда, реализующая алгоритмическую конструкцию ветвления на языке программирования.

Алгоритмическая конструкция повторение (цикл) представляет собой последовательность действий, выполняемых многократно. Саму последовательность называют телом цикла. Оператор цикла — это команда, реализующая алгоритмическую конструкцию повторения на языке программирования.

Существуют разные возможности управлять тем, сколько раз будет повторяться тело цикла. Может быть задано условие продолжения или окончания работы цикла, а также число повторений тела цикла. Выделяют следующие циклы: цикл с предусловием, цикл с постусловием и цикл с параметром. Выбор цикла зависит от задачи. Во многих случаях циклы взаимозаменяемы. При выборе цикла можно ориентироваться на следующее:

  • цикл с параметром используется тогда, когда известно количество повторений;
  • цикл с предусловием используется в том случае, когда известно условие продолжения работы;
  • цикл с постусловием используется тогда, когда тело цикла должно быть выполнено хотя бы один раз.

Пример 3.1. Блок-схемы алгоритмических конструкций.

Следование

Ветвление

Цикл

1. Цикл с параметром (значение параметра изменяется от 1 до N):

2. Цикл с предусловием:

 

3. Цикл с постусловием:

Кроме блок-схем, для графического представления алгоритмов используют структурограммы (NS-диаграммы, диаграммы Насси — Шнейдермана).

Примеры структурограмм

Команда ветвления:

 

Команда цикла с предусловием:

 

3.2. Логический тип данных

В языке программирования С++ для работы с условиями определен логический тип данных bool. Величины типа bool могут принимать два значения — false (ложь) и true (истина).

Значения false и true получаются в результате выполнения операций сравнения над числовыми данными. Сравнивать можно константы, переменные, арифметические и логические выражения. Для сравнения используют следующие знаки:

Операция

С++

Равно (=) ==
Не равно (≠) !=
Больше (>)
Меньше (<)
Больше или равно (³) >=
Меньше или равно (≤) <=

Логическое выражение — выражение, принимающее одно из двух значений: true или false. Логические выражения можно присваивать переменным типа bool, а также выводить их значения на экран: будет выведено 0 для значения true или 1 для значения false соответственно (пример 3.2).

В языке С++ любое числовое значение может восприниматься как логическое. При этом значения, равные нулю, считаются ложью, а не равные нулю — истиной.

В С++ допустимы логические выражения следующего вида: bool a = 3 <= x <= 7;. Однако смысл такого выражения не совпадает с математическим. При выполнении программы компилятор сначала проверит истинность условия 3 <= x и заменит его на 0 или 1 в зависимости от того, истинно это условие или нет. Затем произойдет проверка того, что полученное значение меньше либо равно 7. Вне зависимости от истинности первой части условия результат всегда будет истинным, т. к. 0 <= 7 и 1 <= 7. Поэтому значение переменной a всегда будет истинным, и оно не зависит от значения переменной x.

Тип bool назван в честь английского математика и логика Джорджа Буля, занимавшегося вопросами математической логики в XIX в.

Пример 3.2. Примеры логических выражений:

Выражение

Значение

< 7 true
+ 2 == 8 false
abs(-5) > abs(3) true

Значение логического выражения   >= x * x  можно определить, только зная значения переменных x и y. При = 2 и = 10 значение выражения — true. При = 10 и = 2 – false.

Проверим истинность этих выражений в программе:

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

  bool a1 = 3 < 7;

  cout << "a1=" << a1 << endl;

  bool a2 = 2 + 2 * 2 == 8;

  cout << "a2=" << a2 << endl;

  bool a3 = abs(-5) > abs(3);

  cout << "a3=" << a3 << endl;

  double x, y;

  x = 2, y = 10;

  bool a4;

  a4 = y >= x * x;

  cout << "a4=" << a4 << endl;

  x = 10; y = 2;

  a4 = y >= x * x;

  cout << "a4=" << a4 << endl;

  return 0;

}

Результат работы программы:

Команда    cout << boolalpha   позволит вывести на экран значения true и false вместо 1 и 0. Команду достаточно написать один раз перед первым выводом. Если нужно вернуться к выводу 1/0, то используют команду   cout << noboolalpha.

3.3. Составные условия

 

Для логических переменных в С++ определены логические операции !, &&, ||, соответствующие операциям НЕ, И, ИЛИ, выполняемым над высказываниями.

Логические выражения, в которых наряду с простыми условиями (сравнениями) используются логические операции, называют составными условиями.

Приведем таблицу истинности для  логических операций.

Логическая переменная

Результат операции

A B !(A) A && B A || B
true true false true true
false true true false true
true false false false true
false false true false false

В логических выражениях могут встречаться как арифметические, так и логические операции. Порядок выполнения операций определяется их приоритетом [1]:

1. !;

2. *, /, %;

3/ +, –;

4. <, >, <=, >=

5. ==, !=;

6. &&;

7. ||.

Операции с одинаковым приоритетом выполняются по порядку, слева направо. Для изменения порядка выполнения операций применяют скобки (примеры 3.3 и 3.4).

При составлении программ часто нужно строить отрицания сложным логическим выражениям. Для этого полезно использовать тождества, известные из алгебры логики (пример 3.5) и следующую таблицу:

Условие

Противоположное условие (отрицание условия)

a < b

a >= b

a > b

a <= b

a == b

a != b

Пример 3.6. Написать программу, которая выдаст на экран значение true или false в зависимости от того, находится ли число B между числами A и C.

Этапы выполнения задания

I. Исходные данные: переменные a, b, c (вводимые числа).

II. Результат: rez (true или false).

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. 
Вычисление значения логической переменной. Рассмотрим два случая:

2.1. Верно неравенство: а < b < c. Этому неравенству соответствует логическое выражение: а < b && b < с. Присвоим переменной r1 значение этого выражения.
2.2. Верно неравенство: а > b > c. Этому неравенству соответствует логическое выражение: а > b && b > с. Присвоим переменной r2 значение этого выражения.
2.3. Ответом на задачу будет значение логического выражения r1 or r2.

3. Вывод результата.

IV. Описание переменных: a, b, c – int, r1, r2, rez – bool.


[1] Обратите внимание, что приоритет операций отличается от того, который принят в Pascal (http://informatika8.adu.by/#fif2-2).

Пример 3.3. Определение порядка действий для выражения:

    || c < b && d    

Первым выполняется сравнение c и b, затем логическая операция &&, потом — ||.

Пример 3.4. Рассмотрим выражение:

    (< b) && (< d)    

Здесь скобки определяют приоритет выполнения операций: т. е. сначала должны выполниться сравнения, а затем —логическая операция &&. Однако в С++ операции сравнения обладают более высоким приоритетом, чем логические операции (в отличие от Pascal), поэтому приведенная выше запись эквивалентна:

    < b && c < d    

Пример 3.5. Построение отрицаний:

!!Û a;

!(&& b) Û !|| !b;

!(|| b) Û !&& !b.

Рассмотрим выражение  !a >  с переменными а и b типа int. Здесь операция ! относится к переменной a. Поскольку целые могут рассматриваться как логические, то отрицанием любого числа, кроме нуля, будет 0, отрицанием нуля будет 1. Затем полученный результат (0 или 1) сравнится с числом b. Для отрицания сравнения выражение нужно записать так:  !(a > b).

В языке С++ используются значки «&» и «|». Этими значками обозначаются битовые операции над целыми числами. Значок «&» соответствует операции and (И), проводимой над двоичными разрядами числа, а значок «|» — операции or (ИЛИ). Кроме этих операций, над битами числа можно выполнять операции «~» not (инверсия) и «^» xor (исключающее ИЛИ, сложение по модулю 2).

Пример 3.6.

V. Программа:

#include <iostream>

 

using namespace std;

 

int main()

{

  int a, b, c;

  cout << "vvedi 3 chisla" << endl;

  cin >> a >> b >> c;

  bool r1 = a < b && b < c;

  bool r2 = a > b && b > c;

  bool rez = r1 || r2;

  cout << boolalpha;

  cout << "b mezdu a i c - ";

  cout << rez << endl;

  return 0;

}

VI. Тестирование.

Запустить программу и ввести значения а = 5, b = 0, c = –5. Результат:

Запустить программу и ввести значения a = –2, b = –7, с = 5. Результат:

VII. Анализ результатов. Для полного тестирования программы нужно проверить все 6 возможных случаев взаимного расположения a, b, c.

В программировании на С++ могут использоваться диграфы (англ. digraphs) — последовательности из двух или более символов, которые компилятор воспринимает как один (или более символов). Они созданы и используются для ввода символов, отсутствующих на клавиатуре или в кодировке. К диграфам относят слова and и or, которые эквивалентны && и ||.

Вопросы к параграфу

1. Что такое составное условие?

2. Назовите логические операции, используемые в С++.

3. Какой приоритет у логической операции «!» («&&», «||»)?

Упражнения

 

1. Сформулируйте и реализуйте обратные условия для примера 3.2. Для всех случаев, для которых в исходной задаче вводилось true, нужно было бы вывести false и, наоборот, для всех случаев, в которых в исходной задаче получалось false, получить true.

2. Определите, что делают следующие программы, и дополните команду вывода

1. #include <iostream>

 

using namespace std;

 

int main()

{

  setlocale(0,"");

  int x;

  cout << "x = ";

  cin >> x;

  bool a = x % 10 == 0;

  cout << boolalpha;

  cout << "Число … – " << a;

  return 0;

  }

2. #include <iostream>

 

using namespace std;

 

int main()

{

  setlocale(0,"");

  int x;

  cout << "x = ";

  cin >> x;

  bool a = x > 10 && x < 100;

  cout << boolalpha;

  cout << "Число ... – " << a;

  return 0;

}

3. Напишите программу, которая выведет на экран значение true или false, в зависимости от того, является ли введенное число x положительным или нет.

4. Задано положительное число x — возраст человека в годах. Определите, человек совершеннолетний (x ≥ 18) или нет. Напишите программу, которая выведет на экран true или false.

5. Напишите программу, которая выведет на экран значение true или false в зависимости от того, является введенное число x четырехзначным или нет.

6⃰. Заданы два положительных числа x и y. Определите, верно ли, что первое число меньше второго и хотя бы одно из них нечетное. Напишите программу, которая выведет на экран true или false.

7. Заданы координаты точки (x, y). Проверить, верно ли, что точка принадлежит первому квадранту координатной плоскости. Напишите программу, которая выведет на экран true или false.

8. Заданы координаты точки (x, y). Проверить, верно ли, что точка лежит внутри круга радиусом 5 с центром в начале координат. Напишите программу, которая выведет на экран true или false.