欧拉计划 - 问题#20(Lua)

我已经编写了代码来解决这个问题,然而,它在某些情况下似乎是准确的,而在其他情况下不准确。当我尝试解决问题到10(答案在问题中给出,为27)时,我得到了27,正确的答案。然而,当我尝试解决给定的问题(100)时,我得到了64,错误的答案,因为答案是其他东西。

这是我的代码:

function factorial(num)
    if num>=1 then
        return num*factorial(num-1)
    else
        return 1
    end
end

function getSumDigits(str)
    str=string.format("%18.0f",str):gsub(" ","")
    local sum=0
    for i=1,#str do
        sum=sum+tonumber(str:sub(i,i))
    end
    return sum
end

print(getSumDigits(tostring(factorial(100))))

64

由于Lua将大数字转换为科学计数法,我不得不将其转换回标准记法。我认为这不是问题,但可能有问题。

有任何解释吗?

原文链接 https://stackoverflow.com/questions/9726586

点赞
stackoverflow用户577603
stackoverflow用户577603

很不幸,正确的解决方案更加困难。主要问题在于Lua使用64位浮点变量,这意味着 这个适用。

长话短说:64位浮点中的有效数字太少,无法存储像100!这样的数字。Lua的浮点数最多只能存储52个尾数位,因此任何大于2^52的数字都必然会出现舍入误差,只能保留15位左右的小数。要存储100!,需要至少158个小数。

由factorial()函数计算出的数字与100的实际值相当接近(即相对误差很小),但是为了得到正确的解决方案,您需要确切的值。

您需要做的是实现自己的算法来处理大数。我实际上通过将每个数字存储为表来使用Lua解决了该问题,在这里每个条目存储十进制数字的一个数字。完整的解决方案需要50行多一些的代码,因此并不太困难,是一个不错的练习。

2012-03-15 20:01:53