3

这是我要解决的问题：http://projecteuler.net/problem=20（找到 100 中的数字总和！）

我正在使用 Lua，它只有 double 作为数字类型，所以我不得不手动处理。我使用的代码几乎与我在问题 16 中使用的代码相同（找到 2^1000 中的数字总和）。然而，这一次问题似乎超出了我的算法在相当长的时间内解决的问题——它达到了大约 32 个！在我必须等待超过 10 秒才能计算下一个总数之前，然后是 34！它比我等待的时间更长。有什么办法可以加快速度（使用“原始”Lua - 而不是 LuaJIT 或类似的东西）？

local sum = {1}
for i=1,100 do
    local carry = 0
    for v=1,#sum do
        local c = carry
        carry = 0
        local t = sum[v] * i
        while t >= 10 do
            t = t - 10
            carry = carry + 1
        end
        local s = t + c
        while s >= 10 do
            s = s - 10
            carry = carry + 1
        end
        sum[v] = s
    end
    if carry > 0 then
        sum[#sum+1] = carry
    end
    print(""..i.."! = "..getCharactersReversed(sum))
end
4

2 回答 2

5

您的问题是 的十进制表示的长度(n+1)!可以比​​ 的长一倍以上n!。这首先发生在n == 14,

14! =   87178291200
15! = 1307674368000

因此在这里你的最终carry是 13 并且领先的“数字”大于 10。从那时起，这个问题变得越来越严重，打印出来#sum并且最终产生产量

15      11      13
16      12      20
17      13      35
18      14      64
19      15      121
20      16      243
21      17      510
22      18      1124
23      19      2585
24      20      6204
25      21      15511
26      22      40329
27      23      108888
28      24      304888
29      25      884176
30      26      2652528
31      27      8222838
32      28      26313083

通过逐步减法减少leading_number * i到小于 10 的数字需要越来越长的时间。在某些时候（估计大约 45），该值变得如此之大，以至于t - 10 == t您陷入了无限循环。LuaJIT 根本无济于事。

所以你必须确保你永远不会写一个大于 9 的数字，例如通过减少循环中的最后一个进位，就像前面的数字一样，并根据需要添加尽可能多的数字。这样做，程序运行没有明显的延迟。

if carry > 0 then
    local w = #sum+1
    local cc = 0
    while carry > 0 do
        while carry >= 10 do
            carry = carry - 10
            cc = cc + 1
        end
        sum[w] = carry
        w = w+1
        carry = cc
        cc = 0
    end
end

但是通过除法确定数字和进位要简洁得多，并且对于较大的因子也更有效（当将一个数字乘以 100 时，结果平均为 450，需要 45 次减法，但对于所有因子来说，两次除法就足够了）。

于 2012-07-21T01:06:39.287 回答
0

试试这个短代码：

    def factorial(n):
        return reduce(lambda x,y: x*y,[_ for _ in range(1,n+1)])

    print sum(map(int,list(str(factorial(100)))))
于 2014-06-28T00:44:38.583 回答