Задача 5884. Источник: Поляков. Задание КИМ 23
(В. Петров) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
- Прибавь 1
- Умножь на 2
- Умножь на 3
Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья – умножает на 3. Программа для исполнителя – это последовательность команд. Определите длину самой короткой программы, которая преобразует число 1 в число 9217 и содержит ровно 30 команд "Прибавь 1". Под длиной программы понимается количество команд, входящих в неё.
Решение
Прямое решение задачи рекурсивным алгоритмом в соответствии с формулировкой задания невозможно, т.к. обрабатывается слишком много путей, не дающих решения. Даже на компилируемых языках программирования несколько часов работы программы не приводит к завершению перебора вариантов. Задача легко решается, если двигаться от конечного результата к начальному. В качестве параметров рекурсивной функции передаются: текущее значение вычислений n, длина пути s и количество первых команд k. Возвращает функция минимальную длину пути.
Python
На данном языке программа выполняется несколько минут. На слабых компьютерах время выполнения может превысить 10 минут. Поэтому, желательно отдать предпочтение компилируемым языкам, где время выполнения не превышает нескольких секунд.
def r(n, s=0, k=0):
if n == 1:
if k == 30:
return s
else:
return 10000
res = 10000
if n % 3 == 0:
res = min(res, r(n // 3, s + 1, k))
if n % 2 == 0:
res = min(res, r(n // 2, s + 1, k))
if k < 30:
res = min(res, r(n - 1, s + 1, k + 1))
return res;
print(r(9217))
PascalABC
function r(n: Integer; s: Integer := 0; k: Integer := 0): Integer;
var
z: Integer;
begin
Result := 10000;
if n = 1 then
begin
if k = 30 then
Result := s;
Exit;
end;
if n mod 3 = 0 then
begin
z := r(n div 3, s + 1, k);
if z < Result then
Result := z;
end;
if n mod 2 = 0 then
begin
z := r(n div 2, s + 1, k);
if z < Result then
Result := z;
end;
if k < 30 then
begin
z := r(n - 1, s + 1, k + 1);
if z < Result then
Result := z;
end;
end;
begin
Writeln(r(9217));
end.
C++
#include <iostream>
using namespace std;
int r(int n, int s = 0, int k = 0)
{
if (n == 1)
if (k == 30)
return s;
else
return 10000;
int z, res = 10000;
if (n % 3 == 0)
{
z = r(n / 3, s + 1, k);
if (z < res)
res = z;
}
if (n % 2 == 0)
{
z = r(n / 2, s + 1, k);
if (z < res)
res = z;
}
if (k < 30)
{
z = r(n - 1, s + 1, k + 1);
if (z < res)
res = z;
}
return res;
}
int main()
{
cout << r(9217) << endl;
}
Ответ
36