实验一 阶乘

一、实验目的和要求

熟悉一种编程环境及基础编程练习

二、实验内容

准备并熟悉后续实验项目所用的环境，熟悉一种编程语言的使用方式，并编写简单的求数的阶乘的程序，并通过输入 3、5、7、 10 等数值验证程序的正确性

三、主要仪器设备

  • 计算机
  • 编程语言：Python

四、实验方法与步骤

  1. 打开编程环境，编写程序
  2. 通过输入 3、5、7、 10 等数值验证程序的正确性

五、主要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
i = input("请输入一个整数：")
i = int(i)


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


print("Powered by W1ndys")
print("https://blog.w1ndys.top/")


print(f"结果是：{jiecheng(i)}")

print("—————————以下是验证值—————————")
print("3的阶乘是：", jiecheng(3))
print("5的阶乘是：", jiecheng(5))
print("7的阶乘是：", jiecheng(7))
print("10的阶乘是：", jiecheng(10))

六、实验数据处理及结果分析

  • 分析内容中可以使用文字和图片，可以贴实验过程和实验运行结果的截图或照片作为补充

输出结果

1
2
3
4
5
6
7
8
9
请输入一个整数：5
Powered by W1ndys
https://blog.w1ndys.top/
结果是：120
—————————以下是验证值—————————
3的阶乘是： 6
5的阶乘是： 120
7的阶乘是： 5040
10的阶乘是： 3628800

七、出现的问题及解决方法

  • 无

八、讨论、心得体会

  • Python 递归算法，简单易懂，但在 Python 的 math 库中，已经内置了阶乘函数，可以直接使用 math.factorial(n) 来计算 n 的阶乘。

实验二 斐波那契数列

一、实验目的和要求

理解递归概念及递归算法设计方法。对 Fibonacci 数列的求解问题分别设计递归的程序和非递归程序，并通过输入参数分别运行求解 Fibonacci10、20、30、40、 50 的程序比较两种策略编写的程序的运行速度。

二、实验内容

  • 对 Fibonacci 数列的求解问题分别设计递归的程序和非递归程序，并通过输入参数分别运行求解 Fibonacci10、20、30、40、 50 的程序比较两种策略编写的程序的运行速度。

三、主要仪器设备

  • 计算机
  • 编程语言：Python

四、实验方法与步骤

  1. 打开编程环境，编写程序
  2. 通过输入参数分别运行求解 Fibonacci10、20、30、40、 50 的程序比较两种策略编写的程序的运行速度

五、主要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import time


# 递归求斐波那契数列（带记忆化）
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
        return memo[n]


# 非递归求斐波那契数列
def fibonacci_non_recursive(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        a, b = 0, 1
        for _ in range(2, n + 1):
            a, b = b, a + b
        return b


# 测试递归求斐波那契数列的速度
for n in [10, 20, 30, 40, 50]:
    start_time = time.time()
    print(f"斐波那契数列的第 {n} 项的计算结果如下：")
    print(f"递归求解结果：{fibonacci(n)}")
    end_time = time.time()
    print(f"递归求解耗时: {end_time - start_time} 秒")

    # 测试非递归求斐波那契数列的速度
    start_time = time.time()
    print(f"非递归求解结果：{fibonacci_non_recursive(n)}")
    end_time = time.time()
    print(f"非递归求解耗时: {end_time - start_time} 秒")
    print()

六、实验数据处理及结果分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
斐波那契数列的第 10 项的计算结果如下：
递归求解结果：55
递归求解耗时: 0.002044677734375 秒
非递归求解结果：55
非递归求解耗时: 0.0 秒

斐波那契数列的第 20 项的计算结果如下：
递归求解结果：6765
递归求解耗时: 0.0 秒
非递归求解结果：6765
非递归求解耗时: 0.0 秒

斐波那契数列的第 30 项的计算结果如下：
递归求解结果：832040
递归求解耗时: 0.0 秒
非递归求解结果：832040
非递归求解耗时: 0.0 秒

斐波那契数列的第 40 项的计算结果如下：
递归求解结果：102334155
递归求解耗时: 0.0004742145538330078 秒
非递归求解结果：102334155
非递归求解耗时: 0.0 秒

斐波那契数列的第 50 项的计算结果如下：
递归求解结果：12586269025
递归求解耗时: 0.0 秒
非递归求解结果：12586269025
非递归求解耗时: 0.0 秒

七、出现的问题及解决方法

  • 原版斐波那契数列太慢，优化算法

八、讨论、心得体会

  • 斐波那契数列的递归算法虽然简单易懂，但效率低下，时间复杂度为 O(2^n)，空间复杂度为 O(n)。非递归算法效率更高，时间复杂度为 O(n)，空间复杂度为 O(1)。