Количество программ, ведущих из одного числа в другое

Количество программ, которые преобразуют число 1 в число \(n,\) обозначим \(R(n).\) Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, \(R(1) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Число “2” может быть получено только из числа “1” командой под номером 1. Отсюда \(R(2) = 1.\) Число “3” можем получить из чисел 1 и 2 — \(R(3) = R(1) + R(2) = 2.\) Число “4” получаем из 2 и 3 — \(R(4) = R(2) + R(3) = 3.\) Можем заметить, что количество программ для получения числа n находится по формуле — \(R(n) = R(n-2) + R(n-1).\) Составим таблицу по данной формуле:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 \\ \hline \end{array}\] Отсюда видим, что имеем 34 возможных программ для получения числа 9.

Ответ: 34

Количество программ, которые преобразуют число 2 в число \(n,\) обозначим \(R(n).\) Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, \(R(2) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на три, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: \(R(n) = R(n-2).\)
Если число на три делится, то вариантов последней команды два: прибавь 2 и умножь на 3, тогда \(R(n) = R(n-2) + R(n:3).\) Заполним таблицу по данной формуле:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{2}& 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 & 32 & 34 & 36 & 38 & 40 & 42 \\ \hline \text{1}& 1 & 2 & 2 & 2 & 3 & 3 & 3 & 5 & 5 & 5 & 7 & 7 & 7 & 9 & 9 & 9 & 12 & 12 & 12 & 15 \\ \hline \end{array}\] Отсюда видим, что всего программ 15.

Ответ: 15

Количество программ, которые преобразуют число 1 в число n, обозначим \(R(n).\) Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, \(R(1) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Число “2” может быть получено только из числа “1” командой под номером 1. Отсюда \(R(2) = 1.\) Число “3” можем получить из чисел 1 и 2 — \(R(3) = R(1) + R(2) = 2.\) Число “4” получаем из 1, 2 и 3 — \(R(4) = R(1) + R(2) + R(3) = 6.\) Заметим, что количество программ для получения числа n находится по формуле — \(R(n) = R(n-3) + R(n-2) + R(n-1).\) Составим таблицу по данной формуле:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline \text{1}& 1 & 2 & 4 & 7 & 13 & 24 & 44 & 81 & 149 & 274 & 504 & 927 & 1705 \\ \hline \end{array}\] Отсюда получаем искомое количество программ — 1705.

Ответ: 1705

Обе команды увеличивают исходное число. Старшая цифра — 3, следовательно, использовать команду 2 более двух раз бессмысленно.
Выпишем программы, в которых команда 2 используется два раза: 1122, 2211, 1212, 2121, 2112, 1221. Итого 6 программ.
Выпишем программы, в которых команда 2 используется один раз. Использовав эту команду в первой позиции, мы получим из числа 31 число 41, следовательно, после этого необходимо будет дописать ещё 12 команд 1 чтобы получить число 53. Таким образом, получаем программы: \(211\dots1,\) \(121\dots1,\) и. т. д. Итого имеем 13 программ (двойка побывала в каждой позиции).
Существует лишь одна программа, в которой команда 2 не используется: \(111\dots1.\)
Таким образом получаем \(6 + 13 + 1 = 20.\)

Ответ: 20

Обозначим число программ, преобразующих число 2 в число n как \(R(n).\) Тогда число \(n\) может быть получено либо прибавлением к \(n-1,\) либо к \(n-2,\) либо из некоторого числа \(х\) увеличением на \(x-1,\) так что \(n = x + x - 1,\) откуда \(x = \frac{n + 1}{2};\) так могут быть получены только нечетные числа.
Тогда для четных чисел \(R(n) = R(n-1) + R(n-2),\) а для нечетных — \(R(n) = R(n-1) + R(n-2) + R(\frac{n + 1}{2}\)). Заполним таблицу по данным формулам:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline \text{1}& 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \text{1}& 1 & 3 & 4 & 10 & 14 & 28 & 42 & 80 & 122 \\ \hline \end{array}\] Отсюда получаем искомое количество программ — 122.

Ответ: 122

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

Если число делится на 4, то вариантов последней команды три: прибавить 1, прибавить 2 и умножить на 4, тогда \(R(n) = R(n-1) + R(n-2) + R(n:4)\). Заполним таблицу по данной формуле:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{2}& 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ \hline \text{1}& 1 & 2 & 3 & 5 & 8 & 14 & 22 & 36 & 58 & 95 & 153 & 248 & 401 & 651 & 1052 \\ \hline \end{array}\] Отсюда получаем искомое количество программ — 1052.

Ответ: 1052

Количество программ, которые преобразуют число 2 в число n, обозначим \(R(n)\). Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, \(R(2) = 1\). Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на десять, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: \(R(n) = R(n-2)\).
Если число делится на 10, то вариантов последней команды два: прибавь 2 и умножь на 10, тогда \(R(n) = R(n-2) + R(n:10)\). Заполним таблицу по данной формуле:
\[\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{2}& 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 24 & 26 & 28 & 30 & 32 & 34 & 36 & 38 & 40 \\ \hline \text{1}& 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 3 \\ \hline \end{array}\]

Отсюда получаем искомое количество программ - 3.

Ответ: 3