§ 13. Выкарыстанне асноўных алгарытмічных канструкцый для выканаўцы Робат

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

Паслядоўнасць, цыкл і галінаванне — базавыя алгарытмічныя канструкцыі. Выкарыстоўваючы гэтыя канструкцыі як элементы нейкага «канструк-
тара», можна складаць і распрацоўваць любыя алгарытмы.

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

Разгледзім падрабязней прыклады алгарытмаў, якія змяшчаюць некалькі алгарытмічных канструкцый.

Прыклад 13.1. Рэшым задачу cif1 з убудаванага задачніка.

Робат перамяшчаецца ўправа датуль, пакуль не сустрэне сцяну. На шляху ён павінен зафарбаваць клеткі, над якімі ёсць сцяна.

Для рашэння задачы Робат павінен правяраць кожную клетку на сваім шляху. Калі ўмова «зверху сцяна» выконваецца, Робат зафарбоўвае гэту клетку. Пасля праверкі клеткі Робат зрушваецца ўправа. Такія дзеянні выконваюцца ў цыкле, пакуль справа пуста.

Пасля цыкла патрэбна каманда галінавання, бо для крайняй клеткі поля каманда «справа пуста» не выконваецца і клетка ў цыкле не зафарбоўваецца.
У гэтай задачы ўнутры структуры цыкла выкарыстоўваецца структура галінавання.

Прыклад 13.2. Рэшым задачу cif17 з убудаванага задачніка.

Робат павінен дайсці да канца калідора пераменнага памеру. Калідор можа зварочваць улева або ўправа.

Для рашэння задачы Робат спачатку перамяшчаецца ўверх датуль, пакуль зверху пуста. Сцяна, якая з’явілася зверху, азначае, што пачаўся паварот калідора. Калідор паварочвае ўлева, калі злева пуста, інакш калідор паварочвае ўправа. Далей Робат рухаецца ў тым напрамку, дзе пуста, пакуль не сустрэне сцяну.

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

Аператарныя дужкі begin i end; прапушчаны, паколькі паслядоўнасць складаецца з адной каманды цыкла.

Прыклад 13.3*. Рэшым задачу cc5 з убудаванага задачніка.

Робат знаходзіцца ў верхнім левым вугле поля і павінен перамясціцца ў ніжні левы вугал. На полі прысутнічаюць сцены, якія Робат павінен абысці. Пры гэтым ён павінен спачатку рухацца да правай мяжы поля, затым спусціцца ўніз, а потым рухацца да левай мяжы поля і спусціцца ўніз. Гэтыя дзеянні Робат павінен паўтарыць 4 разы.

У дадзенай задачы ўнутры цыкла з параметрам выкарыстоўваюцца два іншыя цыклы з перадумовай.

Структуру, калі ўнутры адна-го цыкла выконваецца іншы, называюць укладзенымі цыкламі.

Такім чынам, базавыя алгарытмічныя канструкцыі можна камбінаваць адну з адной.

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

Гэта палажэнне было высунута ў сярэдзіне 70-х гг. ХХ ст. нідэрландскім вучоным Эдсгерам Вібе Дэйкстрам (1930—2002).

Яго працы зрабілі ўплыў на развіццё інфарматыкі і інфармацыйных тэхналогій. Э. Дэйкстра з’яўляецца адным з распрацоўшчыкаў канцэпцыі структурнага праграміравання, удзельнічаў у стварэнні мовы праграміравання Алгол. Вядомы сваімі дасягненнямі ў галіне матэматычнай логікі і тэорыі графаў.

Пример 13.1. Адно з магчымых пачатковых становішчаў:

Праграма для Робата:

Пример 13.2. Магчымыя пачатковыя становішчы:

Праграма для Робата:

Пример 13.3 * . Пачатковае становішча:

Праграма для Робата:



1. Назавіце базавыя алгарытмічныя канструкцыі.



2. Што такое ўкладзены цыкл?



  1. Якія алгарытмічныя канструкцыі выкарыстоўваюцца ў прыведзеных праграмах? Нарысуйце блок-схемы дадзеных алгарытмаў. Прапануйце прыклад пачатковага становішча, у якім алгарытм выканаецца карэктна.
  2. Выкарыстоўваючы базавыя алгарытмічныя канструкцыі, запішыце алгарытмы, якія адпавядаюць апісанням. Пабудуйце для іх блок-схемы.
  1. Цела цыкла, што выконваецца пры ўмове WallFromUp, складаецца з дзвюх каманд: right і paint.
  2. Калі ўмова FreeFromRight не выконваецца, то, калі клетка не зафарбавана, яе трэба зафарбаваць, а калі зафарбавана, то зрушыцца ўлева.
  3. Праверку ўмовы CellIsPainted трэба выконваць датуль, пакуль знізу няма сцен. Пры выкананні ўмовы зрушыцца ўніз, пры невыкананні ўмовы зафарбаваць клетку.
  1. Для рашэння задачы cif3 з убудаванага задачніка Міша напісаў праграму, але яна працуе няправільна. Якія памылкі дапусціў Міша?
     
  2. Запоўніце пропускі ў праграме рашэння задачы cc14 з убудаванага задачніка так, каб яна працавала правільна.
     
  3. Рашыце задачу cif2 з убудаванага задачніка, выкарыстоўваючы ўнутры цыкла каманду галінавання.
  4. Рашыце задачу cc7 з убудаванага задачніка, выкарыстоўваючы ўнутры аднаго цыкла два ўкладзеныя цыклы.

7*. Прыдумайце задачу для выканаўцы Робат, у якой будуць выкарыстоўвацца розныя алгарытмічныя канструкцыі.