首页 > 代码库 > 递归算法1

递归算法1

今天学了递归算法,下面的题目是对递归的理解

 &1.问第n个学生多大

题目描述

例2.1有n个学生坐在一起
问第n个学生多少岁?他说比第n-1个学生大2岁.
问第n-1个学生岁数,他说比第n-2个学生大2岁.
..........................................................
问第2个学生,说比第1个学生大2岁.
最后问第1个学生,他说是10岁.
请问第n个学生多大?

输入

输入n

输出

输出第n个学生的年龄

样例输入

5

样例输出

18

 

思路:(关键点为第一个学生的年龄)

        第1个学生年龄为10岁(往后每个学生比前一个学生大两岁)

        n          age

        1           10  (当n=1时age=10,这个条件要单独列出)

 

        2           age(2-1)+2

        3           age(3-1)+2

        ...           ...

        n           age(n-1)+2

 

#include<iostream>
using namespace std;
int fac(int a)
{
    int age;
    if(a==1){return age=10;}
    else return fac(a-1)+2;
}
int main()
{
    int n;
    cin>>n;
    cout<<fac(n)<<endl;
    return 0;
}

 

 &2.Fibonacci

题目描述

?例5.2 求Fibonacci数列问题。
─斐波那契数列指的是这样一个数列:
─0、1、1、2、3、5、8、13、21、……
─F[0]=0, F[1]=1, F[i]=F[i-1]+F[i-2], i>=2;
编程输出前n个Fibonacci数

输入

输入n

输出

输出前n个Fibonacci数

样例输入

5

样例输出

0

1

1

2

3

思路:

技术分享

F[5]=F[4]+F[3];

F[4]=F[3]+F[2];

F[3]=F[2]+F[1];

F[2]=F[1]+F[0];(到这里结束,并且F[1].F[2]的值知道,故先分情况讨论)

 #include <iostream>
 using namespace std;
 int f(int x)
{
     if(x == 0){
         return 0;
     }
     else if(x == 1){
       return 1;
     }
     else return f(x-1)+f(x-2);
}
 int main(){
    int n;
     cin >> n;
    for(int i = 0; i < n; i++)
{
        cout << f(i) << endl;
  }   
  return 0;
 }

&3.汉诺塔问题

题目描述

汉诺(Hanoi)塔问题:古代有一个梵塔,塔内有三个座A、B、C,A座上有n个盘子,盘子大小不等,大的在下,小的在上(如图)。有一个和尚想把这n个盘子从A座移到C座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。在移动过程中可以利用B座,要求打印移动的步骤。如果只有一个盘子,则不需要利用B座,直接将盘子从A移动到C。

输入

输入盘子个数n

输出

输出盘子最少移动的步骤

样例输入

3

样例输出

1:A->C

2:A->B

3:C->B

4:A->C

5:B->A

6:B->C

7:A->C

思路:

技术分享

技术分享

(设A中有n个堆叠的木块,将n-1个看成整体,将第n个看成另一个整体)

第一步:将n-1从A移到B中,此时n仍在A中;

第二步:将A中的n移到C中,n-1不动;

第三步:将B中的n-1移到C中,此时完成堆塔。

#include<iostream>
using namespace std;
int i=1;
void hannoi(int n,char a,char b,char c)
{
    if(n==1)
    {
        cout<<i<<":"<<a<<"->"<<c<<endl;
        i++;
    }
    else {
        hannoi(n-1,a,c,b);
        cout<<i<<":"<<a<<"->"<<c<<endl;
         i++;
        hannoi(n-1,b,a,c);
    }
}
int main()
{
    int n;
    char one=‘A‘,two=‘B‘,three=‘C‘;
    cin>>n;
    hannoi(n,one,two,three);
    return 0;
}

递归算法1