算法设计与分析实验指南：递归、回溯、搜索与动态规划

"该实验指导主要涵盖了算法设计与分析中的几个关键领域，包括递归与分治、回溯、搜索以及动态规划和贪心与随机算法。通过一系列具体实验，旨在帮助学生理解和应用这些基本算法思想，提升问题解决能力。" 实验一关注递归与分治策略，涉及到三个经典算法： 1. 二分查找：一种高效的查找方法，适用于有序数组，将查找范围逐步减半，降低时间复杂度。 2. 合并排序：基于分治的排序算法，将大问题分解成小问题，再合并已排序的小问题得到整体排序。 3. 快速排序：同样运用分治，通过选取基准值进行分区，再对分区分别进行排序。 实验二重点讲解回溯算法，用于解决组合优化问题，包括： 1. 0-1背包问题：在容量限制下选择价值最高的物品放入背包。 2. 装载问题：分配货物到有限的运输工具，最大化装载量。 3. 堡垒问题：ZOJ1002，具体细节未给出，可能涉及图论或逻辑推理。 4. 翻硬币问题：如何通过最少次数使所有硬币翻转过来。 5. 8皇后问题：在棋盘上放置8个皇后，使得它们互不攻击。 6. 素数环问题：寻找环状链的素数序列。 7. 迷宫问题：寻找从起点到终点的路径。 8. 农场灌溉问题（ZOJ2412）：最小化水管长度以灌溉整个农场。 9. 求图像的周长（ZOJ1047）：可能涉及图像处理和几何计算。 10. 骨牌矩阵：未提供具体描述，可能与排列组合相关。 11. 字母转换（ZOJ1003）：字符串操作或编码解码问题。 12. 踩气球（ZOJ1004）：可能是一个基于规则的游戏问题。 实验三涉及搜索算法，如： 1. Floodfill：通常用于填充颜色或标记区域。 2. 电子老鼠闯迷宫：通过搜索算法找到从起点到终点的路径。 3. 跳马：国际象棋中的马移动路径搜索。 4. 独轮车：可能需要规划路径以到达目的地。 5. 皇宫小偷：寻找最大价值的盗窃路径。 6. 分酒问题：合理分配资源的问题。 7. 找倍数：寻找特定数值的倍数。 8. 8数码难题：经典的滑动拼图游戏。 实验四聚焦动态规划，解决具有重叠子问题和最优子结构的问题，例如： 1. 最长公共子序列：找到两个序列最长的相同部分。 2. 计算矩阵连乘积：优化多矩阵相乘的运算顺序。 3. 凸多边形的最优三角剖分：减少切割次数以优化几何分割。 4. 防卫导弹：可能涉及路径规划和拦截策略。 5. 石子合并：可能是一个合并资源或优化操作的问题。 6. 最小代价子母树：构建树型结构时的最低成本问题。 7. 旅游预算：在预算约束下规划旅行路线。 8. 皇宫看守：可能涉及人员调度和覆盖问题。 9. 游戏室问题：涉及游戏策略的优化。 10. 基因问题：遗传算法或生物信息学中的问题。 11. 田忌赛马：经典的策略问题，寻找相对优势。 实验五介绍了贪心与随机算法，涵盖： 1. 背包问题：经典的组合优化问题，考虑贪婪策略。 2. 搬桌子问题：可能涉及空间利用和优化决策。 3. 照亮的山景：可能需要使用贪心策略来照亮整个区域。 4. 用随机算法求解8皇后问题：尝试不同的随机配置来解决问题。 5. 素数测试：检查一个数是否为素数，可以使用随机化算法提高效率。 这些实验旨在让学生通过实践深入理解各种算法，掌握它们的原理、实现方法和应用场景，从而提升算法设计与分析的能力。