Exercises and course design
-
Exericse1:
- Ex1：上机实现第1章中“最大公约数问题”的连续整数检测算法
- Ex2：上机实现第1章中“最大公约数问题”的欧几里得算法
- Ex3：设计算法并编写程序，回答习题1.1的9b
- Ex4：习题1.1的10a，设计算法并编写程序
- Ex5：完善中学时计算“最大公约数问题”的算法，并用程序实现。
- Ex6：设计并实现Fibonacci算法(参见P62)，记录计算不同F(n)值的基本操作执行次数以及程序运行时间。将基本操作次数和运行时间，以曲线图的形式展示出来
-
Exericse2:
- Ex1：实现并验证快速排序算法（参考习题5.2第7a题，P140）
- Ex2：用递归与分治的方法设计并实现寻找第k小元素算法（参见P122-123）
-
Exericse3:
-
Ex1：验证0-1背包问题的动态规划算法（参考习题8.2第2a、2b题，P229
注： 要求自己设计使用合适的数据结构，用于存储计算过程中各个子问题对应的最优子集，以方便最后进行回溯，生成最终问题的最优子集组成元素
-
Ex2：分别采用递归方法与动态规划算法实现“币值最大化问题”和“找零问题”。要求动态地调整两个问题的规模，记录算法每次执行子问题的次数，以及运行时间。绘制曲线图比较采用递归方式和动态规划实现的效率（子问题的计算次数和执行时间）
-
-
Exericse4:
- Ex1：简述求最小生成树问题的Kruskal算法的思想，并用伪代码进行描述，用程序实现该算法（用P255习题9.2的1a,1b的实例进行验证
- Ex2：明确Prim算法和Dijkstra算法的异同之处，并用伪代码描述Dijkstra算法。用程序分别实现求解加权无向图和加权有向图的Dijkstra算法（分别用P260习题9.3的2b,2a进行验证）
-
Exericse5:
- Ex1：设计并实现n皇后问题的算法（用n=4,5,8进行测试）
- Ex2：设计并实现图的三着色问题的算法（分别用P328的图12.3以及P331习题12.1的第5题中的图进行测试）
-
Exericse6:
- Ex1：设计并实现用分支界限法求解背包问题（用P335和P338中的实例进行测试）
- Ex2：设计并实现用分支界限法求解旅行商问题（分别用P337和P339中的实例进行测试）
-
Course Design：
- A1：Tromino谜题。Tromino是指一个由棋盘上的三个1x1方块组成的L 型骨牌。如何用 Tromino 覆盖一个缺少了一个方块（可以在棋盘上任何位置）的2n x 2n棋盘。除了这个缺失的方块，Tromino 应该覆盖棋盘上的所有方块，Tromino 可以任意转向但不能有重叠。
- A2：绘制分形树。先垂直绘制一根线段，然后在线段长度的三分之一处和三分之二处分别以固定夹角绘制另外两根线段，长度分别为原线段的 2/3 和 1/3. 如此反复，直至线段长度小于某个较小的值。其中，线条颜色以及长度，夹角都可以自行进行微调。
- B1：最大总和问题。将正整数排成等边三角形（也叫数塔），三角形的底边有n个数，下图给出了n5的一个例子。从三角形顶点出发通过一系列相邻整数（在图中用正方形表示），如何使得到达底边时的总和最大？
- C1：校园导航问题。给定校园平面图，求任意两给定场所间的最佳路径。