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

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

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

При вы­пол­не­нии любой из этих ко­манд РОБОТ пе­ре­ме­ща­ет­ся на одну клет­ку со­от­вет­ствен­но: вверх \uparrow, вниз \downarrow, влево \leftarrow, впра­во arrow.

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

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

Цикл

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

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

КОНЕЦ ПОКА

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

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

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

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

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

КОНЕЦ ЕСЛИ

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

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

 

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

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

 

 

НА­ЧА­ЛО

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

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

            вниз

        КОНЕЦ ПОКА

    ЕСЛИ спра­ва сво­бод­но ТО

        впра­во

    КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

КОНЕЦ

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

Ре­ше­ние.

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

 

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

 

Про­ана­ли­зи­ро­вав эту про­грам­му, при­хо­дим к вы­во­ду, что РОБОТ будет дви­гать­ся вниз или впра­во, пока у него есть такая воз­мож­ность. РОБОТ при дан­ной про­грам­ме ни­ко­гда не разобьётся.

 

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

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