北京工业大学算法分析与设计一纸开卷资料

1、实现这种分治策略的ehessBoanl 实现这种分治策略的ehessBoanl 口J实现如卜: public void chessBoard (int trtint tcint dr,int int size)if (size = = 1) return；int t = tile + + ,/ L 型骨牌号s = size/2:/分割棋盘/覆盖左上角子棋盘if (dr tr + s & de tc, s)；else /此棋盘中无特殊方格/用t号L型骨牌覆盖右卜角board tr + s - 1 tc + s - 1 = t;/覆盖其余方格chessBoard (tr tc, tr + s 1

2、tc + s - 1 s) ； /覆盖右上角子棋盘if (dr tr + s & d = tc + s)/特殊方格在此棋盘中chessBoard (tr tc + s,drt = tr + s & dr tctr + tc + s - 1 s) ； /覆盖右下角子棋盘if (dr = tr + s & de = tc + s)/特殊方格在此棋盘中法设计与分析chessBoard (tr + tc + s, Hr, s);dse /用t号L型骨牌覆盖左上角tileboard ir + b tc + s = t；了入/覆盖其余方格chessBoard (tr + s tc + tr + s tc

3、+ s s) ； size: 2，棋盘规格为2“ x2设TOO是算法chessBoard覆盖一个2x2“棋盘所需的时间。从算法的分割策略 可知，仏)满足如下递归方程：T2 =* =0(4TG - 1) + 0(1) /t 0解此递归方程可得TG) =0(4)。由于覆盖2k x2J棋盘所需的L型骨牌个数为(- 1)/3,故算法chessBoard是个在渐近意义下最优的算法。如果 f(n)=O(s(n)并且 g(n)=O(r(n),则 f(n)+g(n)=O(s(n)+r(n) 如果 f(n)=O(s(n)并且 g(n)=O(r(n),则 f(n)*g(n)=O(s(n)*r(n) 根据符号o的定

4、义，存在正常数C1, C2和自然数N1，N2,使得对所有的n=Ni, f (n) =N/g(n) =qr(n)所以 f (n) + g(n) = Cs(n)+qr(n), f (n) *g(n)= s(n)r(n)； 令 C3=max( C1,C2)， C4=C1*C2； 则：f (n) + g(n) = C3s(n)+ r(n)=O(s(n)+ r(n)f( n) *g(n) O时，将2*x2棋盘分割为4个x2A 子棋盘如圏2-石所示.迭代模型(算法)。(18分)图2-6 棋盘分刚图2-6 棋盘分刚特殊万格必位于4个较小产棋盘之 中，英余3个r*其盘屮无特殊方格为了将 这3个无特殊力格的了棋

5、盘转化为特殊棋盘，町以用-个L型丹牌覆施这3个较小机 盘的会O处，如图2( 6)所示，这3个子棋盘上被L型皆牌槻歲的力格就成沟该棋盘 I：的特殊力格，从而将原r-j趣转化为4个较小规模的棋麻覆豫问题递)地使川这种 分割直至桃盘简化为1 X I棋盘.struct node int low,high;St10000；void quickso厂七2(int data?int int t)int top=-l.,low.,high;top+;sttop.low=s;sttop.high=t; while(top-l)low=sttop.low;high=sttop.high; top-;int w;i

6、f(loww(v),则将v 从T删除之后，T变为两个连同的分支，此时，一定有T的边v1连同这两个分支，否则T将是 不连通的。从而将v1加入到T中构成一新的生成树T =T-v+v1。且有w(v1)w(v )w(v),从而 w(T )=w(T-v+v1)w(T)。这与T为最小生成树矛盾。证毕。据此利用prim算法或者Kruskal算法 算得 G 的最小生成树即可1证明0-1背包问题满足最优子结构性质假设第k个物品是最优解中的一个物品，则从中拿出Wk对应的物品后所对应的解一定是其余n-1回溯法货郎担问题的解空间是一棵排列树令到第i层为止所构早路径的权和为：cw(i):X呱工丿一1，工川假设已经知道部

7、分解d,盟2,.，心-1)，则从第i-l层节点选择顶点孟i往下走的限界函数为: B (i) = cw(il) +wxi-l, xi若B(i) bestw,则停止搜索xi分枝及其下面void backtrack (int i) if (i 二二 n) Iif (axn - lxn MAX_VALUE & axn 1 MAX_VALUE &i(bestc = MAX_VALUE | cc+axn - 1xn+axn1bestc) for (int j = 1; j = n; j+) bestxtj = xj;ibestc = cc+axn - 1xn+axn1:else for (int j 二

8、i; j - n; j+)if (axi - MAX_VALUE(bestc = MAX_VALUE | | cc+axi - 1 x j bestc) / 搜索子树第1行测试：如果i=n，表示已经搜索到了叶节点。如果从xn-1到xn以及从xn到起点x1有一条边，则找到了一条回路。此时，第3行需要判断该回路是否是目前发现的最优回路。如果是，第4行-6行则更新回路 的权和bestw以及最优回路。第7-13行继续回溯，在第8行，如果从xi-1到xj有一条边，且B(i) 小于当前最优解的值bestw，则表示可以继续往下搜索，同时更新目前所构造路径的权值cw。 证明一个问题具有贪心选择性质的一般方法令

9、子问题S.H0且ai为子问题S.中的最优解，则ai 一定包含在子问题S.中某个任务相互兼容的 ij1ij1ij最大子集中。TSP 问题此问题相当于在一个有向赋权图中寻找一个最短的哈密顿回路。畑卩)=fmind)f6F lki + s(dk,V - dk)卩工 0Ili0 K = 0个物品，装入背包最大承载重量为C-Wk的最优解，否则与假设矛盾。2 对计算复杂性的研究能够使人们弄清所求解问题的固有难度，并得出评价某类算法优劣的准则， 用以指导设计出更高效的算法。试用简短的语言说明“建立一个问题复杂性的下界要比确定它的 上界困难得多！”其复杂性上界是已知求解该问题的最快算法的费用，而复杂性下界只能

10、通过理论 证明来建立。寻求某个问题的计算复杂性上界，只要研究一个算法的复杂性即可。但是要寻求同一 问题的计算复杂性下界，则必须考察所有的解决该问题的算法，证明一个问题的复杂性下界就需要第i个顶点，假设推销员从第0号点出发，调用s时就要传入F -v：从；.出发，要到达的顶点的集合匸:1 ，：从出发，经过v中各点，并仅经过一次后，回到G：所需的最1.最大值和最小值问题的最优算法：1.最大值和最小值问题的最优算法：给定n个实数存放于一维数组A中，试设计一个算法在最坏证明不存在任何复杂性低于下界的算法。显然，建立下界要比确定上界困难得多短路径长度(：与目标点不直接连通，则记其路程为无穷大)情况下用3n

11、/2-2次的比较找出A中的最大值和最小值else smallj = ai; big j else smallj = ai; big j = ai十 1; ” Max = big0;Min = smalllO;!=1:i电g血g世計+) #找到最大值，比较 length1!次”Maxbigi) Max = bigi;pfor(int i=l;ismallj) Min =6.试设计在O(n)时间内求得数组A1.n的中位数的算法。将n个输入元素划分成n/5(上取整)个组，每组5个元素，只可能有一个组不是5个元素。用任意 一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5(上取整)个。找出这n/5(上 取整)个元素的中位数。如果n/5(上取整)是偶数，就找它的2个中位数中较大的一个。第 i 种物品的重量第 i 种物品的价值理回(辿 length) “辿int bigaU:*-1big = new mtlength2: 用来存放较大的数心 small = new jntlength 2: 用来存放较小的数心 fbr(int 1=0 J=O:i=ai4-l)big|j = ai:smallj = ai+l:-：点i到j的距离广义背包问题(从最大递归，决定每个放不放，价值增不增