Печатать книгуПечатать книгу

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

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

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

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

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

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

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

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

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

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

Следование

Ветвление

Цикл

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

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

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

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

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

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

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

Сайт: Профильное обучение
Курс: Інфарматыка. 10 клас (Павышаны ўзровень)
Книга: § 3. Асноўныя алгарытмічныя канструкцыі
Напечатано:: Гость
Дата: Суббота, 4 Май 2024, 05:27

Оглавление

3.1. Алгарытмічныя канструкцыі

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

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

Алгарытмічная канструкцыя галінавання забяспечвае выкананне адной ці іншай паслядоўнасці каманд у залежнасці ад праўдзівасці ці непраўдзівасці некаторай умовы. Аператар галінавання — каманда, якая рэалізуе алгарытмічную канструкцыю галінавання на мове праграміравання.

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

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

  • цыкл з параметрам выкарыстоўваецца тады, калі вядома колькасць паўтарэнняў;
  • цыкл з перадумовай выкарыстоўваецца ў тым выпадку, калі вядома ўмова працягвання работы;
  • цыкл з постумовай выкарыстоўваецца ў тым выпадку, калі вядома ўмова працягвання работы.

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

Паслядоўнасць

Галінаванне

Цыкл 

1. Цыкл з параметрам (значэнне параметра змяняецца ад 1 да N):

 

2. Цыкл з перадумовай:

3. Цыкл з постумовай:

Акрамя блок-схем, для графічнага ўяўлення алгарытмаў выкарыстоўваюць структураграмы (N — S-дыяграмы, дыяграмы Насі — Шнэйдэрмана).

Прыклады структураграм

Каманда галінавання:

 

Каманда цыкла з перадумовай:

 

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 або роўна 7. Па-за залежнасцю ад праўдзівасці першай часткі ўмовы вынік заўсёды будзе праўдзівым, паколькі 0 <= 7 і 1 <= 7. Таму значэнне пераменнай a заўсёды будзе праўдзівым, і яно не залежыць ад значэння пераменнай x.

Тып bool названы ў гонар англійскага матэматыка і логіка Джорджа Буля, які займаўся пытаннямі матэматычнай логікі ў XIX ст.

Прыклад 3.2. Прыклады лагічных выразаў:

Выраз

Значэнне
3 < 7 true
2 + 2 * 2 == 8 false
abs(-5) > abs(3) true

Значэнне лагічнага выразу    y >= x * x    можна вызначыць, толькі ведаючы значэнні пераменных x і y. Пры x = 2 і y = 10 значэнне выразу — true. Пры x = 10 і y = 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. Вызначэнне парадку дзеянняў для выразу:

    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, эквівалентныя && і ||.

Пытанні к параграфу

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.