FCTRL - SPOJ 上的因子

Question

任何人都可以帮助我解决我犯了什么错误吗？这仅仅是一个简单的问题来计算尾随零的阶乘。输出在 Ideone 上成功运行，但由于某种原因抛出&ldquo;错误的答案&rdquo;在 SPOJ 的编译器上。有人可以发现我犯的错误。using System;public class Test{    public static void Main(string[] args)    {        int numberOfValues = int.Parse(Console.ReadLine());        int[] values = new int[numberOfValues];        for(int i=0;i<numberOfValues;i++)        {            values[i] = int.Parse(Console.ReadLine());        }        for (int i = 0; i < numberOfValues; i++)        {            Console.WriteLine(calculateFact(values[i]));        }        Console.ReadKey();    }    static int calculateFact(int value)    {        int finalValue = 0;        for (int i = 0; value > 5; i++)        {            value = value / 5;            finalValue += value;        }        return finalValue;    }}

Answer 1

现在是实施和运行一些测试以找出“错误答案”的时候了：

using System.Linq;

using System.Numerics;

...

// Slow, ugly but easy to understand and check routine

static int naiveCount(int value) {

  BigInteger factorial = 1;

  for (int i = 1; i <= value; ++i)

    factorial *= i;

  return factorial.ToString().Length - factorial.ToString().TrimEnd('0').Length;

}

...

var counterExamples = Enumerable

  .Range(0, 100)

  .Select(v => new {

     value = v,

     actual = calculateFact(v),

     expected = naiveCount(v), })

  .Where(item => item.expected != item.actual)

  .Select(item => $"value: {item.value,4} actual: {item.actual,3} expected: {item.expected,3}");

Console.Write(string.Join(Environment.NewLine, counterExamples));

结果：

value:    5 actual:   0 expected:   1

value:   25 actual:   5 expected:   6

value:   26 actual:   5 expected:   6

value:   27 actual:   5 expected:   6

value:   28 actual:   5 expected:   6

value:   29 actual:   5 expected:   6

当有反例时，很容易调试实例calculateFact(5)案例。你现在能看出问题吗？它在for循环中：

for (int i = 0; value > 5; i++)

这应该是（>=而不是>）

for (int i = 0; value >= 5; i++)

编辑：从技术上讲，您所要做的就是检查以下各项的权力5：

static int calculateFact(int value) {

  int result = 0;

  // 13 loops = floor(log(2**31)/log(5))

  for (int power5 = 5; power5 <= int.MaxValue / 5; power5 *= 5) 

    result += value / power5;

  return result;

}

Answer 2

您可能会遇到内存不足错误。你不需要一个int[] values. 您可以在读取数字后立即计算阶乘。而且你不需要Console.ReadKey();. 请注意，我还没有检查calculateFact.

正如德米特里所指出的，你的功能是错误的......你“差一分”：

for (int i = 0; value >= 5; i++)

看到了>=吗？但是您可以通过删除i变量来加快速度。

static int calculateFact(int value)

{

    int finalValue = 0;

    while (true)

    {

        value /= 5;

        if (value == 0)

        {

            return finalValue;

        }

        finalValue += value;

    }

}

这应该是正确的，但我不确定它是否足够快（通常 SPOJ 问题基于“缓存”数据）