Задача 5543. Источник: Поляков. Задание КИМ 23
(М. Шагитов) Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
- Прибавь 2
- Умножь на 3
- Умножь на 4
Выполняя первую из них, исполнитель увеличивает число на экране на 2, выполняя вторую – умножает на 3, выполняя третью – умножает на 4. Программой для исполнителя называется последовательность команд. Сколько существует различных программ, которые преобразуют исходное число 1 в число 600, и при этом траектория вычислений не содержит двух идущих подряд нечётных чисел.
Решение
Минимальное по объему кода решение на Python, где в рекурсивную функцию в качестве аргумента передается список всех этапов вычисления, а результатом функции является количество программ.
Python
def r(a):
if a[-1] > 600:
return 0
if a[-1] == 600:
for i in range(len(a) - 1):
if a[i] % 2 == 1 and a[i + 1] % 2 == 1:
return 0
return 1
return r(a + [a[-1] + 2]) + r(a + [a[-1] * 3]) + r(a + [a[-1] * 4])
print(r([1]))
Универсальное решение с использованием глобального массива, содержащего этапы вычисления. В рекурсивную функцию передается индекс последнего используемого элемента в массиве. Данное решение более объемно по коду, но быстрее, расходует меньше памяти и может быть реализовано на любом языке программирования.
Python
def r(n=0):
if a[n] > 600:
return 0
if a[n] == 600:
for i in range(n - 1):
if a[i] % 2 == 1 and a[i + 1] % 2 == 1:
return 0
return 1
a[n + 1] = a[n] + 2
k = r(n + 1)
a[n + 1] = a[n] * 3
k += r(n + 1)
a[n + 1] = a[n] * 4
k += r(n + 1)
return k
a = [1] * 301
print(r())
PascalABC
var
a: Array [1..301] of Integer;
function r(n: Integer := 1): Integer;
begin
Result := 0;
if a[n] > 600 then
Exit;
if a[n] = 600 then
begin
for var i := 1 to n - 1 do
if (a[i] mod 2 = 1) and (a[i + 1] mod 2 = 1) then
Exit;
Result := 1;
end
else
begin
a[n + 1] := a[n] + 2;
Result := Result + r(n + 1);
a[n + 1] := a[n] * 3;
Result := Result + r(n + 1);
a[n + 1] := a[n] * 4;
Result := Result + r(n + 1);
end;
end;
begin
a[1] := 1;
Writeln(r());
end.
C++
#include <iostream>
using namespace std;
int a[301];
int r(int n = 0)
{
if (a[n] > 600)
return 0;
if (a[n] == 600)
{
for (int i = 0; i <= n - 1; i++)
if (a[i] % 2 == 1 and a[i + 1] % 2 == 1)
return 0;
return 1;
}
a[n + 1] = a[n] + 2;
int k = r(n + 1);
a[n + 1] = a[n] * 3;
k += r(n + 1);
a[n + 1] = a[n] * 4;
k += r(n + 1);
return k;
}
int main()
{
a[0] = 1;
cout << r() << endl;
}
Ответ
20375