这是一个问题陈述。
考虑一个数字 2345。如果将其数字相乘，则得到数字 120。现在，如果再次将 120 的数字相乘，则将得到数字 0，这是一个数字。如果我添加 2345 的数字，那么我将得到 14。如果我添加 14 的数字，那么我将得到 5，这是一个数字。
因此，任何数字都可以在一定数量的步骤中转换为两个一位数。您可以看到 2345 通过使用 2 步中的数字相乘转换为 0，并通过使用 2 步中的数字加法将其转换为 5。现在考虑任何数字 N。假设它可以通过在 n1 步中将数字乘以一位数字 d1 并通过在 n2 步中将数字与一位数字数字 d2 相加来转换。
您的任务是找到大于 N 且小于 1000000000 的最小数字，可以通过在小于或等于 n1 步内将其数字乘以 d1 并在小于或等于 n2 步内将其数字与 d2 相加来转换。
如何在 C# 中解决它...
There are two memory problems I can see; the first is the generation of lots of strings - you might want to approach that something like:
static int SumDigits(int value)
{
int total = 0;
while (value > 0)
{
total += value % 10;
value /= 10;
}
return total;
}
(which is completely untested)
The second problem is the huge list; you don't need to store (in lstString) every value just to find a minimum. Just keep track of the best you've done so far. Or if you need the data for every value, then: don't store them as a string. Indeed, the i can be implied anyway (from the position in the list/array), so all you would really need would be an int[] of the cnt values for every value. And int[1000000000] is 4GB just by itself, so would require the large-array support in recent .NET versions (<gcAllowVeryLargeObjects>). But much better would be: just don't store it.
但它在抛出
System.OutOfMemoryException。
这仅仅意味着你的内存不足。您的限制是1,000,000,000或大约 1G。对于对于 32 位系统来说已经太大的字符串引用，乘以 4 个字节。即使没有实际的字符串。
您可以将答案更紧凑地存储在int[]数组中，但这仍然会显示相同的问题。
因此，降低您的限制或在 64 位 PC 上编译和运行。
我认为您只是错误地接近/解释了问题；这是在黑暗中刺伤：
using System;
using System.Diagnostics;
static class Program
{
static void Main()
{
// check our math first!
// You can see 2345 is converted to 0 by using multiplication of digits in 2 steps
int value, steps;
value = MultiplyToOneDigit(2345, out steps);
Debug.Assert(value == 0);
Debug.Assert(steps == 2);
// and it is converted to 5 by using addition of digits in 2 steps
value = SumToOneDigit(2345, out steps);
Debug.Assert(value == 5);
Debug.Assert(steps == 2);
// this bit is any random number
var rand = new Random();
for (int i = 0; i < 10; i++)
{
int N = rand.Next(0, MAX);
int result = Execute(N);
Console.WriteLine("For N={0}, our answer is {1}", N, result);
}
}
const int MAX = 1000000000;
//Now consider any number N.
static int Execute(int N)
{
// Let us say that it can be converted by multiplying digits to a one digit number d1 in n1
// steps and by adding digits to one digit number d2 in n2 steps.
int n1, n2;
int d1 = MultiplyToOneDigit(N, out n1),
d2 = SumToOneDigit(N, out n2);
// Your task is to find smallest number greater than N and less than 1000000000
for (int i = N + 1; i < MAX; i++)
{
int value, steps;
// which can be converted by multiplying its digits to d1 in less than or equal to n1 steps
value = MultiplyToOneDigit(i, out steps);
if (value != d1 || steps > n1) continue; // no good
// and by adding its digits to d2 in less than or equal to n2 steps.
value = SumToOneDigit(i, out steps);
if(value != d2 || steps > n2) continue; // no good
return i;
}
return -1; // no answer
}
static int MultiplyToOneDigit(int value, out int steps)
{
steps = 0;
while (value > 10)
{
value = MultiplyDigits(value);
steps++;
}
return value;
}
static int SumToOneDigit(int value, out int steps)
{
steps = 0;
while (value > 10)
{
value = SumDigits(value);
steps++;
}
return value;
}
static int MultiplyDigits(int value)
{
int acc = 1;
while (value > 0)
{
acc *= value % 10;
value /= 10;
}
return acc;
}
static int SumDigits(int value)
{
int total = 0;
while (value > 0)
{
total += value % 10;
value /= 10;
}
return total;
}
}
一个努力:)
现在一起做。您当然可以进行重构。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _17082903_smallest_greatest_number
{
class Program
{
static void Main(string[] args)
{
int N = 2344;
int n1 = 0;
int n2 = 0;
int d1 = SumDigits(N, ref n1);
int d2 = ProductDigits(N, ref n2);
bool sumFound = false, productFound = false;
for (int i = N + 1; i < 1000000000; i++)
{
if (!sumFound)
{
int stepsForSum = 0;
var res = SumDigits(i, ref stepsForSum);
if (res == d1 && stepsForSum <= n1)
{
Console.WriteLine("the smallest number for sum is: " + i);
Console.WriteLine(string.Format("sum result is {0} in {1} steps only", res, stepsForSum));
sumFound = true;
}
stepsForSum = 0;
}
if (!productFound)
{
int stepsForProduct = 0;
var res2 = ProductDigits(i, ref stepsForProduct);
if (res2 == d2 && stepsForProduct <= n2)
{
Console.WriteLine("the smallest number for product is: " + i);
Console.WriteLine(string.Format("product result is {0} in {1} steps only", res2, stepsForProduct));
productFound = true;
}
stepsForProduct = 0;
}
if (productFound && sumFound)
{
break;
}
}
}
static int SumDigits(int value, ref int numOfSteps)
{
int total = 0;
while (value > 0)
{
total += value % 10;
value /= 10;
}
numOfSteps++;
if (total < 10)
{
return total;
}
else
{
return SumDigits(total, ref numOfSteps);
}
}
static int ProductDigits(int value, ref int numOfSteps)
{
int total = 1;
while (value > 0)
{
total *= value % 10;
value /= 10;
}
numOfSteps++;
if (total < 10)
{
return total;
}
else
{
return ProductDigits(total, ref numOfSteps);
}
}
}
}