实验一 阶乘

一、实验目的和要求

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

二、实验内容

准备并熟悉后续实验项目所用的环境，熟悉一种编程语言的使用方式，并编写简单的求数的阶乘的程序，并通过输入 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)。

实验三 贪心算法

一、实验目的和要求

本实验的目的是通过实现一个贪心算法来解决会议安排问题。要求是编写一个函数，能够在给定的会议开始和结束时间中，选择最多数量的会议，使得它们之间没有时间冲突。

二、实验内容

  1. 理解贪心算法的基本原理。
  2. 实现一个函数来选择最多数量的会议。
  3. 测试该函数以验证其正确性。

三、主要仪器设备

  • 计算机

四、实验方法与步骤

  1. 分析问题：确定如何使用贪心算法来解决会议安排问题。
  2. 设计算法：根据会议的结束时间对会议进行排序。
  3. 实现代码：编写 Python 代码来实现该算法。
  4. 测试代码：使用示例数据测试代码的正确性。

五、主要代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def max_meetings(start_times, end_times):
    # 将会议按结束时间排序
    meetings = sorted(zip(start_times, end_times), key=lambda x: x[1])

    # 初始化
    last_end_time = 0
    selected_meetings = []

    # 选择会议
    for start, end in meetings:
        if start >= last_end_time:
            selected_meetings.append((start, end))
            last_end_time = end

    return selected_meetings


# 示例输入
start_times = [1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12]
end_times = [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

# 获取最大可安排会议
result = max_meetings(start_times, end_times)
print("可安排的会议:", result)

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

在实验中，我们使用了一组示例数据来测试代码。结果显示，算法能够正确选择最多数量的会议，并且这些会议之间没有时间冲突。通过对比手动计算的结果，验证了代码的正确性。

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

在实现过程中，可能会遇到以下问题：

  • 问题：排序时未考虑会议的结束时间。

    • 解决方法：确保在排序时使用会议的结束时间作为关键字。

  • 问题：未正确更新最后一个会议的结束时间。

    • 解决方法：在每次选择会议后，更新 last_end_time 变量。

八、讨论、心得体会

通过本次实验，我加深了对贪心算法的理解。贪心算法在解决某些优化问题时非常有效，尤其是当问题可以分解为一系列局部最优解时。通过实践，我也体会到算法设计中细节的重要性，尤其是在处理边界条件时。

实验四合并排序

一、 实验目的和要求

本实验的目的是通过实现合并排序算法，掌握分治法的基本思想和递归编程技巧。要求学生能够理解并实现合并排序算法，并对其时间复杂度和空间复杂度进行分析。

二、 实验内容

  1. 理论学习：学习合并排序算法的基本原理和实现方法。
  2. 代码实现：编写合并排序算法的 Python 代码。
  3. 测试与验证：对编写的代码进行测试，验证其正确性和效率。
  4. 结果分析：分析排序结果，讨论算法的优缺点。

三、 主要仪器设备

  • 计算机
  • Python 编程环境

四、 实验方法与步骤

  1. 理论学习

    • 阅读教材或参考资料，了解合并排序算法的基本原理。
    • 理解分治法的思想和递归的实现方法。

  2. 代码实现

    • 打开 Python 编程环境，创建一个新的 Python 文件。
    • 编写合并排序算法的代码，确保代码结构清晰，注释详细。

  3. 测试与验证

    • 准备一组无序数组作为测试数据。
    • 运行编写的合并排序代码，对测试数据进行排序。
    • 验证排序结果是否正确，记录测试数据和排序结果。

  4. 结果分析

    • 分析排序结果，讨论合并排序算法的时间复杂度和空间复杂度。
    • 比较合并排序与其他排序算法的优缺点，总结实验心得。

五、 主要代码

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
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1


# 测试合并排序
arr = [8, 3, 2, 9, 7, 1, 5, 4]
merge_sort(arr)
print("排序后的数组:", arr)

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

在实验过程中，我们对一组无序数组进行了合并排序。以下是实验数据和结果分析：

  • 测试数据： [8, 3, 2, 9, 7, 1, 5, 4]
  • 排序结果： [1, 2, 3, 4, 5, 7, 8, 9]

通过对比排序前后的数组，可以看出合并排序算法成功地将无序数组排序为有序数组。合并排序的时间复杂度为 O(n log n)，空间复杂度为 O(n)。

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

在实验过程中，我们遇到了一些问题：

  1. 问题：代码中存在数组索引越界的错误。
    解决方法：通过检查数组索引的边界条件，确保在访问数组元素时不会越界。

  2. 问题：排序结果不正确。
    解决方法：仔细检查合并排序算法的实现，发现是由于合并过程中索引变量更新不正确导致的，修正后问题解决。

八、 讨论、心得体会

通过本次实验，我们深入理解了合并排序算法的原理和实现过程。合并排序是一种稳定的排序算法，适用于大规模数据的排序。与其他排序算法相比，合并排序的时间复杂度较低，但空间复杂度较高。在实际应用中，可以根据具体需求选择合适的排序算法。

本次实验还让我们意识到，编写代码时需要特别注意边界条件和索引的正确性，避免出现数组越界等问题。同时，通过不断调试和修正代码，我们提高了编程能力和解决问题的能力。