欧拉计划问题#20的算法效率低下。

2015-1-22 18:59:49
收藏：0
阅读：182
评论：2

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

我正在使用Lua，它只有double作为数字类型，所以我不得不手动处理。我使用的代码与我用于类似的问题16的代码（查找2^1000中数字的总和）几乎相同。但是，这次问题似乎超出了我的算法在合理的时间内解决-在我必须等待超过10秒才能计算出下一个总和之前，它达到了32！，而到34！时，它需要比我等待的时间更长。有没有办法可以加快这个过程（使用“raw”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
点赞
用户1011995
用户1011995

你的问题在于 (n+1)! 的十进制表示长度可能比 n! 的长度多1以上。这在 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-21 01:06:39
用户1751920
用户1751920

试试这段简短的代码：

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

print sum(map(int,list(str(factorial(100)))))

将 100 的阶乘结果转换成字符串，然后将每个数字转化为整数并求和。

2014-06-28 00:44:38

作者:

用户1870451

用户1870451
推荐文章