python - Python - Project Euler #80，了解错误

Question

Project Euler 问题 #80 看起来很简单：

https://projecteuler.net/problem=80

使用十进制模块计算平方根到给定精度：

from decimal import Decimal, localcontext

def prob80():
    total = 0
    for x in range(1,100):
        with localcontext() as ctx:
            ctx.prec = 100
            total+=sum([int(i) for i in str(Decimal(x).sqrt())[2:]])
    return total
print prob80()

我返回 40308，据我了解，这与正确答案不符。对于前十个自然数的平方根的数字和，我返回：

0 475 441 0 472 470 397 463 0 456

这里的错误在哪里？我认为这归结为某种舍入误差，但我似乎无法解决。

Answer 1

http://blog.dreamshire.com/project-euler-80-solution/

首先，100 位数字包括小数点左右的数字。

其次，确保计算的位数超过必要的位数，以避免舍入错误，因为它会影响某些数字。

from decimal import Decimal, localcontext

def prob80():
    total = 0
    for x in range(1,100):
        print x
        with localcontext() as ctx:
            ctx.prec = 105
            if len(str(Decimal(x).sqrt())) == 1:
                total+=0
            else:
                a = sum([int(i) for i in str(Decimal(x).sqrt())[2:101]])+int(str(Decimal(x).sqrt())[0])
                total+=a
    return total
print prob80()

Answer 2

您犯了两个错误，在示例案例中相互抵消了。

1. 你没有计入第一位1
2. 您将精度设置得太低了一位数。最后一位几乎总是包含一些舍入误差。的第 100 位和第 101 位sqrt(2)是27，所以当你使用prec=100它时，它会向上取整3，弥补第一个错误。

顺便提一句。有一个简单的实现。Decimal对象有as_tuple()方法：

返回数字的命名元组表示：DecimalTuple(sign, digits, exponent)。

所以你可以去：

decimal.getcontext().prec = 101
i = 2
sum(decimal.Decimal(i).sqrt().as_tuple()[1][:100]) # [1] is `digits`; [:100] are 1st 100

不需要字符串转换或“iffing”。