Задача 5932. Источник: Поляков. Задание КИМ 23
(Е. Джобс) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
- Прибавь 1
- Прибавь 2
- Умножь на 2
Первая команда увеличивает число на 1, вторая – на 2, третья – вдвое. Программа для исполнителя – это последовательность команд. Сколько существует таких программ, которые исходное число 3 преобразуют в число 25 и при этом в программе есть все три команды?
Решение
Используем рекурсивную функцию, в которую передаются два параметра: текущее вычисленное значение n и флаговая переменная f с использованными в программе командами. Использованные команды будут кодироваться побитово тремя младшими битами. Интересующие нас программы должны имет флаг равный 7. Функция возвращает количество программ, удовлетворяющих условию задачи.
Python
def r(n, f=0):
if n > 25:
return 0;
if n == 25:
if f == 7:
return 1;
else:
return 0;
return r(n + 1, f | 1) + r(n + 2, f | 2) + r(n * 2, f | 4)
print(r(3))
PascalABC
function r(n: Integer; f:Integer := 0): Integer;
begin
if n > 25 then
r := 0
else if n = 25 then
if f = 7 then
r := 1
else
r := 0
else
r := r(n + 1, f or 1) + r(n + 2, f or 2) + r(n * 2, f or 4);
end;
begin
Writeln(r(3));
end.
C++
#include <iostream>
using namespace std;
int r(int n, int f = 0)
{
if (n > 25)
return 0;
if (n == 25)
if (f == 7)
return 1;
else
return 0;
return r(n + 1, f | 1) + r(n + 2, f | 2) + r(n * 2, f | 4);
}
int main()
{
cout << r(3) << endl;
}
Ответ
15092