算法实验详解：递归与棋盘覆盖问题

本篇文档详细记录了两个算法实验，包括递归算法的基本应用和棋盘覆盖问题。首先，我们来看第一个实验——基本题一：整数划分递归算法。 在这个实验中，目标是编写一个递归函数`q(int n, int m)`，接收两个整数参数n和m，用于计算将整数n划分为一系列不超过m的正整数和的可能方案数量。递归过程定义了四个基本情况： 1. 当n或m小于1时，结果为0。 2. 如果n等于1或m等于1，表示单个元素，结果为1。 3. 当n小于m时，说明没有合适的划分，返回递归调用`q(n, n)`。 4. 当n等于m时，表示一个等差序列的划分，结果为`q(n, m-1) + 1`，即前m-1个数的划分加上最后一个数。 5. 当n大于m且n-m也大于1时，表示可以将n分为两部分，分别递归处理，最后结果为`q(n, m-1) + q(n-m, m)`。 在实际操作中，如n=6，m=6时，递归会正确地计算出11种划分方式。这个实验展示了递归在解决复杂问题中的简洁表达和分解能力。 第二个实验是基本题二：棋盘覆盖问题。题目要求在2k×2k的特殊棋盘（只有一个特殊方格）上，使用L型骨牌进行覆盖，确保每个方格都恰好被一个骨牌覆盖且不重叠。程序清单采用递归方法，通过变量`tile`跟踪当前使用的骨牌编号，`board`数组表示棋盘状态。 函数`chessBoard`接收五个参数：起始行`tr`、起始列`tc`、结束行`dr`、结束列`dc`和骨牌大小`size`。根据`size`的值，递归分为两种情况：如果特殊方格在当前子棋盘内，继续处理；否则，将`t`号L型骨牌放置在右下角，然后递归处理剩余未覆盖的区域。 总结来说，这两个实验展示了递归在算法中的应用，不仅涉及基础的递归思想，还结合了实际问题场景，如整数划分的计数和棋盘覆盖的策略设计。通过实践这些算法，学生可以深入理解递归原理，提升逻辑思维和编程能力。