Задания
Версия для печати и копирования в MS Word
Тип Д12 № 4552
i

Си­сте­ма ко­манд ис­пол­ни­те­ля РОБОТ, «жи­ву­ще­го» в пря­мо­уголь­ном ла­би­рин­те на клет­ча­той плос­ко­сти, вклю­ча­ет в себя 4 ко­ман­ды-при­ка­за и 4 ко­ман­ды про­вер­ки усло­вия.

Ко­ман­ды-при­ка­зы:

вверхвнизвлевовпра­во

При вы­пол­не­нии любой из этих ко­манд РОБОТ пе­ре­ме­ща­ет­ся на одну клет­ку со­от­вет­ствен­но: вверх ↑, вниз ↓, влево ←, впра­во →.

Если РОБОТ начнёт дви­же­ние в сто­ро­ну на­хо­дя­щей­ся рядом с ним стены, то он раз­ру­шит­ся, и про­грам­ма прервётся.

Дру­гие 4 ко­ман­ды про­ве­ря­ют ис­тин­ность усло­вия от­сут­ствия стены у каж­дой сто­ро­ны той клет­ки, где на­хо­дит­ся РОБОТ:

свер­ху сво­бод­носнизу сво­бод­нослева сво­бод­носпра­ва сво­бод­но

Цикл

ПОКА < усло­вие >

по­сле­до­ва­тель­ность ко­манд

КОНЕЦ ПОКА

вы­пол­ня­ет­ся, пока усло­вие ис­тин­но.

В кон­струк­ции

ЕСЛИ < усло­вие >

ТО ко­ман­да1

ИНАЧЕ ко­ман­да2

КОНЕЦ ЕСЛИ

вы­пол­ня­ет­ся ко­ман­да1 (если усло­вие ис­тин­но) или ко­ман­да2 (если усло­вие ложно).

 

Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, начав дви­же­ние в ней и вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка А1)?

НА­ЧА­ЛО

ПОКА < слева сво­бод­но ИЛИ свер­ху сво­бод­но >

ЕСЛИ < слева сво­бод­но >

ТО влево

ИНАЧЕ вверх

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Спрятать решение

Ре­ше­ние.

Один из глав­ных приёмов в ре­ше­нии этой за­да­чи  — про­ве­рять клет­ки груп­па­ми а не по одной.

 

При дан­ной про­грам­ме РОБОТ по­сту­па­ет сле­ду­ю­щим об­ра­зом: спер­ва РОБОТ про­ве­ря­ет сво­бод­на ли клет­ка слева или свер­ху от него, если это так, то РОБОТ пе­ре­хо­дит к пер­во­му дей­ствию внут­ри цикла. Про­ве­ря­ет­ся сво­бод­на клет­ка слева, если сво­бод­на  — то РОБОТ де­ла­ет шаг влево, иначе  — шаг вверх. После воз­вра­ща­ет­ся к на­ча­лу цикла ПОКА. В этом цикле пока слева клет­ки в ко­то­рой на­хо­дит­ся РОБОТ нет стены он про­дол­жа­ет дви­гать­ся влево. В про­тив­ном слу­чае он дви­га­ет­ся вверх.

 

Про­ве­рив все клет­ки груп­па­ми вы­яс­ня­ем, что число кле­ток, удо­вле­тво­ря­ю­щих усло­вию за­да­чи, равно 21.

Источник: Де­мон­стра­ци­он­ная вер­сия ЕГЭ—2013 по ин­фор­ма­ти­ке
Раздел кодификатора ФИПИ: 1.6.2 Вы­чис­ли­мость. Эк­ви­ва­лент­ность ал­го­рит­ми­че­ских мо­де­лей