Алгоритмы, виды алгоритмов, описания алгоритмов. Формальное исполнение алгоритма.
Выберите действие:
Соответствующие задания демо-версии 2009 года: А12, А18, В5, В8,C3.
План занятия:
1. Повторение теоретического материала по теме "Алгоритмы, виды алгоритмов, описания алгоритмов. Формальное исполнение алгоритма."
2. Решение примеров типичных задач этого раздела.
3. Разбор соответствующих заданий демо-версии ЕГЭ 2009 года.
Ход занятия:
При решении заданий этой темы необходимо, прежде всего, уяснить систему команд исполнителя алгоритма, т.е. как записывается каждая команда, что означают ее параметры (если они есть), и каков должен быть результат ее выполнения.
1. Повторение теоретического материала по теме "Алгоритмы, виды алгоритмов, описания алгоритмов. Формальное исполнение алгоритма."
Вопросы для повторения:
1. Сформулируйте понятие алгоритма.
2. Определите свойства алгоритмов.
3. Охарактеризуйте виды алгоритмов.
4. Какими способами можно записать алгоритм?
5. Кто или что является Исполнителем алгоритмов?
6. Что вы понимаете под Командой?
7. Что означают параметры Команды?
8. Дайте понятие Системы Команд Исполнителя.
2. Примеры решения типичных задач этого раздела.
Рассмотрим примеры решения типичных задач этого раздела.
Пример 1.
Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика: «Вперед N» (Кузнечик прыгает вперед на N единиц); «Назад М» (Кузнечик прыгает назад на М единиц). Переменные М и N могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 40 команд, в которой команд «Назад 2» на 10 больше, чем команд «Вперед 3». Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?
Решение. Если всего команд 40, то команд «Назад 2» было 25, а «Вперед 3» всего 15. кузнечик прыгнул вперед на 15*3=45 шагов, а назад на 25*2=50 шагов. Тем самым, он оказался на 5 шагов назад от первоначальной точки. Последовательность команд в алгоритме в данном случае не имеет значения.
Ответ: Назад 5.
Пример 2.
Исполнитель Черепашка перемещается на экране компьютера, оставляя след в виде линии. В каждый конкретный момент известно положение исполнителя и направление его движения. У исполнителя существуют две команды:
Впередn, где n – целое число, вызывающая передвижение Черепашки на n шагов в направлении движения.
Направоm, где m - целое число, вызывающая изменение направления движения на m градусов по часовой стрелке.
Запись Повтори 4 [Команда 1 Команда 2] означает, что последовательность команд в скобках повторится 4 раза.
Черепашке был дан для исполнения следующий алгоритм:
Повтори 4[Вперед 10 Направо 120]
Какая фигура появится на экране?
1) Незамкнутая ломаная линия
2) Правильный треугольник
3) Квадрат
4) Правильный пятиугольник
Решение:
Черепашка прочертит на экране 4 линии, но последний отрезок полностью совпадет с первым, так как после третьего выполнения цикла Черепашка полностью обернется вокруг своей оси и окажется в той же точке, что и изначально. Так что на экране появится правильный треугольник.
Ответ: 3.
Пример 3.
Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо), 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу
3233241.
Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?
Решение:
Начертим траекторию, по которой двигался Робот. Обозначим буквой А – начальную точку его движения, В – конечную. Из рисунка видно, что возвращение из точки В в точку А можно осуществить по программе из трех команд: влево-вверх-влево, т.е. 414.
А ---->
|
v
---->
В ---->
|
V
^
|
<---
Ответ: 414.
Пример 4.
В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные a,b,c имеют тип «строка», а переменные, k – тип «целое». Используются следующие функции:
Длина (а) – возвращает количество символов в строке а. (Тип «целое»)
Извлечь (а, i) - возвращает i-тый (слева) символ в строке а. (Тип «строка»)
Склеить (а, в) – возвращает строку, в которой записаны сначала все символы строки а, а затем все символы строки в. (Тип «строка»)
Значения строк записываются в одинарных кавычках.
(Например, а:=’дом’).
Фрагмент алгоритма:
i:= Длина (а)
k:=1
b:=’П’
пока i >0
нц
c:= Извлечь (a,i)
b:= Склеить (b,c)
i:=i-k
кц
Какое значение будет у переменной b после выполнения вышеприведенного фрагмента алгоритма, если значение переменной a было ‘РОЗА’?
1) ‘ПАЗ’ 2) ‘ПАЗОР’ 3) ‘ПОЗА’ 4) ‘ПРОЗА’
Решение:
В данном случае для решения задачи достаточно знания обычного Алгоритмического языка и описания функций, приведенного в условии. Выполним программу по шагам, занося значения переменных в таблицу:
Выполняемый оператор
a
b
c
i
k
‘РОЗА’
Не определено
Не определено
Не определено
Не определено
i:= Длина (а)
‘РОЗА’
Не определено
Не определено
4
Не определено
k:=1
‘РОЗА’
Не определено
Не определено
4
1
b:=’П’
‘РОЗА’
’П’
Не определено
4
1
c:= Извлечь (a,i)
‘РОЗА’
’П’
‘A’
4
1
b:= Склеить (b,c)
‘РОЗА’
‘ПА’
‘A’
4
1
i:=i-k
‘РОЗА’
‘ПА’
‘A’
3
1
c:= Извлечь (a,i)
‘РОЗА’
‘ПА’
‘З’
3
1
b:= Склеить (b,c)
‘РОЗА’
‘ПАЗ’
‘З’
3
1
i:=i-k
‘РОЗА’
‘ПАЗ’
‘З’
2
1
c:= Извлечь (a,i)
‘РОЗА’
‘ПАЗ’
‘O’
2
1
b:= Склеить (b,c)
‘РОЗА’
‘ПАЗО’
‘O’
2
1
i:=i-k
‘РОЗА’
‘ПАЗО’
‘O’
1
1
c:= Извлечь (a,i)
‘РОЗА’
‘ПАЗО’
‘P’
1
1
b:= Склеить (b,c)
‘РОЗА’
‘ПАЗОР’
‘P’
1
1
i:=i-k
‘РОЗА’
‘ПАЗОР’
‘P’
0
1
Ответ: 2.
Пример 5.
Записано 6 строк, каждая имеет свой номер – от 0 до 5.
В нулевой строке записана цифра 0 (ноль).
Каждая последующая строка состоит из двух повторений предыдущей и добавленного в конец своего номера (в i-той строке в конце приписана цифра i). Ниже показаны первые четыре строки, сформированные по описанному правилу (в скобках записан номер строки):
(0) 0
(1) 001
(2) 0010012
(3) 001001200123
Какая цифра стоит в последней строке на 62-м месте (считая слева направо)?
Решение:
Найдем длину последней строки. По условию, длина каждой последующей строки увеличивается в 2 раза, по сравнению с предыдущей, плюс еще один символ – цифра, обозначающая порядковый номер самой строки.
Получается, что длина строк составит:
(0) 1 элемент в строке;
(1) 1*2+1=3 элемента в строке;
(2) 3*2+1=7;
(3) 7*2+1=15 элементов в строке;
(4) 15*2+1=31;
(5) 31*2+1=63 элемента в строке.
Требуется найти 62-й элемент в строке длиной в 63 символов. Это означает, что нам нужен второй элемент с конца, предпоследний в строке.
Последний символ в последней строке, это ее номер – 5.
Предпоследний элемент строки – это последняя цифра в предыдущей строке (по правилу формирования строк). А окончание предыдущей строки – это ее номер, т.е. цифра 4.
Ответ: 4.
Пример 6.
Цепочка из трех бусин формируется по следующему правилу:
На первом месте в цепочке стоит одна из бусин А, Б, В. На втором – одна из бусин Б, В, Г. На третьем месте – одна из бусин А, В, Г, не стоящая в цепочке на первом или втором месте.
Какая из следующих цепочек создана по этому правилу:
1) АГБ 2) ВАГ 3) БГГ 4) ББГ
Решение:
Полное решение.
На первом месте в цепочке стоит одна из бусин А, Б, В.
После выполнения второго условия остаются варианты:
АБ, АВ, АГ,
ББ, БВ, БГ,
ВБ, ВВ, ВГ.
На третьем шаге складываются цепочки:
АБВ, АБГ, АВГ, АГВ,
ББА, ББВ, ББГ, БВА, БВГ, БГА, БГВ,
ВБА, ВБГ, ВВА, ВВГ, ВГА.
Итого, 16 цепочек, из четырех предложенных подходит только «ББГ».
Краткое решение.
В цепочке «АГБ» нарушено правило третьей бусины.
В цепочке «ВАГ» нарушено правило второй бусины.
В цепочке «БГГ» нарушено правило третьей бусины.
В цепочке «ББГ» все правила соблюдаются.
Ответ: 4.
Пример7.
Два игрока играют в следующую игру.
Имеются три кучи камней, содержащих соответственно 2,3,4 камня. За один ход разрешается или удвоить количество камней в какой-нибудь куче, или добавить по два камня в каждую из трех куч. Предполагается, что у каждого игрока имеется неограниченный запас камней.
Выиграет тот игрок, после чьего хода в какой-нибудь куче становится > 15 камней или во всех трех кучах суммарно становится > 25 камней.
Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре, - первый или второй игрок.
Решение:
Для решения задачи составим таблицу (дерево развития игры при различных продолжениях); в колонке 0 показано начальное состояние игры (вершина дерева игры), в колонке 1 показаны 4 возможных состояния игры после 1-го хода 1-го игрока, в колонке 2 – 16 возможных состояний игры после 1-го хода 2-го игрока, далее дерево игры не ведется, а проводится анализ уже рассчитанных состояний игры.
0
1
2
3
4
2,3,4
4,3,4
8,3,4
4,6,4
4,3,8
6,5,6
Проигрыш 1 игрока при любом продолжении
2,6,4
4,6,4
2,12,4
2,6,8
4,8,6
Проигрыш 1 игрока при любом продолжении
2,3,8
Проигрыш 1 игрока (при ходе 2 игрока 2,3,16)
4,5,6
8,5,6
4,10,6
4,5,12
6,7,8
Выигрыш 1 игрока (при ходе 16,5,6)
Выигрыш 1 игрока (при ходе 4,20,6)
Выигрыш 1 игрока (при ходе 4,5,24)
Выигрыш 1 игрока (при ходе 6,7,16)
Если 1-й игрок сделает свой первый ход 2,3,4-->4, 3,4, то второй игрок при правильной игре сделает ход 4,3,4-->4,6,4, что приводит к проигрышу 1-го игрока (т.к. из состояния (4,6,4) 1-й игрок может своим ходом перевести игру в одно из четырех состояний – (8,6,4), (4,12,4), (4,6,8), (6,8,6), и для любого из этих состояний найдется ход второго игрока, дающий ему выигрыш, например, по критерию S25).
Если 1-й игрок сделает свой первый ход 2,3,4-->2, 6,4, то второй игрок при правильной игре сделает ход 2,6,4-->4,6,4, что, как мы только видели, приводит к выигрышу 2-го игрока.
Если 1-й игрок сделает свой первый ход 2,3,4-->2, 3,8, то его проигрыш очевиден, т.к. 2-й игрок, как указано в таблице, добьется выигрывающего состояния игры 2,3,16.
Наконец, если 1-й игрок сделает свой первый ход 2,3,4-->4, 5,6, то он выигрывает игру, т.к. на любой из четырех возможных ответов 2-го игрока 9см. таблицу) есть выигрывающий ход 1-го игрока.
Таким образом, окончательный ответ к данной задаче:
При правильной игре выигрывает 1-й игрок (при этом его первый ход должен быть 2,3,4-->4, 5,6).
(Можно предложить учащимся выполнить эти задания самостоятельно или в качестве домашнего задания с последующим разбором на занятии)
A12. Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу.
В конце цепочки стоит одна из бусин A, B, C.
На первом месте – одна из бусин B, D, C, которой нет на третьем месте.
В середине – одна из бусин А, C, E, B, не стоящая на первом месте.
Какая из перечисленных цепочек создана по этому правилу?
1) CBB
2) EAC
3) BCD
4) BCB
Решение:
Проанализируем представленные данные:
1) Поскольку в конце цепочки стоят бусины A, B, C, вариант ответа 3) исключается из рассмотрения. По второму условию на первом месте должны быть бусины B, D, C. К этому условию не подходит вариант 2). Проверяем последнее условие (в середине – одна из бусин А, C, E, B, не стоящая на первом месте) – не подходит 4) вариант.
Правильный ответ – 1.
А18. Система команд исполнителя РОБОТ, "живущего" в прямоугольном лабиринте на клетчатой плоскости
вверх
вниз
влево
вправо
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх, вниз, влево, вправо.
Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
сверху свободно
снизу свободно
слева свободно
справа свободно
Цикл ПОКА < условие > команда
выполняется, пока условие истинно, иначе происходит переход на следующую строку.
Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?
НАЧАЛО
ПОКА < снизу свободно > вниз
ПОКА < слева свободно > влево
ПОКА < сверху свободно > вверх
ПОКА < справа свободно > вправо
КОНЕЦ
1) 1 2) 2 3) 3 4) 0
Решение:
Проходить для каждой клетки все циклы приведенной программы бессмысленно. В данном случае, очевидно, что для того, чтобы РОБОТ вернулся в исходное состояние, необходимо, чтобы:
он не имел возможности первоначально двигаться вниз; имел возможность двигаться влево до стены;
не имел возможности двигаться вверх;
имел возможность двигаться вправо до стены.
Проанализировав структуру рисунка, приходим к выводу, что такая клетка есть только одна в верхнем ряду F6.
Правильный ответ – 1.
B5. У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 3 и 2. умножь на 4
Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а, выполняя вторую, умножает его на 4. Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд. (Например, программа 21211 это программа
умножь на 4
прибавь 3
умножь на 4
прибавь 3
прибавь 3 которая преобразует число 2 в 50.)
Решение:
Можно рассуждать от обратного, получая кратчайший результат. При этом команда прибавь 3 меняется на обратную ей вычти 3, а команда умножь на 4 меняется на раздели на 4.
1) 57 – 3 = 54 2) 54 – 3 = 51 3) 51 – 3 = 48
4) 48 : 4 = 12 5) 12 : 4 = 3
А теперь восстановим прямой порядок действий:
1) умножь на 4 2) умножь на 4 3) прибавь 3
4) прибавь 3 5) прибавь 3
Правильный ответ – 22111.
B8. Строки (цепочки символов латинских букв) создаются по следующему правилу. Первая строка состоит из одного символа – латинской буквы «А». Каждая из последующих цепочек создается такими действиями: в очередную строку сначала записывается буква, чей порядковый номер в алфавите соответствует номеру строки (на i-м шаге пишется «i»-я буква алфавита), к ней справа дважды подряд приписывается предыдущая строка.
Вот первые 4 строки, созданные по этому правилу:
(1) A
(2) BAA
(3) CBAABAA
(4) DCBAABAACBAABAA
Латинский алфавит (для справки):
ABCDEFGHIJKLMNOPQRSTUVWXYZ
Запишите семь символов подряд, стоящие в восьмой строке со 126-го по 132-е место (считая слева направо).
Видно, что все строки заканчиваются одними и теми же символами, начиная с 3-ей строки. Количество символов в получающихся строках находим по формуле: ki+1= ki * 2 +1. Получаем, что в 8-ой строке на 128 месте (H+7-ая строка) будет стоять последняя буква всех последовательностей (А). Значит, на первые три буквы искомой записи – BAA. Нужно записать 7 символов (с 126 по 132 буквы). Берем первые 4 буквы строки 7, так как она повторится дважды.
Правильный ответ –BAAGFED.
C3. Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
Решение:
Выигрывает второй игрок.
Для доказательства рассмотрим неполное дерево игры, из вариантов оформленное в виде таблицы, где в каждой ячейке записаны координаты фишки на каждом этапе игры. 1 ход 2 ход 3 ход 4 ход Стартовая позиция I-й игрок (все варианты хода) II-й игрок (выигрышный ход) I-й игрок (все варианты хода) II-й игрок (выигрышный ход, один
