递归与分治算法设计实验：棋盘覆盖问题、合并排序问题等

算法分析与设计实验-递归与分治算法设计 在这篇实验报告中，我们将学习递归与分治算法的设计思想，并通过四个实验题目来实践这些算法。这些题目包括棋盘覆盖问题、合并排序问题、集合最大元问题和循环赛日程表。 **递归与分治算法设计** 递归与分治算法是解决复杂问题的一种常见方法。它将一个大问题分割成一些规模较小的子问题，然后对每个子问题求解，最后将这些子问题的解合并为一个更大规模的问题的解。 **实验目的** 掌握分治算法的基本思想，掌握分治算法的设计步骤及用递归技术实现分治策略。 **实验原理** 算法总体思想：对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。 **分治法的设计思想** 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 **实验内容** **1.棋盘覆盖问题** 在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 在这个实验中，我们使用C语言来实现棋盘覆盖问题的解决方案。我们定义了一个二维数组bord来存储棋盘的状态，并使用递归函数chess来实现棋盘的覆盖。 **知识点** * 递归与分治算法的设计思想 * 分治法的基本思想 * 递归技术的应用 * C语言的应用 **实验环境** 实验环境：Windows7以上操作系统，PC机，codeblocks环境 **实验结果** 通过这次实验，我们掌握了递归与分治算法的设计思想和实现方法，并通过四个实验题目来实践这些算法。这些知识点将有助于我们更好地理解和应用递归与分治算法。