CSharp · Console
using System;
public class Program
{
static int GetMinNumberOfOperations(int N)
{
const int Max = 1000000;
if (N <= 0 || N > Max)
{
throw new Exception(string.Format("N should be less than {0} and greater than 0", Max));
}
int[] numOperations = new int[N + 1];
// частный случай
numOperations[0] = 0;
numOperations[1] = 0;
for (int i = 2; i < numOperations.Length; i++)
{
// операция вычитания
numOperations[i] = numOperations[i - 1] + 1;
// делим на 2
if (i % 2 == 0)
{
numOperations[i] = Math.Min(numOperations[i], numOperations[i / 2] + 1);
}
// делим на 3
if (i % 3 == 0)
{
numOperations[i] = Math.Min(numOperations[i], numOperations[i / 3] + 1);
}
}
return numOperations[N];
}
public static void Main()
{
Console.WriteLine("UniLecs");
Console.WriteLine(string.Format("Answer = {0}", GetMinNumberOfOperations(10))); // 3
Console.WriteLine(string.Format("Answer = {0}", GetMinNumberOfOperations(11))); // 4
Console.WriteLine(string.Format("Answer = {0}", GetMinNumberOfOperations(12))); // 3
}
}