C++递归应用

角谷猜想
题目描述
日本一位中学生发现一个奇妙的
定理，请角谷教授证明，而教授
无能为力，于是产生了角谷猜想。
猜想的内容：任给一个自然数，
若为偶数则除以2，若为奇数则乘
3加1，得到一个新的自然数后按
上面的法则继续演算。若干次后
得到的结果必为1。请编写代码验
证该猜想：求经过多少次运算可
得到自然数1。
如：输入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
经过15次运算得到自然数1。
输入
一行，一个正整数n。
（1 <= n <= 20000 )
输出
一行，一个整数，表示得到1
所用的运算次数。
样例
输入复制
22
输出复制
15

#include<iostream>
#include<string>
using namespace std;
int func(int);
int main()
{int s;cin>>s;cout<<func(s);return 0;
}
int func(int n)
{if(n==1) return 0;if(n%2==1) return 1+func(n*3+1);else if(n%2==0) return 1+func(n/2);
}

求两个数M和N的最大公约数
题目描述
求两个正整整数 M 和 N 的最大公约数(M，N都在长整型范围内）
（5.1.42）
输入
输入一行，包括两个正整数。
输出
输出只有一行，包括1个正整数。
样例
输入复制
45 60
输出复制
15

#include<iostream>
using namespace std;
int func(int,int);
int main()
{int a,b;cin>>a>>b;cout<<func(a,b);return 0;
}
int func(int c,int d)
{if(c%d==0) return d;else func(d,c%d);
}

数的计数
题目描述
输入一个自然数n（n<=100），然后对自然数按照如下方法进行处理：
在该自然数的左侧加上一个自然数，但加上的数不能超过n的一半；加上数后继续按此规则处理，直到不
能再添加自然数为止；请问按照这样的方法添加数，能够产生多少个新数？
例如：n=6，则左侧添加数的方案有
16
26
126
36
136
共能够产生5个新数。
输入
一个整数n（n<=100）
输出
按照规则能够产生的新数的个数
样例
输入复制
6
输出复制5

#include<iostream>
using namespace std;
int cnt=0;
void func(int,string);
int main()
{int p;cin>>p;func(p/2,to_string(p));cout<<cnt;return 0;
}
void func(int k,string s)
{for(int i=1;i<=k;i++){string t=to_string(i)+s;;cnt++;func(i/2,t);}
}

树根
题目描述
数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数，那么这个数就是
数根。如果结果是两位数或者包括更多位的数字，那么再把这些数字加起来。如此进行下去，直
到得到是一位数为止。 比如，对于24来说，把2和4相加得到6，由于6是一位数，因此6是24的数
根。再比如39，把3和9加起来得到12，由于12不是一位数，因此还得把1和2加起来，最后得到3，
这是一个一位数，因此3是39的数根。
样例输入
24
样例输出
6
输入格式
一个正整数(小于10000)。
输出格式
一个数字，即输入数字的数根。

#include<iostream>
using namespace std;
void func(int z);
int main()
{int n;cin>>n;func(n);return 0;
}
void func(int z)
{int t=z;while(t>10){int a=t%10;int b=t/10%10;int c=t/100%10;int d=t/1000%10;int e=t/10000%10;t=a+b+c+d+e;}cout<<t;}

阿克曼（Ackmann）函数
题目描述
输入
两个非负整数 m和 n。
输出
阿克曼函数 A(m，n) 的值。测试数据保证结果不超过 int 范围，直接用递归不超时。
（提示：阿克曼函数的值增长速度非常高，仅是对于 A(4,2)的输出就有 19729 位，
而 A(4,3)则即使是位数也不易估计。）
样例
输入复制
2 3
输出复制
9

#include<iostream>
using namespace std;
void func(int z,int y);
int main()
{int n,m;cin>>n>>m;func(n,m);return 0;
}
void func(int z,int y)
{y=y+1;func(z-1,1);func(z-1,x);cout<<z;
}

 求两个数M和N的最小公倍数
题目描述
求两个正整整数 M 和 N 的最小公倍数(M，N都在长整型范围内）
输入
输入一行，包括两个正整数。
输出
输出只有一行，包括1个正整数。
样例
输入复制
45 60
输出复制
180

#include<iostream>
using namespace std;
void func(int,int,int);
int main()
{int a,b;cin>>a>>b;func(a,b,0);return 0;
}
void func(int y,int z,int x)
{x=0;while(1){x++;if(x%y==0&&x%z==0) break;}cout<<x;
}

埃尔米特函数
题目描述
输入给定的n 和正整数x，输出多项式的值。比如输入 n=1，x=2，输出值 4.00

#include<iostream>
using namespace std;
void func(double z,double y);
int main()
{int n,m;cin>>n>>m;func(n,m);return 0;
}
void func(double z,double y)
{func(1,0);func(2*z,1);func(2*z,y-1);cout<<y;
}