GetMinNumberOfOperations.cs

CSharp · Console

/Program.cs

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
	}
}
;