问题描述:火车从始发站(第 1站)开出,在始发站上车的人数为 a,然后到达第 2 站,在第 2 站有人上、下车,但上、下车的人数相同,因此在第 2 站开出时车上的人数保持为 a 人。从第 3 站起,上、下车的人数有如下规律:上车的人数都是前两站上车人数之和,而下车人数等于上一站上车人数,一直到终点站的前一站。已知:共有 n 个车站,始发站上车的人数为 a ,终点站全部下车的人数是 m。试问 第x 站开出时车上的人数是多少?程序运行时,先输入四个整数:始发站上车人数 a,车站数 n,终点站下车人数 m 和所求的站点编号 x。要求输出从 x 站开出时车上的人数。
根据题意列出上车下车人数的表格:
车站 |
进站前人数 |
上车人数 |
下车人数 |
出站人数 |
1 |
0 |
a |
0 |
a |
2 |
a |
b |
b |
a |
3 |
a |
a+b |
b |
2a |
4 |
2a |
a+2b |
a+b |
2a+b |
5 |
2a+b |
2a+3b |
a+2b |
3a+2b |
… |
… |
… |
… |
… |
n-1 |
? |
? |
? |
m |
n |
m |
0 |
m |
0 |
根据表格本题的关键在于根据m求出b
m=f(n-1)a+g(n-1)b
求出f和g即可
而出站人数=进站人数 + 上车人数 - 下车人数
每站的上车人数和下车人数可以根据题意递推求得
据此可解决问题
C++代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
| #include <iostream> #include <string>
using std::cin; using std::cout; using std::endl; using std::string;
int upa(int n){ if(n==1){ return 1; }else if(n==2){ return 0; }else{ return upa(n-1) + upa(n-2); } }
int upb(int n){ if(n==1){ return 0; }else if(n==2){ return 1; }else{ return upb(n-1) + upb(n-2); } }
int downa(int n){ if(n==1 || n==2){ return 0; }else{ return upa(n-1); } }
int downb(int n){ if(n==1){ return 0; }else if(n==2){ return 1; }else { return upb(n-1); } }
int f(int n){ if(n==1 || n==2){ return 1; }else{ return (upa(n) - downa(n)) + f(n-1); } }
int g(int n){ if(n==1 || n==2){ return 0; }else{ return (upb(n) - downb(n)) + g(n-1); } } int main() { int a, n, m, x; int b; cout << "输入始发站上车人数,车站数,终点站下车人数和所求的站点编号:"<<endl; cin >> a; cin >> n; cin >> m; cin >> x; int ans = 0; b = (m-(f(n-1) * a)) / g(n-1); ans = (f(x)*a) + (g(x)*b); cout <<"第"; cout <<x; cout <<"站开出时车上的人数是:"; cout <<ans<<endl; return 0; }
|