算法设计与分析(第2版) 王红梅 胡明 习题答案

r = (i%4==1)?r+f:r-f;

e = e*sqr;//e每次乘于x的平方 i+=2;//i每次加2 }//while return r; }

7. 圣经上说:神6天创造天地万有,第7日安歇。为什么是6天呢?任何一个自然数的因数中都有1和它本身,所有小于它本身的因数称为这个数的真因数,如果一个自然数的真因数之和等于它本身,这个自然数称为完美数。例如,6=1+2+3,因此6是完美数。神6天创造世界,暗示着该创造是完美的。设计算法,判断给定的自然数是否是完美数

#include using namespace std;

int main() {

int value, k=1; cin>>value;

for (int i = 2;i!=value;++i) {

while (value % i == 0 ) {

k+=i;//k为该自然数所有因子之和 value = value/ i; }

}//for

if(k==value)

cout<<\该自然数是完美数\ else

cout<<\该自然数不是完美数\ return 0; }

8. 有4个人打算过桥,这个桥每次最多只能有两个人同时通过。他们都在桥的某一端,并且是在晚上,过桥需要一只手电筒,而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的:甲过桥要用1分钟,乙过桥要用2分钟,丙过桥要用5分钟,丁过桥要用10分钟,显然,两个人走路的速度等于其中较慢那个人的速度,问题是他们全部过桥最少要用多长时间?

由于甲过桥时间最短,那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如:

第一趟:甲,乙过桥且甲回来 第二趟:甲,丙过桥且甲回来 第一趟:甲,丁过桥 一共用时19小时

9.欧几里德游戏:开始的时候,白板上有两个不相等的正整数,两个玩家交替行动,每次行动时,当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差,而且这个数字必须是新的,也就是说,和白板上的任何一个已有的数字都不相同,当一方再也写不出新数字时,他就输了。请问,你是选择先行动还是后行动?为什么?

设最初两个数较大的为a, 较小的为b,两个数的最大公约数为factor。

则最终能出现的数包括: factor, factor*2, factor*3, ..., factor*(a/factor)=a. 一共a/factor个。

如果a/factor 是奇数,就选择先行动;否则就后行动。

习题2

1.如果T1(n)=O(f (n)),T2(n)=O(g(n)),解答下列问题: (1)证明加法定理:T1(n)+T2(n)=max{O(f (n)), O(g(n))}; (2)证明乘法定理:T1(n)×T2(n)=O(f (n))×O(g(n)); (3)举例说明在什么情况下应用加法定理和乘法定理。

,(1) (2)

(3)比如在 for(f(n)) {

for(g(n)) }

中应该用乘法定理

如果在“讲两个数组合并成一个数组时”,应当用加法定理

2.考虑下面的算法,回答下列问题:算法完成什么功能?算法的基本语句是什么?基本语句执行了多少次?算法的时间复杂性是多少?

(2)int Q(int n) (1)int Stery(int n)

{ {

if (n == 1) int S = 0;

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++) m=m+1; y = y + i * j;

(1) 基本语句2*i

基本语句y = y + i * j执行了2/n次 一共执行次数=n/2+n/2=O(n)

(2) 基本语句m+=1执行了(n/2)*n=O(n*n) 4. 使用扩展递归技术求解下列递推关系式:

1n?1?4n?1 (2)(1)T(n)?? T(n)???2T(n3)?nn?1??3T(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

a

b

8.国际象棋是很久以前由一个印度人Shashi发明的,当他把该发明献给国王时,国王很高兴,就许诺可以给这个发明人任何他想要的奖赏。Shashi要求以这种方式给他一些粮食:棋盘的第1个方格内只放1粒麦粒,第2格2粒,第3格4粒,第4格8粒,??,以此类推,直到64个方格全部放满。这个奖赏的最终结果会是什么样呢?

#include using namespace std;

int main() {

long double result=1; double j=1;

for(int i=1;i<=64;++i) { j=j*2; result+=j; j++; }

cout<

return 0; }

联系客服:779662525#qq.com(#替换为@)