递归与分治：L型骨牌覆盖算法设计

本篇实验报告是关于计算机科学与工程系软件工程专业的一次算法与算法设计课程作业，主题是“棋盘覆盖问题”。实验目的是让学生掌握递归和分治策略在算法设计中的应用，通过实际编程来深入理解这两种策略。具体任务是在一个2^k * 2^k的棋盘上，用L型骨牌（L-shape pieces）覆盖所有普通方格，只留下一个特殊方格不被覆盖。 实验者刘帅在2008年4月15日进行的这项实验中，采用了分治策略来解决问题。首先，将大棋盘划分为4个大小为2^(k-1) * 2^(k-1)的小棋盘，确保特殊方格位于其中一个小棋盘内，并且其他三个小棋盘没有特殊方格。然后，使用L型骨牌覆盖这三个无特殊方格的小棋盘的边缘，使其也包含特殊方格。这个过程会递归地进行，直到每个小棋盘都变为1 * 1的单元格，从而实现全局的覆盖。 核心代码部分展示了递归函数`chessBoard`的设计，它接受五个参数：起始行(tr)，起始列(tc)，结束行(dr)，结束列(dc)以及棋盘的大小(size)。通过判断当前位置是否在覆盖范围内，递归地调用自身，同时在边界处放置L型骨牌，直到达到基础情况（棋盘大小为1）为止。 这个实验不仅锻炼了学生的编程技能，还让他们亲身体验到如何运用递归和分治的思想解决实际问题，对提高算法设计能力、逻辑思维和问题解决策略具有重要意义。通过完成这样的实验，大学生可以更好地理解和掌握这些基本的IT概念，并能在未来的学习和工作中灵活运用。