复习参考分析和总结.pdfVIP

一、概念类 1、试描述回溯法及其基本要素，并举例说明。 2、试比较分治法和动态规划法。 3、描述分治法的一般算法步骤，并说明使用分治法必须满足哪些基本要素？ 4、比较回溯法和分支限界法。 二、简答类 1、求解下列递推关系 f (0)  f (1)  f (n) f (n 1) f (n  2) n  2 解：根据式3，得方程 2 ，求解得两根为2和4， x  6x  8 故 n n ，又 ， ， f (n)  c 2  c 4 f (0)  2 f (1) 6 1 2 得c  1,c  1，故f n  n n ( ) 2 4 1 2 2、求解下列递推方程 f (0)  0  f (1) 1  f (n)  f (n 1) f (n  2) n  2 1 5 1 5 解：根据式3，得方程 2 ，求解得两根为 , ， x  x  1 2 2 1 5 1 5 故 ( )n ( )n ，又 ， ， f (n)  c  c f (0)  0 f (1) 1 1 2 2 2 1 1 1 1 5 1 1 5 得c  ,c   ，故f (n)  ( )n  ( )n 1 5 2 5 5 2 5 2 3、 ＝ n 成立吗？证明你的答案。 n ! (n ) n! n n n (n ) (n ) 解：当n   时，， lim  0 ，故为O(n ) ，但不是 或 n nn 4、 log n ！是 和 的吗？证明你的答案。   O(n),(n) (n) 解：令2  n  2k k1 ，则当n   时，k   ， logn ! k ! 而lim  lim   ，故为(n) n n k 2k1 二、简单分析解题类 1、二分有哪些信誉好的足球投注网站问题 设a[0 : n 1] 是已排好序的数组。请改写二分有哪些信誉好的足球投注网站算法，使得当有哪些信誉好的足球投注网站元素x 不在数字中时， 返回小于x 的最大元素位置i 和大于x 的最小位置j。当有哪些信誉好的足球投注网站元素在数字中时，i 和j 相同， 均为x 在数组中的位置。 public static boolean binarysearch(int []a,int x,int left,int rig