Lab4: 算法入门

IMPORTANT

开始 Lab4 前请确保提交了 Lab3，请使用 git commit --all 进行提交

使用 git pull 更新任务仓库

你可能需要使用 git pull --rebase 来处理分支冲突

1. 汉诺塔

实验目的

• 理解递归，认识递归的强大
• 实践分治算法的设计过程

实验要求

根据 hanoi 目录下的 README.md 完成实验

实验思考

请在完成该实验后思考以下问题：

1. 你的代码给出的操作步数是最少的吗？你能利用数学归纳法证明最少操作步数与塔的层数的关系吗？
2. 尝试绘制 n=3 时的递归树，理解递归的过程。

2. 矩阵乘法

实验目的

• 认清时间复杂度和实际运行时间的关系与差异
• 认识递归的劣势
• 学习调用函数的方法（即使在不清楚函数实现原理的情况下）

实验要求

根据 matrix 目录下的 README.md 完成实验

实验思考

请在完成该实验后思考以下问题：

1. 在程序出错时，你有尝试使用输出信息进行调试吗？
2. 为什么时间复杂度更优的算法运行起来更慢？简要浏览 matrix_function.c, 怀着疑问准备下一周的学习。