斐波那契数列
火车从始发站(称为第1站)开出,在始发站上车的人数为a,然后到达第2站,在第2站有人上、下车,但上、下车的人数相同,因此在第2站开出时(即在到达第3站之前)车上的人数保持为a人。从第3站起(包括第3站)上、下车的人数有一定规律:上车的人数都是前两站上车人数之和,而下车人数等于上一站上车人数,一直到终点站的前一站(第(n−1)站),都满足此规律。现给出的条件是:共有n个车站,始发站上车的人数为a,最后一站下车的人数是m(全部下车)。试问x站开出时车上的人数是多少?
对于全部的测试点,保证1≤ a ≤20,1≤ x ≤n ≤20,1 ≤ m ≤ 2×104。
输入格式
输入只有一行四个整数,分别表示始发站上车人数 a ,车站数 n ,终点站下车人数 m 和所求的站点编号 x 。
5 7 32 4
输出格式
输出一行一个整数表示答案:从 x 站开出时车上的人数。
整体思路
我们不妨先来列一个表格,a 代表始发站人数,t 代表第二站上车人数。
|
上车人数 |
下车人数 |
车上增加人数 |
出站时人数 |
1 |
a |
\ |
a |
a |
2 |
t |
t |
0 |
a |
3 |
1a+1t |
0a+1t |
1a+0t |
2a |
4 |
1a+2t |
1a+1t |
0a+1t |
2a+t |
5 |
2a+3t |
1a+2t |
1a+1t |
3a+2t |
6 |
3a+5t |
2a+3t |
1a+2t |
4a+4t |
7 |
5a+8t |
3a+5t |
2a+3t |
6a+7t |
8 |
8a+13t |
5a+8t |
3a+5t |
9a+12t |
9 |
13a+21t |
8a+13t |
5a+8t |
14a+20t |
······
我们不难发现,除了“出站时人数”这一列,其他几列都有数据符合斐波那契数列的规律(即第i项等于第i-1项+第i-2项),可以很轻松的用循环求出任意一列的 a , t 系数。
因为数据 n 最大只有20,我们可以把 1~n 站火车出站时的人数都用始发站人数 a 和第2站上车人数 t 表示出来。
蒟个栗子
拿样例来说:
始发站为5人,共有7站,结束时32人下车,求第4站驶出时人数。
(注意:总站数是7站,32人下车,所以第6站驶出时为32人。)
看到上面表格,第6站驶出时人数为 4a+4t ,所以:
4×5+4×t = 32
可以很轻松算出t=3。
再看第4站驶出时人数,为2a+t,所以:
2×5+3 = 13
最终得到的结果就是13。
这样除去数据预处理的时间,该解决方式的时间复杂的只有O(n).
代码实现看这里
#include<iostream>
using namespace std;
int a,n,m,x,t;
int Fibo[25];
struct train{//为了看上去明白就用了结构体,其实用二维数组或两个一维数组就行了
int a,t;//存储每一站火车出站时人数a和t的系数
}sum[25];
void pre()
{
Fibo[1]=1;
Fibo[2]=1;
for(int i=3;i<=n;i++)//求斐波那契数列
Fibo[i]=Fibo[i-1]+Fibo[i-2];
sum[1].a=1;//根据表格初始化值
sum[2].a=1;
sum[3].a=2;
for(int i=4;i<=n;i++)//根据表格规律计算a和t的系数
{
sum[i].a+=Fibo[i-4]+sum[i-1].a;
sum[i].t+=Fibo[i-3]+sum[i-1].t;
}
return ;
}
void solve()
{
t=(m-sum[n-1].a*a)/sum[n-1].t;//计算t的值(注意是终点站前一站)
cout<<sum[x].a*a+sum[x].t*t<<endl;//输出第x站火车出站时人数
return ;
}
int main()
{
cin>>a>>n>>m>>x;//读入始发站人数,总车站数,n-1站火车出站时人数
pre();//预处理
solve();
return 0;
}