Электрификация

Справочник домашнего мастера

Кем задаются маршруты прохождения лабиринтов

Скандинавские язычники верили, что пройдя лабиринт, можно справиться с трудностями, усилить защиту и обрести удачу. Для верующих он символизирует путь к Богу и способ искупления от грехов. Лабиринты строили в Древнем Египте, Древней Греции и в Римской империи. Журнал Smithsonian рассказывает, чем так привлекательны лабиринты в наши дни, и где найти интересный лабиринт для просветления или неспешной прогулки.

У некоторых людей слово «лабиринт» ассоциируется с Минотавром Дедала или с фильмом, в котором Дэвид Боуи сыграл короля гоблинов. Но настоящий лабиринт совсем не такой. В нём есть лишь один маршрут, и нет никаких неправильных поворотов. Настоящий лабиринт это не головоломка, это медитация.

Эти сложные однопутные цепи использовались задолго до летописной истории. Историки делят лабиринты на типы, исходя из их формы и временного периода. Все уникурсальные лабиринты имеют один вход и одну дорожку, ведущую к центру пространства, а затем обратно. Ещё лабиринты делятся на левосторонние и правосторонние, в зависимости от направления первого поворота.

Разгадывание лабиринтов всегда являлось увлекательнейшим занятием, но еще более увлекательным является создание машин, способных пройти Лабиринт.
Попробуем описать робота, действующего в соответствии с правилом «правой руки».

В начале своей работы робот должен найти стену, по которой он будет следовать. Для этого он может просто двигаться вперед, пока не упрется в преграду.
После того как робот наткнулся на препятствие, он начинает передвигаться в соответствии с правилом «правой руки».
Двигаясь вдоль стены, робот следит, есть ли проход справа. Если проход есть, робот должен идти по нему, чтобы не оторваться от стены справа.
Если прохода нет — впереди стена — робот поворачивает налево. Если прохода снова нет, он еще раз поворачивает налево, таким образом разворачиваясь на 180 градусов, и идет в обратном направлении.

Блок-схема алгоритма для робота, работающего по правилу «правой руки», представлена на рисунке.

Попробуем проверить работу данного алгоритма и напишем для него программу. Для этой цели обратимся к среде программирования GameLogo. Эта среда является удобным средством для моделирования различных алгоритмов, связанных с управлением роботами. В ней есть исполнитель черепаха, который по своей сути является не чем иным, как самым настоящим роботом. Черепаха располагает очень удобным набором команд — вперед, направо, налево, назад. Кроме того, в центре черепахи есть датчик, принимающий значение от 0 до 100, в зависимости от тона поверхности, на которой она находится.

Задача №14. Выполнение алгоритма.

Автор материалов — Лада Борисовна Есакова.

В этой задаче используется, в основном, описание алгоритмов на псевдокоде (условном алгоритмическом языке, включающем в себя и элементы языка программирования, и элементы обычного естественного языка).

Основные конструкции псевдокода описаны перед текстом задачи.

Исполнитель чертежник

Пример 1.

Ис­пол­ни­тель Чертёжник пе­ре­ме­ща­ет­ся на ко­ор­ди­нат­ной плос­ко­сти, остав­ляя след в виде линии. Чертёжник может вы­пол­нять ко­ман­ду сме­стить­ся на (a, b), где a, b – целые числа. Эта ко­ман­да пе­ре­ме­ща­ет Чертёжника из точки с ко­ор­ди­на­та­ми (x, y) в точку с ко­ор­ди­на­та­ми (x + a; y + b).

Цикл

ПО­ВТО­РИ число РАЗ

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

КОНЕЦ ПО­ВТО­РИ

озна­ча­ет, что по­сле­до­ва­тель­ность ко­манд будет вы­пол­не­на ука­зан­ное число раз (число долж­но быть на­ту­раль­ным).

Чертёжнику был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм (бук­ва­ми n, a, b обо­зна­че­ны не­из­вест­ные числа, n>1):

НА­ЧА­ЛО

сме­стить­ся на (60, 100)

ПО­ВТО­РИ n РАЗ

сме­стить­ся на (a, b)

сме­стить­ся на (33, 44)

КОНЕЦ ПО­ВТО­РИ

сме­стить­ся на (13, 200)

сме­стить­ся на (-1, 60)

КОНЕЦ

Ука­жи­те наи­боль­шее воз­мож­ное зна­че­ние числа n, для ко­то­ро­го най­дут­ся такие зна­че­ния чисел a и b, что после вы­пол­не­ния про­грам­мы Чертёжник воз­вра­тит­ся в ис­ход­ную точку.

Решение:

В результате выполнения алгоритма Чертежник переместится

по оси х на:

60 + n*a + n*33 + 13 – 1

по оси y на:

100 + n*b + n*44 + 200 + 60

Известно, что в результате перемещения Чертежник вернулся в исходную точку, т.е. перемещение по оси х равно нулю, и перемещение по оси y равно нулю:

60 + n*a + n*33 + 13 – 1 = 0

100 + n*b + n*44 + 200 + 60 = 0

Т.е.

n*(a + 33) = -72

n*(b + 44) = -360

Наибольшее n – это наибольший общий делитель чисел -72 и -360. Это число 72.

Ответ: 72

Исполнитель робот

Пример 2.

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

вверх

вниз

влево

впра­во

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

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

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

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

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

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

Цикл

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

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

КОНЕЦ ПОКА

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

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

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

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

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

КОНЕЦ ЕСЛИ

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

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

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

НА­ЧА­ЛО

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

впра­во

КОНЕЦ ПОКА

вниз

КОНЕЦ ПОКА

КОНЕЦ

1) 22

2) 19

3) 15

4) 12

Решение:

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

Про­ве­рив последовательно все клет­ки по пра­ви­лу дви­же­ния РО­БО­ТА вы­яс­ня­ем, что число кле­ток, удо­вле­тво­ря­ю­щих усло­вию за­да­чи равно 15 (вся пер­вая строч­ка, весь стол­бец F, клет­ки D2, E2, D4, D6, E4).


Пра­виль­ный ответ ука­зан под но­ме­ром 3.

Ответ: 3

Исполнитель редактор

Пример 3.

Ис­пол­ни­тель Ре­дак­тор по­лу­ча­ет на вход стро­ку цифр и пре­об­ра­зо­вы­ва­ет её. Ре­дак­тор может вы­пол­нять две ко­ман­ды, в обеих ко­ман­дах v и w обо­зна­ча­ют це­поч­ки цифр.

А) за­ме­нить (v, w).

Эта ко­ман­да за­ме­ня­ет в стро­ке пер­вое слева вхож­де­ние це­поч­ки v на це­поч­ку w. На­при­мер, вы­пол­не­ние ко­ман­ды за­ме­нить (111, 27) пре­об­ра­зу­ет стро­ку 05111150 в стро­ку 0527150. Если в стро­ке нет вхож­де­ний це­поч­ки v, то вы­пол­не­ние ко­ман­ды за­ме­нить (v, w) не ме­ня­ет эту стро­ку.

Б) на­шлось (v).

Эта ко­ман­да про­ве­ря­ет, встре­ча­ет­ся ли це­поч­ка v в стро­ке ис­пол­ни­те­ля Ре­дак­тор. Если она встре­ча­ет­ся, то ко­ман­да воз­вра­ща­ет ло­ги­че­ское зна­че­ние «ис­ти­на», в про­тив­ном слу­чае воз­вра­ща­ет зна­че­ние «ложь». Стро­ка ис­пол­ни­те­ля при этом не из­ме­ня­ет­ся.

Цикл

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

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

КОНЕЦ ПОКА

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

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

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

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

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

КОНЕЦ ЕСЛИ

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

Какая стро­ка по­лу­чит­ся в ре­зуль­та­те при­ме­не­ния при­ведённой ниже про­грам­мы к стро­ке, со­сто­я­щей из 68 иду­щих под­ряд цифр 8? В от­ве­те за­пи­ши­те по­лу­чен­ную стро­ку.

НА­ЧА­ЛО

ПОКА на­шлось (222) ИЛИ на­шлось (888)

ЕСЛИ на­шлось (222)

ТО за­ме­нить (222, 8)

ИНАЧЕ за­ме­нить (888, 2)

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Решение:

Обозначим строку из 68 восьмерок — 68″8″,

строку из двойки и 65 восьмерок – 1″2″65″8″ и т.д.

Отработаем 4 первых цикла программы:

68″8″ → 1″2″65″8″ → 2″2″62″8″ → 3″2″59″8″ → 60″8″

В результате количество восьмерок уменьшилось на 8. Не сложно понять, что строка будет уменьшаться на 8 восьмерок каждые 4 итерации. В результате останется строка из 4 восьмерок. Доработаем программу:

…→ 4″8″ → 1″2″1″8″ = 28

Ответ: 28

Исполнитель черепашка

Пример 4.

Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:

Вперед n, где n – целое число, вызывающее передвижение черепашки на n шагов в направлении движения.

Направо m, где m – целое число, вызывающее изменение направления движения на m градусов по часовой стрелке.

Запись Повтори 5 означает, что последовательность команд в скобках повторится 5 раз.

Черепашке был дан для исполнения следующий алгоритм:

Повтори 5 Направо 120]

Какая фигура появится на экране?

Решение:

Последовательность действий Вперед 40 Направо 90 рисует отрезок длиной 40 шагов, а затем меняет направление на 90 градусов по часовой стрелке. Тогда последовательность Повтори 4 нарисует квадрат, а направление вернется в исходное.

Затем выполняется команда Направо 120, она изменит направление на 120 градусов от исходного.

Если повторить все рассмотренные действия 5 раз:

Повтори 5 Направо 120], то будет 5 раз нарисован квадрат. Причем каждый следующий повернут вокруг вершины относительно предыдущего на 120 градусов. Не сложно заметить, что 4-й квадрат будет нарисован поверх первого (120*3 = 360, сделан поворот на целый круг, возврат в исходное положение), а 5-й поверх второго.

Результат изображен под номером 3.

Ответ: 3

Записать программу для Робота (кумир). Робот находится в левом верхнем углу в лабиринте шириной в одну клетку. Лабиринт спускается в правый нижний угол поля. Длина лабиринта неизвестна, количество поворотов тоже неизвестно, известно только, что движение по лабиринту возможно вправо и вниз. Использовать цикл и ветвление.

Дана программа:Какое наибольшее число может выдать эта программа,если вводить перестановки чисел 1,2,3? Сделайте пожалуйста таблицу по информатике. Желательно на листочке Даю 15 баллов. Помогите срочно пж!Очень нужно! Помогите пж дам 30 баллов​ 1 Оцените информационный объем изображения (в битах, байтах, Кбайтах) размером 300х750 пикселей в палитре, состоящей из 16 цветов. 2 Запишите в различ ных единицах измерения _____Кбайт = ______ байт= 81920 бит 3 Определите глубину цвета изображения 170х180, информационный объем, которого равен 214200 бит На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном ст релкой. Сколько существует различных путей из города А в город Л, проходящих через город B? (Должно быть написано решение!) Составить программу вычисления значения функции : Помогите с информатикой У терема представляющего иерархическую систему,выделяется одна главная вершина,которая называется Нужно письменно обьяснить все действия задания задания на ПК.

admin

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Наверх