《数据结构与算法习题讲解(全).ppt》由会员分享，可在线阅读，更多相关《数据结构与算法习题讲解(全).ppt（97页珍藏版）》请在第壹文秘上搜索。
1、第一章n1.5编写一个递归方法，它返回数n的二进制表示中1的个数。利用这样的事实：如果n是奇数，那么它等于n/2的二进制表示中1的个数加1。nint 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; cout“Please input n:”i; if(i0) i=-i; cou
2、nt(i); cout“所输入整数中的二进制中1的个数是：”jendl; return 0;n1.7证明下列公式na. logx0成立n数学归纳法：当0 x1, 命题显然成立：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,有log2x2x, 即xx 即2xx, 得logxx;命题得证nb. log(AB)=BlogA证
3、明：令2X=A, 则AB =(2X)B =2XB ; 则logAB =XB, X=logA;命题得证第二章n2.1按增长率排列函数：N, N1/2, N1.5, N2, NlogN, Nlog(logN), Nlog2N, Nlog(N2), 2/N, 2N, 2N/2, 37, N2logN, N3。指出哪些函数以相同的增长率增长。n答：2/N, 37, N1/2, N, Nlog(logN), NlogN, Nlog(N2), Nlog2N, N1.5, N2, N2logN, N3, 2N/2, 2N. 其中，NlogN, Nlog(N2)有相同的增长率。n常见的几种计算时间的关系： O
4、(1)O(logN)O(N)O(NlogN)O(N2)O(N3)O(2N)O(N!)O(NN)n2.7对于下列六个程序片段中的每一个：给出运行时间分析n1) 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)n3) sum=0; for(i=0; in; i+) for(j=0; jn*n; j+) sum+; O(N3)n4) sum=0; for(i=0; in; i+) for(j=0; ji; j+) sum+; O(N2)n5)sum=0; for(i=0
5、; in; i+) for(j=0; ji*i; j+) for(k=0; kj; k+) sum+; O(N5)nj可等规模于i2, 同样也等规模于N2. k等规模于j, 即N2. 则该程序段的运行时间复杂度分析为 N*N2*N2, 即O(N5). n6) 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”,n如上题所述if 语句至多要执行N3次, 但是实际上只有O(N2)次 (因为对每一个i，实际上都严格执行了i次), 因
6、此最内的循环只执行了O(N2)次。 而每执行一次, 将花费 O(j2) = O(N2) 的时间, 总数即为O(N4)。n个人理解： if(j%i=0) for(k=0; kj; k+) sum+;这段程序段的循环次数O(N)n2.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的数
7、组a:为了填入ai,生成随机数直到它不同于已经生成的一个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);n试问： a.证明这三个算法都生成合法的置换，并且所以的置换都是等可能的； b.对每个算法都给出你能够得出的尽可能不同的期望运行时间
8、分析； c.没个算法的最坏情形的运行时间是什么？n答：a. 所有的算法都可以生成合法的置换。很明显，前2个算法在测试中可以保证不生成重复的数，并且它们是完全随机的，故它们生成的置换是等可能。第3个算法轮换数组中的元素，这个数组最初是没有重复数的，也不会存在非法置换。n前2个算法很明显成立，第3个算法可以用数学归纳法证明，详细证明如下：n1.当n=1时，a0=1，都是100%，成立；n2.当n=2时，for(i = 1; i n; +i) swap (ai,arandInt(0,i); 第一次循环，当i=1时，即a0=1,ai=a1；n3.当 n=3时，第二次循环时，当i=2时，此时有两种可能，
9、原序列为0,1; 1,0的几率各为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,所以，此时成立。n4.假设此命题在n = k时成立，那么就是说，前面序列共有序列k-1种，且所有序列的几率为1/(k-1)*k)。n5. 当n=k+1时,第k+1次循环时,前面序列正好为n=k时的
10、情况,此时i = k. randInt(0,k)共可能为0k,k+1种可能。所以以前的每个可能序列在置换后有k+1种可能，而以前共有k种等可能序列，那么最后可能的序列为k*(k+1)种可能，并且，因为原序列为等可能的，每个等可能序列产生的序列都是k+1种，所以最后的序列也是等可能的。而当n=k+1时，应该共有 =(k+1)*k种，所以，此命题得证。n注：证明时默认地利用了一个命题：当原序列为互不相等的等可能序列时，新加入一个与原来序列任何数值都不相等的数值，无论这个数值放在原序列的哪个位置，都不可能使原不相等的序列相等。n例：210, 021, 012, 201, 120, 102，这时加入一
11、个新的数值3，无论把3插入序列的哪个位置，因为原来序列的排列不相等，所以，他们还是不会相等，这样，才保证了最后k个序列的k+1种可能都不相等，不会重复。nb.第一个算法中，决定ai中一个之前没有使用过的随机数是否被填入的时间是O(i)。 在那些需要测试的随机数中，需要产生期望的随机数的次数为N/(N i)次。得出结论如下：n个数中有i个可能是重复的。因此，置换成功的概率为(N i)/N。因此，在独立的测试中，期望数为N/(N i)。时间复杂度即为：n第2个算法为每个随机数保留了因子i ，因此，时间度平均减少到了O(NlogN) 。n第3个算法很明显是线性的，O(N)。nc. 算法1和算法2的最
12、坏运行时间无法被界定，在一直随机到重复数字的时候可以到达无限大。算法3的运行时间是线性的它的运行时间并不依赖于随机数的次序。n2.12 一个算法对于大小为100的输入花费0.5ms，如果运行时间如下：则用1min可以解决多大的问题(设低阶项可以忽略)。 a.是线性的； b.为O(NlogN) c. 是二次的； d. 是三次的n(a) 12000 times as large a problem, or input size 1,200,000. N=60*1000*100/0.5=12,000,000=1.2*107n(b) input size of approximately 425,00
13、0. 由NlogN=1.2*107 可得n(c) 120001/2 times as large a problem, or input size 10,954. 由N2=1.2*107 可得n(d) 120001/3 times as large a problem, or input size 2,289. 由N3=1.2*107 可得n2.18 数值分析中一个重要的问题是对某一个任意的函数f找出方程f(x)=0的一个解。如果该函数是连续的，并有两个点low和hign使得f(low)和f(high)符号相反，那么在low与high之间必然存在一个根。并且这个根可以通过二分搜索求得。写一个函
14、数，以f, low和high为参数，并且解出一个零点。nfloat 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); 为使程序正常终止，必须设置基准情况。（注意精度防止溢出）n一个例子：n#includen#includenfloat f(float a)nnreturn 5*a+1;nnvoid find(float,float);nfloat static
15、 c=0;nvoid main()nnnfind(-4,5.0);nprintf(%fn,c);nreturn 0;nnvoid find(float low, float high)nnnfloat mid=(low+high)/2;nif(fabs(f(mid)=0.0001)nnc=mid;nnelsennif(f(mid)*f(low)next;nafterp = p-next; / both p and afterp assumed not NULLnp-next = afterp- next;nbeforep -next = afterp;nafterp-next = p;nbef
16、orepnextpnextafterpnextn(b) doubly linked lists:n/ p and afterp are cells to be switched. Error checks as beforennNode *beforep, *afterp;nbeforep = p-prev;nafterp = p-next;np-next = afterp-next;nbeforep-next = afterp;nafterp-next = p;np-next-prev = p;np-prev = afterp;nafterp-prev = beforep;nbeforepprevnextpprevnextafterpprevnextn3.6 Josephus问题是下面一个游戏：有N个人坐成一圈，编号为1至N。从编号为1的人开始传递热马铃薯。M次传递之后，持有马铃薯的人退出游戏，圈缩小，然后游戏从退出的下面的人开始继续，最终留下的获胜。这样M=0且N=5，那么参加游戏的人依次退出，5号获胜。na.写出一个程序来解决Josephus问题，此时M和N为任意值，尽可能使程序
