Исполнители. Динамическое программирование (Задачи №6, №14, №15, №22)
Задачи №6 ЕГЭ
1. У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 2,
2. умножь на 5.
Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, умножает его на 5. Запишите порядок команд в программе, которая преобразует число 1 в число 29 и содержит не более 4 команд. Указывайте лишь номера команд.
2. Некоторый исполнитель может выполнить только 2 команды:
1. К числу прибавить 1
2. Число умножить на 2
Запишите порядок команд в программе получения из числа 17 числа 729, содержащей не более 13 команд, указывая лишь номера команд.
3. Вася забыл пароль к Windows XP, но помнил алгоритм его получения из строки подсказки «B265C42GC4»: если все последовательности символов «C4» заменить на «F16», а затем из получившейся строки удалить все трехзначные числа, то полученная последовательность и будет паролем. Определите пароль.
4. Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.
1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).
Пример. Исходное число: 3165. Суммы: 3 + 1 = 4; 6 + 5 = 11. Результат: 114.
Укажите наименьшее число, в результате обработки которого, автомат выдаст число 1311.
5. Автомат получает на вход трёхзначное число. По этому числу строится новое число по правилам.
1. Складываются первая и вторая, а также вторая и третья цифры исходного числа.
2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).
Пример. Исходное число: 843. Суммы: 8 + 4 = 12; 4 + 3 = 7. Результат: 712.
Сколько существует чисел, в результате обработки которых автомат выдаст число 1216?
6. Иван пригласил своего друга Сашу в гости, но не сказал ему код от цифрового замка своего подъезда, а послал следующее сообщение: «Исходная последовательность: 8, 1, 6, 2, 4. Сначала все числа меньше 5 увеличить на 1. Потом все чётные больше 5 разделить на 2. Затем удалить из полученной последовательности все нечётные цифры». Выполнив действия, указанные в сообщении, какой код Саша получил для цифрового замка?
7. В некоторой информационной системе информация кодируется двоичными шестиразрядными словами. При передаче данных возможны их искажения, поэтому в конец каждого слова добавляется седьмой (контрольный) разряд таким образом, чтобы сумма разрядов нового слова, считая контрольный, была чётной. Например, к слову 110011 справа будет добавлен 0, а к слову 101100 — 1.
После приёма слова производится его обработка. При этом проверяется сумма его разрядов, включая контрольный. Если она нечётна, это означает, что при передаче этого слова произошёл сбой, и оно автоматически заменяется на зарезервированное слово 0000000. Если она чётна, это означает, что сбоя не было или сбоев было больше одного. В этом случае принятое слово не изменяется. Исходное сообщение 1011100 0000011 0001010 было принято в виде 1011110 0000011 0001001. Как будет выглядеть принятое сообщение после обработки?
8. Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 6 (если в числе есть цифра больше 6, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам.
Вычисляются два шестнадцатеричных числа – сумма старших разрядов заданных чисел и сумма младших разрядов этих чисел.
Полученные два шестнадцатеричных числа записываются друг за другом в порядке возрастания (без разделителей).
Пример. Исходные числа: 66, 43. Поразрядные суммы: A, 9. Результат: 9A. Определите, какое из предложенных чисел может быть результатом работы автомата:
1) AF 2) 410 3) 8B 4) 76
9. Автомат получает на вход четырёхзначное число. По этому числу строится новое число по следующим правилам.
1. Складываются первая и вторая, а также третья и четвёртая цифры исходного числа.
2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).
Пример. Исходное число: 3165. Суммы: 3 + 1 = 4; 6 + 5 = 11. Результат: 411.
Укажите минимальное число, в результате обработки которого, автомат выдаст число 79.
10. Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.
1. Складываются первая и вторая, а также вторая и третья цифры исходного числа.
2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей).
Пример. Исходное число: 348. Суммы: 3 + 4 = 7; 4 + 8 = 12. Результат: 127.
Укажите наименьшее число, в результате обработки которого автомат выдаст число 157.
11. Автомат получает на вход два трехзначных числа. По этим числам строится новое число по следующим правилам. Вычисляются три числа – сумма старших разрядов заданных трехзначных чисел, сумма средних разрядов этих чисел, сумма младших разрядов. Полученные три числа записываются друг за другом в порядке невозрастания (без разделителей).
Пример. Исходные трехзначные числа: 835, 196. Поразрядные суммы: 9, 12, 11. Результат: 12119
Какое наименьшее значение может иметь одно из чисел, полученных на входе, если другое число равно 694, а в результате работы автомата получено число 11108?
12. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) в конец числа (справа) дописывается 1, если число единиц в двоичной записи числа чётно, и 0, если число единиц в двоичной записи числа нечётно.
б) к этой записи справа дописывается остаток от деления количества единиц на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает 31 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
13. На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописывается справа бит чётности: 0, если в двоичном коде числа N было чётное число единиц, и 1, если нечётное.
3) К полученному результату дописывается ещё один бит чётности.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число, большее, чем 103. В ответе это число запишите в десятичной системе.
14. У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера:
1. сдвинь влево
2. вычти 1
Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 91 и выполнил цепочку команд 112112. Запишите результат в десятичной системе.
15. Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика:
Вперед N – Кузнечик прыгает вперед на N единиц
Назад M – Кузнечик прыгает назад на M единиц
Переменные N и M могут принимать любые целые положительные значения. Кузнечик выполнил программу из 20 команд, в которой команд «Назад 4» на 4 меньше, чем команд «Вперед 3» (других команд в программе нет). На какую одну команду можно заменить эту программу?
У исполнителя Аккорд две команды, которым присвоены номера:
вычти x
умножь на 3
где x – неизвестное положительное число. Выполняя первую из них, Аккорд вычитает из числа на экране x, а выполняя вторую, умножает это число на 3.
Программа для исполнителя Аккорд – это последовательность номеров команд.
Известно, что программа 12211 переводит число 12 в число 53. Определите значение x.
Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 15. Система команд Кузнечика:
Вперед 17 – Кузнечик прыгает вперёд на 17 единиц,
Назад 6 – Кузнечик прыгает назад на 6 единиц.
Какое наименьшее количество раз должна встретиться в программе команда «Назад 6», чтобы Кузнечик оказался в точке 36?
Задачи №14 ЕГЭ
18. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, состоит из 8 команд. Четыре команды — это команды-приказы:
вверх | вниз | влево | вправо |
сверху свободно | снизу свободно | слева свободно | справа свободно |
Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?
НАЧАЛО
ПОКА снизу свободно ИЛИ справа свободно
ЕСЛИ снизу свободно
ТО вниз
ИНАЧЕ вправо
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
19. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия.
Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F1)?
НАЧАЛО
ПОКА справа свободно ИЛИ сверху свободно
ЕСЛИ справа свободно
ТО вправо
ИНАЧЕ вверх
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
20. Исполнитель Редактор получает на вход строку цифр и преобразует её.
Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 125 идущих подряд цифр «8»? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (333) ИЛИ нашлось (888)
ЕСЛИ нашлось (333)
ТО заменить (333, 8)
ИНАЧЕ заменить (888, 3)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
заменить (v, w)
нашлось (v)
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (9999) ИЛИ нашлось (333)
ЕСЛИ нашлось (9999)
ТО заменить (9999, 3)
ИНАЧЕ заменить (333, 99)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 207 идущих подряд цифр 3? В ответе запишите полученную строку.
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
заменить (v, w)
нашлось (v)
Дана программа для исполнителя Редактор:
НАЧАЛО
ПОКА нашлось (222) ИЛИ нашлось (888)
ПОКА нашлось (555)
заменить (555, 8)
КОНЕЦ ПОКА
ЕСЛИ нашлось (222)
ТО заменить (222, 8)
ИНАЧЕ заменить (888, 2)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Дана строка, состоящая из 21 цифры, причем первые три цифры – двойки, а остальные – пятерки. Какая строка получится в результате применения программы к данной строке?
23. Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b — целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, −3) переместит Чертёжника в точку (6, −1).
Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и смещения в первой из повторяемых команд неизвестны):
НАЧАЛО
сместиться на (5, 2)
ПОВТОРИ … РАЗ
сместиться на (…, …)
сместиться на (−1, −2)
КОНЕЦ ПОВТОРИ
сместиться на (−25, −12)
КОНЕЦ
После выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ … РАЗ»?.
24. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости. Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ остановится в той же клетке, с которой он начал движение?
НАЧАЛО
ПОКА вниз
ПОКА вправо
ПОКА вверх
ПОКА влево
КОНЕЦ
25. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости. Сколько клеток приведенного лабиринта соответствует требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?
НАЧАЛО
ПОКА вниз
ПОКА вправо
ПОКА вверх
ПОКА влево
КОНЕЦ
26. Чертёжник находился в начале координат. Ему был дан для исполнения следующий алгоритм:
Сместиться на (-7,–1)
Повтори N раз
Сместиться на (15, 22)
Сместиться на (a, b)
конец
Сместиться на (23, –32)
Найдите наибольшее число повторений N в конструкции «Повтори … раз», при котором значения a и b можно выбрать так, что после выполнения алгоритм Чертёжник окажется в точке (1; –3).
Чертежник находился в начале координат. Ему был дан для исполнения следующий алгоритм:
Сместиться на (-3,–5)
Повтори N раза
Сместиться на (2, b)
Сместиться на (8, –12)
конец
Сместиться на (2, 3)
Найдите целое значение b, для которого после выполнения программы Чертёжник окажется в точке (59; 46).
Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a, b) (где a, b – целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Чертёжнику был дан для исполнения следующий алгоритм:
Сместиться на (-3, 4)
Повтори N раз
Сместиться на (a, b)
Сместиться на (12, 5)
конец
Сместиться на (-9, 32)
Сколько существует натуральных значений N, для которых найдутся такие значения чисел a и b, что после выполнения программы Чертёжник возвратится в исходную точку?
Задачи №15 ЕГЭ
29. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Т?
30. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г?
31. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город Л и проходящих через город Ж, но НЕ проходящих через город Д?
32. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город Л и проходящих через участок дороги, который связывает город Д и Ж напрямую?
33. На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город Г?
Задачи №22 ЕГЭ
34. У исполнителя Кузнечик две команды:
прибавь 7
вычти 5
Первая из них увеличивает число на экране на 7, вторая – уменьшает его на 5 (отрицательные числа допускаются). Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 7 команд?
35. У исполнителя Прибавитель две команды, которым присвоены номера:
1. прибавь 1,
2. увеличь старшую цифру числа на 1.
Первая из них увеличивает число на экране на 1, вторая увеличивает на 1 старшую (левую) цифру числа, например число 23 с помощью такой команды превратится в число 33. Если старшая цифра числа равна 9, то вторая команда оставляет это число неизменным. Сколько есть программ, которые число 35 преобразуют в число 57?
36. Исполнитель Май16 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2. Программа для исполнителя Май16 — это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 14 и при этом траектория вычислений содержит число 7, но не содержит числа 9? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 10, 11.
37. Исполнитель Июнь15 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Умножить на 3
Сколько существует программ, для которых при исходном числе 2 результатом является число 28 и при этом траектория вычислений содержит число 7?
38. Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Сколько существует программ, для которых при исходном числе 2 результатом является число 34 и при этом траектория вычислений содержит число 10 и не содержит число 28?
39. Исполнитель Калькулятор преобразует целое число, записанное на экране. У исполнителя две команды, каждой команде присвоен номер:
1. Прибавь 1
2. Умножь на 2
Первая команда увеличивает число на экране на 1, вторая увеличивает это число в 2 раза. Сколько существует программ, которые число 3 преобразуют в число 20 и в которых предпоследняя команда 1?
40. Исполнитель Калькулятор преобразует целое число, записанное на экране. У исполнителя две команды, каждой команде присвоен номер:
1. Прибавь 1
2. Прибавь 2
Первая команда увеличивает число на экране на 1, вторая увеличивает – на 2. Сколько существует программ, которые число 3 преобразуют в число 18 и в которых предпоследняя команда 2?
Исполнитель А23S преобразует целое число, записанное на экране. У исполнителя три команды, каждой команде присвоен номер:
1. Прибавь 2
2. Прибавь 3
3. Прибавь предыдущее
Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 3, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.). Программа для исполнителя А23S – это последовательность команд.
Сколько существует программ, которые число 2 преобразуют в число 11?
У исполнителя Калькулятор три команды, которым присвоены номера:
1. прибавь 1
2. сделай чётное
3. сделай нечётное
Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 16?
Ключ
1 | 2211 |
2 | 1111121212221 |
3 | BFGF16 |
4 | 2949 |
5 | 6 |
6 | 4, 2 |
7 | 0000000 0000011 0001001 |
8 | 3 |
9 | 1609 |
10 | 169 |
11 | 217 |
12 | 33 |
13 | 26 |
14 | 11 |
15 | Вперед4 |
16 | 5 |
17 | 5 |
18 | 16 |
19 | 23 |
20 | 388 |
21 | 33 |
22 | 228 |
23 | 10 |
24 | 3 |
25 | 3 |
26 | 15 |
27 | 20 |
28 | 6 |
29 | 33 |
30 | 24 |
31 | 9 |
32 | 9 |
33 | 42 |
34 | 8 |
35 | 20 |
36 | 65 |
37 | 52 |
38 | 21 |
39 | 17 |
40 | 377 |
41 | 17 |
42 | 40 |