《算法设计与分析2014期末考试题目》由会员分享，可在线阅读，更多相关《算法设计与分析2014期末考试题目（6页珍藏版）》请在金锄头文库上搜索。
1、1. 中国象棋中马的走法回 溯 法！马当前所在的位置是当前扩展结点！每个活结点可能有八个孩子结点！如何记录马行走的路径？class Horseprivate:int chess56;int d28=(1,2,2,1-1,-2,-2,-1),(2,1,-1,-2,-2,-1,1,2);int sx,sy;int count;public:Horse(int x,int y) sx=x; sy=y;for(int i=0;i=6|sy=5) return ;backtrack(sx,sy);return count;Private static void backtrack(int p1,int
2、p2);Private static void Horse: backtrack(int p1,int p2)int pi,pj;for(int i=0;i=0&pi=0&pjfishmax) fishmax = fish;time_trans +=Ti 要对需要钓的湖进行枚举，n 种可能 如果需要钓 k 个单位时间的鱼，k 次选择 每个单位时间选择的时间复杂度为 O(n)时间复杂度 O(kn2)17. 折纸留痕问题 18. 三色凸多边形问题 19. 超长数字串问题 20. 彩球问题递归与分治算法！21.月亮之眼问题递推22.丢失的正整数数列问题问题描述：数学老师给全班同学写了一个包含 n 个
3、正整数的递增数列，要求大家回家后同样按照递增的次序，写出所有的、任意两个数的和。有个同学很快就写完了作业。可是他出去玩了一会，回来后发现老师给的原始数列丢失了。你能帮他找回来吗？问题分析：假设这个同学丢失的正整数递增数列是：a1,a2,a3,a4,an他写出的结果包含了 n(n-1)/2 个数，它们由小到大是：k1,k2,k3,k4,a1+a2=k1, a1+a3=k2 a2+a3= ? 假设 a2+a3=kx , 则解方程可得：a 1,a2,a3 依次递推计算写出每个 ai 23.电气工程师的烦恼问题分析：以各条网线的编号 1,2,3,n 为顶点构造一个有向图。若 ij 同时 i 与 j 不
4、相交，则画由 i 到 j 的有向边；若 ij 同时 i 与 j 相交，则画由 j 到 i 的有向边；每个顶点的入度就是它前面网线的条数！入度为 0 的顶点唯一！拓扑排序！25.士兵排队问题中位数原理 快速选择算法28.团伙(i,j,0)：i 和 j 是朋友，合并 i 和 j 所在的朋友集合(i,j,1)：i 和 j 是敌人，i 的敌人是集合 ei将 i 置入集合 ej将 j 置入集合 ei 集合的存储结构树29.方块消除游戏一个方块游戏可以描述成：(c1,l1), (c2,l2), , (cn,ln)(ci,li)表示第 i 个区域的颜色 ci和方块个数 li假设 fi,j,k是消除下列区域的最大得分：(ci,li), (ci+1,li+1), , (cj-1,lj-1),(cj,lj+k)
