算法设计与分析书中程序(第01章)

《算法设计与分析书中程序(第01章)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、【程序1-1】欧几里德递归算法voidSwap(int&a,int&b){intc=a;a=b;b=c;}intRGcd(intm,intn){if(m==0)returnn;returnRGcd(n%m,m);}intGcd(intm,intn){if(m>n)Swap(m,n);returnRGcd(m,n);}【程序1-2】欧几里德迭代算法intGcd(intm,intn){if(m==0)returnn;if(n==0)returnm;if(m>n)Swap(m,n);while(m>0){intc=n%m;n=m;m=c;}returnn;}【程序1-3】Gcd的连续整数检测

2、算法intGcd(intm,intn){if(m==0)returnn;if(n==0)returnm;intt=m>n?n:m;while(m%t

3、

4、n%t)t--;returnt;}【程序1-4】求FnlongFib(longn){if(n<=1)returnn;elsereturnFib(n-2)+Fib(n-1);}【程序1-5】逆序输出正整数的各位数·5·#includevoidPrintDigit(unsignedintn){//设k位正整数为d1d2Ldk,按各位数的逆序dkdk-1Ld1形式输出cout<

5、>=10)PrintDigit(n/10);//以逆序输出前k-1位数}voidmain(){unsignedintn;cin>>n;PrintDigit(n);}【程序1-6】汉诺塔问题#includeenumtower{A='X',B='Y',C='Z'};voidMove(intn,towerx,towery){//将第n个圆盘从塔座x移到塔座y的顶部cout<<"Thedisk"<

6、towerz){//将塔座x上部的n个圆盘移到塔座y上，顺序不变。if(n){Hanoi(n-1,x,z,y);//将前n-1个圆盘从塔座x移到塔座z，塔座y为中介Move(n,x,y);//将第n个圆盘从塔座x移到塔座yHanoi(n-1,z,y,x);//将塔座z上的n-1个圆盘移到塔座y上，塔座x为中介}}voidmain(){Hanoi(4,A,B,C);//假定n＝4}【程序1-7】排列产生算法templatevoidPerm(Ta[],intk,intn){if(k==n-1){//输出一种排列for(inti=0;i

7、";cout<