欧拉计划为什么说我得错了20号？

Question

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

n! 手段 n ? (n - 1) ? ... ? 3 ? 2 ? 1

例如,10! = 10 ? 9 ? ... ? 3 ? 2 ? 1 = 3628800和数字中的数字之和10!为3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

找到数字中的数字总和 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这就是我应该得到的问题,但我得到675,factorial(100)程序说错了.我做错了什么？我对Python并不熟悉,对不起,如果我犯了一个愚蠢的错误.

Answer 1

问题在于您的实施count,特别是线路:

    y = int(y) / 10

从Python 3开始,/就是真正的划分.在Python 2.2及更高版本中,您可以使用Python 3的除法行为from __future__ import division.执行上面的行后,y是一个浮点数.大多数系统上的Python浮点数只有大约15个有效十进制数字(sys.float_info.dig将为您提供系统的精度;请注意,实际上有53 位精度,等于53/log ₂(10)≈15.955).count在那些重要的数字之后提取的任何十进制数字是舍入误差的结果,并且是将基数2浮点数转换为基数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函数.

至于脱离了全球y的factorial,它很容易通过一个额外的参数:

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

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

或者,编写一个迭代版本,这是一个更加pythonic.