Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Оператор розгалуження



План:


Введення

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


1. Загальний опис

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

2. Види умовних інструкцій

Існує дві основні форми умовної інструкції, що зустрічаються в реальних мовах програмування: умовний оператор (оператор if) і оператор багатозначного вибору (перемикач, case, switch).

2.1. Умовний оператор

Віктор Михайлович Васнєцов. Витязь на роздоріжжі (1878)

Умовний оператор реалізує виконання певних команд за умови, що певний логічний вираз (умова) приймає значення "істина" true. В більшості мов програмування умовний оператор починається з ключового слова if.

Зустрічаються такі форми умовного оператора:

Умовний оператор з однією гілкою
 if  умова  then  команди  end 
При виконанні такого оператора обчислюється умова, і якщо воно істинне, то виконуються команди до ключового слова end, інакше виконання програми продовжується з наступного за умовним оператором команди. У мовах низького рівня (асемблерах) це - єдина доступна форма умовного оператора. У деяких мовах для умовного оператора з однією гілкою використовується спеціальне ключове слово (зазвичай це when).
Умовний оператор з двома гілками
 if  умова  then  команди  1  else  команди  2  end 
Тут при істинності умови виконуються команди1 при помилковості - команди2. При необхідності перевірити послідовно кілька умов можливо каскадування умовних операторів:
 if  умова  1  then  команди  1  else  if  умова  2  then  команди  2  else  if  умова  3  then  команди  3  ...  else  if  условіеN  -  1  then  командиN  -  1  else  командиN  end  ; 
У цьому випадку умови будуть перевірятися послідовно, і як тільки зустрінеться справжнє, буде виконаний відповідний набір команд і виконання перейде до команди, наступної за умовним оператором. Якщо жодна з умов не виявиться істинним, виконуються командиN з гілки else.
Умовний оператор з декількома умовами
Вищенаведена схема каскаду умовних операторів використовується досить часто, тому ряд мов програмування містить спеціальну конструкцію для неї, що дозволяє записати множинне розгалуження кілька компактніше і менш піддану помилок написання:
 if  умова  1  then  команди  1  elsif  умова  2  then  команди  2  elsif  умова  3  then  команди  3  ...  else  командиN  end  ; 
порядок виконання цього оператора в точності відповідає вищенаведеному каскаду простих операторів if-then-else, а відмінність чисто формальне: замість вкладених кількох умовних операторів ця конструкція є єдиним цілим і містить додаткове ключове слово elsif вимагає після себе чергове умова.

2.1.1. Реалізація

2.1.1.1. Algol, Pascal

Паскаль успадкував від Алгол -60 синтаксис, згідно з яким у гілках умовного оператора може бути поміщена тільки одна команда. Тому для розміщення там більшої кількості команд вони групуються в складовою оператор за допомогою пари ключових слів begin і end. Гілка else необов'язкова. begin і end необхідні, тільки якщо операторів кілька (наприклад, з міркувань однаковості оформлення коду). У прикладі - оператор вибору у Паскалі:

 If  умова  then  begin  оператори;  end  else  begin  оператори;  end  ; 

2.1.1.2. Algol-68, Ada, Modula-2

Необхідність умовного оператора в Алгол і Паскалі з моменту появи була об'єктом критики. Критики говорили, що численні складові оператори захаращують програму, заважають нормальній розстановці відступів і провокують помилки (якщо в останній гілки оператора if забути складовою оператор там, де він необхідний, то компілятор нічого не помітить, але при виконанні програми з групи операторів, які повинні виконуватися в цій гілці, за умовою буде виконуватися тільки перший, всі інші - завжди). Наступні покоління мов - нащадків Алгол спробували позбутися цього недоліку. У їх числі три широко відомих мови: Алгол-68, Модула-2 і Ада. Конструкція оператора if в них практично однакова, з точністю до окремих ключових слів:

  • Алгол-68:
 if  умова ...  fi  ; 
  • Модула-2
 IF  умова  1  THEN  команди  1  ELSE  IF  умова  2  THEN  команди  2  ...  ELSE  командиN  END  ; 
  • Ада
 if  умова  1  then  команди  1  else  if  умова  2  then  команди  2  ...  else  командиN  end  if  ; 

У всіх випадках "командиX" - будь-яке число операторів розділених крапкою з комою. У всіх випадках всі гілки умовного оператора, крім першої (гілки "then") необов'язкові і можуть бути пропущені. Якщо гілка "else" відсутня і жодна з умов не виконується, то управління передається на команду, наступну за ключовим словом завершення умовної конструкції (END, FI або END IF).


2.1.1.3. C, C + + та їх нащадки

C і C + + (а слідом за ними і Java, C #, PHP і безліч інших мов) мають умовний оператор, структурно аналогічний Паскалю. Відмінність полягає в тому, що умова має бути записано в круглих дужках, а замість ключових слів begin і end використовуються фігурні дужки {} :

 if  (  <  умова  >  )  {  <  оператори  >  }  else  {  <  оператори  >  } 

2.1.1.4. Nemerle

На відміну від більшості мов, де оператор if може мати як одну, так і дві гілки, в Nemerle оператор if (синтаксис повністю аналогічний мови Сі) зобов'язаний мати дві гілки. Умовний оператор з однією гілкою починається з ключового слова when, крім того, в мові є ще один умовний оператор - unless, що представляє собою "зворотний when" - в ньому команди умовної гілки виконуються, якщо умова помилкова.

 when  (  умова  )  {  оператори  }  unless  (  умова  )  {  оператори  } 

2.1.1.5. Forth

В Forth умовний оператор має відмінний від виду в інших мовах вид, через постфіксной форми запису і стекової організації. Умовний оператор складається з трьох слів IF ELSE THEN [1].

 <Умова>  IF  <Выражение_1_если_условие_истинно>  ELSE  <Выражение_2_если_условие_ложно>  THEN 

Тут <условие> просто поміщає значення на вершину стека, IF аналізує прапор, і якщо:

  • він не дорівнює нулю, то виконуються вирази до ELSE або THEN;
  • якщо він дорівнює нулю, то виконується вираження між ELSE і THEN.

При відсутності ELSE виходить селектор з однією гілкою: вислови між IF і THEN виконуються тільки при ненульове значення прапора.


2.1.1.6. Fortran

Fortran спочатку мав тільки арифметичний IF, в якому в залежності від знака виразу проводився перехід на одну з трьох міток. Наприклад, частина коду підпрограми рішення квадратного рівняння:

 DN  =  B  *  B  -  4  *  A  *  C  IF  (  DN  )  90  ,  10  ,  10  10  D  =  SQRT  (  DN  )  X1  =  (  -  B  +  D  )  /  (  2  *  A  )  X2  =  (  -  B  -  D  )  /  (  2  *  A  ) 

Потім були додані логічні (булеві) вираження і логічний IF з одним оператором, обчислюваний GOTO, пізніше - структурний IF (з декількома умовами), наприклад:

 DN  =  B  *  B  -  4  *  A  *  C  IF  (  DN.  GE  .0  )  THEN  D  =  SQRT  (  DN  )  X1  =  (  -  B  +  D  )  /  (  2  *  A  )  X2  =  (  -  B  -  D  )  /  (  2  *  A  )  ELSE  (  код для випадку негативного дискриминанта не наводиться  )  END  IF 



2.1.1.7. Perl

Perl підтримує структурний if з кількома умовами, а також модифікатори оператора (statement modifiers), які записуються після виконуваної частини оператора. Наприклад, два наступних прикладу ідентичні по функціональності:

 if  (  $ A  ==  0  )  {  + +  $ Zero_count  ;  } 
 + +  $ Zero_count  if  $ A  ==  0  ; 

Замість if можна писати unless, що призводить до інверсії значення умовного виразу перед перевіркою. Те ж саме діяння через unless:

 + +  $ Zero_count  unless  $ A  ! =  0  ; 

Для складеного оператора (блоку) допустима тільки структурна форма, але не модифікатор. Наприклад:

 if  (  $ A  ==  0  )  {  ...  }  else  if  (  $ A  >  0  )  {  ...  }  else  {  ...  } 

Завершальне ключове слово не потрібно, за рахунок вимоги обов'язкового оформлення операторів під умовами в блоки {...}.

Не існує аналога слова unless для гілок elsif.


2.1.1.8. Erlang

Erlang використовує два умовних оператора - if і case. Обидва мають результуюче значення, яке дорівнює значенню останнього оператора у виконаній гілці і може бути використане (призначено імені, передано у функцію ...), тому в ньому немає окремого тернарного умовного оператора. У операторі case виконується Зіставлення зі зразком, з можливістю додаткових умов на значення в порівнюваних, а в операторі if - тільки перевірка умов. В умовах (guard tests) допускається обмежене безліч операцій та вбудованих функцій.

Приклад на case (видалення запису про подію з дерева часів):

 {  NewEBW  ,  NewEBN  }  =  case  dict  :  find  (  EBN  ,  Node  )  of  error  ->  {  EBW  ,  EBN  }  ;  {  ok  ,  Expiry  }  ->  {  gb_trees  :  delete_any  (  {  Expiry  ,  Node  }  ,  EBW  )  ,  dict  :  erase  (  Node  ,  EBN  )  }  end  , 

Приклади на if:

 if  NeedLater  ->  erlang  :  send_after  (  trunc  (  1000  *  (  1  +  Elapsed  )  )  ,  self  (  )  ,  i_apply_nodes_portion  )  ;  true  ->  nop  end  , 
 After2  =  if  %% If it was too far ago, schedule timeout immediately.  After1  = <  ?  EXPIRY_STEP_MIN  ->  ?  EXPIRY_STEP_MIN  ;  After1  > =  ?  EXPIRY_STEP_MAX  ->  ?  EXPIRY_STEP_MAX  ;  true  ->  After1  end  , 

2.2. Перемикач

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

Прототипом сучасної синтаксичної конструкції була використовувана в старих мовах програмування команда переходу по обчислюється мітці. У цій команді вказувалося вираз-селектор, що повертає ціле значення, і набір міток. При виконанні команди обчислювалося вираз, а його значення використовувалося як номер мітки (у списку команди), на яку проводився перехід. Такі конструкції були, наприклад, в мовах програмування Фортран ("обчислюваний GOTO") і Бейсік. Привабливою стороною конструкції є її досить висока ефективність: для визначення потрібної галузі (мітки переходу) не потрібно послідовно порівнювати результат вирази-селектора з багатьма занчению, достатньо записати в пам'ять масив команд безумовного переходу з потрібними адресами, щоб при виконанні команди обчислювати потрібний елемент безпосередньо з значення виразу. При цьому швидкість виконання команди не залежить від кількості міток. У сучасних мовах реалізація оператора-перемикача також часто виконується у вигляді таблиці переходу, що складається з команд безумовного переходу на відповідні фрагменти коду. Обчислюване вираз перетворюється у значення зсуву по таблиці переходу, що визначає виконувану команду. У мовах, де вираз-селектор може мати неціле значення, безпосередньо обчислити потрібну гілку конструкції перемикача можна далеко не завжди, тому в них використовуються інші методи оптимізації виконання.

У сучасних мовах програмування високого рівня команда-перемикач зазвичай має ім'я switch або case. Проте, вибір за обчислюється мітці може зберігатися в сучасних мовах програмування низького рівня, наприклад, інструкція JL мови програмування STL для програмованих логічних контролерів S7-300 і S7-400, що випускаються Siemens

Наприклад, у мові Сі синтаксис команди наступний:

 switch  (  i  )  {  case  0  :  case  1  :  / / Послідовність операторів  break  ;  case  2  :  / / Послідовність операторів  break  ;  default  :  } 

Тут i - вираз-селектор, яка зобов'язана мати приводиться до цілого тип, кожна гілка виконання починаються з ключового слова case, за ним слідує значення виразу, при якому повинна виконуватися дана гілка. Цікавою особливістю мови Сі є те, що в ньому перемикач трактується саме як команда переходу по обчислюється мітці, а роль міток грають заголовки гілок ( case значение :). Щоб після завершення коду гілки стався вихід з оператора перемикача, використовується спеціальна команда break. Якщо такої команди в гілці ні, після виконання коду обраної гілки почнеться виконання коду наступної за нею. Ця особливість може використовуватися для оптимізації, хоча може служити причиною труднообнаружіваемих помилок (якщо програміст випадково пропустить break, компілятор не видасть помилки, але програма виконуватиметься невірно). Гілка default виповнюється тоді, коли серед інших гілок не знайшлося жодної відповідної.

Синтаксис команди-перемикача Сі успадкований безліччю мов, але семантика його не завжди повністю аналогічна Сі. Наприклад, в C # допускається використовувати вираз-селектор строкового типу та відповідні позначки.


3. Особливості обчислення логічних виразів

На порядок виконання програми з умовними операторами може істотно впливати прийнята в мові логіка обчислення умовних виразів. Коли умова являє собою складне логічне вираження, наприклад "f (x)> 0 І g (y)> 0", існує дві стратегії обчислення його результату:

  • Повне обчислення: обчислити f (x), g (y), провести порівняння результатів з нулем, потім виконати операцію "І" для результатів. Так надходить, наприклад, Visual Basic.
  • Неповне обчислення: обчислити f (x), порівняти значення з нулем. Якщо результат порівняння - "істина", то обчислювати іншу частину виразу. Якщо ж перша умова помилково, то пропустити другу умову, в тому числі обчислення входить до нього g (y), так як для операції "І" при хибності одного з операндів весь вираз завідомо неправдиво.

Другий варіант є найбільш поширеним для промислових мов (зокрема, для Алгол, Фортрану, С + +, С, Java, JavaScript, ECMAScript, JScript, C #). У цих мовах діє жорстке правило: "Логічне вираз завжди обчислюється зліва направо і його обчислення зупиняється відразу ж, як тільки результат всього висловлювання стає певним". Це означає, що якщо вираз складається з декількох підумови, об'єднаних оператором "І" (AND), то обчислення виразу припиниться, як тільки одна з підумови виявиться помилковим (так як "брехня AND будь-яке значення" в результаті завжди дає "брехня"), і, навпаки, якщо кілька підумови об'єднані оператором "АБО" (OR), обчислення припиниться після першого ж істинного підумови, оскільки в цьому випадку все вираз істинний, незалежно від подальших обчислень. А от вираз, що містить оператор "Що виключає АБО" (XOR) неповного обчисленню не піддається, оскільки в ньому одне із значень не може визначити результат обчислення всього виразу.

Мови Ада і Erlang використовують різні ключові слова для цих варіантів: слова and і or означають повне обчислення, а and then, or else (Ада), andalso, orelse (Erlang) - неповне. У Erlang andalso і orelse менш пріоритетними, ніж операції порівняння, що дозволяє уникнути дужок навколо елементарних умов.

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

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

 / / Пошук в масиві цілих чисел на мові Паскаль  / / Параметри - шукане значення і відкритий масив цілих чисел  / / Результат - індекс знайденого елементу або -1 у випадку, якщо елемент не знайдений  function  Find  (  e  :  integer  ;  var  a  :  array  of  integer  )  :  integer  ;  var  i  :  integer  ;  begin  i  : =  0  ;  while  (  i <  =  High  (  a  )  )  AND  (  a  [  i  ]  <> E  )  do  inc  (  i  )  ;  / /!  if  i <  =  High  (  a  )  then  Find  : =  i  else  Find  : =  -  1  ;  end  ; 

Алгоритм, реалізований програмою, абсолютно очевидний, але в реалізації є одна тонкість (див. рядок, позначену знаками оклику): умова циклу складається з двох частин, пов'язаних оператором AND. Перше підумови перевіряє, чи не вийшла індекс i за межі масиву, друге - не дорівнює чи поточний елемент масиву згаданої значенням. Якщо масив не містить шуканого значення, то після перевірки останнього елемента значення змінної i збільшиться на одиницю; на наступній ітерації перший підумови виявиться помилковим і цикл завершиться без перевірку другого підумови. Якби логічні вирази обчислювалися повністю, то при відсутності шуканого елементу в масиві після останньої ітерації відбувалася б помилка: спроба визначити a [i] викликала б некоректне звернення до пам'яті.

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

При повному обчисленні логічних виразів наведений алгоритм довелося б записати приблизно в наступному вигляді:

 / / Пошук в масиві цілих чисел на мові Паскаль  / / Гіпотетичний варіант при повному обчисленні логічних виразів  / / Параметри - шукане значення і відкритий масив цілих чисел  / / Результат - індекс знайденого елементу або -1 у випадку, якщо елемент не знайдений  function  Find  (  e  :  integer  ;  var  a  :  array  of  integer  )  :  integer  ;  var  i  :  integer  ; F  :  boolean  ;  / / Додаткова змінна - прапор завершення циклу  begin  i  : =  0  ; F  : =  false  ;  while  not  f  do  if  i> High  (  a  )  then  f  : =  true  else  if  a  [  i  ]  =  e  then  f  : =  true  else  inc  (  i  )  ;  if  i <  =  High  (  a  )  then  Find  : =  i  else  Find  : =  -  1  ;  end  ; 

Як бачимо, довелося штучно задати порядок обчислення умов виходу і ввести додаткову змінну. Саме для того, щоб уникнути подібних трюків, і введено неповне обчислення логічних виразів.

Примітка: Код викладений вище, є прикладом використання оператора IF але не більше. Цей код не можна використовувати як правило для написання алгоритмів мовою Паскаль.

Нижче наведено оптимальний алгоритм для пошуку числа в масиві:

 function  Find  (  e  :  integer  ;  var  a  :  array  of  integer  )  :  integer  ;  var  i  :  integer  ;  begin  Result  : =  -  1  ;  for  i  : =  Low  (  a  )  to  High  (  a  )  do  begin  if  a  [  i  ]  =  e  then  begin  Result  : =  i;  Break  ;  end  ;  end  ;  end  ; 

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Точка розгалуження
Оператор
Оператор (математика)
Унітарний оператор
Оператор Д'Аламбера
Оператор замикання
Ерміта оператор
Оператор Кенні
Обмежений оператор
© Усі права захищені
написати до нас