История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Топ:
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
2020-08-21 | 53 |
5.00
из
|
Заказать работу |
|
|
A13 (повышенный уровень, время – 6 мин)
Тема: Выполнение алгоритмов для исполнителя.
Что нужно знать:
· правила выполнения линейных, разветвляющихся и циклических алгоритмов
· основные операции с символьными строками (определение длины, выделение подстроки, удаление и вставка символов, «сцепка» двух строк в одну)
· исполнитель – это человек, группа людей, животное, машина или другой объект, который может понимать и выполнять некоторые команды
· в школьном алгоритмическом языке нц обозначает «начало цикла», а кц – «конец цикла»; все команды между нц и кц – это тело цикла, они выполняются несколько раз
· запись нц для i от 1 до n обозначает начало цикла, в котором переменная i (она называется переменной цикла) принимает последовательно все значения от 1 до n с шагом 1
Пример задания:
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
Вверх вниз влево вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
Сверху свободно снизу свободно
слева свободно справа свободно
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 | ||||||
A | B | C | D | E | F |
Цикл
ПОКА < условие >
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно. В конструкции
ЕСЛИ < условие >
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если
|
условие ложно).
Если РОБОТ начнёт движение в сторону находящейся рядом с ним
стены, то он разрушится и программа прервётся.
Сколько клеток лабиринта соответствуют требованию, что, начав
движение в ней и выполнив предложенную программу, РОБОТ уцелеет
и остановится в закрашенной клетке (клетка А1)?
1) 8 2) 12 3) 17 4) 21
ПОКА слева свободно ИЛИ сверху свободно
ЕСЛИ слева свободно
ТО влево
ИНАЧЕ вверх
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
Решение:
1) в программе один цикл со сложным условием, внутри которого расположен условный оператор «если»
2) в этой программе Робот не может разрушиться, так как возможность шага влево проверяется, а если влево ходить нельзя, то можно идти вверх, так как условие цикла «слева свободно ИЛИ сверху свободно» выполнено
3) Робот останавливается в клетке, где нарушается условие «слева свободно ИЛИ сверху свободно», в этой клетке должны быть стенки слева и сверху; таких клеток на поле всего три: конечная цель маршрута А1 и две «ложные цели» в В3 и Е1:
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 | ||||||
A | B | C | D | E | F |
4) из п. 2 и 3 следует, что Робот успешно придет в клетку А1, если только он не попадёт в клетки В3 и Е1
5) подсчитаем, сколько есть клеток, из которых Робот попадает в клетку В3; Робот сначала идет влево до упора, потом – вверх, пока не упрётся в стенку сверху или не откроется «окно» влево; отметим голубым цветом все клетки, из которых Робот попадает в В3, их всего 13
1 | ||||||
2 | ||||||
· | 3 | |||||
4 | ||||||
5 | ||||||
6 | ||||||
A | B | C | D | E | F |
6) кроме того, есть две клетки, из которых Робот попадает в Е1, они показаны фиолетовым цветом:
|
· | 1 | |||||
2 | ||||||
· | 3 | |||||
4 | ||||||
5 | ||||||
6 | ||||||
A | B | C | D | E | F |
7) таким образом, на поле есть всего 15 клеток, из которых Робот при выполнении заданной программы не попадает в клетку А1
8) следовательно, «нужных» клеток 36 – 15 = 21
9) Ответ: 4.
Ещё пример задания:
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
Вверх вниз влево вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
Сверху свободно снизу свободно
слева свободно справа свободно
1 | ||||||
2 | ||||||
3 | ||||||
4 | ||||||
5 | ||||||
6 | ||||||
A | B | C | D | E | F |
Цикл
ПОКА < условие >
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно. В конструкции
ЕСЛИ < условие >
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если
условие ложно).
Если РОБОТ начнёт движение в сторону находящейся рядом с ним
стены, то он разрушится и программа прервётся.
Сколько клеток лабиринта соответствуют требованию, что, начав
движение в ней и выполнив предложенную программу, РОБОТ уцелеет
и остановится в закрашенной клетке (клетка F6)?
1) 8 2) 15 3) 24 4) 27
НАЧАЛО
ПОКА < справа свободно ИЛИ снизу свободно >
ПОКА < справа свободно >
вправо
КОНЕЦ ПОКА
ПОКА < снизу свободно >
вниз
КОНЕЦ ПОКА
КОНЕЦ ПОКА
КОНЕЦ
Решение:
1) обратим внимание, что в программе три цикла, причем два внутренних цикла вложены в один внешний
2) цикл
ПОКА < справа свободно >
вправо
КОНЕЦ ПОКА
означает «двигаться вправо до упора», а цикл
ПОКА < снизу свободно >
вниз
КОНЕЦ ПОКА
означает «двигаться вниз до упора»
3) тогда программу можно записать в свободном стиле так:
ПОКА не пришли в угол
|
двигаться вправо до упора
двигаться вниз до упора
КОНЕЦ ПОКА
где угол – это клетка, в которой есть стенки снизу и справа
4) за каждый шаг внешнего цикла Робот проходит путь в виде «сапога», двигаясь сначала вправо до упора, а затем – вниз до упора:
→ | → | ↓ | |
↓ | |||
↓ |
клетка, выделенная красным фоном особая – в ней заканчивается один шаг внешнего цикла и начинается следующий:
а) Робот может попасть в эту клетку, двигаясь вниз из клетки, где справа – стенка
б) снизу есть стенка;
в) снизу стенка есть, справа – нет, поэтому будет выполнен еще один шаг внешнего цикла.
5) в клетку F6 (это угол, где Робот остановился), Робот мог придти за один шаг внешнего цикла (за один «сапог») только из отмеченных клеток:
1 | ||||||
2 | ||||||
3 | ||||||
→ | → | → | → | → | ↓ | 4 |
→ | → | ↓ | 5 | |||
→ | → | → | → | → | 6 | |
A | B | C | D | E | F |
6) теперь отметим красным фоном особые клетки, которые удовлетворяют условиям а-в пункта 4 (см. выше), их всего 2:
1 | ||||||
2 | ||||||
3 | ||||||
→ | → | → | → | → | ↓ | 4 |
→ | → | ↓ | 5 | |||
→ | → | → | → | → | 6 | |
A | B | C | D | E | F |
7) отметим все пути в форме «сапога», которые приводят в особые клетки:
1 | ||||||
→ | → | ↓ | 2 | |||
→ | → | ↓ | 3 | |||
→ | → | → | → | → | ↓ | 4 |
→ | → | ↓ | → | → | ↓ | 5 |
→ | → | → | → | → | 6 | |
A | B | C | D | E | F |
8) больше особых клеток (см. пункт 4) нет; всего отмечено 24 клетки (считая конечную клетку F6)
9) таким образом, правильный ответ – 3.
Возможные ловушки и проблемы: · нужно помнить, что внешний цикл может выполняться более одного раза; неучет этого обстоятельства приводит к неверному ответу 2 (15 клеток) · важен порядок выполнения внутренних циклов (в данном случае сначала Робот идет вправо, а затем – вниз); при изменении этого порядка изменится и результат, в частности, изменятся условия, определяющие особую клетку |
Еще пример задания:
|
6 | ||||||
5 | ||||||
4 | ||||||
3 | ||||||
2 | ||||||
1 | ||||||
A | B | C | D | E | F |
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
Вверх вниз влево вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
НАЧАЛО
ПОКА <снизу свободно> вниз
ПОКА <слева свободно> влево
ПОКА <сверху свободно> вверх
ПОКА <справа свободно> вправо
КОНЕЦ
Решение:
10) легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо:
на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно;
11) кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода
12) обратим внимание, что возможны еще «вырожденные» варианты, вроде таких:
13) итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты:
· | · | 6 | ||||
· | · | 5 | ||||
· | 4 | |||||
· | 3 | |||||
· | · | 2 | ||||
· | · | 1 | ||||
A | B | C | D | E | F |
· | 6 | |||||
· | 5 | |||||
· | 4 | |||||
· | 3 | |||||
· | 2 | |||||
· | 1 | |||||
A | B | C | D | E | F |
14) этих «подозрительных» клеток не так много, но можно еще сократить количество рассматриваемых вариантов: если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, одну клетку мы нашли, а остальные клетки вертикали F условию не удовлетворяют:
15) проверяем оставшиеся четыре клетки-кандидаты, но для каждой из них после выполнения алгоритма РОБОТ не приходит в ту клетку, откуда он стартовал:
· | 6 | |||||
5 | ||||||
4 | ||||||
3 | ||||||
2 | ||||||
1 | ||||||
A | B | C | D | E | F |
|
6 | ||||||
5 | ||||||
4 | ||||||
3 | ||||||
· | 2 | |||||
1 | ||||||
A | B | C | D | E | F |
6 | ||||||
· | 5 | |||||
4 | ||||||
3 | ||||||
2 | ||||||
1 | ||||||
A | B | C | D | E | F |
6 | ||||||
5 | ||||||
4 | ||||||
3 | ||||||
2 | ||||||
· | 1 | |||||
A | B | C | D | E | F |
16) итак, условию удовлетворяет только одна клетка – F4
17) таким образом, правильный ответ – 1.
Возможные ловушки и проблемы: · вариантов может быть достаточно много, важно не пропустить ни один из них · можно попытаться выполнить алгоритм для каждой клетки лабиринта, но это займет много времени; поэтому лучше ограничиться только клетками-кандидатами · нужно правильно определить свойства, по которым клетку можно считать «кандидатом» · можно не заметить стенку и таким образом получить лишнее решение |
Еще пример задания:
6 | ||||||
5 | ||||||
4 | ||||||
3 | ||||||
2 | ||||||
1 | ||||||
A | B | C | D | E | F |
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
Вверх вниз влево вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
НАЧАЛО
ПОКА <слева свободно> вверх
ПОКА <сверху свободно> вправо
ПОКА <справа свободно> вниз
ПОКА <снизу свободно> влево
КОНЕЦ
Решение:
1) особенность этой задач в том, что РОБОТ проверяет стенку в одном направлении, а движется в другом
2) рассмотрим первый цикл:
ПОКА <слева свободно> вверх
понятно, что при движении вверх РОБОТ остановится в первой же клетке, где слева будет стена
3) рассуждая аналогично, находим, что во втором цикле при движении вправо РОБОТ останавливается в клетке, где есть стена сверху; в третьем цикле (движение вниз) РОБОТ останавливается в клетке, где есть стена справа;
4) наконец, в четвертом цикле РОБОТ останавливается в клетке, где есть стена снизу; при этом он должен попасть обратно в исходную клетку, обозначенную на рисунке красной точкой;
5) кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке зеленым фоном, был свободен для прохода, иначе РОБОТ врежется в стенку
6) теперь отметим на карте все клетки-кандидаты, где снизу есть стена:
· | 6 | |||||
· | 5 | |||||
4 | ||||||
· | 3 | |||||
· | 2 | |||||
· | · | · | · | · | · | 1 |
A | B | C | D | E | F |
7) при движении из клеток B5, D1, E1, E6, F1 и F3 РОБОТ врежется в стенку, потому что слева стены нет и условие «слева свободно» всегда истинно:
· | 6 | |||||
· | 5 | |||||
4 | ||||||
· | 3 | |||||
· | 2 | |||||
· | · | · | · | · | · | 1 |
A | B | C | D | E | F |
8) начав движение с клетки A1, C1 или C2, РОБОТ также врезается в стенку и разрушается:
6 | ||||||
5 | ||||||
4 | ||||||
3 | ||||||
· | 2 | |||||
· | · | · | 1 | |||
A | B | C | D | E | F |
9) и только путь, начатый в клетке B1, приводит РОБОТА обратно в точку старта:
6 | ||||||
5 | ||||||
4 | ||||||
3 | ||||||
2 | ||||||
· | 1 | |||||
A | B | C | D | E | F |
10) таким образом, только клетка B1 удовлетворяет условию задачи, поэтому …
11) правильный ответ – 1.
Еще пример задания:
В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные a, b, c имеют тип «строка», а переменные i, k – тип «целое». Используются следующие функции:
Длина(a) – возвращает количество символов в строке a. (Тип «целое»)
Извлечь(a,i) – возвращает i -тый (слева) символ в строке a. (Тип «строка»)
Склеить(a,b) – возвращает строку, в которой записаны сначала все символы
строки a, а затем все символы строки b. (Тип «строка»)
Значения строк записываются в одинарных кавычках (Например, a:='дом' ). Фрагмент алгоритма:
i:= Длина(a)
k:= 2
b:= 'А'
пока i > 0
нц
c:= Извлечь(a,i)
b:= Склеить(b,c)
i:= i – k
кц
b:= Склеить(b,'Т')
Какое значение будет у переменной b после выполнения вышеприведенного фрагмента алгоритма, если значение переменной a было ‘ПОЕЗД’?
1) ‘АДЕПТ’ 2) ‘АДЗЕОП’ 3) ‘АДТЕТПТ’ 4) ‘АДЗОТ’
Решение:
1) эта задача более близка к классическому программированию, здесь выполняется обработка символьных строк; вся информация для успешного решения, вообще говоря, содержится в условии, но желательно иметь хотя бы небольшой опыт работы с символьными строками на Паскале (или другом языке)
2) заметим, что последняя команда алгоритма, b:=Склеить(b,'Т'), добавляет букву 'Т' в конец строки b, поэтому ответ 2 – явно неверный (строка должна оканчиваться на букву 'Т', а не на 'П')
3) для решения будем использовать ручную прокрутку; здесь пять переменных: a, b, c, i, k, для каждой из них выделим столбец, где будем записывать изменение ее значения
4) перед выполнением заданного фрагмента мы знаем только значение a, остальные неизвестны (обозначим их знаком вопроса):
a | b | c | i | k | |
'ПОЕЗД' | ? | ? | ? | ? |
5) в первой команде длина строки a (она равна 5 символам) записывается в переменную i:
a | b | c | i | k | |
'ПОЕЗД' | ? | ? | ? | ? | |
i:=Длина(a) | 5 |
6) следующие два оператора записывают начальные значения в k и b:
a | b | c | i | k | |
'ПОЕЗД' | ? | ? | ? | ? | |
i:=Длина(a) | 5 | ||||
k:=2 | 2 | ||||
b:='А' | 'A' |
7) далее следует цикл пока с проверкой условия i >0 в начале цикла; сейчас i=5>0, то есть, условие выполняется, цикл начинает работать и выполняются все операторы в теле цикла:
a | b | c | i | k | |
'ПОЕЗД' | ? | ? | ? | ? | |
i:=Длина(a) | 5 | ||||
k:=2 | 2 | ||||
b:='А' | 'A' | ||||
i > 0? | да | ||||
c:=Извлечь(a,i) | i:=Длина(a) | 5 | |||
b:=Cклеить(b,c) | k:=2 | ||||
i:=i–k | 3 |
· поскольку i =5, вызов функции Извлечь(a, i) выделяет из строки a символ с номером 5, это 'Д';
· следующей командой этот символ приписывается в «хвост» строки b, теперь в ней хранится цепочка 'АД';
· в команде i:=i-k значение переменной i уменьшается на k (то есть, на 2)
8) далее нужно перейти в начало цикла и снова проверить условие i>0, оно опять истинно, поэтому выполняется следующий шаг цикла, в котором к строке b добавляется 3-й символ строки a, то есть 'Е':
a | b | c | i | k | |
... | 'ПОЕЗД' | 'АД' | … | 3 | 2 |
i > 0? |
Да
9) условие i >0 истинно, поэтому тело цикла выполняется еще один раз, к строке b добавляется 1-й символ строки a, то есть 'П':
a | b | c | i | k | |
... | 'ПОЕЗД' | 'АДЕ' | … | 1 | 2 |
i > 0? |
Да | ||||
c:=Извлечь(a,i) | 'П' | ||||
b:=Cклеить(b,c) | 'АДЕП' | ||||
i:=i–k | –1 |
10) теперь i =-1, поэтому при очередной проверке условие i >0 в начале цикла оказывается ложным, выполнение цикла заканчивается, и исполнителю остается выполнить единственную строчку после цикла, которая дописывает в конец строки b букву 'Т':
a | b | c | i | k | |
... | 'ПОЕЗД' | 'АДЕП' | … | –1 | 2 |
i > 0? |
Нет | ||||
b:=Склеить(b,'Т') | 'АДЕПТ' |
11) у нас получилось, что в конце выполнения фрагмента алгоритма в переменной b будет записана последовательность символов 'АДЕПТ'
12) таким образом, правильный ответ – 1.
Возможные проблемы: · таблица получилась достаточно громоздкая, однако она позволяет наиболее наглядно решить задачу |
Еще пример задания [1]:
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
Вверх вниз влево вправо.
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
НАЧАЛО
ПОКА <снизу свободно> вниз
ПОКА <слева свободно> влево
Вверх
Вправо
КОНЕЦ
Решение:
1) нарисуем примерный путь Робота в соответствии с программой; вот три варианта, когда Робот не разбивается:
1) | ? | ? | ? | ? | 2) | ? | ? | ? | 3) | ? | ? | ? | |||
? | ? | ? | ? | ? | ? | ? | ? | ? | ? | ||||||
? | ? | ? | ? | ? | ? | ||||||||||
? | ? | ? | |||||||||||||
? | ? | ? | ? | ? | ? | ? | ? | ? | ? |
здесь ключевые клетки – две стенки (слева и снизу) и три ярко-зеленых клетки, которые должны быть свободны
2) теперь ищем на карте участки, где есть все ключевые клетки (они выделены на рисунке):
обратите внимание, что в двух случаях нижняя «ключевая» стенка имеет длину больше 1 (темно-коричневый цвет), то есть Робот может спускаться по разным линиям.
3) теперь осталось подсчитать все клетки, спускаясь из которых Робот упирается в темно-коричневые стенки:
&nb
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют... Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы... Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями... Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится... © cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста. |