3

これが私が解決しようとしている問題です：http：//projecteuler.net/problem=20（100の数字の合計を見つけてください！）

数値タイプが2倍しかないLuaを使用しているので、手動でアプローチする必要がありました。問題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

問題は、の10進表現の長さが。の長さ(n+1)!より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の減算が必要になりますが、すべての係数に対して2つの除算で十分です。 ）。

于 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 に答える