color read code 技术 alt lib pri blog
火车从始发站(称为第 1 站)开出,在始发站上车的人数为 a,然后到达第 2 站,在第 2 站有人上、下车,但上、下车的人数相同,因此在第 2 站开出时(即在到达第 3 站之前)车上的人数保持为 a 人。从第 3 站起(包括第 3 站)上、下车的人数有一定规律:上车的人数都是前两站上车人数之和,而下车人数等于上一站上车人数,一直到终点站的前一站(第 n-1 站),都满足此规律。现给出的条件是:共有 N 个车站,始发站上车的人数为 a,最后一站下车的人数是 m(全部下车)。试问 x 站开出时车上的人数是多少?
输入格式:
a(<=20),n(<=20),m(<=2000),和 x(<=20),
输出格式:
从 x 站开出时车上的人数。
输出样例 #1:
- 5 7 32 4
- 13解法一:暴力枚举(有点不靠谱,由于测试数据太水,竟让我给水过了)
- #include
- #include
- #include
- #includeusing namespace std;
- int read()
- {
- intx=0,f=1;
- charch=getchar();
- while(ch<'0'||ch>'9')
- {
- if(ch=='-') f=-1;
- ch=getchar();
- }
- while(ch>='0'&&ch<='9')
- {
- x=x*10+ch-'0';
- ch=getchar();
- }
- returnf*x;
- }
- int main()
- {
- inta=read(),n=read(),m=read(),b=read();
- inton[21],oncar[21],down[21];
- on[1]=a;
- oncar[1]=a;
- for(inti=0;;i++)
- {
- on[2]=i;
- oncar[2]=a;
- down[2]=i;
- for(intj=2;j<=n-1;j++)
- {
- oncar[j]=oncar[j-1]+on[j]-down[j];
- on[j+1]=on[j-1]+on[j];
- down[j+1]=on[j];
- }
- if(oncar[n-1]==m)break;
- }
- printf("%d\n",oncar[b]);
- return 0;
- }
法二:
通过分析题目我们可以发现以下规律
以下是上车人数的规律
- 通过观察上述表格会发现:红色部位和蓝色部位都是斐波那契数列耶!!
- 那就好玩了这样我们就可以推出这样一个方程上车人数=f(x-2)a+f(x-1)t
- 车上人数的规律也就是说车上人数=前一站人数+上两站人数(1站);
- 废话少说,下面提供蒟蒻代码
- #include#include#include#include#include < string > using namespace std;
- int main() {
- int a,
- b,
- n,
- m,
- x,
- fibo[21] = {
- 0
- };
- scanf("%d%d%d%d", &a, &n, &m, &x);
- fibo[0] = 0;
- fibo[1] = 1;
- for (int i = 2; i <= n; i++) fibo[i] = fibo[i - 1] + fibo[i - 2];
- //f[n-1]=fibo[n-2]*b+fibo[n-3]*a
- //m=fibo[n-2]*b+fibo[n-3]*a+a-b
- //m=(fibo[n-2]-1)*b+(fibo[n-3]+1)*a
- b = (m - (fibo[n - 3] + 1) * a) / (fibo[n - 2] - 1);
- printf("%d", (fibo[x - 1] - 1) * b + (fibo[x - 2] + 1) * a);
- }
车站——斐波那契 (再做做)
来源: http://www.bubuko.com/infodetail-2015505.html