目录
递推的概念
递推是一种处理问题的重要方法。
递推通过对问题的分析,找到问题相邻项之间的关系(递推式),从起点出发(首项或者末项)然后使用循环不断地迭代,得到最后需要的结果。
训练:斐波那契数列
对于Fibonacci数列,已知:fib(1) = 1; fib(2) = 1; 从第三项开始满足公式fib(i) = fib(i-1) + fib(i-2)。输入一个整数n(1<=n<=100),求fib(n)的值。
【输入描述】一行:一个整数n。
【输出描述】一行:feibonacci数列第n项的值
【样例输入】5
【样例输出】5
解析
1.问题求的是斐波那契数列第i项的数值。
2.前两项的数值,题目中已经给出,分别为:
fib(1) = 1; fib(2) = 1;
3.从第3项开始,满足如下规律:
fib(i) = fib(i-1) + fib(i-2);
即当前项由前两项之和构成。
4.我们可以根据题目给出的fib(1)、fib(2)推出fib(3),
再按照顺序由fib(2)、fib(3)推出fib(4),以此类推。
参考代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n,f1,f2,f3;
cin>>n;
f1=f2=f3=1;//初始化,f3表示第n项
for(long long i=3;i<=n;i++)
{
f3=f1+f2;
f1=f2;
f2=f3;
}
cout<<f3;
return 0;
}
训练:上台阶
楼梯有n(1<=n<=100)阶台阶,上楼时可以一步上1阶,也可以一步上2阶,也可以一步上3阶,编程计算共有多少种不同的走法。
【输入描述】输入的每一行包括一组测试数据,即为台阶数n。最后一行为0,表示测试结束。
【输出描述】每一行输出对应一行输入的结果,即为走法的数目。
【样例输入】
1
2
3
4
0
【样例输出】
1
2
4
7
参考代码
#include<bits/stdc++.h>
using namespace std;
long long a[105];
//a[i]表示i层楼梯方案数
int main()
{
int n,t;
a[1]=1,a[2]=2,a[3]=4;
//边界条件
while(1)
{
cin>>t;
if(!t) break;
if(a[t]){ //如果已经计算过,直接输出
cout<<a[t]<<endl;
continue;
}
for(int i=4;i<=t;i++)
a[i]=a[i-1]+a[i-2]+a[i-3];
//从第4层楼梯开始
//每一步有3种方案:1阶、2阶、3阶
//分别对应 a[i-1]、a[i-2]、a[i-3]
cout<<a[t]<<endl;
}
return 0;
}
训练:信封
现在有n封信和n个信封,如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。
【输入描述】1行:输入一个整数n。
【输出描述】1行:输出一个整数,表示所有的情况数。
【样例输入】4
【样例输出】9
解析
先任取一封信,此时可供选择的信封有:n-1种情况。
每种情况下,我们在放置这封信的时候有2种方案:
- 这封信的位置,不与剩余的任意一封信互换,此时,剩余的问题就是:将n-1封信,错放在n-1个信封里,即f(n-1)
- 这封信的位置,与剩余的任意一封信互换,此时会有2个信封被使用掉。剩余的问题就是:将n-2封信,错放在n-2个信封里,即f(n-2),得出递推式:f(n)=(n-1)*(f(n-1)+f(n-2))。边界是:f(1)=0,f(2)=1。
参考代码
#include<bits/stdc++.h>
using namespace std;
long long f[25];
int main()
{
int n;
cin>>n;
f[1]=0,f[2]=1;
for(int i=3;i<=n;i++)
{
f[i]=(i-1)*(f[i-1]+f[i-2]);
}
cout<<f[n];
return 0;
}
从入门到算法,再到数据结构,查看全部文章请点击此处http://www.bigbigli.com/
标签:信封,01,int,样例,long,fib,算法,递推 From: https://blog.csdn.net/qq_39434533/article/details/139624689