Занятие 3.3 Количество программ (23)

1.

Подсчет количества программ

2.

Суть задания
• Это задача на комбинаторику и поиск путей для
автоматического Исполнителя.
• У Исполнителя есть набор простых команд (например,
«прибавь 1» или «умножь на 2»). Он преобразует
стартовое число в конечное.
• Необходимо вычислить точное количество всех
возможных программ (способов), которыми можно
добраться от старта до финиша, часто соблюдая
дополнительные условия (обязательно пройти через одно
число или избежать другое).

3.

Пример
• Задача
• Исполнитель преобразует число 4 в число 10.
• У него есть две команды:
• 1. +1 (прибавь 1)
• 2. *2 (умножь на 2)
• Сколько существует таких программ (путей)?

4.

Пример
• Задача
• Исполнитель преобразует число 4 в число 10.
• У него есть две команды:
• 1. +1 (прибавь 1)
• 2. *2 (умножь на 2)
• Сколько существует таких программ (путей)?
• 1) 4*2(8) -> 8+1(9) -> 9+1(10)
• 2) 4+1(5) -> 5*2(10)
• 3) 4+1(5) -> 5+1(6) -> 6+1(7) -> 7+1(8) -> 8+1(9) -> 9+1(10)

5.

Пример
• Задача
• Исполнитель преобразует число 4 в число 10.
• У него есть две команды:
• 1. +1 (прибавь 1)
• 2. *2 (умножь на 2)
• Сколько существует таких программ (путей)?
• R(4) = 1 R(8)=2
• R(5)= 1
R(9)=2
• R(6)=1
R(10)=3
• R(7)=1

6.

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

7.

Рекурсивное решение
• def f(x, end):
if x == end:
return 1
if x > end:
return 0
return f(x+2,end) + f(x*3,end)
• print(f(1,31)) #12

8.

Задача 2
• У исполнителя Арифметик две команды, которым
присвоены номера.
• 1. Прибавь 1.
• 2. Прибавь 3.
• Первая из них увеличивает на 1 число на экране, вторая
увеличивает это число на 3.
• Программа для Арифметика — это последовательность
команд.
• Сколько существует программ, которые число 2
преобразуют в число 15?

9.

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

10.

Задача 4
• У исполнителя три команды, которым присвоены номера.
• 1. Прибавь 1.
• 2. Сделай чётное.
• 3. Сделай нечётное.
• Первая из них увеличивает на 1 число x на экране, вторая
умножает это число на 2, третья переводит число x в число
2x + 1. Например, вторая команда переводит число 10 в
число 20, а третья переводит число 10 в число 21.
• Программа для исполнителя — это последовательность
команд. Сколько существует программ, которые число 2
преобразуют в число 16?

11.

Задача 5
• У исполнителя четыре команды, которым присвоены номера.
• 1. Прибавь 1.
• 2. Сделай чётное.
• 3. Сделай нечётное.
• 4. Умножь на 10.
• Первая из них увеличивает на 1 исходное число x, вторая умножает
это число на 2, третья переводит число x в число 2x + 1, четвёртая
умножает его на 10. Например, вторая команда переводит число 10 в
число 20, а третья переводит число 10 в число 21. Программа для
исполнителя — это последовательность команд.
• Сколько существует программ, которые число 1 преобразуют в число
15?

12.

Задача 6
• Исполнитель Увеличитель345 преобразует число, записанное на
экране. У исполнителя три команды, которым присвоены номера:
• 1. Прибавь 3.
• 2. Прибавь 4.
• 3. Прибавь 5.
• Первая из них увеличивает число на экране на 3, вторая увеличивает
это число на 4, а третья — на 5. Программа для исполнителя
Увеличитель345 — это последовательность команд.
• Сколько есть программ, которые число 22 преобразуют в число 42?

13.

Задача 7
• Исполнитель А22 преобразует целое число, записанное на экране.У
исполнителя три команды, каждой команде присвоен номер.
• 1. Прибавь 1.
• 2. Прибавь 3.
• 3. Прибавь предыдущее.
• Первая команда увеличивает число на экране на 1, вторая
увеличивает это число на 3, третья прибавляет к числу на экране
число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11
прибавляется 10 и так далее). Программа для исполнителя А22 — это
последовательность команд.
• Сколько существует программ, которые число 2 преобразуют в число
10?

14.

Задача 8
• Исполнитель Плюс преобразует число на экране.У исполнителя есть
две команды, которым присвоены номера.
• 1. Прибавить 2.
• 2. Прибавить 5.
• Первая команда увеличивает число на экране на 2, вторая
увеличивает это число на 5. Программа для исполнителя Плюс — это
последовательность команд.
• Сколько существует программ, которые число 1 преобразуют в число
20?

15.

Задача 9
• Исполнитель преобразует число, записанное на экране.У исполнителя
есть команды, которым присвоены номера.
• 1. Вычесть 2.
• 2. Вычесть 3.
• 3. Разделить нацело на 3.
• Первая команда уменьшает число на экране на 2, вторая — на 3,
третья уменьшает число в 3 раза. Сколько существует программ, для
которых при исходном числе 20 результатом является число 3?

16.

Задача 10
• Исполнитель Минус преобразует число на экране. У исполнителя есть
две команды, которым присвоены номера:
• 1. Вычесть 2.
• 2. Вычесть 5.
• Первая команда уменьшает число на экране на 2, вторая уменьшает
это число на 5. Программа для исполнителя Минус — это
последовательность команд. Сколько существует программ, которые
число 23 преобразуют в число 2?

17.

Ответы
• 2) 88
• 3) 38
• 4) 40
• 5) 84
• 6) 73
• 7) 39
• 8) 18
• 9) 76
• 10) 29

18.

Задачи с обязательным этапом
• В них траектория вычислений должна проходить через
определённое число (например, путь от 3 до 12 через 10).
• Принцип решения: Путь разбивается на два независимых
этапа:
• 1. От исходного числа до обязательного.
• 2. От обязательного числа до конечного.
• Количества программ на каждом этапе перемножаются.

19.

Пример
Исполнитель А16 преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера.
1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 2.
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья
умножает его на 2.
Программа для исполнителя А16 — это последовательность команд.
Сколько существует таких программ, которые исходное число 3 преобразуют в число 12 и при
этом траектория вычислений программы содержит число 10?
Траектория вычислений программы — это последовательность результатов выполнения всех
команд программы. Например, для программы 132 при исходном числе 7 траектория будет
состоять из чисел 8, 16, 18.

20.

Пример
• def f(curr, end):
if curr == end:
return 1
if curr > end:
return 0
return f(curr+1,end) + f(curr+2,end) + f(curr*2,end)
• print(f(3,10)*f(10,12)) # 60

21.

Задача 1
Исполнитель Май17 преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера.
1. Прибавить 1.
2. Прибавить 3.
Первая команда увеличивает число на экране на 1, вторая увеличивает
его на 3. Программа для исполнителя Май17 — это последовательность
команд.
Сколько существует программ, для которых при исходном числе 1
результатом является число 17 и при этом траектория вычислений
содержит число 9? Траектория вычислений программы — это
последовательность результатов выполнения всех команд программы.
Например, для программы 121 при исходном числе 7 траектория будет
состоять из чисел 8, 11, 12.

22.

Задача 2
Исполнитель Осень16 преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера.
1. Прибавить 1.
2. Прибавить 2.
3. Прибавить 4.
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья —
увеличивает на 4.
Программа для исполнителя Осень16 — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 15 и
при этом траектория вычислений содержит число 8?
Траектория вычислений программы — это последовательность результатов выполнения всех
команд программы. Например, для программы 121 при исходном числе 7 траектория будет
состоять из чисел 8, 10, 11.

23.

Задача 3
Исполнитель Тренер преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера.
1. Прибавить 1.
2. Умножить на 2.
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя Тренер — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 1 в
число 30 и при этом траектория вычислений содержит числа 10 и 21?
Траектория должна содержать оба указанных числа. Траектория
вычислений — это последовательность результатов выполнения всех команд
программы. Например, для программы 212 при исходном числе 7
траектория будет состоять из чисел 14, 15, 30.

24.

Задача 4
Исполнитель Вычислитель преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера.
1. Прибавить 2.
2. Умножить на 2.
3. Прибавить 3.
Первая команда увеличивает число на экране на 2, вторая умножает его на 2, третье увеличивает
его на 3.
Программа для исполнителя Вычислитель — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 2 в число 22 и при этом
траектория вычислений содержит число 11?
Траектория вычислений программы — это последовательность результатов выполнения всех
команд программы. Например, для программы 132 при исходном числе 7 траектория будет
состоять из чисел 9, 12, 24.

25.

Задача 5
Исполнитель РазДва преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера.
1. Прибавить 1.
2. Умножить на 2.
Первая команда увеличивает число на экране на 1, вторая умножает его
на 2.
Программа для исполнителя РазДва — это последовательность команд.
Сколько существует программ, для которых при исходном числе 3
результатом является число 37 и при этом траектория вычислений
содержит число 18?
Траектория вычислений — это последовательность результатов
выполнения всех команд программы. Например, для программы 122 при
исходном числе 4 траектория будет состоять из чисел 5, 10, 20.

26.

Задача 6
Исполнитель Вычислитель преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера.
1. Прибавить 1.
2. Умножить на 3.
3. Прибавить 2.
Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает
его на 2.
Программа для исполнителя Вычислитель — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 1 в число 15 и при этом
траектория вычислений содержит числа 10 и 12?
Траектория вычислений программы — это последовательность результатов выполнения всех
команд программы. Например, для программы 132 при исходном числе 7 траектория будет
состоять из чисел 8, 10, 30.

27.

Задача 7
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера.
1. Прибавить 1.
2. Умножить на 2.
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1
результатом является число 20 и при этом траектория вычислений содержит
число 10?
Траектория вычислений программы — это последовательность результатов
выполнения всех команд программы. Например, для программы 121 при
исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

28.

Задача 8
Исполнитель преобразует число на экране. У исполнителя есть три
команды, которым присвоены номера.
1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 2.
Сколько существует программ, для которых при исходном числе 4
результатом является число 13 и при этом траектория вычислений
содержит число 11?

29.

Задача 9
Исполнитель преобразует число на экране. У исполнителя есть три команды,
которым присвоены номера.
1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 3.
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2,
третья умножает на 3.
Программа для исполнителя — это последовательность команд. Сколько
существует программ, которые преобразуют исходное число 1 в число 15 и при
этом траектория вычислений содержит число 8?
Траектория вычислений — это последовательность результатов выполнения всех
команд программы. Например, для программы 231 при исходном числе 4
траектория будет состоять из чисел 6, 18, 19.

30.

Задача 10
Исполнитель Увеличитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера.
1. Вычти 1.
2. Найди целую часть от деления на 3.
Первая из них число на экране уменьшает на 1, вторая число на экране заменяет
на целую часть от деления его на 3.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 67 результатом
является число 5 и при этом траектория вычислений содержит число 33?
Траектория вычислений программы — это последовательность результатов
выполнения всех команд программы. Например, для программы 122 при
исходном числе 10 траектория состоит из чисел 9, 3, 1.

31.

Ответы
• 1) 169
• 2) 961
• 3) 28
• 4) 100
• 5) 28
• 6) 504
• 7) 28
• 8) 50
• 9) 651
• 10) 20

32.

Задачи с избегаемым этапом
• Траектория вычислений не должна проходить через
определённое число (например, путь от 3 к 12, минуя
6).
• Принцип решения: Исключаем запрещенное число из
расчетов.
• Количество программ для этого числа принудительно
принимаем равным 0. Оно не участвует в
формировании путей для следующих чисел.

33.

Пример
• Исполнитель НечетМ преобразует число на экране. У исполнителя
НечетМ две команды, которым присвоены номера.
• 1. Прибавь 1.
• 2. Сделай нечётное.
• Первая из этих команд увеличивает число x на экране на 1, вторая
переводит число x в число 2x + 1. Например, вторая команда
переводит число 10 в число 21. Программа для исполнителя
НечетМ — это последовательность команд. Сколько существует
таких программ, которые число 1 преобразуют в число 27, причём
траектория вычислений не содержит число 26? Траектория
вычислений программы — это последовательность результатов
выполнения всех команд программы. Например, для программы
121 при исходном числе 7 траектория будет состоять из чисел 8,
17, 18.

34.

Пример
• def f(curr, end):
if curr == 26:
return 0
if curr == end:
return 1
if curr > end:
return 0
return f(curr+1,end) + f(2*curr+1,end)
• print(f(1,27))

35.

Задача 1
Исполнитель РазДваТри преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера.
1. Прибавить 1.
2. Умножить на 2.
3. Прибавить 3.
Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья
увеличивает на 3.
Программа для исполнителя РазДваТри — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 3 в число 16 и
при этом траектория вычислений не содержит чисел 6 и 12?
Траектория вычислений — это последовательность результатов выполнения всех
команд программы. Например, для программы 312 при исходном числе 6 траектория
будет состоять из чисел 9, 10, 20.

36.

Задача 2
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены буквами.
A. Вычесть 1.
B. Умножить на 2.
C. Умножить на 3.
Программа для исполнителя — это последовательность команд.
Например, программа BAC при исходном числе 2 последовательно
получит числа 4, 3, 9.
Сколько существует программ, которые преобразуют исходное число
3 в число 20 и при этом не содержат двух команд A подряд?

37.

Задача 3
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены буквами.
A. Вычесть 1.
B. Прибавить 3.
C. Умножить на 2.
Программа для исполнителя — это последовательность команд.
Например, программа BAC при исходном числе 2
последовательно получит числа 5, 4, 8.
Сколько существует программ, которые преобразуют исходное
число 3 в число 12 и при этом не содержат двух команд A подряд?

38.

Задача 4
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены буквами.
A. Вычесть 1.
B. Разделить на 2.
С. Разделить на 3.
Команда B может быть исполнена только для чётного числа, команда C — только для
числа, кратного 3.
Программа для исполнителя — это последовательность команд. Траектория
вычислений программы — это последовательность результатов выполнения всех
команд программы.
Например, для программы BAС при исходном числе 20 траектория вычислений
содержит числа 10, 9, 3.
Сколько существует программ, которые преобразуют исходное число 19 в число 1 и
при этом траектория вычислений не содержит чисел 12 и 15?

39.

Задача 5
Исполнитель Калькулятор преобразует число на экране. У исполнителя есть
две команды, которые обозначены латинскими буквами:
A. вычти 7
B. подели на 2
Первая команда уменьшает число на экране на 7, вторая команда делит
число на 2 (нецелый результат округляется до ближайшего целого в большую
сторону). Программа для исполнителя — это последовательность команд.
Сколько существует таких программ, которые исходное число 300
преобразуют в число 40, при этом траектория вычислений не содержит
чисел 61 и 122?
Траектория вычислений программы — это последовательность результатов
выполнения всех команд программы.
Например, для программы ABA при исходном числе 100 траектория состоит
из чисел 93, 47, 40.

40.

Ответы
• 1) 22
• 2) 4
• 3) 53
• 4) 43
• 5) 12

41.

Задачи с обязательным и
избегаем этапами
Одновременно и то, и другое

42.

Задача 1
Исполнитель Фибо преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера.
1. Прибавить 1.
2. Прибавить 2.
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2.
Программа для исполнителя Фибо — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 2 в число 18 и
при этом траектория вычислений содержит число 9 и не содержит числа 14?
Траектория вычислений — это последовательность результатов выполнения всех
команд программы. Например, для программы 212 при исходном числе 7 траектория
будет состоять из чисел 9, 10, 12.

43.

Ответы
• 1) 315
• 2)
• 3)
• 4)
• 5)