如何使我的阶乘函数更快更高效？

Question

我用列表做了阶乘计算函数

n = int(input("Enter a number: "))

def num2list(num):
    first = [int(i) for i in str(num)]
    return first

def multiplylists(x, y):
    listx = x
    listy = y
    value=0
    for n in range(len(listx)):
        for m in range(len(listy)):
            prod = listx[n]*listy[m]
            power=10**((len(listx)-n-1)+(len(listy)-m-1))
            value+=prod*power
    return(num2list(value))

def factorial(n):
    if n <= 1:
        return [1]

    return multiplylists(factorial(n-1), num2list(n))

print("the factorial of",n,"is",factorial(n))

这是大学项目，我认为教授的意图是使用 1000 之类的列表制作更快、更高效的阶乘函数！

但我的代码很慢，当数字 > 997

我遇到这样的错误

Enter a number: 1000
Traceback (most recent call last):
  File "part2.py", line 24, in <module>
    print("the factorial of",n,"is",factorial(n))
  File "part2.py", line 22, in factorial
    return multiplylists(factorial(n-1), num2list(n))
  File "part2.py", line 22, in factorial
    return multiplylists(factorial(n-1), num2list(n))
  File "part2.py", line 22, in factorial
    return multiplylists(factorial(n-1), num2list(n))
  [Previous line repeated 995 more times]
  File "part2.py", line 19, in factorial
    if n <= 1:
RecursionError: maximum recursion depth exceeded in comparison

我不知道为什么我的代码在数字 > 997 时出错

Answer 1

只需简单地在 O(n) 中迭代到运行。

n = 500
facts = [1]*(n+1)
for i in range(1,n+1):
   facts[i] = facts[i-1]*(i)

print(facts[n])

Answer 2

def fact(n):
if n==0:
    return 1
else:
    return (n * fact(n-1))


 x=fact(1000)
print(x)

Answer 3

由于最大递归深度，您将无法计算大于 1000 的阶乘（实际上更小，因为某些堆栈级别已被其他调用函数使用）

因此您需要实施迭代方法。要在列表中生成以数字表示的数字，以相反的顺序存储数字会更容易，这样数字的索引对应于它乘以的 10 的幂。您可以在打印或返回结果时颠倒列表以便于人阅读。

使用这种数字存储策略，乘法逻辑可以更加直接。您还应该在没有 "cheating" 的情况下使用 Python 的无限大小整数（例如 10**((len(listx)-n-1)+(len(listy)-m-1)）来实现它：

def toDigits(n):
    result = []
    while n:
        n,d = divmod(n,10)
        result.append(d)
    return result or [0]

def multDigits(A,B):
    result = [0]
    for i,a in enumerate(A):
        for j,b in enumerate(B):
            p10,carry = i+j,a*b 
            while carry:
                if p10 >= len(result): result.append(0); continue
                carry,result[p10] = divmod(carry+result[p10],10)
                p10 += 1
    return result

def factorial(N):
    result = [1]
    for n in range(2,N+1):
        result = multDigits(result,toDigits(n))
    return result[::-1]

输出：

print(factorial(1000))

[4, 0, 2, 3, 8, 7, 2, 6, 0, 0, 7, 7, 0, 9, 3, 7, 7, 3, 5, ...


# proof that it works:

from math import factorial
digits = [ int(d) for d in str(factorial(1000)) ]
print(digits)

[4, 0, 2, 3, 8, 7, 2, 6, 0, 0, 7, 7, 0, 9, 3, 7, 7, 3, 5, ...

Answer 4

Python中的sys模块提供了一个名为setrecursionlimit()的函数来修改Python中的递归限制。它有一个参数，新递归限制的值。

import sys 

sys.setrecursionlimit(10**6) 
def fact(n):  
    if(n == 0): 
        return 1 
    return n * fact(n - 1)

如何使我的阶乘函数更快更高效？

How to make my factorial function faster and efficient?

python

function

factorial