2011Algorithm.doc

贪心算法总体思想 棋盘（骨牌）覆盖问题算法思想一个2k2k （k为非负整数）个方格组成的特殊棋盘中，有一个方格为特殊方格。用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，任何2个L型骨牌不得重叠覆盖。4种L型骨牌 （ 解题思路）核心算法思想：分治思想在2k x 2k个方格组成的棋盘中用到的L型骨牌恰有（4k-1）/3个。如上图所示：为解决该问题的算法思想。从分治的思想易得到需将问题微型化，于是我们将棋盘平均分成四个相似的棋盘。若特殊方格恰在图示的第一块区域，为了符合分治的思想我们需要将其他三部分转化成同样具有特殊方格的棋盘，依次递归直到棋盘为1x1的规模即可解决问题。我的理解：倘若特殊方格在第一象限的区域内。按照算法的思想将其余三块也转化成类似问题后一次递归，最终将会把2、3、4这三个格子留下来其余的格子会被全部覆盖掉。而2、3、4着三个位置也恰好可以防止一个骨牌上去，最终就会完成整个问题的求解。 符号三角形问题算法思想第1行有n个符号。两个同号下是“”，两个异号下是“”。对于给定n，计算有多少个不同符号三角形，使其所含的“”和“”的个数相同。u 回溯法是一种通用性解法，可以将回溯法看作是带优化的穷举法。u 回溯法的基本思想是在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。u 在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程，逐步构造出状态空间树，即边搜索，边构造。减枝： ()个数超过n*(n+1)/4 ；n*(n+1)/2为奇数， 用cij记录序列Xi和Yj的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。证明：最长公共子序列问题的动态规划算法的递归结构为：动态规划与分治法相同之处是也将原问题分解为若干子问题，再递归求解；不同之处是所分解的子问题彼此并不独立，而是互有重叠。 函数A(n，m)定义如下：设计计算函数值A(n，m)的递归函数。 在一个nn的棋盘上放置彼此不受攻击n个皇后。即任何2个皇后不放在同一行或同一列或同一斜线上。使用回溯法求解如下：static int n; /皇后个数 static int x; /当前解 static long sum; /当前已找到的可行方案数 public static long nQueen(int nn) n=nn; sum=0; x=new int n+1; for(int i=0;i n ) sum+; else for( int i = 1; i = n; +i ) /如果是全排列的则需要回溯时复原原来的值 /完全N叉树确定值范围则不需要这样 xt = i; /将第t个元素放在i列 if ( Place(t) ) Backtrack( t + 1 ); 或者 已知方法randomizedPartition(a,p,r) (1) 设计找出这n个元素中第k小的元素的算法。(2) 分析算法的时间复杂性。 设有n个活动的集合E=1,2,n，每个活动i（iE）都有一个要求使用公共资源的起始时间si和一个结束时间fi,