资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,函数的递归调用,长沙市一中岳麓中学信息学奥赛培训,阅读程序，分析结果：,#include,using namespace std;,void p(int n),if(n0),p(n-1);,for(int i=0;in;i+)coutn;,cout1),long long jc(int n),if(n=0|n=1)return 1;,return jc(n-1)*n;,思考：最后一行可否写成：,else return jc(n-1)*n;,例,2,：求最大公约数（,gcd,1s,64MB,）,问题分析：,(,先使,mn),根据欧几定理，发现,(m,n),的最大公约数与,(n,m%n),的最大公约数是一样的，但是数据规模变小了。所以，最大公约数问题的递归公式为：,gcd(m,n)=m (n=0),gcd(n,m%n)(n!=0),int gcd(int m,int n),if(n=0)return m;,else return gcd(n,m%n);,例,3,：分解质因子（,zyz,1s,64MB,）,问题描述：,输入一个正整数,n,，用递归方法从小到大输出它的所有质因子。,输入格式：,一行一个正整数,n,，,2=n1 zyz(n/p,p,),n%p!=0 zyz(n,p+1),例,4,：抽奖（,lottery2,1s,64MB,）,公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会的每位员工都有一张带有号码的抽奖券。现在，主持人从小到大依次公布,n,个不同的获奖号码，小谢看着自己抽奖券上的号码,win,，无比紧张。请编写一个程序，如果小谢获奖了，请输出他中奖的是第几个号码；如果没有中奖，请输出,0.,输入格式：,第一行,1,个正整数,n,，表示有,n,个获奖号码，,2=n=100.,第二行包含,n,个正整数，之间用一个空格隔开，表示依次公布的,n,个获奖号码。,第三行,1,个正整数,win,，表示小谢抽奖券上的号码。,1=,获奖号码,win10000,。,输出格式：,一行一个整数，如果小谢中奖了，请输出中的是第几个号码；如果没有中奖，请输出,0.,思考,1,：走楼梯（,stairs,1s,64MB,）,问题描述：,已知一个楼梯有,n,级，小谢同学从下往上走，一步可以走一级，也可以走两级。问：他走到第,n,级楼梯有多少种走法？要求用递归函数实现。,输入格式：,一行，一个正整数,n,，,1=n=40,。,输出格式：,一行，一个整数，表示走到第,n,级有多少种走法。,输入样例：,9,输出样例：,10,思考,2,：角谷猜想,问题描述：,角谷猜想是指对于每一个正整数，如果它是奇数，则对它乘,3,再加,1,；如果它是偶数，则对它除以,2.,如此循环，最终都能够得到,1.,也就是说，给定正整数,n,，要进行如下操作：,1,）若,n,为,1,，操作结束；,2,）若,n,为偶数，则,n,变成,n/2,；,3,）若,n,为大于,1,的奇数，则,n,变成,n*3+1.,请编程验证此猜想。,输入格式：,1,行，一个正整数,n,，,1=n=20000,。,输出格式：,若干行，每行表示一个操作，具体格式参见输出样例。,样例输入：,22,样例输出：,22/2=11,11*3+1=34,34/2=17,17*3+1=52,52/2=26,26/2=13,13*3+1=40,40/2=20,20/2=10,10/2=5,5*3+1=16,16/2=8,8/2=4,4/2=2,2/2=1,思考,3,：数的计算（,count,1s,256MB,）,问题描述：,输入一个自然数,n,，然后对此自然数按照如下方法处理：,1,）不做任何处理；,2,）在它的左边加上一个自然数，但该自然数不能超过原数的一半。,3,）加上数后继续按此规则进行处理，直到不能再加自然数为止。,请找出以上操作能得到的数的个数。例如，,n=6,时，满足条件的数有,6,个，分别是,6,、,16,、,26,、,126,、,36,、,136.,输入格式：,一行，一个正整数,n,，,n=1000,。,输出格式：,一行，一个整数，表示满足条件的数的个数。,
展开阅读全文