《数据结构与算法习题讲解(全)》由会员分享，可在线阅读，更多相关《数据结构与算法习题讲解(全)（97页珍藏版）》请在金锄头文库上搜索。
1、第一章,1.5编写一个递归方法，它返回数n的二进制表示中1的个数。利用这样的事实：如果n是奇数，那么它等于n/2的二进制表示中1的个数加1。 int ones( int n ) if( n 2 ) return n; return n%2 + ones(n/2); ,#include using namespace std; int j=0; count(int n) int k; k=n/2; j+; while(k=1) if(n%2=0) j-; return count(); ,main() int i,j; couti; if(i0) i=-i; count(i); cout“所输入
2、整数中的二进制中1的个数是：”jendl; return 0; ,1.7证明下列公式 a. logx0成立 数学归纳法：当0x1, 命题显然成立：x=1, 公式是成立的；当x1时, logx 是负数。 同理可以很容易推出当1x2时命题成立：x=2, 公式成立；当x2, logx最大为1。假设命题在px2p时成立(p为正整数), 这时考虑有2pY4p (p 1)。则logy=1+log(y/2) 1+y/2y/2+y/2y, 由此可推导出公式成立。,二项式法：令x=2x,有log2xx 即2xx, 得logxx;命题得证 b. log(AB)=BlogA 证明：令2X=A, 则AB =(2X)B
3、 =2XB ; 则logAB =XB, X=logA;命题得证,第二章,2.1按增长率排列函数：N, N1/2, N1.5, N2, NlogN, Nlog(logN), Nlog2N, Nlog(N2), 2/N, 2N, 2N/2, 37, N2logN, N3。指出哪些函数以相同的增长率增长。 答：2/N, 37, N1/2, N, Nlog(logN), NlogN, Nlog(N2), Nlog2N, N1.5, N2, N2logN, N3, 2N/2, 2N. 其中，NlogN, Nlog(N2)有相同的增长率。 常见的几种计算时间的关系： O(1)O(logN)O(N)O(Nl
4、ogN)O(N2)O(N3) O(2N)O(N!)O(NN),2.7对于下列六个程序片段中的每一个：给出运行时间分析 1) sum=0; 2) sum=0; for(i=0; in; i+) for(i=0; in; i+) sum+; for(j=0; jn; j+) O(N) sum+; O(N2),3) sum=0; for(i=0; in; i+) for(j=0; jn*n; j+) sum+; O(N3),4) sum=0; for(i=0; in; i+) for(j=0; ji; j+) sum+; O(N2),5)sum=0; for(i=0; in; i+) for(j=0
5、; ji*i; j+) for(k=0; kj; k+) sum+; O(N5),j可等规模于i2, 同样也等规模于N2. k等规模于j, 即N2. 则该程序段的运行时间复杂度分析为 N*N2*N2, 即O(N5).,6) sum=0; for(i=1; in; i+) for(j=1; jii; j+)* if(j%i=0) for(k=0; kj; k+) sum+; O(N4) 注： *处的for语句的循环次数 为“12+22+32+n2”,如上题所述if 语句至多要执行N3次, 但是实际上只有O(N2)次 (因为对每一个i，实际上都严格执行了i次), 因此最内的循环只执行了O(N2)次
6、。 而每执行一次, 将花费 O(j2) = O(N2) 的时间, 总数即为O(N4)。 个人理解： if(j%i=0) for(k=0; kj; k+) sum+; 这段程序段的循环次数O(N),2.8 假设需要生成n个自然数的一个随机置换。例如：4, 3, 1, 5, 2和3, 1, 4, 2, 5就是合法的置换，但5, 4, 1, 2, 1则不是，因为数1出现2次而数3却没有。这种程序常常用于模拟一些算法。我们假设存在一个随机数生成器n，它用方法randInt(i,j)以相同的概率生成i和j之间的一个整数。下面是三个算法： (1).如下填入从a0到an-1的数组a:为了填入ai,生成随机数
7、直到它不同于已经生成的一个a0,a1,ai-1时再将其填入； (2).同算法(1)，但是要使用一个附加的数组，称之为used数组。当一个随机数ran最初被放入数组a的时候，设置usedran=ture。就是说，当一个随机数填入ai时，可以用一步来测试是否该随机数已经被使用，而不是像第一个算法那样可能用i步来测试； (3).填写该数组，使得ai=i+1，然后for(i=1; in; i+) swap(ai, arandInt(0,i); 试问： a.证明这三个算法都生成合法的置换，并且所以的置换都是等可能的； b.对每个算法都给出你能够得出的尽可能不同的期望运行时间分析； c.没个算法的最坏情形
8、的运行时间是什么？,答：a. 所有的算法都可以生成合法的置换。很明显，前2个算法在测试中可以保证不生成重复的数，并且它们是完全随机的，故它们生成的置换是等可能。第3个算换数组中的元素，这个数组最初是没有重复数的，也不会存在非法置换。 前2个算法很明显成立，第3个算法可以用数学归纳法证明，详细证明如下：,1.当n=1时，a0=1，都是100%，成立； 2.当n=2时，for(i = 1; i n; +i) swap (ai,arandInt(0,i); 第一次循环，当i=1时，即a0=1,ai=a1； 3.当 n=3时，第二次循环时，当i=2时，此时有两种可能，原序列为0,1; 1,0的几率各为
9、50%。randInt(0,2)可能为0,1,2的几率各为1/3。此时,原序列为0,1时,randInt(0,2)为0,那么此序列经过swap(a2,a0),最后序列为2,1,0,此序列的可能性为(1/2)*(1/3)=1/6; 同理易得,最后此序列为“210, 021, 012, 201, 120, 102”的几率各为1/6,而此序列的所有排列可能为=3*2= 6,所以，此时成立。 4.假设此命题在n = k时成立，那么就是说，前面序列共有序列k-1种，且所有序列的几率为1/(k-1)*k)。 5. 当n=k+1时,第k+1次循环时,前面序列正好为n=k时的情况,此时i = k. randI
10、nt(0,k)共可能为0k,k+1种可能。所以以前的每个可能序列在置换后有k+1种可能，而以前共有k种等可能序列，那么最后可能的序列为k*(k+1)种可能，并且，因为原序列为等可能的，每个等可能序列产生的序列都是k+1种，所以最后的序列也是等可能的。而当n=k+1时，应该共有 =(k+1)*k种，所以，此命题得证。,注：证明时默认地利用了一个命题：当原序列为互不相等的等可能序列时，新加入一个与原来序列任何数值都不相等的数值，无论这个数值放在原序列的哪个位置，都不可能使原不相等的序列相等。 例：210, 021, 012, 201, 120, 102，这时加入一个新的数值3，无论把3插入序列的哪
11、个位置，因为原来序列的排列不相等，所以，他们还是不会相等，这样，才保证了最后k个序列的k+1种可能都不相等，不会重复。,b.第一个算法中，决定ai中一个之前没有使用过的随机数是否被填入的时间是O(i)。 在那些需要测试的随机数中，需要产生期望的随机数的次数为N/(N i)次。得出结论如下：n个数中有i个可能是重复的。因此，置换成功的概率为(N i)/N。因此，在独立的测试中，期望数为N/(N i)。时间复杂度即为：,第2个算法为每个随机数保留了因子i ，因此，时间度平均减少到了O(NlogN) 。 第3个算法很明显是线性的，O(N)。,c. 算法1和算法2的最坏运行时间无法被界定，在一直随机到
12、重复数字的时候可以到达无限大。算法3的运行时间是线性的它的运行时间并不依赖于随机数的次序。,2.12 一个算法对于大小为100的输入花费0.5ms，如果运行时间如下：则用1min可以解决多大的问题(设低阶项可以忽略)。 a.是线性的； b.为O(NlogN) c. 是二次的； d. 是三次的,(a) 12000 times as large a problem, or input size 1,200,000. N=60*1000*100/0.5=12,000,000=1.2*107 (b) input size of approximately 425,000. 由NlogN=1.2*107
13、 可得 (c) 120001/2 times as large a problem, or input size 10,954. 由N2=1.2*107 可得 (d) 120001/3 times as large a problem, or input size 2,289. 由N3=1.2*107 可得,2.18 数值分析中一个重要的问题是对某一个任意的函数f找出方程f(x)=0的一个解。如果该函数是连续的，并有两个点low和hign使得f(low)和f(high)符号相反，那么在low与high之间必然存在一个根。并且这个根可以通过二分搜索求得。写一个函数，以f, low和high为参数
14、，并且解出一个零点。,float find(float low, float high) mid=(low+high)/2; if(fabs(f(mid)=0.000001) return mid; else if(f(mid)*f(low)0) find(low, mid); else find(mid,high); 为使程序正常终止，必须设置基准情况。 （注意精度防止溢出）,一个例子： #include #include float f(float a) return 5*a+1; void find(float,float); float static c=0; void main()
15、find(-4,5.0); printf(“%fn“,c); return 0; ,void find(float low, float high) float mid=(low+high)/2; if(fabs(f(mid)=0.0001) c=mid; else if(f(mid)*f(low)0) find(low, mid); else find(mid,high); ,2.26 大小为N的数组A，其主元素是一个出现超过N/2次的元素(从而这样的元素最多有一个)。例如：数组：3,3,4,2,4,4,2,4,4有一个主元素4；而数组3,3,4,2,4,4,2,4没有主元素。如果没有主元素，那么你的程序应该指出来。 a.递归如何终止？ b.当N是奇数时的情形如何处理？ c.该算法的运行时间是多少？ d.我们如何避免使用附加数组B？,a.如果只有2个或更少的元素，不需要递归。 b. 一种方法是：标记，如果前N-1个元素已经出现主元素，则最后一个元素不需要考虑。否则， 最后一个元素有可能是主元素。因此当N是奇数时，忽略最后一个元素。像之前一样运行算法。如果没有主元素出现，则将第N个元素作为候选值返回。 c.运行时间为O(N), 并且满足T(N)=T(N/2)+O(N)。 d. 保存一份数据到数组B。之后，通过复制每一个Bi到数组A即可避免递归。
