用函数或函数的递归实现求n!的算法。（主程序已给出）。同时估计程序的复杂度。 def fact(n): //函数代码 n=int(input("Calculate n! Enter n=")) print(n,'!=',fact(n))

以下是使用递归方式实现求n!的代码：

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

n = int(input("Calculate n! Enter n="))
print(n,'!=',fact(n))

该递归函数的时间复杂度为O(n)，因为在每次递归调用中，函数将会执行一次乘法和一次减法操作。因此，总共会执行n次。

相关问题

设计一个算法时间复杂度为O（n），求1!+2!+…+n!，写出一个代码，并叙述算法思想以及实现思路

设计一个算法计算从1到n的所有阶乘之和的时间复杂度为O(n)，可以使用动态规划的思想来实现，因为连续两个阶乘之间的差是一个整数倍，所以我们只需要存储前一项的阶乘即可避免重复计算。

算法思想：
1. 初始化一个变量sum，用于保存阶乘总和，初始值设为0。
2. 从1开始遍历到n，对于每个i，计算i的阶乘并加到sum上，同时更新sum的值。
3. 阶乘可以通过循环或者递归实现，这里为了效率考虑，我们采用循环来避免函数调用带来的开销。
4. 记录每个阶乘后直接累加到结果，不需要额外的空间复杂度。

Python代码实现：

def factorial_sum(n):
    sum_ = 0
    if n < 0:
        return "输入错误，阶乘只对非负整数定义"
    elif n == 0 or n == 1:
        return 1
    else:
        fact = 1
        for i in range(2, n + 1):
            fact *= i
            sum_ += fact
        return sum_

# 测试
print(factorial_sum(5)) # 输出: 153 (1! + 2! + ... + 5!)

计算e = 1 + 1/1!+1/ 2!+1/ 3!+…+1/n! 。要求：使最后一项 n! 1 ​ 的值小于等于给定的 ϵ 即可结束运算（注意：最后一项 n! 1 ​ 的值不计算在内），ϵ 的值从键盘输入

算法1：迭代计算

1. 初始化 e = 1，n = 1，fact = 1
2. 计算当前项 term = 1 / fact
3. 如果 term <= eps，则结束计算
4. 否则，将当前项加入 e 中，即 e = e + term
5. 将 n 加 1，fact 乘以 n，返回第 2 步

时间复杂度：O(n)

算法2：递归计算

1. 递归函数 f(n) 表示前 n 项的和
2. 如果 n = 0，则返回 1
3. 否则，返回 f(n-1) + 1 / n!

时间复杂度：O(n)

Python 代码：迭代计算

eps = float(input("请输入 eps："))
e, n, fact = 1, 1, 1
term = 1 / fact
while term > eps:
e += term
n += 1
fact *= n
term = 1 / fact
print("e 的值为：", e)

Python 代码：递归计算

def f(n):
if n == 0:
return 1
else:
return f(n-1) + 1 / fact(n)

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

eps = float(input("请输入 eps："))
e = f(0)
n = 1
while 1 / fact(n) > eps:
e += 1 / fact(n)
n += 1
print("e 的值为：", e)