首页 > 代码库 > 递归算法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