Лекції >> Програмування, комп’ютери і кібернетика >> Програми з розгалуженнями

У розглянутих раніше прикладах та задачах всі дії виконувались послідовно одна за одною, але насправді таких задач дуже мало.

Багато задач вимагає від виконавця змінити послідовність виконання дій у залежності від певних умов. Під вказаними умовами будемо розуміти логічні вирази, кожен з ких може набувати двох значень: “так” (true) – якщо умова істинна і “ні” (false) – якщо умова хибна. Нагадаємо, що умови можуть бути складними, тобто використовувати логічні операції[1]. Прості умови обмежуються дужками, якщо вони є частинами складної умови. Істинність складних умов визначається за таблицею істинності.

Наприклад, на деякому етапі розв’язку певної задачі виконавцю потрібно послідовно виконати дві дії: обчислити значення виразу x-1, а потім і значення кореня квадратного цього виразу. У цьому випадку необхідно передбачити ність складних умов визначається за таблицею істинності.

Наприклад, на деякому етапі розв’язку певної задачі виконавцю потрібно послідовно виконати дві дії: обчислити значення виразу x-1, а потім і значення кореня квадратного цього виразу. У цьому випадку необхідно передбачити виконання таких дій:

1. обчислити значення виразу x-1;

2. у залежності від результатів перевірки умови змінити послідовність виконання дій, тобто, якщо  умова 0 є істинною, то обчислювати значення , інакше – умова є хибною – виконати інші дії (наприклад, запропонувати користувачу ввести правильні дані).

Алгоритми та відповідні програми, які вимагають від виконавця перевірки деяких умов і зміни послідовності виконання дій у залежності від результатів перевірки, будемо називати алгоритмами (програмами) з розгалуженнями.

1. обчислити значення виразу x-1;

2. у залежності від результатів перевірки умови змінити послідовність виконання дій, тобто, якщо  умова 0 є істинною, то обчислювати значення , інакше – умова є хибною – виконати інші дії (наприклад, запропонувати користувачу ввести правильні дані).

Алгоритми та відповідні програми, які вимагають від виконавця перевірки деяких умов і зміни послідовності виконання дій у залежності від результатів перевірки, будемо називати алгоритмами (програмами) з розгалуженнями.

Розв’язуючи задачі з розгалуженнями, при описанні алгоритмів  обов’язково використовують базову структуру “розгалуження” (див. стор. 8), а у програмах – оператор (вказівку) розгалуження або, як його ще називають, оператор умовного переходу.

Для організації зміни послідовності виконання дій при розв’язу­ван­ні задачі іноді використовують (Basic, Pascal) оператор безумовного переходу GOTO. Зауважимо, що його використання може порушити структурний підхід до розв’язування задачі і призвести до логічних помилок, які важко шукати у текс дії (наприклад, запропонувати користувачу ввести правильні дані).

Алгоритми та відповідні програми, які вимагають від виконавця перевірки деяких умов і зміни послідовності виконання дій у залежності від результатів перевірки, будемо називати алгоритмами (програмами) з розгалуженнями.

Розв’язуючи задачі з розгалуженнями, при описанні алгоритмів  обов’язково використовують базову структуру “розгалуження” (див. стор. 8), а у програмах – оператор (вказівку) розгалуження або, як його ще називають, оператор умовного переходу.

Для організації зміни послідовності виконання дій при розв’язу­ван­ні задачі іноді використовують (Basic, Pascal) оператор безумовного переходу GOTO. Зауважимо, що його використання може порушити структурний підхід до розв’язування задачі і призвести до логічних помилок, які важко шукати у тексті програми. 

Навчальна алгоритмічна мова.

Вказівка розгалуження у НАМ має такий вигляд:

если <умова>

      то <1-ша послідовність дій>

      иначе <2-га послідовність дій>

все 

Якщо умова істинна, то виконується 1-ша послідовність дій, інакше (умова хибна) то виконується 2-га послідовність дій.

Іноді вказівка розгалуження використовується у неповній формі:

если <умова>

      то <послідовність дій>

все 

Узагальненням вказівки розгалуження є вказівка вибору, за допомогою якої ефективно описуються розгалуження, що мають більше як три напрями:

выбор

      при <умова 1>

                         <1-ша послідовність дій>

      при <умова 2>

                         <2-га послідовність дій>

      . . .

      при <умова N>

      иначе <серія інших команд>

все

У неповній формі оператора вибору конструкція иначе відсутня.

Basic.

Оператор розгалуження на мові Basic можна подати в повній та неповній формах. Повна форма має вигляд:

If <умова> Then <1-ша серія операторів> Else <2-га серія операторів>

Неповна форма оператора розгалуження має наступний вигляд:

If <умова> Then <серія операторів>

Зауважимо, що кожна з вказаних форм має міститися в одному логічному рядку. Враховуючи те, що кількість символів (а значить і кількість операторів серії) логічного рядка обмежена, іноді оператор розгалуження записують у декількох логічних рядках. Такий запис використовують і для більш зручного візуального подання тексту програми, що може полегшити її перегляд та пошук можливих помилок.   При цьому необхідно користуватися оператором безумовного переходу Goto, що без будь-яких умов змінює послідовність виконання команд програми.

Розглянемо  різні способи запису фрагмента програми, в якому спочатку у залежності від істинності умови змінюється послідовність виконання дій - визначається більше із двох чисел, а потім послідовність дій продовжується – на екран виводиться значення більшого числа.

1-й спосіб:

50  if a>b then y=a else y=b         {повна форма розгалуження}

60  print Y     

Спочатку виконується рядок 50: якщо умова істинна, то змінній Y присвоюється значення числа А, інакше змінній Y присвоюється значення числа В. Далі виконується наступний рядок 60.

2-й спосіб:

50  if a>b then 60 else 70             {повна форма розгалуження}

60  y=a : goto 80

70  y=b

80  print Y

Спочатку виконується рядок 50:

якщо умова істинна,

то виконання програми перейде на рядок 60, де змінній Y присвоїться значення числа А і виконання програми перейде на рядок 80,

інакше  (умова хибна) виконання програми перейде на рядок 70, де змінній Y присвоїться значення числа В і виконання програми перейде на наступний рядок.

Далі виконується рядок 80.

3-й спосіб:

50  if a>b then Y=A : goto 70    {неповна форма розгалуження}          

60  y=B

70  print Y

Спочатку виконується рядок 50:

якщо умова істинна, то змінній Y присвоїться значення числа А  і виконання програми перейде на рядок 70,

інакше (умова хибна) виконання програми перейде на наступний рядок, де змінній Y присвоїться значення числа В.

Далі виконується рядок 70.

Якщо після THEN і перед ELSE (1-ша серія операторів) записується декілька операторів, то оператори один від одного відокремлюються двокрапкою. Аналогічно поступають з 2-гою серією операторів. 

Оператор вибору у мові Basic реалізовано командою-перемикачем ON. За допомогою цієї команди можна реалізувати багаторазово розгалужений алгоритм[2]. 

Зауважимо, що доцільно оператор вибору реалізовувати за допомогою неповної форми оператора розгалуження, наприклад:

40 If <умова1>    Then <1-ша послідовність операторів> : GOTO 100

50 If <умова2>    Then <2-га послідовність операторів> : GOTO 100

      . . .

90  If <умоваN>   Then : GOTO 100

Pascal.

Оператор умовного переходу на мові Pascal можна подати в повній та неповній формах. Повна форма має вигляд:

      If <умова> Then <оператор1>

                         Else <оператор2> ;

Якщо умова істинна (True), виконується оператор1, інакше (умова хибна - False) виконується оператор2.

Неповна форма оператора умовного переходу  має вигляд:

      If <умова> Then <оператор1> ;

Якщо умова істинна, виконується оператор1, інакше – пропускається.

Для того, щоб була можливість виконати серію операторів у разі істинності чи хибності умови оператора розгалуження, у мові Pascal існує поняття та конструкція складового оператора.

Складовий оператор є групою із декількох операторів, відокремлених один від одного символами “крапка з комою”, і обмежену оператор ними дужками Begin і End. Його схема така:

Begin 

      < оператор1 ; >

      . . .

      < операторN >    

End;

Складовий оператор сприймається як єдине ціле і може знаходитися у будь-якому місці програми, де можна використовувати простий оператор[3].

Змінити послідовність виконання дій дозволяє оператор безумовного переходу Goto. Він використовується тоді, коли після виконання деякого оператора без будь-якої умови потрібно виконати не наступний, а деякий інший, позначений міткою оператор. Формат оператора безумовного переходу:

GOTO М ;

Цей оператор означає “перейти до” і перенаправляє виконання програми (здійснює перехід) до оператора з міткою М. Міткою можуть бути імена або цифри, які мають бути описані в розділі міток. Мітка ставиться зліва від оператора та відокремлюється від нього символом “двокрапка”. Одна мітка не може використовуватись двічі, але до однієї мітки можна звертатися з різних ділянок програми.

Наведемо приклад фрагмента програми з використанням оператора умовного переходу, складового оператора та оператора безумовного переходу:

M1 : Readln ( X ) ;

         If   ( Х - 1) >= 0  Then Y := Sqrt ( X – 1 )

         Else Begin

             Writeln ( ‘ Неправильні дані. Повторіть ввід Х. ’ ) ;

             Goto M1

         End ;      

Оператор вибору CASE дозволяє здійснити вибір із довільної кількості існуючих варіантів. Він складається з виразу (селектору) та списку параметрів (операторів), кожному з яких передує список констант вибору. Список констант може складатися з однієї константи). При цьому тип констант має бути сумісним з типом селектора. Для селектора заборонені типи real, string.

Формат оператора вибору:

CASE <вираз> OF

      <1-й список констант> : <оператор1 ;>

         . . .

      : <операторN >

   ELSE < оператор >

END ;

При виконанні оператора  <вираз> обчислюється і його значення шукається в одному із списків констант. Після цього виконується оператор, що відповідає знайденому списку.

І етап. Математична модель: спочатку знайдемо найбільше з двох перших чисел, а потім порівняємо знайдене число з третім. Таким чином знайдемо найбільше.

ІІ етап. Складемо алгоритм у вигляді блок-схеми (мал. 9).

ІІІ етап. Запишемо текст програми.

ІV етап. Виконаємо повне тестування (за всіма лініями потоку).

Тест1. Вхідні дані : А=5, B=0, С= 7. Результат: 7.

Тест2. Вхідні дані: А=5, B=0, С= -1. Результат: 5.

Тест3. Вхідні дані: А=0, B=6, С= -1. Результат: 6. n

І етап. Математична модель: значення даної функції обчислюється за формулами як значення одного із трьох виразів у залежності від значення аргумента.

ІІ етап. Складемо алгоритм у вигляді блок-схеми (мал. 10).

ІІІ етап. Запишемо текст програми.

ІV етап. Виконаємо повне тестування (за всіма лініями потоку).

Тест1: x=0.5, Y=0.25. Тест2: x=10, Y=2. Тест3: x= - 3.14, Y= - 2.14. n

І етап. Математична модель. Дана функція подібна раніше розглянутій ( Приклад 4. ): вираз  замінено на .

Тоді дану функцію доцільно подати як:   

ІІ етап. Складемо алгоритм у вигляді блок-схеми (мал. 11).

ІІІ етап. Запишемо текст програми.

ІV етап. Виконаємо повне тестування.

Тест1: x=0.5, Y=0.25.

Тест2: x= - 3.14, Y= - 2.14. n