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

Ис­пол­ни­тель РОБОТ умеет пе­ре­ме­щать­ся по пря­мо­уголь­но­му ла­би­рин­ту, на­чер­чен­но­му на плос­ко­сти, раз­би­той на клет­ки. Между со­сед­ни­ми по сто­ро­нам клет­ка­ми может сто­ять стена.

Си­сте­ма ко­манд ис­пол­ни­те­ля РОБОТ со­дер­жит во­семь ко­манд. Че­ты­ре ко­ман­ды - это ко­ман­ды пе­ре­ме­ще­ния:

вверх

вниз

влево

впра­во


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

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

свер­ху сво­бод­но

снизу сво­бод­но

слева сво­бод­но

спра­ва сво­бод­но


Цикл

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

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

КОНЕЦ ПОКА

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

В кон­струк­ци­ях ПОКА усло­вие может со­дер­жать ко­ман­ды про­вер­ки, а также слова И, ИЛИ, НЕ.

Схема ла­би­рин­та:

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

НА­ЧА­ЛО

     ПОКА <снизу сво­бод­но ИЛИ спра­ва сво­бод­но>

          ПОКА <снизу сво­бод­но>

               вниз

          КОНЕЦ ПОКА

          впра­во

     КОНЕЦ ПОКА

КОНЕЦ

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

Ре­ше­ние.

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

Про­ве­рив все клет­ки по вы­ве­ден­но­му нами пра­ви­лу дви­же­ния РО­БО­ТА вы­яс­ня­ем, что число кле­ток, удо­вле­тво­ря­ю­щих усло­вию за­да­чи, равно 12.

 

Ответ: 12.

 

При­ме­ча­ние.

За­ме­тим, что стар­то­вав из клет­ки F6, РОБОТ не нач­нет вы­пол­не­ние цикла (по­сколь­ку снизу и спра­ва не сво­бод­но) и во­об­ще не вы­пол­нит ни­ка­ких дей­ствий, остав­шись после окон­ча­ния про­грам­мы в клет­ке F6, по­это­му клет­ка F6 под­хо­дит. Если же РОБОТ стар­ту­ет из любой дру­гой клет­ки столб­ца F, то он нач­нет вы­пол­не­ние цикла и будет дви­гать­ся вниз до клет­ки F6, после чего вы­пол­нит ко­ман­ду «впра­во» и разо­бьет­ся.

Раздел кодификатора ФИПИ: 1.6.2 Вы­чис­ли­мость. Эк­ви­ва­лент­ность ал­го­рит­ми­че­ских мо­де­лей
Vlad Vlad 23.05.2016 12:58

по­че­му диа­па­зон F3:F5 не под­хо­дит???

Сергей Никифоров

За­меть­те, что начав дви­же­ние из кле­ток F3, F4, F5, робот дой­дет вниз до клет­ки F6, после чего по­пы­та­ет­ся вы­пол­нить ко­ман­ду "впра­во", и разобьётся.