7

我正在尝试计算数字序列中每个数字的数字乘积，例如：

21、22、23……98、99……

将会：

2, 4, 6 ... 72, 81 ..

为了降低复杂性，我会只考虑有限长度数字中的 [连续数字]，例如 from 001to999或 from 0001to 9999。

但是，例如，当序列很大时1000000000，重复提取数字然后对每个数字相乘将是低效的。

基本思想是跳过我们在计算过程中遇到的连续零，例如：

using System.Collections.Generic;
using System.Linq;
using System;

// note the digit product is not given with the iteration
// we would need to provide a delegate for the calculation
public static partial class NumericExtensions {
    public static void NumberIteration(
            this int value, Action<int, int[]> delg, int radix=10) {
        var digits=DigitIterator(value, radix).ToArray();
        var last=digits.Length-1;
        var emptyArray=new int[] { };
        var pow=(Func<int, int, int>)((x, y) => (int)Math.Pow(x, 1+y));
        var weights=Enumerable.Repeat(radix, last-1).Select(pow).ToArray();

        for(int complement=radix-1, i=value, j=i; i>0; i-=1)
            if(i>j)
                delg(i, emptyArray);
            else if(0==digits[0]) {
                delg(i, emptyArray);

                var k=0;

                for(; k<last&&0==digits[k]; k+=1)
                    ;

                var y=(digits[k]-=1);

                if(last==k||0!=y) {
                    if(0==y) { // implied last==k
                        digits=new int[last];
                        last-=1;
                    }

                    for(; k-->0; digits[k]=complement)
                        ;
                }
                else {
                    j=i-weights[k-1];
                }
            }
            else {
                // receives digits of a number which doesn't contain zeros 
                delg(i, digits);

                digits[0]-=1;
            }

        delg(0, emptyArray);
    }

    static IEnumerable<int> DigitIterator(int value, int radix) {
        if(-2<radix&&radix<2)
            radix=radix<0?-2:2;

        for(int remainder; 0!=value; ) {
            value=Math.DivRem(value, radix, out remainder);
            yield return remainder;
        }
    }
}

此处仅用于数字的枚举，为避免包含零的数字首先被计算，数字乘积尚未由代码给出；但是通过提供委托来执行计算来生成数字产品仍然需要时间。

如何有效地计算连续数字的数字积？

4

7 回答 7

5

编辑：“从任何地方开始，扩展范围”版本......

这个版本有一个显着扩展的范围，因此返回一个IEnumerable<long>而不是一个IEnumerable<int>- 将足够多的数字相乘并超过int.MaxValue. 它也上升到 10,000,000,000,000,000 - 不是完整的范围long，但相当大:) 你可以从任何你喜欢的地方开始，它会从那里一直持续到结束。

class DigitProducts
{
    private static readonly int[] Prefilled = CreateFirst10000();

    private static int[] CreateFirst10000()
    {
        // Inefficient but simple, and only executed once.
        int[] values = new int[10000];
        for (int i = 0; i < 10000; i++)
        {
            int product = 1;
            foreach (var digit in i.ToString())
            {
                product *= digit -'0';
            }
            values[i] = product;
        }
        return values;
    }

    public static IEnumerable<long> GetProducts(long startingPoint)
    {
        if (startingPoint >= 10000000000000000L || startingPoint < 0)
        {
            throw new ArgumentOutOfRangeException();
        }
        int a = (int) (startingPoint / 1000000000000L);
        int b = (int) ((startingPoint % 1000000000000L) / 100000000);
        int c = (int) ((startingPoint % 100000000) / 10000);
        int d = (int) (startingPoint % 10000);

        for (; a < 10000; a++)
        {
            long aMultiplier = a == 0 ? 1 : Prefilled[a];
            for (; b < 10000; b++)
            {
                long bMultiplier = a == 0 && b == 0 ? 1
                                 : a != 0 && b < 1000 ? 0
                                 : Prefilled[b];
                for (; c < 10000; c++)
                {
                    long cMultiplier = a == 0 && b == 0 && c == 0 ? 1
                                     : (a != 0 || b != 0) && c < 1000 ? 0
                                     : Prefilled[c];

                    long abcMultiplier = aMultiplier * bMultiplier * cMultiplier;
                    for (; d < 10000; d++)
                    {
                        long dMultiplier = 
                            (a != 0 || b != 0 || c != 0) && d < 1000 ? 0
                            : Prefilled[d];
                        yield return abcMultiplier * dMultiplier;
                    }
                    d = 0;
                }
                c = 0;
            }
            b = 0;
        }
    }
}

编辑：性能分析

我没有详细查看性能，但我相信此时大部分工作只是简单地迭代超过十亿个值。一个仅返回值本身的简单for循环在我的笔记本电脑上需要超过 5 秒，而迭代数字产品只需要 6 秒多一点，所以我认为没有更多优化空间 - 如果你想从开始。如果您想（有效地）从不同的位置开始，则需要进行更多的调整。

好的，这是一个尝试，它使用迭代器块来产生结果，并预先计算前一千个结果以使事情变得更快。

我已经测试了大约1.5亿，到目前为止它是正确的。它只返回前十亿个结果——如果你需要更多，你可以在最后添加另一个块......

static IEnumerable<int> GetProductDigitsFast()
{
    // First generate the first 1000 values to cache them.
    int[] productPerThousand = new int[1000];

    // Up to 9
    for (int x = 0; x < 10; x++)
    {
        productPerThousand[x] = x;
        yield return x;
    }
    // Up to 99
    for (int y = 1; y < 10; y++)
    {
        for (int x = 0; x < 10; x++)
        {
            productPerThousand[y * 10 + x] = x * y;
            yield return x * y;
        }
    }
    // Up to 999
    for (int x = 1; x < 10; x++)
    {
        for (int y = 0; y < 10; y++)
        {
            for (int z = 0; z < 10; z++)
            {
                int result = x * y * z;
                productPerThousand[x * 100 + y * 10 + z] = x * y * z;
                yield return result;
            }
        }
    }

    // Now use the cached values for the rest
    for (int x = 0; x < 1000; x++)
    {
        int xMultiplier = x == 0 ? 1 : productPerThousand[x];
        for (int y = 0; y < 1000; y++)
        {
            // We've already yielded the first thousand
            if (x == 0 && y == 0)
            {
                continue;
            }
            // If x is non-zero and y is less than 100, we've
            // definitely got a 0, so the result is 0. Otherwise,
            // we just use the productPerThousand.
            int yMultiplier = x == 0 || y >= 100 ? productPerThousand[y]
                                                 : 0;
            int xy = xMultiplier * yMultiplier;
            for (int z = 0; z < 1000; z++)
            {
                if (z < 100)
                {
                    yield return 0;
                }
                else
                {
                    yield return xy * productPerThousand[z];
                }
            }
        }
    }
}

我已经通过将它与一个非常天真的版本的结果进行比较来测试它：

static IEnumerable<int> GetProductDigitsSlow()
{
    for (int i = 0; i < 1000000000; i++)
    {
        int product = 1;
        foreach (var digit in i.ToString())
        {
            product *= digit -'0';
        }
        yield return product;
    }
}

希望这个想法有点用......我不知道它与这里显示的其他人相比在性能方面如何。

编辑：稍微扩展一下，使用我们知道结果为 0 的简单循环，我们最终需要担心的条件更少，但由于某种原因，它实际上稍微慢了一点。（这真的让我吃惊。）这段代码更长，但可能更容易理解。

static IEnumerable<int> GetProductDigitsFast()
{
    // First generate the first 1000 values to cache them.
    int[] productPerThousand = new int[1000];

    // Up to 9
    for (int x = 0; x < 10; x++)
    {
        productPerThousand[x] = x;
        yield return x;
    }
    // Up to 99
    for (int y = 1; y < 10; y++)
    {
        for (int x = 0; x < 10; x++)
        {
            productPerThousand[y * 10 + x] = x * y;
            yield return x * y;
        }
    }
    // Up to 999
    for (int x = 1; x < 10; x++)
    {
        for (int y = 0; y < 10; y++)
        {
            for (int z = 0; z < 10; z++)
            {
                int result = x * y * z;
                productPerThousand[x * 100 + y * 10 + z] = x * y * z;
                yield return result;
            }
        }
    }

    // Use the cached values up to 999,999
    for (int x = 1; x < 1000; x++)
    {
        int xMultiplier = productPerThousand[x];
        for (int y = 0; y < 100; y++)
        {
            yield return 0;
        }
        for (int y = 100; y < 1000; y++)
        {
            yield return xMultiplier * y;
        }
    }

    // Now use the cached values for the rest
    for (int x = 1; x < 1000; x++)
    {
        int xMultiplier = productPerThousand[x];
        // Within each billion, the first 100,000 values will all have
        // a second digit of 0, so we can just yield 0.
        for (int y = 0; y < 100 * 1000; y++)
        {
            yield return 0;
        }
        for (int y = 100; y < 1000; y++)
        {
            int yMultiplier = productPerThousand[y];
            int xy = xMultiplier * yMultiplier;
            // Within each thousand, the first 100 values will all have
            // an anti-penulimate digit of 0, so we can just yield 0.
            for (int z = 0; z < 100; z++)
            {
                yield return 0;
            }
            for (int z = 100; z < 1000; z++)
            {
                yield return xy * productPerThousand[z];
            }
        }
    }
}
于 2013-07-19T18:19:14.567 回答
4

您可以使用以下递归公式以类似 dp 的方式执行此操作：

n                   n <= 9
a[n/10] * (n % 10)  n >= 10

其中a[n]是 的数字相乘的结果n。

这导致了一个简单的O(n)算法：在计算时f(n)假设您已经计算f(·)了较小的n，您可以只使用所有数字的结果，但最后一个数字乘以最后一个数字。

a = range(10)
for i in range(10, 100):
    a.append(a[i / 10] * (i % 10))

a[n - 1] + a[n / 10]您只需在最后一位不是的数字上加上 do ，就可以摆脱昂贵的乘法0。

于 2013-07-11T08:05:26.097 回答
4

效率的关键不是枚举数字并提取数字，而是枚举数字并生成数字。

int[] GenerateDigitProducts( int max )
{
    int sweep = 1;
    var results = new int[max+1];
    for( int i = 1; i <= 9; ++i ) results[i] = i;
    // loop invariant: all values up to sweep * 10 are filled in
    while (true) {
        int prior = results[sweep];
        if (prior > 0) {
            for( int j = 1; j <= 9; ++j ) {
                int k = sweep * 10 + j; // <-- the key, generating number from digits is much faster than decomposing number into digits
                if (k > max) return results;
                results[k] = prior * j;
                // loop invariant: all values up to k are filled in
            }
        }
        ++sweep;
    }
}

由调用者来忽略小于的结果min。

这是使用分支绑定修剪技术的低空间版本：

static void VisitDigitProductsImpl(int min, int max, System.Action<int, int> visitor, int build_n, int build_ndp)
{
    if (build_n >= min && build_n <= max) visitor(build_n, build_ndp);

    // bound
    int build_n_min = build_n;
    int build_n_max = build_n;

    do {
        build_n_min *= 10;
        build_n_max *= 10;
        build_n_max +=  9;

        // prune
        if (build_n_min > max) return;
    } while (build_n_max < min);

    int next_n = build_n * 10;
    int next_ndp = 0;
    // branch
    // if you need to visit zeros as well: VisitDigitProductsImpl(min, max, visitor, next_n, next_ndp);
    for( int i = 1; i <= 9; ++i ) {
        next_n++;
        next_ndp += build_ndp;
        VisitDigitProductsImpl(min, max, visitor, next_n, next_ndp);
    }

}

static void VisitDigitProducts(int min, int max, System.Action<int, int> visitor)
{
    for( int i = 1; i <= 9; ++i )
        VisitDigitProductsImpl(min, max, visitor, i, i);
}
于 2013-07-13T23:57:29.890 回答
2

我最终得到了非常简单的代码，如下所示：

  • 代码：

    public delegate void R(
    R delg, int pow, int rdx=10, int prod=1, int msd=0);

R digitProd=
    default(R)!=(digitProd=default(R))?default(R):
    (delg, pow, rdx, prod, msd) => {
        var x=pow>0?rdx:1;

        for(var call=(pow>1?digitProd:delg); x-->0; )
            if(msd>0)
                call(delg, pow-1, rdx, prod*x, msd);
            else
                call(delg, pow-1, rdx, x, x);
    };

    msd是最高位，它就像二进制中的最高位。

我没有选择使用迭代器模式的原因是它比方法调用需要更多的时间。完整的代码（带测试）放在这个答案的后面。

请注意，该行default(R)!=(digitProd=default(R))?default(R): ...仅用于digitProd分配 ，因为在分配之前不能使用委托。我们实际上可以写成：

  • 替代语法：

    var digitProd=default(R);

digitProd=
    (delg, pow, rdx, prod, msd) => {
        var x=pow>0?rdx:1;

        for(var call=(pow>1?digitProd:delg); x-->0; )
            if(msd>0)
                call(delg, pow-1, rdx, prod*x, msd);
            else
                call(delg, pow-1, rdx, x, x);
    };

这种实现的缺点是它不能从一个特定的数字开始，而是从最大的全位数开始。

我有一些简单的想法可以解决：

  1. 递归

    delegate( Action)R是一个递归委托定义，用作尾调用递归，用于算法和接收数字乘积结果的委托。

    下面的其他想法解释了为什么递归。

  2. 没有划分

    对于连续的数字，使用除法提取每个数字被认为是低效率的，因此我选择以递减的方式直接对数字进行操作。

    例如，使用 3 位数字123，它是从 开始的 3 位数字之一999：

    9 8 7 6 5 4 3 2 [1] 0 -- 第一级递归

    9 8 7 6 5 4 3 [2] 1 0 -- 第二级递归

    9 8 7 6 5 4 [3] 2 1 0 -- 第三级递归

  3. 不要缓存

    正如我们所看到的，这个答案

    如何有效地将数字中的每个数字相乘

    建议使用缓存的机制，但是对于连续的数字，我们不使用，因为它是缓存。

    对于数字123, 132, 213, 231, 312, 321，数字产品是相同的。因此对于缓存，我们可以减少要存储的只有相同数字但顺序（排列）不同的项目，我们可以将它们视为相同的键。

    但是，对数字进行排序也需要时间。通过HashSet实施的密钥集合，我们为更多的项目支付更多的存储空间；即使我们减少了项目，我们仍然花时间进行平等比较。似乎没有比使用其值进行相等比较更好的散列函数了，而这正是我们正在计算的结果。例如，两位数的乘法表中，除了0和1之外，只有36种组合。

    因此，只要计算足够高效，我们可以认为算法本身就是一个虚拟缓存，而不需要存储。

  4. 减少计算包含零的数字的时间

    对于连续数的位数积，我们会遇到：

    每 10 个 1 个零

    每 100 个连续 10 个零

    每 1000 个连续 100 个零

    等等。请注意，我们仍然会遇到 9 个per 10零per 100。可以使用以下代码计算零的计数：

    static int CountOfZeros(int n, int r=10) {
    var powerSeries=n>0?1:0;

    for(var i=0; n-->0; ++i) {
        var geometricSeries=(1-Pow(r, 1+n))/(1-r);
        powerSeries+=geometricSeries*Pow(r-1, 1+i);
    }

    return powerSeries;
}

    Forn是位数，r是基数。该数字将是从几何级数计算的幂级数，对于.0

    例如，4位数字，我们会遇到的零是：

    (1)+(((1*9)+11)*9+111)*9 = (1)+(1*9*9*9)+(11*9*9)+(111*9) = 2620

    对于这个实现，我们并没有真正跳过数字包含零的计算。原因是浅层递归的结果被递归实现重用，我们可以将其视为缓存。可以在执行之前检测并避免与单个零相乘的尝试，我们可以将零直接传递给下一级递归。但是，仅乘法不会对性能造成太大影响。

完整代码：

public static partial class TestClass {
    public delegate void R(
        R delg, int pow, int rdx=10, int prod=1, int msd=0);

    public static void TestMethod() {
        var power=9;
        var radix=10;
        var total=Pow(radix, power);

        var value=total;
        var count=0;

        R doNothing=
            (delg, pow, rdx, prod, msd) => {
            };

        R countOnly=
            (delg, pow, rdx, prod, msd) => {
                if(prod>0)
                    count+=1;
            };

        R printProd=
            (delg, pow, rdx, prod, msd) => {
                value-=1;
                countOnly(delg, pow, rdx, prod, msd);
                Console.WriteLine("{0} = {1}", value.ToExpression(), prod);
            };

        R digitProd=
            default(R)!=(digitProd=default(R))?default(R):
            (delg, pow, rdx, prod, msd) => {
                var x=pow>0?rdx:1;

                for(var call=(pow>1?digitProd:delg); x-->0; )
                    if(msd>0)
                        call(delg, pow-1, rdx, prod*x, msd);
                    else
                        call(delg, pow-1, rdx, x, x);
            };

        Console.WriteLine("--- start --- ");

        var watch=Stopwatch.StartNew();
        digitProd(printProd, power);
        watch.Stop();

        Console.WriteLine("  total numbers: {0}", total);
        Console.WriteLine("          zeros: {0}", CountOfZeros(power-1));

        if(count>0)
            Console.WriteLine("      non-zeros: {0}", count);

        var seconds=(decimal)watch.ElapsedMilliseconds/1000;
        Console.WriteLine("elapsed seconds: {0}", seconds);
        Console.WriteLine("--- end --- ");
    }

    static int Pow(int x, int y) {
        return (int)Math.Pow(x, y);
    }

    static int CountOfZeros(int n, int r=10) {
        var powerSeries=n>0?1:0;

        for(var i=0; n-->0; ++i) {
            var geometricSeries=(1-Pow(r, 1+n))/(1-r);
            powerSeries+=geometricSeries*Pow(r-1, 1+i);
        }

        return powerSeries;
    }

    static String ToExpression(this int value) {
        return (""+value).Select(x => ""+x).Aggregate((x, y) => x+"*"+y);
    }
}

在代码中，doNothing, countOnly,printProd是当我们得到数字乘积的结果时要做什么，我们可以将它们中的任何一个传递给digitProd实现了完整算法的任何一个。例如，digitProd(countOnly, power)只会增加count，最终结果将与CountOfZeros返回相同。

于 2013-07-11T07:31:40.073 回答
2

从前一个计算产品

因为数字是连续的，在大多数情况下，您可以通过仅检查单位位置从前一个产品生成一个产品。

例如：

12345 = 1 * 2 * 3 * 4 * 5 = 120

12346 = 1 * 2 * 3 * 4 * 6 = 144

但是，一旦您计算出 12345 的值，您就可以将 12346 计算为(120 / 5) * 6。

显然，如果以前的产品为零，这将不起作用。它在从 9 到 10 换行时确实有效，因为新的最后一位数字为零，但无论如何您都可以优化这种情况（见下文）。

如果您要处理大量数字，即使涉及除法，这种方法也可以节省大量资金。

处理零

当您遍历值以生成产品时，一旦遇到零，您就知道产品将为零。

例如，对于四位数字，一旦达到 1000，您就知道到 1111 的产品都将为零，因此无需计算这些。

极致效率

当然，如果您愿意或能够预先生成和缓存所有值，那么您可以在 O(1) 中检索它们。此外，由于它是一次性成本，因此在这种情况下，用于生成它们的算法的效率可能不太重要。

于 2013-07-13T23:19:38.700 回答
1

根据数字的长度和序列的长度是否会进行一些优化。

由于您可以限制数字的最大大小，您可以通过增加模数来迭代数字本身。

假设您有数字 42：

var Input = 42;
var Product = 1;
var Result = 0;

// Iteration - step 1: 
Result = Input % 10; // = 2
Input -= Result;
Product *= Result;

// Iteration - step 2:
Result = Input % 100 / 10; // = 4
Input -= Result;
Product *= Result;

您可以将此操作打包到一个不错的循环中，该循环可能足够小以适合处理器缓存并迭代整个数字。当您避免任何函数调用时，这可能也非常快。

如果您想将零作为中止标准，那么实现这一点显然很容易。

正如Matthew 已经说过的：通过查找表将获得终极性能和效率。

你的序号范围越小，查表越快；因为它将从缓存中检索，而不是从慢速内存中检索。

于 2013-07-16T07:49:50.000 回答
1

我将创建一个表示数字的十进制数字的数组，然后像在现实生活中一样增加该数字（即在溢出时增加更重要的数字）。

从那里我会使用一系列可以用作小型查找表的产品。

例如，数字 314 将导致产品数组：3、3、12 数字 345 将导致产品数组：3、12、60

现在，如果你增加十进制数，你只需要重新计算最右边的乘积乘以左边的乘积。当第二个数字被修改时，您只需要重新计算两个产品（右边的第二个和最右边的产品）。这样，您将永远不会计算超过绝对必要的量，并且您有一个非常小的查找表。

因此，如果您从数字 321 开始并递增，则：

digits = 3, 2, 1      products = 3, 6, 6
incrementing then changes the outer right digit and therefore only the outer right product is recalculated
digits = 3, 2, 2      products = 3, 6, 12
This goes up until the second digit is incremented:
digits = 3, 3, 0      products = 3, 9, 0 (two products recalculated)

这是一个展示这个想法的例子（不是很好的代码，但只是作为一个例子）：

using System;
using System.Diagnostics;

namespace Numbers2
{
    class Program
    {
        /// <summary>
        /// Maximum of supported digits. 
        /// </summary>
        const int MAXLENGTH = 20;
        /// <summary>
        /// Contains the number in a decimal format. Index 0 is the righter number. 
        /// </summary>
        private static byte[] digits = new byte[MAXLENGTH];
        /// <summary>
        /// Contains the products of the numbers. Index 0 is the righther number. The left product is equal to the digit on that position. 
        /// All products to the right (i.e. with lower index) are the product of the digit at that position multiplied by the product to the left.
        /// E.g.
        /// 234 will result in the product 2 (=first digit), 6 (=second digit * 2), 24 (=third digit * 6)
        /// </summary>
        private static long[] products = new long[MAXLENGTH];
        /// <summary>
        /// The length of the decimal number. Used for optimisation. 
        /// </summary>
        private static int currentLength = 1;
        /// <summary>
        /// The start value for the calculations. This number will be used to start generated products. 
        /// </summary>
        const long INITIALVALUE = 637926372435;
        /// <summary>
        /// The number of values to calculate. 
        /// </summary>
        const int NROFVALUES = 10000;

        static void Main(string[] args)
        {
            Console.WriteLine("Started at " + DateTime.Now.ToString("HH:mm:ss.fff"));

            // set value and calculate all products
            SetValue(INITIALVALUE);
            UpdateProducts(currentLength - 1);

            for (long i = INITIALVALUE + 1; i <= INITIALVALUE + NROFVALUES; i++)
            {
                int changedByte = Increase();

                Debug.Assert(changedByte >= 0);

                // update the current length (only increase because we're incrementing)
                if (changedByte >= currentLength) currentLength = changedByte + 1;

                // recalculate products that need to be updated
                UpdateProducts(changedByte);

                //Console.WriteLine(i.ToString() + " = " + products[0].ToString());
            }
            Console.WriteLine("Done at " + DateTime.Now.ToString("HH:mm:ss.fff"));
            Console.ReadLine();
        }

        /// <summary>
        /// Sets the value in the digits array (pretty blunt way but just for testing)
        /// </summary>
        /// <param name="value"></param>
        private static void SetValue(long value)
        {
            var chars = value.ToString().ToCharArray();

            for (int i = 0; i < MAXLENGTH; i++)
            {
                int charIndex = (chars.Length - 1) - i;
                if (charIndex >= 0)
                {
                    digits[i] = Byte.Parse(chars[charIndex].ToString());
                    currentLength = i + 1;
                }
                else
                {
                    digits[i] = 0;
                }
            }
        }

        /// <summary>
        /// Recalculate the products and store in products array
        /// </summary>
        /// <param name="changedByte">The index of the digit that was changed. All products up to this index will be recalculated. </param>
        private static void UpdateProducts(int changedByte)
        {
            // calculate other products by multiplying the digit with the left product
            bool previousProductWasZero = false;
            for (int i = changedByte; i >= 0; i--)
            {
                if (previousProductWasZero)
                {
                    products[i] = 0;
                }
                else
                {
                    if (i < currentLength - 1)
                    {
                        products[i] = (int)digits[i] * products[i + 1];
                    }
                    else
                    {
                        products[i] = (int)digits[i];
                    }
                    if (products[i] == 0)
                    {
                        // apply 'zero optimisation'
                        previousProductWasZero = true;
                    }
                }
            }
        }

        /// <summary>
        /// Increases the number and returns the index of the most significant byte that changed. 
        /// </summary>
        /// <returns></returns>
        private static int Increase()
        {
            digits[0]++;
            for (int i = 0; i < MAXLENGTH - 1; i++)
            {
                if (digits[i] == 10)
                {
                    digits[i] = 0;
                    digits[i + 1]++;
                }
                else
                {
                    return i;
                }
            }
            if (digits[MAXLENGTH - 1] == 10)
            {
                digits[MAXLENGTH - 1] = 0;
            }
            return MAXLENGTH - 1;
        }
    }
}

这种方法计算 1000 亿范围内的数字的乘积几乎与计算 1 到 1000 的数字一样快。

顺便说一句，我很好奇你想用这一切做什么？

于 2013-07-17T10:20:14.790 回答