python - 为什么欧拉计划说我弄错了第 20 位？

Question

这是我要解决的问题:Euler 20 .

n! means n ⨉ (n - 1) ⨉ ... ⨉ 3 ⨉ 2 ⨉ 1

For example, 10! = 10 ⨉ 9 ⨉ ... ⨉ 3 ⨉ 2 ⨉ 1 = 3628800, and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

我试过这个:

y = 1  #The actual number
sum = 0 #The sum of its digits.

def factorial(x): #Calculates the number using a recursive factorial algorithm
    global y
    y = y*x
    if x > 1:
        factorial(x-1)
    else:
        return 0

factorial(100) #Calculate 100! and the function will put it in y.

def count(): #Calculates the sum.
    global y, sum
    while y > 0:
        currentDigit = int(y) % 10 #Find the remainder of the number gives the very last digit
        sum = sum + currentDigit #Add that to the total sum.
        y = int(y) / 10 #Divide y by 10 knocking of the 1s-digit place and putting the 10s digit in its place.
    return sum #return the sum.

print(count()) #print the count.

如果我执行 factorial(10) 而不是 100，我会得到 27，这是问题所说的我应该得到的，但是对于 factorial(100) 我会得到 675，这程序说错了。我做错了什么？我对 Python 不是很熟悉，如果我犯了一个愚蠢的错误，抱歉。

Answer 1

问题出在你对 count 的实现上，特别是这一行:

    y = int(y) / 10

自 Python 3 起，/ 为 true division .在 Python 2.2 及更高版本中，您可以使用 from __future__ import division 获取 Python 3 的除法行为。执行上述行后，y 是一个 float 。大多数系统上的 Python float 只有大约 15 个有效的小数位(sys.float_info.dig 将为您提供系统的精度；请注意，实际上有 53 个位精度，等于 53/log₂(10) ≈ 15.955)。 count 在那些有效数字之后提取的任何十进制数字都是舍入误差的结果，并且是将 base-2 float 转换为 base 10 的结果。在一定长度上，中间数字不会产生影响到 count 计算的总和。

[count(int('8' * 17 + str(k) + '0')) for k in range(1, 10)]
# [130, 130, 130, 130, 130, 130, 130, 130, 130]
import random
[count(int('8' * 17 + ('%05d' % random.randint(1,99999)) + '0')) for k in range(1, 10)]
# [146, 146, 146, 146, 146, 146, 146, 146, 146]

解决方案是使用//进行整数除法，此时也可以去掉int转换。当你这样做时，你还不如将 y 设为 count 的参数，并将 sum 设为局部。否则，您的全局 sum 变量将隐藏内置的 sum功能。

至于在 factorial 中取消全局 y，传递一个额外的参数很容易:

def factorial(x, p=1):
    p *= x
    if x > 1:
        return factorial(x-1, p)
    else:
        return p

这具有成为 tail-recursive 的优点.标准的 python 解释器不实现尾调用优化，但可以使用装饰器来完成。将这样的装饰器应用于 factorial，结果是一个不会导致堆栈溢出的函数。这种传递累加的技术可用于许多其他函数以创建尾递归函数。

或者，编写一个更像 Python 的迭代版本。