1 2014/2015 学年第一学期《数据结构与算法课程设计》任务书一、课程设计目的数据结构与算法课程设计是 《数据结构与算法》 课程教学必不可缺的一个重要环节，它可加深学生对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。通过课程设计，能够提高学生分析问题、解决问题，从而运用所学知识解决实际问题的能力，因而必须给予足够的重视。2 二、课程设计题目2.1 棋盘覆盖【间题描述】在一个 2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。【基本要求】2 （1）输入 k以及特殊方格所在的行号dr 和特殊方格的列号 dc。（2）要求输出每一步用什么形态L型骨牌覆盖，覆盖后得到的棋盘图形。（3）如果输出的结果只是用矩阵表示则为良好，用图形表示则为优。【测试数据】【实现提示】使用分治策略，把棋盘划分成4个小棋盘，然后用一个 L型骨牌覆盖将这 4个小棋盘变为都具有特殊方格的棋盘。2.2 Hanoi 塔问题（ *）【 问题描述】设a，b，c是三个塔座。开始时，在塔座a上有一叠共 n个圆盘，这些圆盘自下而上，由大到小地叠放在一起，各圆盘从小到大编号为1,2, ⋯,n ，要求将塔座 a上的这一叠圆盘移到塔座 b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则（ 1）每次只能移动一个圆盘；规则（ 2）任何时刻都部允许将较大的圆盘压在较小的圆盘之上；规则（ 3）在满足移动规则（ 1）和（ 2）的前提下，可将圆盘移至a，b，c中任一塔座上。【基本要求】（1）设计出 Hannoi塔游戏，供用户玩；（2）提供正确的搬运方法。3 【实现说明】正确的搬运方法使用递归方法实现。【测试数据】2.3 矩阵连乘问题【问题描述】给定n个矩阵 {12,,...,nA AA }, 其中iA 和1iA是可乘的， i ＝1,2, ⋯,n-1 。考察这 n个矩阵的连乘积12,...,nA AA ，通过加括号方式，找出矩阵乘积所需的最少计算量的方法。【基本要求】输入每个矩阵的行和列，要求输出最少计算量的矩阵乘积方法，如1234((()))A AA A。【实现说明】使用动态规划方法。2.4 多边形游戏（ * ）【问题描述】多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符...
