Обозначим R(n) — количество программ, которые преобразуют число 2 в число n. Обозначим t(n) наибольшее кратное 5, не превосходящее n. Заметим, что нечётные числа мы никак получить не можем. Обе команды исполнителя увеличивают исходное число, поэтому общее количество команд в программе не может пре-восходить (50 - 2) / 2 = 24.

Верны следующие соотношения:

1. Если n не делится на 10, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) — прибавлением двоек.

2. Пусть n делится на 5.

Тогда R(n) = R(n / 5) + R(n - 2)= R(n / 5) + R(n - 10) (если n > 10).

При n = 10 R(n) = 2 (два способа: прибавлением четырёх двоек или однократным умножением на 5).

Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных десяти и не превосходящих 50: сначала вычисляем R(2), затем R(10), R(20) и т. д.

Имеем:

R(2) = 1 = R(4) = R(6) = R(8),

R(10) = 2 = R(2) + R(8),

R(20) = R(4) + R(10) =1 + 2 = 3 = R(22) = R(28),

R(30) = R(6) + R(20) =1 + 3 = 4 = R(32) = R(38),

R(40) = R(8) + R(30) =1 + 4 = 5 = R(42) = R(48),

R(50) = R(10) + R(40) = 2 + 5 = 7.

Ответ: 7.

Другая форма решения.

Будем решать поставленную задачу последовательно для чисел 2, 4, 6, 50 (то есть для каждого из чисел определим, сколько программ исполнителя существует для его получения). Заметим, что нечётные числа мы никак получить не можем. Количество программ, которые преобразуют число 2 в число n, будем обозначать через R(n). Число 2 у нас уже есть, значит, его можно получить с помощью «пустой» программы. Любая непустая программа увеличит исходное число, т. е. даст число, больше 2. Значит, R(2) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на пять, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа:

Если число на пять делится, то вариантов последней команды два: прибавь 2 и умножь на 5, тогда . Заполним соответствующую таблицу по приведёным формулам слева направо:

При этом ячейки, относящиеся к числам, которые не делятся на 5, можно в решении и опустить (за исключением первого числа):

Ответ: 7.

Очевидно, из числа 1 нельзя получить четное число. Пусть n — нечетное число, не превосходящее 31. Обозначим R(n) — количество программ, которые преобразуют число 1 в число n. Обозначим t(n) наибольшее нечетное число, кратное трем, не превосходящее n. Обе команды исполнителя увеличивают исходное число, поэтому общее количество команд в программе не может превосходить 31.

Верны следующие соотношения:

1) Если n не делится на 3, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) — прибавлением двоек.

2) Пусть n делится на 3. Тогда R(n) = R(n/3)+R(n-2) (если n>3).

При n=3 R(n) = 2 (два способа: прибавлением двойки или однократным умножением на 3). Поэтому достаточно по индукции вычислить значения R(n) для всех нечетных чисел, кратных трем и не превосходящих 31.

Имеем:

R(1)= 1

R(3) = 2 = R(5)=R(7)

R(9) = R(3)+R(7) = 2+2 = 4 = R(11) = R(13)

R(15) = R(5)+R(13) = 2+4 = 6 = R(17) = R(19)

R(21) = R(7)+R(19) = 2+6 = 8 = R(23) = R(25)

R(27) = R(9)+R(25) = 4+8 =12 = R(29) = R(31)

Ответ: 12.

Другой способ решения:

Очевидно, из числа 1 нельзя получить четное число. Будем решать поставленную задачу последовательно для чисел 1, 3, 5,…, 31 (то есть для каждого из таких чисел определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 1 в число n, обозначим R(n). Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, R(1) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на три, то оно может быть получено только из предыдущего нечетного числа с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего нечетного числа: R(i)=R(i-2). Если число на 3 делится, то вариантов последней команды два: прибавь 2 и умножь на 3, тогда R(i)=R(i-2) + R(i/3). Заполним соответствующую таблицу по приведенным формулам слева направо:

Для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения для результата.

Обе команды увеличивают исходное число, поэтому количество команд не может превосходить 15 − 2 = 13. При этом минимальное количество команд — 5 (так как (15 −2)/3 = 4 с остатком 1). При этом заметим, что 15 — нечетное, а 2 — четное. А так как обе команды увеличивают исходное число на нечетное число, то количество команд должно быть нечетным.

Иначе говоря, команд может быть 5, 7, 9, 11 или 13. Так как, как было сказано выше, порядок команд не имеет значения, каждому числу команд соответствует один набор команд, которые можно расположить в любом порядке. Пяти командам соответствует набор 22221 (5 возможных вариантов расположения), 7 командам — набор 2221111 (здесь получается 35 возможных вариантов расположения: это число перестановок с повторениями P₇(3,4)=7!/(3! · 4!)), 9 командам — 22111111 (здесь получается 36 возможных вариантов расположения), 11 командам — 21111111111 (11 возможных вариантов расположения), 13 командам — 11111111111111 (1 вариант расположения). Всего имеем 88 программ.

Ответ: 88.

Обозначим R(n) — количество программ, которые преобразуют число 1 в число n.

Верны следующие соотношения:

1. Если n не делится на 2 или на 3, то тогда R(n) = R(n−1), так как существует единственный способ получения n из n−1 — прибавлением единиц.

2. Пусть n делится на 2 и на 3.

Тогда R(n) = R(n / 2) + R(n / 3) + R(n − 1).

Достаточно вычислить все значения R(n).

Имеем:

R(2) = 2 (можно умножить единицу на 2 или прибавить 1),

R(3) = 3 (можно умножить единицу на 3 или прибавить 1 к двойке, которую, в свою очередь, можно получить двумя способами(см. выше)),

R(4) = R(2) + R(3) = 5,

R(5) = R(4) = 5,

R(6) = R(2) + R(3) + R(5) = 10,

R(7) = R(6) = 10,

R(8) = R(4) + R(7) = 5 + 10 = 15,

R(9) = R(3) + R(8) = 3 + 15 = 18,

R(10) = R(5) + R(9) = 5 + 18 = 23,

R(11) = R(10) = 23,

R(12) = R(11) + R(4) + R(6) = 23 + 5 + 10 = 38,

R(13) = R(12) = 38.

Обе команды увеличивают исходное число. Старшая цифра — 3, следовательно, использовать команду 2 более двух раз бессмысленно.

Выпишем программы, в которых команда 2 используется два раза: 1122, 2211, 1212, 2121, 2112, 1221. Итого 6 программ.

Выпишем программы, в которых команда 2 используется один раз. Использовав эту команду в первой позиции, мы получим из числа 35 число 45, следовательно, после этого необходимо будет дописать ещё 12 команд 1 чтобы получить число 57. Таким образом, получаем программы: 211...1, 121...1, и. т. д. Итого имеем 13 программ (двойка побывала в каждой позиции).

Существует всего одна программа, в которой команда 2 не используется: 111....1.

Таким образом, имеем 6 + 13 + 1 = 20 программ.

Ответ: 20.

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n. Обозначим t(n) наибольшее кратное 2, не превосходящее n.

Верны следующие соотношения:

1. Если n не делится на 2, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) — прибавлением единиц.

2. Пусть n делится на 2. Тогда R(n) = R(n / 2) + R(n - 1)= R(n / 2) + R(n - 2) (если n > 2). При n = 2 R(n) = 2 (два способа: прибавлением единицы и удвоением). Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных 2 и не превосходящих 20.

Имеем:

R(3) = 1

R(4) = 2 = R(5),

R(6) = R(3) + R(4) = 1 + 2 = 3 = R(7),

R(8) = R(4) + R(6) = 2 + 3 = 5 = R(9),

R(10) = R(5) + R(8) = 2 + 5 = 7 = R(11),

R(12) = R(6) + R(10) = 3 + 7 = 10 = R(13),

R(14) = R(7) + R(12) = 3 + 10 = 13 = R(15),

R(16) = R(8) + R(14) = 5 + 13 = 18 = R(17),

R(18) = R(9) + R(16) = 5 + 18 = 23 = R(19),

R(20) = R(10) + R(18) = 7 + 23 = 30 = R(21),

R(22) = R(11) + R(20) = 7 + 30 = 37.

Ответ: 37.

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n.

Верны следующие соотношения:

1. Если n нечётное, то тогда R(n) = R(n − 1) + R((n − 1) \ 2), (если n > 5) так как есть два способа получения n: прибавлением единицы или использованием команды 3.

2. Если n чётное, то тогда R(n) = R(n − 1) + R(n \ 2), (если n > 4) так как есть два способа получения n: прибавлением единицы или использованием команды 2.

Достаточно вычислить значения R(n) для всех чисел не превосходящих 16.

Имеем:

R(3) = 1,

R(4) = 2,

R(5) = 3 ,

R(6) = R(5) + R(3) = 3 + 1 = 4,

R(7) = R(6) + R(3) = 4 + 1 = 5,

R(8) = R(7) + R(4) = 5 + 2 = 7,

R(9) = R(8) + R(4) = 7 + 2 = 9,

R(10) = R(9) + R(5) = 9 + 3 = 12,

R(11) = R(10) + R(5) = 12 + 3 = 15,

R(12) = R(11) + R(6) = 15 + 4 = 19,

R(13) = R(12) + R(6) = 19 + 4 = 23,

R(14) = R(13) + R(7) = 23 + 5 = 28,

R(15) = R(14) + R(7) = 28 + 5 = 33,

R(16) = R(15) + R(8) = 33 + 7 = 40,

Ответ: 40.

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n.

Верны следующие соотношения:

1. Если n нечётное, то тогда R(n) = R(n − 1) + R((n − 1) / 2), (если n > 3) так как есть два способа получения n: прибавлением единицы или использованием команды 3.

2. Если n чётное, но не делится на 10, то тогда R(n) = R(n − 1) + R(n / 2), (если n > 2) так как есть два способа получения n: прибавлением единицы или использованием команды 2.

3. Если n чётное и делится на 10, то тогда R(n) = R(n − 1) + R(n / 2) + R(n / 10), так как есть три способа получения n: прибавлением единицы, использованием команды 2 или использованием команды 4.

Достаточно вычислить значения R(n) для всех чисел не превосходящих 15.

Имеем:

R(2) = 2,

R(3) = 3,

R(4) = R(3) + R(2) = 5,

R(5) = R(4) + R(2) = 5 + 2 = 7,

R(6) = R(5) + R(3) = 7+ 3 = 10,

R(7) = R(6) + R(3) = 10 + 3 = 13,

R(8) = R(7) + R(4) = 13 + 5 = 18,

R(9) = R(8) + R(4) = 18 + 5 = 23,

R(10) = R(9) + R(5) + R(1) = 23 + 7 +1 = 31,

R(11) = R(10) + R(5) = 31 + 7 = 38,

R(12) = R(11) + R(6) = 38 + 10 = 48,

R(13) = R(12) + R(6) = 48 + 10 = 58,

R(14) = R(13) + R(7) = 58 + 13 = 71,

R(15) = R(14) + R(7) = 71 + 13 = 84.

Ответ: 84.

Для сложения справедлив переместительный (коммутативный) закон, значит, порядок команд в программе не имеет значения для результата.

Все команды увеличивают исходное число, поэтому количество команд не может превосходить (30 − 21) = 9. При этом минимальное количество команд — 3.

Таким образом, команд может быть 3, 4, 5, 6, 7, 8 или 9. Поэтому порядок команд не имеет значения, каждому числу команд соответствует один набор команд, которые можно расположить в любом порядке.

Рассмотрим все возможные наборы и вычислим количество вариантов рассположения команд в них. Набор 133 имеет 3 возможных вариантов расположения. Набор 1223 — 12 возможных вариантов расположения: это число перестановок с повторениями (1+2+1)!/(1! · 2! · 1!)). Набор 12222 — 5 вариантов. Набор 111222 — 20 возможных вариантов. Набор 11123 — 20 вариантов. Набор 111113 — 6 вариантов, набор 1111122 — 21 вариант, набор 11111112 — 8 вариантов, набор 111111111 — один вариант.

Всего имеем 3 + 12 + 5 + 20 + 20 + 6 + 21 + 8 + 1 = 96 программ.

Ответ: 96.

Ответ: 96.

Обозначим число программ, преобразующих число 2 в число N как К_N. Тогда число N может быть получено либо прибавление единице к N − 1, либо двойки к N − 2, либо из некоторого числа X увеличением на X − 1 (предыдущее число), так что N = X + X − 1, откуда X = (N + 1) / 2; так могут быть получены только нечетные числа.

Тогда для чётных чисел K_N = K_{N − 1} + K_{N − 2}, а для нечётных — K_N = K_{N − 1} + K_{N − 2} + K_{(N + 1)/2}. Заполним таблицу для значений от 2 до 9:

Ответ: 57.

Заметим, что все операции только лишь прибавляют некоторую константу к числу. Поэтому не важно, в каком порядке выполнять некоторый данный набор команд. Пусть x − количество первых команд, y − вторых, а z − третьих. Составим уравнение:

А именно найдём с его помощью все наборы команд, которые подходят под условие. И уже для каждого набора в отдельности подсчитаем количество возможных перестановок.

Найдём все решения уравнения: (0, 5, 0), (4, 2, 0), (1, 3, 1), (5, 0, 1), (2, 1, 2), (0, 0, 4).

Количество перестановок для данного набора посчитаем по формуле подсчёта перестановок с повторениями:

Пусть каждого вида команд a, b и с. Тогда всего перестановок из этих команд будет

Найдём теперь ответ на задачу, просуммировав ответы для каждого набора:

Пусть R(x) — количество программ, которыми можно из 2 получить x.

Заметим, что чётное число нельзя получить с использованием команды 3, поскольку в её процессе складывается чётное и нечётное число. Также заметим, что для того, чтобы получить x с помощью команды 3, нужно применять её к числу .

Вычислим последовательно значение R:

R(0) = 0

R(1) = 0

R(2) = 1

R(3) = R(2) + R(0) + R(2) = 1 + 0 + 1 = 2

R(4) = R(3) + R(1) = 2 + 0 = 2

R(5) = R(4) + R(2) + R(3) = 2 + 1 + 2 = 5

R(6) = R(5) + R(3) = 5 + 2 = 7

R(7) = R(6) + R(4) + R(4) = 7 + 2 + 2 = 11

R(8) = R(7) + R(5) = 11 + 5 = 16

R(9) = R(8) + R(6) + R(5) = 16 + 7 + 5 = 28

R(10) = R(9) + R(7) = 28 + 11 = 39

Для ответа на задачу нужно найти количество программ, которые из 2 получают 14, количество программ, которые из 14 получают 29, не проходя при этом через 25, и перемножить найденные значения. Сначала найдём количество программ, получающих 14.

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n.

Верны следующие соотношения:

1. Если n не делится на 2, то тогда R(n) = R(n - 1), так как существует единственный способ получения n из n - 1 — прибавление единицы.

2. Пусть n делится на 2.

Тогда R(n) = R(n / 2) + R(n - 1).

Теперь можно постепенно вычислить все значения:

R(4) = R(2) + R(3) = 1 + 1 = 2 = R(5),

R(6) = R(3) + R(5) = 1 + 2 = 3 = R(7),

R(8) = R(4) + R(7) = 2 + 3 = 5 = R(9),

R(10) = R(5) + R(9) = 2 + 5 = 7 = R(11),

R(12) = R(6) + R(11) = 3 + 7 = 10 = R(13),

R(14) = R(7) + R(13) = 3 + 10 = 13.

Программа, получающая из числа 14 число 29, не проходящих через 25, одна: 21.

Таким образом, всего программ 13 · 1 = 13.

Ответ: 13.

Для вычитания справедлив коммутативный (переместительный) закон, значит, порядок команд в программе не имеет значения для результата.

Обе команды уменьшают исходное число, поэтому количество команд не может превосходить (22 — 2)/2 = 10. При этом минимальное количество команд — 4 (т. к. [22 − 2]/5 = 4). Заметим, что 22 — чётное и 2 — четное. Поскольку команда 2 вычитает нечётное число, то команда 2 должна встречаться чётное число раз.

Иначе говоря, команд может быть от четырёх, до десяти.

Четырём командам соответствует набор 2222.

При помощи пяти команд нельзя преобразовать число 22 в число 2.

При помощи шести команд нельзя преобразовать число 22 в число 2.

Семи командам соответствует набор 111 1122. (21 возможный вариант расположения: это число перестановок с повторениями P₇(2,5) = 7!/(2! · 5!))

При помощи восьми команд нельзя преобразовать число 22 в число 2.

При помощи девяти команд нельзя преобразовать число 22 в число 2.

Десяти командам соответствует набор 11 1111 1111.

Всего имеем 23 программы.

Ответ: 23.

Искомое количество программ равно произведению количества программ, получающих из числа 3 число 10, на количество программ, получающих из числа 10 число 12.

Пусть R(n) — количество программ, которые число 3 преобразуют в число n, а P(n) — количество программ, которые число 10 преобразуют в число n.

Для всех n > 5 верны следующие соотношения:

1. Если n не делится на 2, то тогда R(n) = R(n - 1) + R(n - 2), так как существует два способа получения n — прибавлением единицы или прибавлением двойки. Аналогично P(n) = P(n - 1) + P(n - 2)

2. Если n делится на 2, тогда R(n) = R(n - 1) + R(n - 2) + R(n / 2). Аналогично P(n) = P(n - 1) + P(n - 2) + P(n / 2)

Последовательно вычислим значения R(n):

R(3) = 1

R(4) = R(3) = 1

R(5) = R(4) + R(3) = 1 + 1 = 2

R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4

R(7) = R(6) + R(5) = 4 + 2 = 6

R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11

R(9) = R(8) + R(7) = 11 + 6 = 17

R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30

Теперь вычислим значения P(n):

P(10) = 1

P(11) = P(10) = 1

P(12) = P(11) + P(10) = 2

Таким образом, количество программ, удовлетворяющих условию задачи равно 30 · 2 = 60.

Ответ: 60.

Используем метод динамического программирования. Возьмем массив dp, где dp[i] - кол-во способов получить число i из единицы с помощью данных команд.

База динамики:

dp[1]=1;

Переход:

dp[i]=dp[i-2]+dp[i-5].

Тогда значения в нашем массиве будут следующие(от 1 до 20): 1 0 1 0 1 1 1 2 1 3 2 4 4 5 7 7 11 11 16 18.

Ответ: 18.

Используем метод динамического программирования. Заведем массив dp, где dp[i] — кол-во способов получить число i с помощью таких команд.

База динамики:

dp[1]=1;

Формула перехода:

dp[i]=dp[i-1] - если i - четное.

dp[i]=dp[i-1] + dp[(i-1)/2] - если i нечетное.

Но при этом, если i-1 = 26 или (i-1)/2 = 26, то оно не учитывается. Можно заметить, что для числа 27 будет формула dp[27]=dp[26] + dp[13], а поскольку dp[26] не считается, то ответ совпадает с dp[13].

Посчитаем dp[13] (далее будет приведены значения в ячейках dp от 1 до 13): 1 1 2 2 3 3 5 5 7 7 10 10 13.

Ответ: 13.

Используем метод динамического программирования. Заведем массив dp, где dp[i] — количество способов получить число i с помощью таких команд.

База динамики:

dp[1]=1;

Формула перехода:

dp[i]=dp[i-1] - если i - четное.

dp[i]=dp[i-1] + dp[(i-1)/2] - если i нечетное;

Но при этом если i-1 = 24 или (i-1)/2 = 24, то его не учитываем. Можно заметить, что для числа 25 будет формула

dp[25]=dp[24] + dp[12], а т.к. dp[24] не считаем, то ответ совпадает с dp[12].

Посчитаем dp[13] (далее будет приведены значения в ячейках dp от 1 до 12): 1 1 2 2 3 3 5 5 7 7 10 10.

Ответ: 10.

Используем метод динамического программирования. заведем массив dp, где dp[i] — количество способов получить число i с помощью таких команд.

База динамики:

dp[1]=1;

Формула перехода:

dp[i]=dp[i-1] + dp[i-3]

При этом не учитываются значения для чисел больше 9, которые можно получить из чисел меньше 9 (перескочив тем самым траекторию 9):

Далее будут приведены значения в ячейках dp от 1 до 17: 1 1 1 2 3 4 6 9 13 13 13 26 39 52 78 117 169.

Ответ: 169.

Используем метод динамического программирования. Заведем массив dp, где dp[i] — количество способов получить число i с помощью таких команд.

База динамики:

dp[1]=1;

Формула перехода:

dp[i]=dp[i-1] + dp[i-3]

Но при этом не учитываются такие числа, которые больше 8, но в них мы можем добраться из значения меньше 8. Далее будет приведены значения в ячейках dp от 1 до 15: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81.

Ответ: 81.

Используем метод динамического программирования: Заведем массив dp, где dp[i] — количество способов получить число i через данные команды.

База динамики dp[1] = 1.

Переходы будут иметь вид:

dp[i] = dp[i-1] + dp[i -2] + dp[i-4].

При этом, если i-1 или i-2 или i-4 меньше 8, а i больше 8, то тогда его не нужно учитывать (поскольку тогда мы обойдем число 8, а этого нельзя делать по условию).

Далее будут значения от 1 до 15 в нашем массиве dp: 1 1 2 3 6 10 18 31 31 62 93 186 310 558 961

Ответ: 961.

Искомое количество программ равно произведению количества программ, получающих из числа 1 число 8, на количество программ, получающих из числа 8 число 15.

Пусть R(n) — количество программ, которые число 3 преобразуют в число n, а P(n) — количество программ, которые число 8 преобразуют в число n.

Для всех n > 3 верны следующие соотношения:

1. R(n) = R(n - 1) + R(n - 2) + R(n - 3), так как существует три способа получения n — прибавлением единицы, прибавлением двойки или прибавлением тройки. Аналогично P(n) = P(n - 1) + P(n - 2) + P(n - 3)

Последовательно вычислим значения R(n):

R(1) = 1

R(2) = 1

R(3) = 2

R(4) = R(1) + R(2) + R(3) = 4

R(5) = R(4) + R(3) + R(2) = 4 + 2 + 1 = 7

R(6) = R(5) + R(4) + R(3) = 7 + 4 + 2 = 13

R(7) = R(6) + R(5) + R(4) = 13 + 7 + 4 = 24

R(8) = R(7) + R(6) + R(5) = 24 + 13 + 7 = 44

Теперь вычислим значения P(n):

P(8) = 1

P(9) = 1

P(10) = 2

P(11) = 4

P(12) = P(11)+ P(10) + P(9) = 4 + 2 + 1 = 7

P(13) = P(12) + (11) + P(10) = 7 + 4 + 2 = 13

P(14) = P(13) + P(12) + P(11) = 13 + 7 + 4 = 24

P(15) = P(14) + P(13) + P(12) = 24 + 13 + 7 = 44

Таким образом, количество программ, удовлетворяющих условию задачи равно 44 · 44 = 1936.

Ответ: 1936.

Используем динамическое программирование. Заведем массив dp, где dp[i] — количество способов получить число i.

База динамики dp[2] = 1.

Переходы:

dp[i] = dp[i-1] + dp[i/2](если i - четно) + dp[i/3] (если i - кратно 3).

При этом, если i > 14, а i-1 или i/2 или i/3 меньше 14, то этими значениями пренебрегаем, т.к. тогда не будет выполнено условие траектории. Далее будут показаны значения массива dp от 2 до 28:

1 1 2 2 4 4 6 7 9 9 15 15 19 19 19 19 19 19 19 19 19 19 19 19 19 19 38.

Ответ:38.

Используем динамическое программирование. Заведем массив dp, где dp[i] — количество способов получить число i.

База динамики dp[2] = 1.

Переходы:

dp[i] = dp[i-1] + dp[i/2](если i - четно) + dp[i/3] (если i кратно 3).

При этом если i > 15, а i-1 или i/2 или i/3 меньше 15, то этими значениями будем пренебрегать, т.к. тогда не будет выполнено условие траектории. Далее будут показаны значения массива dp от 2 до 30:

1 1 2 2 4 4 6 7 9 9 15 15 19 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 42

Ответ:42.

Искомое количество программ равно произведению количества программ, получающих из числа 2 число 8, на количество программ, получающих из числа 8 число 10, и на количество программ, получающих из числа 10 число 12.

Будем решать задачу с конца. Число 12 из числа 10 можно получить двумя способами (10+1+1; 10+2). Число 10 из числа 8 можно получить двумя способами (8+1+1; 8+2). Остается узнать количество способов получения числа 8 из числа 2. Начнем свои рассуждения с числа 3, т.к. двойка это начальное число. Тройку можно получить только одним способом – прибавив 1. Четверку получим двумя способами – прибавив единицу к тройке или добавив двойку к двойке и т. д. Запишем эти рассуждения в следующем виде:

R(2) = 1

R(3) = R(2) = 1

R(4) = R(3) + R(2) = 2

R(5) = R(4) + R(3) = 2 + 1 = 3

R(6) = R(5) + R(4) + R(2) = 3 + 2 + 1 = 6

R(7) = R(6) + R(5) = 6 + 3 = 9

R(8) = R(7) + R(6) = 9 + 6 = 15

Таким образом, количество программ, удовлетворяющих условию задачи равно R(2) * R(8) * R(10) * R(12) = 1 * 15 * 2 * 2 = 60.

Ответ: 60.

Пусть — количество способов получить из числа 1 число х. Заметим, что для x > 2: .

Ответ: 144.

Пусть — количество способов получить из числа 1 число х. Заметим, что для x > 2: .

Ответ: 89.

Нужно найти количество программ, которые из 1 получают 10, количество программ, которые из 10 получают 21, количество программ, которые из 21 получают 30 и перемножить найденные значения. Сначала найдём количество программ, получающих 10 из 1.

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n.

Верны следующие соотношения:

1. Если n не делится на 2, то тогда R(n) = R(n - 1), так как существует единственный способ получения n из n - 1 — прибавление единицы.

2. Пусть n делится на 2.

Если n > 1, то R(n) = R(n / 2) + R(n - 1).

Если n = 1, то R(n) = 1 (два способа: прибавление единицы и удвоение).

Теперь можно постепенно вычислить все значения:

R(2) = R(1) + R(1) = 1 + 1 = 2 = R(3)

R(4) = R(2) + R(3) = 2 + 2 = 4 = R(5),

R(6) = R(3) + R(5) = 2 + 4 = 6 = R(7),

R(8) = R(4) + R(7) = 4 + 6 = 10 = R(9),

R(10) = R(5) + R(9) = 4 + 10 = 14

Программ, получающих из числа 10 число 21 достаточно мало, можно их просто перечислить: 21, 11111111111.

А программ, получающих из числа 21 в число 30 всего один способ: добавление единиц.

Тем самым, находим ответ:

Ответ: 28.

Нужно найти количество программ, которые из 1 получают 12, количество программ, которые из 12 получают 25, количество программ, которые из 25 получают 40 и перемножить найденные значения. Сначала найдём количество программ, получающих 12 из 1.

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n.

Верны следующие соотношения:

1. Если n не делится на 2, то тогда R(n) = R(n - 1), так как существует единственный способ получения n из n − 1 — прибавление единицы.

2. Пусть n делится на 2.

Если n > 1, то R(n) = R(n / 2) + R(n - 1).

Если n = 1, то R(n) = 1 (два способа: прибавление единицы и удвоение).

Теперь можно постепенно вычислить все значения:

R(2) = R(1) + R(1) = 1 + 1 = 2 = R(3)

R(4) = R(2) + R(3) = 2 + 2 = 4 = R(5),

R(6) = R(3) + R(5) = 2 + 4 = 6 = R(7),

R(8) = R(4) + R(7) = 4 + 6 = 10 = R(9),

R(10) = R(5) + R(9) = 4 + 10 = 14 = R(11)

R(12) = R(6) + R(11) = 6 + 14 = 20

Программ, получающих из числа 12 число 25 достаточно мало, можно их просто перечислить: 21, 1111111111111.

А программ, получающих из числа 25 число 40, всего один способ: добавление единиц.

Тем самым, находим ответ:

Ответ: 40.