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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

uses Robot;
begin 
Task(‘cif1’);
while  FreeFromRight do
begin
if  WallFromUp then
paint;
right;
end; 
if  WallFromUp then
paint;
end.

1

2

3

4

5

6

7

8

9

10

11

12

uses Robot;

begin

Task(‘cif1’);

while FreeFromRight do

begin

if WallFromUp then

paint;

right;

end;

if WallFromUp then

paint;

end.

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

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

uses Robot;
begin
Task('cif17'); 
while FreeFromUp do
up;
if FreeFromLeft then 
while FreeFromLeft do
left 
else
while FreeFromRight do
right; 
end.

1

2

3

4

5

6

7

8

9

10

11

12

uses Robot;

begin

Task('cif17');

while FreeFromUp do

up;

if FreeFromLeft then

while FreeFromLeft do

left

else

while FreeFromRight do

right;

end.

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

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

uses Robot;
begin 
Task('cc5');
for var i:=1 to 4 do
begin 
while FreeFromRight do
right;
down;
while FreeFromLeft do
left;
down; 
end; 
end.

1

2

3

4

5

6

7

8

9

10

11

12

13

uses Robot;

begin

Task('cc5');

for var i:=1 to 4 do

begin

while FreeFromRight do

right;

down;

while FreeFromLeft do

left;

down;

end;

end.

1 Якія алгарытмічныя канструкцыі выкарыстоўваюцца ў прыведзеных праграмах? Нарысуйце блок-схемы дадзеных алгарытмаў. Прапануйце прыклад пачатковага становішча, у якім алгарытм выканаецца карэктна.

uses Robot;
begin 
while WallFromLeft do
begin 
down;
paint;
end; 
end.

1

2

3

4

5

6

7

8

uses Robot;

begin

while WallFromLeft do

begin

down;

paint;

end;

end.

uses Robot;
begin 
while CellIsPainted do
if FreeFromleft then
left;
end.

1

2

3

4

5

6

uses Robot;

begin

while CellIsPainted do

if FreeFromleft then

left;

end.

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

1. Цела цыкла, што выконваецца пры ўмове WallFromUp, складаецца з дзвюх каманд: right і paint.
2. Калі ўмова FreeFromRight не выконваецца, то, калі клетка не зафарбавана, яе трэба зафарбаваць, а калі зафарбавана, то зрушыцца ўлева.
3. Праверку ўмовы CellIsPainted трэба выконваць датуль, пакуль знізу няма сцен. Пры выкананні ўмовы зрушыцца ўніз, пры невыкананні ўмовы зафарбаваць клетку.

3 Для рашэння задачы cif3 з убудаванага задачніка Міша напісаў праграму, але яна працуе няправільна. Якія памылкі дапусціў Міша?

uses Robot;
begin 
Task('cif3');
while WallFromRight do
begin
if WallFromDown or WallFromUp then
paint;
right;
end; 
if WallFromUp and WallFromDown then
paint;
end.

1

2

3

4

5

6

7

8

9

10

11

12

uses Robot;

begin

Task('cif3');

while WallFromRight do

begin

if WallFromDown or WallFromUp then

paint;

right;

end;

if WallFromUp and WallFromDown then

paint;

end.

4 Запоўніце пропускі ў праграме рашэння задачы cc14 з убудаванага задачніка так, каб яна працавала правільна.

uses Robot;
begin 
Task('cc14'); 
for var i:=1 to 4 do
begin 
while … do
right;
down; 
while … do
left;
down;
end;
end.

1

2

3

4

5

6

7

8

9

10

11

12

13

uses Robot;

begin

Task('cc14');

for var i:=1 to 4 do

begin

while … do

right;

down;

while … do

left;

down;

end;

end.

5 Рашыце задачу cif2 з убудаванага задачніка, выкарыстоўваючы ўнутры цыкла каманду галінавання.
6 Рашыце задачу cc7 з убудаванага задачніка, выкарыстоўваючы ўнутры аднаго цыкла два ўкладзеныя цыклы.

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

Інфарматыка. 7 клас

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