Задача 5544. Источник: Поляков. Задание КИМ 23
(М. Шагитов) Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
- Прибавь 2
- Умножь на 3
- 3. Умножь на 4
Выполняя первую из них, исполнитель увеличивает число на экране на 2, выполняя вторую – умножает на 3, выполняя третью – умножает на 4. Программой для исполнителя называется последовательность команд. Сколько существует различных программ, которые преобразуют исходное число 1 в число 600, и при этом траектория вычислений (включая начальное число) содержит три подряд идущих числа, сумма которых кратна 11.
Решение
В плане минимизации объема кода, наилучшим решением будет реализация на языке Python, где рекурсивной функции передается список, содержащий этапы вычислений. Время выполнения программы может доходить до нескольких десятков секунд на малопроизводительных компьютерах.
Python
def r(a):
if a[-1] > 600:
return 0
if a[-1] == 600:
for i in range(len(a) - 2):
if (a[i] + a[i + 1] + a[i + 2]) % 11 == 0:
return 1
return 0
return r(a + [a[-1] + 2]) + r(a + [a[-1] * 3]) + r(a + [a[-1] * 4])
print(r([1]))
Более универсальным, быстрым и менее затратным по использованию памяти решением является использование глобального массива (списка) с передачей в рекурсивную функцию индекса последнего вычисленного элемента. Исходя из минимальной операции, достаточно будет создать массив из 301 элемента.
Python
def r(n=0):
if a[n] > 600:
return 0
if a[n] == 600:
for i in range(n - 1):
if (a[i] + a[i + 1] + a[i + 2]) % 11 == 0:
return 1
return 0
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 - 2 do
if (a[i] + a[i + 1] + a[i + 2]) mod 11 = 0 then
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 - 2; i++)
if ((a[i] + a[i + 1] + a[i + 2]) % 11 == 0)
return 1;
return 0;
}
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;
}
Ответ
58085