发布时间 : 星期四 文章算法设计与分析习题答案1-6章更新完毕开始阅读
设最初两个数较大的为a, 较小的为b，两个数的最大公约数为factor。 则最终能出现的数包括: factor, factor*2, factor*3, ..., factor*(a/factor)=a. 一共a/factor个。
如果a/factor 是奇数，就选择先行动;否则就后行动。 习题2
1(如果T(n)=O(f (n))，T(n)=O(g(n))，解答下列问题: 12 (1)证明加法定理:T(n)，T(n)=max{O(f (n)), O(g(n))}; 12 (2)证明乘法定理:T(n)×T(n)=O(f (n))×O(g(n)); 12 (3)举例说明在什么情况下应用加法定理和乘法定理。 ,(1) (2) (3)比如在 for(f(n)) { for(g(n)) }
中应该用乘法定理
如果在“讲两个数组合并成一个数组时”，应当用加法定理
2(考虑下面的算法，回答下列问题:算法完成什么功能,算法的基本语句是什么,基本语句执行了多少次,算法的时间复杂性是多少,
(1)int Stery(int n) (2)int Q(int n) { {
int S = 0; if (n == 1)
for (int i = 1; i <= n; i++) return 1;
S = S + i * i; else
return S; return Q(n-1) + 2 * n - 1; } }
(1) 完成的是1-n的平方和 基本语句:s+=i*i，执行了n次 时间复杂度O(n)
(2) (2)完成的是n的平方
基本语句:return Q(n-1) + 2 * n – 1，执行了n次 时间复杂度O(n)
3. 分析以下程序段中基本语句的执行次数是多少，要求列出计算公式。 (1)for (i = 1; i <= n; i++) (2)m = 0; if (2*i <= n) for (i = 1; i <= n; i++)
for (j = 2*i; j <= n; j++) for (j = 1; j <= 2*i; j++) y = y + i * j; m=m+1;
(1) 基本语句2*i (2) 基本语句m+=1执行了(n/2)*n=O(n*n) 4. 使用扩展递归技术求解下列递推关系式: 1n,14n,1,,(1) (2) T(n),T(n),,,2T(n3)，nn,13T(n,1)n,1,, (1) int T(int n) { if(n==1) return 4; else if(n>1) return 3*T(n-1); } (2) int T(int n) { if(n==1) return 1; else if(n>1) return 2*T(n/3)+n; } 5. 求下列问题的平凡下界，并指出其下界是否紧密。 (1)求数组中的最大元素; (2)判断邻接矩阵表示的无向图是不是完全图; (3)确定数组中的元素是否都是惟一的; (4)生成一个具有n个元素集合的所有子集 (1) Ω(n) 紧密, (2) Ω(n*n) (3) Ω(logn+n)(先进行快排，然后进行比较查找) (4) Ω(2^n) 7(画出在三个数a, b, c中求中值问题的判定树。 a b a 8(国际象棋是很久以前由一个印度人Shashi发明的，当他把该发明献给国王时，国王 很高兴，就许诺可以给这个发明人任何他想要的奖赏。Shashi要求以这种方式给他一些粮 食:棋盘的第1个方格内只放1粒麦粒，第2格2粒，第3格4粒，第4格8粒，??， 以此类推，直到64个方格全部放满。这个奖赏的最终结果会是什么样呢, #include long double result=1; double j=1; for(int i=1;i<=64;++i) { j=j*2; result+=j; j++; }