从零开始算法之路 ----车站-蒲公英云

从零开始算法之路 ----车站

题目链接：https://ac.nowcoder.com/acm/problem/16782
题目来源：牛客网

题目描述

火车从始发站（称为第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

输出

1. (1) 原本解题思路：

  根据题目总结出了递推公式： passenger\[n\] = passenger\[n -1\] + up\[n - 2\] (当前车站的乘客人数等于上个车站的乘客人数加上 上上个(n - 2)车站的上车人数),所以要求当前车站的乘客人数必须算出第二个车站的上车人数，就想着设 第二个车站的上车人数为 X，然后根据最后 一 个车站的下车人数，列出一个方程组解出 X，那根据递推公式就可以求出任何一个站的乘客人数。但是根据这种方法好像有点难实现，有点烦。

(2) 正解解题思路：

   看了别人的代码才发现之前的思路有点不对，别人的思路是 直接假设 第二个站的上车人数范围为 0 ~ m 个人，用for 循环一个个去算，直到passenger\[n-1\] = m, 那么就找到了第二个站的上车人数，并把每个车站人数存在数组 passenger\[n\] 中，之后要哪个车站的人数去passenger\[n\] 中取就行了。

2.代码：

#include<stdio.h>
int main(){
    int a, n, m, x, up[25], down[25], passenger[25], i, j;
    scanf("%d %d %d %d", &a, &n, &m, &x);    
    //第一个站上车 a 人， 下车 0 人， 乘客人数 a 人 
    up[1] = a, down[1] = 0, passenger[1] = a; 
    //乘客总是递增的，最后下来m个人所以第二站下车人数只能在0到m之间
    for(i = 0; i < m; i++){
        up[2] = i, down[2] = i, passenger[2] = a;
        for(j = 3; j <= n; j++){
            //从第3站起（包括第3站),车的人数都是前两站上车人数之和
            up[j] = up[j-1] + up[j-2];
            //下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站）,都满足此规律
            down[j] = up[j-1];
            //由题意可得 递推公式 passenger[n] = passenger[n -1] + up[n - 2]
            //当前车站的乘客人数等于上个车站的乘客人数加上 上上个(n - 2)车站的上车人数
             passenger[j] = passenger[j -1] + up[j - 2];            
        }
        // 题目给的结束条件 
        //如果n-1站的人数等于m跳出
        if(passenger[n-1] == m){
            printf("%d", passenger[x]);
            return 0;  //结束循环 
        }
    }
}