Исполнитель РазДваПять преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера.
1. Прибавить 1.
2. Умножить на 2.
3. Прибавить 5.
Первая команда увеличивает число на экране
Программа для исполнителя РазДваПять — это последовательность команд.
Сколько существует программ, которые преобразуют исходное
Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном
Искомое количество программ равно количеству программ, получающих
Пусть R(n) — количество программ, которые
Верно следующее соотношение:
R(2) = 2;
R(3) = 2;
R(4) = 4;
R(5) = 4;
R(6) = 7;
R(7) = 9;
R(8) = 15;
R(9) = 15;
R(10) = 0;
R(11) = 0;
R(12) = 0;
R(13) = 15;
R(14) = 30;
R(15) = 30;
R(16) = 45.
Таким образом, количество программ, удовлетворяющих условию задачи,
Ответ: 45.
Приведем другое решение.
Количество программ, преобразующих
Найдем количество программ, преобразующих
R(2) = 2;
R(3) = 2;
R(4) = 4;
R(5) = 4;
R(6) = 7;
R(7) = 9;
R(8) = 15.
Программ, преобразующих
Следовательно, количество программ, преобразующих
Приведём другое решение на языке Python.
def f(x, y):
if x > y or x == 10:
return 0
if x == y:
return 1
else:
return f(x + 1, y) + f(x * 2, y) + f(x + 5, y)
print(f(1, 8) * f(8, 16))
Приведём решение Виктории Сапроновой на языке С с использованием компилятора GCC(code::blocks).
#include int count_trs(int from, int to) { if (from > to || from == 10) { return 0; } if (from == to) { return 1; } int result = count_trs(from + 1, to) + count_trs(from * 2, to) + count_trs(from + 5, to); return result; } int main() { int count = count_trs(1, 8) * count_trs(8, 16); printf("%d\n", count); return 0; }