DS100.3 上机作业 3.ppt

Xidian University * 回溯法与树的遍历——数据结构第三次上机作业上机时间：2011-11-22 E-208 西安电子科技大学·理学院 hjTang@xidian.edu.cn Xidian University * 实验目的 理解回溯法 理解递归函数的执行过程 学会编写递归函数解决实际问题 以下题任选1题 题1：八皇后问题 题2：停车场 题3：排列组合 题4：整数的拆分 题5: 马踏棋盘问题 题6：背包问题 题7：表达式计算 Xidian University * Xidian University * 题1：八皇后问题 在8×8的国际棋盘上放置八个皇后，要求这八个皇后相互不能攻击(同行，同列，斜线) Q Q Q Q Q Xidian University * 题2：停车场 有一栈式结构的停车场，入口处有A,B,C,D四辆车，试写出所有可能的出车顺序； A B C D Xidian University * 题3：排列组合 用递归函数或使用堆栈生成排列组合数。测试用例： {A, B, C, D, E}中任取三个元素的组合数 {A, B, C, D, E}中取出不多于三个大组合数 写出{A, B, C, D, E}的所有5!个全排列 Xidian University * 题4：整数的拆分 将正整数n表示成一系列正整数之和，即： n = n1+n2+…+nk,其中：n1≥n2 ≥…≥nk≥1并给出给定正整数所有的分法的 Xidian University * 题5 马踏棋盘问题 在国际棋盘上一只马从(1,1)格出发，踏遍其他所有格，要求每个格经过且只经过一次，最后回到出发点 题6 背包问题 给我们一个容量为12的背包，让我们装上面这些物品，使得包内货物价值最大 Xidian University * 物品编号 大小 价值 1 2 1 2 3 4 3 4 3 4 5 6 5 6 8 题7 表达式计算 编写一个表达式计算程序，要求能处理类似 2+(32*67-67*3+(35-56/28))^2 log(exp(2)*sin(pi/3) + e^55) (3+4*i)*((2+4*i)-(-2*i)+6) Xidian University * 选作： 选1：折半查找 用递归函数实现折半查找算法 选2：数学运算 编程快速计算An(A为一个N*N的矩阵) 选3：递推表达式 斐波那契数列 Ackerman函数 Xidian University *