习题课—医学讲解课件

《习题课—医学讲解课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题课——1第一章算法及基础知识1-6请对冒泡排序算法进行描述，并对其复杂性进行分析。算法描述：VoidBubbleSort(intscore[]){inti,j,temp;for(i=0;i<=n-2;i++)for(j=0;jscore[j+1]){temp=score[j];score[j]=score[j+1];score[j+1]=temp;}}该算法的时间复杂性为O(n2),算法为稳定的排序方法。1-7给出求解汉诺塔问题的算法描述，并对其复杂性进行分析。HanoiTower问题是印度的一个古老的传

2、说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。计算结果非常恐怖(移动圆片的次数)18446744073709551615，众僧们即便是耗尽毕生精力也不可能完成金片的移动了。1-7给出求解汉诺塔问题的算法描述，并对其复杂性进行分析。算法思想：将n个盘子从A座移动到C座上可以分解为三个步骤：（1）将A座上的n-1个盘子移动到座上（借助C座）（

3、2）将A座上剩下的一个盘子移动到C座上。（3）将n-1个盘子从B座移动到C座上（借助A座）Voidhanio(intn,chara,charb,charc){if(n==1)move(a,c)else{hanio(n-1,a,c,b);move(a,c);hanio(n-1,b,a,c);}}voidmove(charx,intn,chary)//汉诺塔的递归算法{cout<<"把编号为"<

4、B);}else{hanoi(N-1,A,B,C);move(A,N,B);hanoi(N-1,C,A,B);}}intmain(){cout<<"------汉诺塔递归实现------"<>n;cout<<"移动步骤："<

5、dhanoi(intn)//汉诺塔的非递归算法{intfromPole,toPole,Disk;int*BitStr=newint[n],*Hold=newint[n];charPlace[]={'A','B','C'};inti,j,temp;for(i=0;i

6、sk=j+1;if(Disk==1){fromPole=Hold[0];toPole=6-fromPole-temp;temp=fromPole;}else{fromPole=Hold[Disk-1];toPole=6-Hold[0]-Hold[Disk-1];}cout<<"把编号为"<

7、说明：利用塔C将盘子从塔A移到塔B"<>n;hanoi(n);system("PAUSE");return0;}该算法的时间复杂性为O(n)第二章贪心法2-4给定n位正整数a，去掉其中任意k(k<=n)个数字后，剩下的数字按原序列排列组成一个新的正整数。对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。解：设n位正整数a=anan-1…a1，其中ai={0,1,2,3,4,5,6,7,8,9}说明：正整数的大小取决于它的高位数值。1.n=1时，设

8、有a=a1和b=b1，并且a1>b1可知有：a>b2.n=2时，设有a=a2a1和b=b2b1