Динамическое программирование

• Название: Динамическое программирование
• Дата: 21.11.2022
• Размер: 0.94 Mb.
• Имя файла: ege23 (2).doc
• Тип: Решение; #803927
• страница: 12 из 13

2. Прибавь 3

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 1 в число 14 и при этом не содержат двух команд умножения подряд?

166. 
     Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
     

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 2 в число 20 и при этом не содержат двух команд «Прибавить 3» подряд?

167. 
     Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
     

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 3 в число 30 и при этом не содержат двух команд «Прибавить 1» подряд?

168. 
     (М. Фирсов) Исполнитель Счеты преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
     

1. Прибавь 4

2. Прибавь 7

3. Раздели нацело на 2

Первая команда увеличивает число на экране на 4, вторая увеличивает его на 7, третья делит на 2 нацело (остаток отбрасывается). Программа для исполнителя – это последовательность команд. Сколько существует программ, которые состоят из 10 команд и при исходном числе 1 результатом является 1?

169. 
     (М. Фирсов) Исполнитель Счеты преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
     

1. Прибавь 3

2. Вычти 1

Первая команда увеличивает число на экране на 3, вторая уменьшает его на 1 Программа для исполнителя – это последовательность команд. Будем называть циклической программу, при выполнении которой исполнитель на каком-то этапе вновь получает начальное число и далее псоледовательность команд повторяется. Например, циклической является программа следующих преобразований: 1  4  3  2  1  4. Сколько существует циклических программ, состоящих из 9 команд?

170. 
     (А. Сапегин) Исполнитель Ландыш преобразует пару чисел, записанную на экране. У исполнителя Ландыш есть четыре команды:
     

1. Прибавь к первому числу 3

2. Умножь первое число на 4

3. Прибавь ко второму числу 5

4. Умножь второе число на 2

Первая из них увеличивает первое число из пары на 2, вторая – умножает его на 4. Третья команда увеличивает второе число из пары на 5, четвертая – умножает его на 2. Сколько различных пар взаимно простых чисел можно получить из пары чисел (2, 3) с помощью программы, которая состоит ровно из 5 команд? Пары, отличающиеся только перестановкой чисел, считать одинаковыми.

171. 
     (А. Бычков) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
     

1. Прибавь 1

2. Прибавь 2

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 3 в число 79, и при этом траектория вычислений содержит число 11 и не содержит число 23. Также программа не должна содержать двух команд «Прибавь 1» подряд.

172. 
     Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
     

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 4 в число 93, и при этом траектория вычислений содержит число 10 и не содержит число 28. Также программа не должна содержать двух команд «Прибавь 1» подряд.

173. 
     Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
     

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 2 в число 51, и при этом траектория вычислений содержит число 18 и не содержит число 33. Также программа не должна содержать двух команд «Умножь на 2» подряд.

174. 
     Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
     

1. Прибавь 1

2. Прибавь 3

3. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3, третья – умножает на 2. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 3 в число 60, и при этом траектория вычислений содержит число 20 и не содержит чисел 30 и 40. Также программа не должна содержать двух команд «Умножь на 2» подряд.

175. 
     Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
     

1. Прибавь 1

2. Прибавь 2

3. Умножь на 3

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья – умножает на 3. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 1 в число 43, и при этом траектория вычислений содержит число 15 и не содержит чисел 25 и 30. Также программа не должна содержать двух команд «Умножь на 3» подряд.

176. 
     Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
     

1. Прибавь 1

2. Прибавь 2

3. Умножь на 3

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья – умножает на 3. Программа для исполнителя – это последовательность команд. Сколько существует программ, которые преобразуют исходное число 2 в число 38, и при этом траектория вычислений содержит числа 15 и 30, а также не содержит чисел 12 и 20. Также программа не должна содержать двух команд «Умножь на 3» подряд.

177. 
     (А. Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:
     

1. Вычесть 2

2. Вычесть 3

3. Извлечь корень

Первые две команды уменьшают число на доске на 2 и 3 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 25 в число 3?

178. 
     (А. Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:
     

1. Вычесть 3

2. Вычесть 4

3. Извлечь корень

Первые две команды уменьшают число на доске на 3 и 4 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 36 в число 3 и содержат в траектории число 21?

179. 
     (А. Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:
     

1. Вычесть 2

2. Вычесть 4

3. Извлечь корень

Первые две команды уменьшают число на доске на 2 и 3 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 46 в число 2 и содержат в траектории числа 32 и 12?

180. 
     (А. Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:
     

1. Вычесть 1

2. Вычесть 2

3. Извлечь корень

Первые две команды уменьшают число на доске на 1 и 2 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 27 в число 6, содержат в траектории число 18, но не содержит число 20?

181. 
     (А. Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:
     

1. Вычесть 1

2. Вычесть 2

3. Извлечь корень

Первые две команды уменьшают число на доске на 1 и 2 соответственно, третья команда — извлекает из числа квадратный корень, если число является квадратом любого числа. Программа для такого исполнителя — это последовательность команд. Сколько различных результатов можно получить из исходного числа 113 в ходе исполнения программы, содержащей ровно 17 команд?

182. 
     (А. Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:
     

1. Прибавь 2

2. Сделай чётное

3. Сделай нечётное

Первая команда увеличивает число на 2, вторая команда преобразует число N в число 2N при условии, что оно является нечетным. Третья — преобразует четное число N в нечетное вида 2N+1. Сколько существует программ, которые преобразуют исходное число 2 в 35, а траектория вычислений программы содержит не более двух преобразований в нечетное?

183. 
     (А. Брейк) Непоседливый Непоседа решил сыграть в игру. Он придумал исполнителя, преобразующего числа на доске и имеющего три команды:
     

1. Прибавь 3

2. Сделай чётное

3. Сделай нечётное

Первая команда увеличивает число на 3, вторая команда преобразует число N в число 2N при условии, что оно является нечетным. Третья — преобразует четное число N в нечетное вида 2N+1. Сколько существует программ, которые преобразуют исходное число 1 в 76, а траектория вычислений программы содержит не более пяти преобразований в чётное?

184. 
     (А. Брейк) Исполнитель Великий Отрицатель преобразует число, записанное на доске. У Великого Отрицателя есть две команды:
     

1. Вычесть 3

2. Умножить на -3

Первая команда уменьшает число на 3, вторая команда умножает его на –3. Сколько различных положительных результатов можно получить из исходного числа 133 в ходе исполнения программы, содержащей ровно 9 команд?

185. 
     (А. Брейк) Исполнитель Великий Отрицатель преобразует число, записанное на доске. У Великого Отрицателя есть две команды:
     

1. Вычесть 2

2. Умножить на -3

Первая команда уменьшает число на 2, вторая команда умножает его на –3. Сколько различных отрицательных результатов можно получить из исходного числа 91 в ходе исполнения программы, содержащей ровно 11 команд?

186. 
     (А. Брейк) Исполнитель Великий Отрицатель преобразует число, записанное на доске. У Великого Отрицателя есть две команды:
     

1. Вычесть 5

2. Умножить на -2

Первая команда уменьшает число на 5, вторая команда умножает его на –2. Сколько различных неотрицательных результатов можно получить из исходного числа 216 в ходе исполнения программы, содержащей ровно 7 команд?

187. 
     (А. Брейк) Лягушке нужно добраться до укрытия, избегая опасностей. У Лягушки есть три действия:
     

1. Короткий прыжок +2

2. Длинный прыжок +3

3. Избежать опасности 2n

Первые два действия увеличивают позицию Лягушки на 2 и 3 соответственно. Третье действие можно применить только тогда, когда Лягушка находится в нечетной позиции — позиция N преобразуется в позицию 2N, позволяя Лягушке избежать опасности. Лягушка была замечена на расстоянии 3. Сколько существует различных путей Лягушки к укрытию в позиции 46, каждый их которых содержит не более двух действий «Избежать опасности»?

188. 
     (А. Брейк) Лягушке нужно добраться до укрытия, избегая опасностей. У Лягушки есть три действия:
     

1. Короткий прыжок +1

2. Длинный прыжок +2

3. Избежать опасности 2n

Первые два действия увеличивают позицию Лягушки на 1 и 2 соответственно. Третье действие применяет тогда, когда Лягушка находится в нечетной позиции — позиция N преобразуется в позицию 2N, позволяя Лягушке избежать опасности. Другие действия в нечетных позициях не могут быть выполнены. Лягушка была замечена на расстоянии 2. Сколько существует различных путей Лягушки к укрытию в позиции 76, каждый их которых содержит позиции 20 и 38?

189. 
     (Е. Джобс) Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
     

1. Прибавь 2

2. Вычти 3

Первая команда увеличивает число на экране на 2, вторая уменьшает на 3. При выходе за пределы отрезка [–40; 40] исполнитель аварийно завершает свою работу. Программа для исполнителя – это последовательность команд. Сколько существует таких программ, которые исходное число 1 преобразуют в число 30 и при этом траектория вычислений не содержит одинаковых чисел?

190. 
     Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
     

1. Прибавь 1

2. Припиши 1

Первая команда увеличивает число на экране на 1, вторая приписывает 1 в конец десятичной записи числа. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 212 последовательно преобразует его в 11, 12, 121. Сколько существует различных программ, которые преобразуют исходное число 1 в число 555?

191. 
     Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
     

1. Прибавь 2

2. Припиши 2

Первая команда увеличивает число на экране на 2, вторая приписывает 2 в конец десятичной записи числа. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 212 последовательно преобразует его в 12, 14, 142. Сколько существует различных программ, которые преобразуют исходное число 2 в число 900?

192. 
     Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
     

1. Прибавь 1

2. Припиши 3

Первая команда увеличивает число на экране на 1, вторая приписывает 1 в конец десятичной записи числа. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 212 последовательно преобразует его в 13, 14, 143. Сколько существует различных программ, которые преобразуют исходное число 3 в число 462?

193. 
     Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
     

1. Прибавь 1

2. Припиши 1

Первая команда увеличивает число на экране на 1, вторая приписывает 1 в начало десятичной записи числа. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 1, то программа 212 последовательно преобразует его в 11, 12, 112. Сколько существует различных программ, которые преобразуют исходное число 1 в число 512?

194. 
     Исполнитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
     

1. Прибавь 1

2. Припиши 2

Первая команда увеличивает число на экране на 1, вторая приписывает 2 в начало десятичной записи числа. Программа для исполнителя – это последовательность команд. Например, если в начальный момент на экране находится число 3, то программа 212 последовательно преобразует его в 23, 24, 224. Сколько существует различных программ, которые преобразуют исходное число 3 в число 678?

195. 
     Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: