§ 3. Асноўныя алгарытмічныя канструкцыі

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

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

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

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

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

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

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

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

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

Следование

Ветвление

Цикл

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

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

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

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

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

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

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

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. Вызначэнне парадку дзеянняў для выразу:

    a || c < b && d    

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

Прыклад 3.4. Разгледзім выраз:

    (a < b) && (c < d)    

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

    a < b && c < d    

Прыклад 3.5. Пабудова адмаўленняў:

!!a Û a;

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

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

Разгледзім выраз  !a > b   з пераменнымі а і 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, эквівалентныя && і ||.