Текстовые решения некоторых заданий
| Сайт: | Не ждем, а готовимся! |
| Курс: | 23 задание (аналитика) |
| Книга: | Текстовые решения некоторых заданий |
| Напечатано:: | Гость |
| Дата: | вторник, 25 августа 2026, 19:59 |
1. Демоверсия 2023
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 35, при этом траектория вычислений содержит число 10 и не содержит 17?
1.1. Аналитическое решение
Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 35, при этом траектория вычислений содержит число 10 и не содержит 17?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы ABA при исходном числе 7 траектория будет состоять из чисел 8, 16, 17
Решение задачи сводится к тому, что мы подсчитываем сколькими способами можно попасть в текущее число из 1. В 2 можно попасть двумя способами, 1+1 и 1*2. В тройку можно попасть тоже двумя способами 1+1+1 и 1*2+1, т.е. в тройку можно попасть одним способом из двойки, а в двойку можно было попасть двумя способами. В четверку можно попасть из 3, и из 2, 3+1 и 2*2. В двойку можно было попасть двумя способами, в тройку также можно было попасть двумя способами, следовательно в четверку можно попасть четырьмя способами. Т.о. количество способов которыми можно попасть в некоторое число, равно сумме способов которыми можно попасть в те числа, из которых можно попасть в текущее.
|
Кол-во способов |
1 |
2 |
2 |
4 |
4 |
6 |
6 |
10 |
10 |
14 |
|
Число |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
Откуда можно попасть |
(условно считаем, что для начального числа 1 способ) |
1+1 1*2 |
2+1 |
3+1 2*2 |
4+1 |
5+1 3*2 |
6+1 |
7+1 4*2 |
8+1 |
9+1 5*2 |
В этот момент необходимо остановиться, т.к. по условию задачи необходимо проходить через число 10, т.е. вариантов как добраться до числа 11 у нас 14, только из 10, а в число 12 мы могли бы попасть как из 6, так и из 11, но из 6 нельзя, потому что тогда мы не пройдем через число 10. По сути нам нужно построить новую табличку, которая начинается с числа 10, и попасть в него у нас есть 14 способов, и начать заполнять уже эту табличку.
|
Кол-во способов |
14 |
14 |
14 |
14 |
14 |
14 |
14 |
0 |
0 |
0 |
14 |
14 |
28 |
28 |
42 |
42 |
56 |
56 |
70 |
70 |
84 |
84 |
98 |
98 |
98 |
98 |
|
Число |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
33 |
34 |
35 |
|
Откуда можно попасть |
- |
10+1 |
11+1 |
12+1 |
13+1 |
14+1 |
15+1 |
Здесь мы пишем 0, т.к. это число нужно обходить |
17+1 |
18+1 |
19+1 10*2 |
20+1 |
21+1 11*2 |
22+1 |
23+1 12*2 |
24+1 |
25+1 13*2 |
26+1 |
27+1 14*2 |
28+1 |
29+1 15*2 |
30+1 |
31+1 16*2 |
32+1 |
33+1 17*2 |
34+1 |
Т.о. в число 35 можно попасть 98 способами.
Ответ: 98