1>递归解决年龄的问题
五个人在一起,问第5个人,他说比第四个人大两岁,问第四个人,他说比第三个人大两岁….最后一人说他十岁,求输入几个人时求出对应的年龄
归纳为数学公式
age(n-1)+2 (n>1)
age(n)=
10 (n=1)
//递归函数
int age(int n){
if (n==1) {
return 10;
}else {
return age(n-1)+10;
}
}2>递归法求解分鱼问题
问题描述
有5个人（A,B,C,D,E）分鱼。A先把鱼分成5份，然后扔掉一条多出的鱼，之后A拿走一份。B把剩下的鱼分成5份，然后扔掉一条多出的鱼，之后B拿走一份。然后C,D,E也做同样的事。请问这些鱼至少有多少条？
问题分析
假设5个人合伙不了x条鱼
假设Xn为第n个人分鱼前的总数,则(Xn-1)/5必须为整数,
x4=4(X5-1)/5;
x3=4(X4-1)/5;
x2=4(X3-1)/5;
x1=4(X2-1)/5;
因此递归函数
int fish (int n,int x) {
if (x%5==1) {
if (n==1)
return 1;
else
return fish(n-1,(x-1)/5*4);
}
return 0;
}
int main(int argc,char*argv[]) {
int x,i=0,flag=0;
do {
i++;
x=i*5+1;
if (fish(5,x)) {
flag=1;
printf("合伙捕到的鱼数为%d",x);
}
}while(!flag);
}
3>汉诺塔问题
个人觉得汉诺塔这个递归算法比电子老鼠的难了一些，不过一旦理解了也还是可以的，其实网上也有很多代码，可以直接参考。记得大一开始时就做过汉诺塔的习题，但是那时代码写得很长很长，也是不理解递归的结果。现在想起来汉诺塔的算法就3个步骤：第一，把a上的n-1个盘通过c移动到b。第二，把a上的最下面的盘移到c。第三，因为n-1个盘全在b上了，所以把b当做a重复以上步骤就好了。所以算法看起来就简单多了。不过
static int step = 0;
void moveing( char sour, char dest )
{
printf ( "move from %c to %c \n", sour, dest );
}
void hanoi ( int n, char sour, char temp, char dest )
{
if ( n == 1 )
{
moveing ( sour, dest );
++step;
}
else
{
printf("n===%d\n",n);
hanoi ( n-1, sour, dest, temp );
moveing ( sour,dest );
++step;
hanoi ( n-1, temp, sour, dest );
}
}
int main ( int argc, char **argv )
{
int n= 5;
hanoi ( n, 'A', 'B', 'C' );
printf ( "Total steps is %d\n", step );
return 0;
}
#endif
4>猴子吃桃
猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。
//以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘了多少。
递归函数
Ai表示第i天吃完后剩下的桃子数
A0=2X(A1+1);
A1=2X(A2+1);
….
A8=2(A9+1);
A9=1;
int A(int n){
if(n>=9)
return 1;
else
return 2*(A(n+1)+1);
}
int main (int argc,char**argv){
printf("猴子摘了总共%d个桃子",A(0));
}循环来做
int main (int argc,char**argv){
int day,x1,x2;
day=9;
x2=1;
while (day>0) {
x1=2*(x2+1);
x2=x1;
day--;
}
printf("猴子摘了总共%d个桃子",x2);
return 0;
}
4>逆序输出数字
void reverse(int n){
if (n) {
printf("%d",n%10);
reverse(n/20);
}
}逆序输出字符串
void rvstr(){
char ch;
scanf("%c",&ch);
if (ch!='\n') {
rvstr();
}
printf("%c",ch);
}
int main (int argc,char**argv){
printf("请输入一个字符串");
rvstr();
printf("\n");
return 0;
}
5>最大公约数
#if 0
//递归函数
int main()
{
int n,m;
int GCD(int,int);
scanf("%d %d",&n,&m);
printf("%d\n",GCD(n,m));
}
int GCD(int n,int m)
{
if(m<=n)
if(n%m==0)
return(m);
else
return GCD(m,n%m);
else
return GCD(m,n);
}
#endif
//穷举法
//两个最大公约数
#if 0
int main(int argc,char* argv[]){
int m,n;
printf("输入两个数:\n");
scanf("%d%d",&m,&n);
//交换两个数,m存大值,n存小值
if (n>m) {
int tmp=m;
m=n;
n=tmp;
}
int max=1;//最大公约数
for (int i=1; i<n; i++) {
if (n%i==0&&m%i==0) {
max=i;
}
}
printf("最大公约数:%d",max);
return 0;
}
#endif
#if 0
//转转相除法
int main(int argc,char* argv[]){
int m,n;
printf("输入两个数:\n");
scanf("%d%d",&m,&n);
//交换两个数,m存大值,n存小值
if (n>m) {
int tmp=m;
m=n;
n=tmp;
}
int b=m%n;
while (b) {
m=n;//m为小值
n=b;//n为余数
b=m%n;//辗转相除
}
printf("最大公约数:%d",n);
return 0;
}
#endif
6>兔子产仔,斐波纳妾
#if 0
//斐波那契
//递归
int fab(int i){
if (i==0||i==1) {
return i;
}else {
return fab(i-1)+fab(i-2);
}
}
int main ( int argc, char **argv )
{
int result=fab(8);
printf("递归:result==%d\n",result);
int fib=0,fib1=1,fib2=1;
for (int i=2; i<8; i++) {
fib=fib1+fib2;
fib2=fib1;
fib1=fib;
}
printf("循环体fib==%d\n",fib);
return 0;
}
#endif7递归求角谷猜想
//角谷猜想在一定范围内成立
//递归函数
int jiaogu(long long n){
if (n==1) {
printf("-->%lld",n);
return 1;
}
else
{
if (n%2) {
printf("-->%lld",n);
n=3*n+1;
return jiaogu(n);
}
else{
printf("-->%lld",n);
n/=2;
return jiaogu(n);
}
}
}
//验证角谷猜想
int main ( int argc, char **argv )
{
jiaogu(1189989898976767145);
return 0;
}
#endif