FCTRL - SPOJ 上的因子

Question

任何人都可以帮助我解决我犯了什么错误吗？这仅仅是一个简单的问题来计算尾随零的阶乘。

输出在 Ideone 上成功运行，但由于某种原因抛出

“错误的答案”

在 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 routinestatic int naiveCount(int value) {&nbsp; BigInteger factorial = 1;&nbsp; for (int i = 1; i <= value; ++i)&nbsp; &nbsp; factorial *= i;&nbsp; return factorial.ToString().Length - factorial.ToString().TrimEnd('0').Length;}...var counterExamples = Enumerable&nbsp; .Range(0, 100)&nbsp; .Select(v => new {&nbsp; &nbsp; &nbsp;value = v,&nbsp; &nbsp; &nbsp;actual = calculateFact(v),&nbsp; &nbsp; &nbsp;expected = naiveCount(v), })&nbsp; .Where(item => item.expected != item.actual)&nbsp; .Select(item => $"value: {item.value,4} actual: {item.actual,3} expected: {item.expected,3}");Console.Write(string.Join(Environment.NewLine, counterExamples));结果：value:&nbsp; &nbsp; 5 actual:&nbsp; &nbsp;0 expected:&nbsp; &nbsp;1value:&nbsp; &nbsp;25 actual:&nbsp; &nbsp;5 expected:&nbsp; &nbsp;6value:&nbsp; &nbsp;26 actual:&nbsp; &nbsp;5 expected:&nbsp; &nbsp;6value:&nbsp; &nbsp;27 actual:&nbsp; &nbsp;5 expected:&nbsp; &nbsp;6value:&nbsp; &nbsp;28 actual:&nbsp; &nbsp;5 expected:&nbsp; &nbsp;6value:&nbsp; &nbsp;29 actual:&nbsp; &nbsp;5 expected:&nbsp; &nbsp;6当有反例时，很容易调试实例calculateFact(5)案例。你现在能看出问题吗？它在for循环中：for (int i = 0; value > 5; i++)这应该是（>=而不是>）for (int i = 0; value >= 5; i++)编辑：从技术上讲，您所要做的就是检查以下各项的权力5：static int calculateFact(int value) {&nbsp; int result = 0;&nbsp; // 13 loops = floor(log(2**31)/log(5))&nbsp; for (int power5 = 5; power5 <= int.MaxValue / 5; power5 *= 5)&nbsp;&nbsp; &nbsp; result += value / power5;&nbsp; return result;}

Answer 2

您可能会遇到内存不足错误。你不需要一个int[] values. 您可以在读取数字后立即计算阶乘。而且你不需要Console.ReadKey();. 请注意，我还没有检查calculateFact.正如德米特里所指出的，你的功能是错误的......你“差一分”：for (int i = 0; value >= 5; i++)看到了>=吗？但是您可以通过删除i变量来加快速度。static int calculateFact(int value){&nbsp; &nbsp; int finalValue = 0;&nbsp; &nbsp; while (true)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; value /= 5;&nbsp; &nbsp; &nbsp; &nbsp; if (value == 0)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return finalValue;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; finalValue += value;&nbsp; &nbsp; }}这应该是正确的，但我不确定它是否足够快（通常 SPOJ 问题基于“缓存”数据）