《采用递归方法.doc》由会员分享，可在线阅读，更多相关《采用递归方法.doc（8页珍藏版）》请在金锄头文库上搜索。
1、/ 采用递归方法，基于欧几里德算法（也称辗转法）求两个整数的最大公约数。/假定两个整数分别为num1和num2，最大公约数应当是不超过其中较小数的一个整数。/辗转法的思想是：用num1除以num2，求出余数resd，如果resd=0，则当前num2就是最大公约数，/否则（resd!=0），num1=num2, num2=resd, 重复以上过程，直到resd=0为止。#includeusing namespace std;int GrtComDivisor(int, int) ;int main() int num1,num2; do coutnum1num2; while (! (num1*
2、num2); int gcd=GrtComDivisor(num1,num2); coutnum1和num2的最大公约数为：gcdendl; return 0;int GrtComDivisor(int num1, int num2) if (! (num1%num2)return num2;elsereturn GrtComDivisor(num2, num1%num2);/分别采用递推和递归的方式实现：一球从100米高度落下，每次落地后反弹回原高度的一半，再落下，/编程求它在第10次落地时共经过多少米？第10次反弹多高？/递归法#include using namespace std;/计
3、算第n次反弹的高度double reboundhigh(double m, int n);double path(double m,int n);int main()double h = 100.0;double d, s=0.0;int i, n;while (1)cout 0)：;cin n;if (n 0) break;s=h;/s：第1次落地时经过的路程for (i=1; in; i+)d = reboundhigh(h, i);/h：第i次落地反弹的高度s = s + 2*d;/s：第i次落地时经过的路程d = reboundhigh(h, n);cout 第 n 次落地时共经过 s
4、 米 endl;cout 第 n 次落地时共经过(递归) path(h, n) 米 endl;cout 第 n 次反弹 d 米 endl;return 0;double reboundhigh(double h, int n)double d;if (n = 0)d = h;elsed = reboundhigh(h/2, n-1);return d;double path(double m,int n)double l;if (n=0)l=0;else if (n=1)l=100;elsel=path(m, n-1) + reboundhigh(m, n-1)*2;return l;/采用递
5、归方法，计算一个数的平方根。#include #includeusing namespace std;const double e = 1e-5;double Newton(double, double x0);int main()double a;docout a;while (a0);double x;x=Newton(a, a/2.0);cout a的平方根为 x endl;return 0;double Newton(double a, double x0)if (fabs(a)e) return 0;double x1;x1= (x0+a/x0)/2.0;if (fabs(x1-x0
6、)e)return x1;elsereturn Newton(a, x1);/在Newton(a, x1)前，不能少return/约瑟夫（Josephus）问题#include using namespace std;const int Max = 100;int Josephus(int n, int m)int aMax;/定义数组aa0=0;for (int i=1; i=n; i+) ai=1;/a1an为有效信息，1：在圈内；0：出局for (i=n+1 ;i 1)k=0;/报数前初始化while (km)/循环报数start = start + 1;if (start = n+1)
7、 start = 1;k = k + astart;astart = 0;/出局cout start t;count-;/更新圈内人数int lastno = -1;/查找最后留在圈内的序号for (k=1; k=n & ak=0; k+);if (ak) lastno = k;cout k n;return lastno;/约瑟夫（Josephus）问题主程序/n=8, m=4, lastno=6/n=41, m=3, lastno = 31#include using namespace std;int Josephus(int n, int m);int main()int n, m;d
8、ocout n m;while(n0)|(m0);int lastno;lastno = Josephus(n, m);cout 最后一个人的编号为 lastno endl;return 0;/编写程序，其中包含三个重载的display()函数，/针对不同的参数类型，分别可输出该参数的类型（如：double、int、char）及参数的值。/在主函数中，分别用double、float、int、char和short型的变量作为实参去调用display()函数。#include #include using namespace std;int menu();void display(int);voi
9、d display(double);void display(char);void main()int choice;while (1)choice = menu();switch (choice)case 1:cout setw(15)double:3.2t; display(3.2);break;case 2:cout setw(15)float:3.2t; display(3.2f);break;case 3:cout setw(15)int:5t;display(5);break;case 4:cout setw(15)char:at;display(a);break;case 5:c
10、out setw(15)short:5t;display(short(5);break;case 0:cout exitn;break;default:cout choice error !n;if (choice=0) break;int menu()int ch;cout endl;cout *n;cout * 1. display a double *n;cout * 2. display a float *n;cout * 3. display a int *n;cout * 4. display a char *n;cout * 5. display a short *n;cout * 0. exit *n;cout *n;cout ch;return ch;void display(int a)cout 整型数：aendl;void display(double a)cout 实数：aendl;void display(char a)cout 字符：aendl;/定义内联函数precision ，将一个实数精确到小数点后第i位#include #include using namespace std;inline double precision(double , int);int main()
