C语言入门算法——车站

题目描述：

火车从始发站（称为第 1 站）开出，在始发站上车的人数为 a，然后到达第 2 站，在第 2 站有人上、下车，但上、下车的人数相同，因此在第 2 站开出时（即在到达第 3 站之前）车上的人数保持为 a 人。从第 3 站起（包括第 3 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 n−1 站），都满足此规律。现给出的条件是：共有 n 个车站，始发站上车的人数为 a，最后一站下车的人数是 m（全部下车）。试问 x 站开出时车上的人数是多少？

输入格式

输入只有一行四个整数，分别表示始发站上车人数 a，车站数 n，终点站下车人数 m 和所求的站点编号 x。

输出格式

输出一行一个整数表示答案：从 x 站开出时车上的人数。

输入输出样例

输入 #1

5 7 32 4

输出 #1

13

说明/提示

对于全部的测试点，保证 1≤a≤20，1≤x≤n≤20，1≤m≤2×10^4。

题目来源

P1011 [NOIP1998 提高组] 车站

思路及部分代码：

1. 根据第二站上车人数，算出终点站下车人数

//按照固定规律计算最后一站下车人数
int station(int a,int n, int test){
    //如果是前两站为终点
    if(n == 1 || n==2) return a;
    
    int car_people_number = a;      //最初车上人数
    int people_number[2]={a,test};   //记录三站上车人数
 
    for(int i=3;i < n ;i++){         //到n-1站结束
        //更新车上人数
        car_people_number = car_people_number + people_number[0] ;
        //更新上车人数
        int TS =  people_number[1];
        people_number[1] = people_number[0] + people_number[1];
        people_number[0] = TS;
    }
    //printf("car_people_number = %d\r\n",car_people_number);
    return car_people_number;   //返回最终车上人数
}

2. 根据a,n,m求出第二站的上车人数

//判断第二站上次人数
int two_people(int a,int n,int m){
    int i=0;
    while(1){
        if(m == station(a,n,i)){
            //printf("two = %d\r\n",i);
            return i;
        }
        i++;
        //超出数据
        if(i >= 2*10000) return -1;
    }
}

3.代码整合

        以上两个函数可以计算第二站的上车人数，而第一个函数可以根据输入的车站数量n计算车上的总人数。同样的逻辑也可以用于完成题目要求。

int main (){
    int a,n,m,x;
    scanf("%d %d %d %d",&a,&n,&m,&x);
 
    //输出题目要求的下车数
    int two = two_people(a,n,m);
    printf("%d\r\n",station(a,x+1,two));
    
    return 0;
}

总代码：

#include <stdio.h>
 
 
//按照固定规律计算最后一站下车人数
int station(int a,int n, int test){
    //如果是前两站为终点
    if(n == 1 || n==2) return a;
    
    int car_people_number = a;      //最初车上人数
    int people_number[2]={a,test};   //记录三站上车人数
 
    for(int i=3;i < n ;i++){         //到n-1站结束
        //更新车上人数
        car_people_number = car_people_number + people_number[0] ;
        //更新上车人数
        int TS =  people_number[1];
        people_number[1] = people_number[0] + people_number[1];
        people_number[0] = TS;
    }
    //printf("car_people_number = %d\r\n",car_people_number);
    return car_people_number;   //返回最终车上人数
}
 
 
//判断第二站上次人数
int two_people(int a,int n,int m){
    int i=0;
    while(1){
        if(m == station(a,n,i)){
            //printf("two = %d\r\n",i);
            return i;
        }
        i++;
        //超出数据
        if(i >= 2*10000) return -1;
    }
 
}
 
 
int main (){
    int a,n,m,x;
    scanf("%d %d %d %d",&a,&n,&m,&x);
 
    //输出题目要求的下车数
    int two = two_people(a,n,m);
    printf("%d\r\n",station(a,x+1,two));
 
    return 0;
}

总结：

        程序的主要目的是计算一个公交车上乘客的人数变化，并根据输入的条件来确定最后一站的下车人数。程序的基本逻辑是模拟了公交车途经若干站后的人数变化过程，并通过函数 station 计算每一站的乘客人数，然后通过 two_people 函数来确定第二站的上车人数。

不足之处：

1. two_people 函数中的 while 循环没有合适的退出条件，限制 i 的最大值为 2*10000 也不是一个很好的做法。应该考虑使用更有效的搜索方法，避免不必要的循环次数。

2. 程序中缺少注释，特别是对于一些关键函数的作用和参数含义，应该添加更多的注释以提高代码的可读性。

3. 变量命名可以更具有描述性，以便于他人理解代码的意图。

4. 程序中没有对输入参数进行有效性检查和边界情况处理，例如输入的站数 n、查询的站数 x 等应该做合理性判断，以避免潜在的错误或异常情况。

改进建议：

1. 在 two_people 函数中，使用更有效的搜索方法来确定第二站的上车人数 m 对应的位置 i。

2. 在 two_people 函数中，添加合适的退出条件，避免不必要的循环次数。

3. 在程序中添加更多的注释，特别是对于一些关键函数的作用和参数含义，以提高代码的可读性。

4. 变量命名应该更具有描述性，以便于他人理解代码的意图。

5. 对输入参数进行有效性检查和边界情况处理，例如输入的站数 n、查询的站数 x 等应该做合理性判断，以避免潜在的错误或异常情况。

6. 考虑使用更高效的算法来解决问题，例如在 two_people 函数中可以使用更快速的查找方法来确定第二站的上车人数 m 对应的位置 i。

7. 在程序中加入更多的错误处理机制，例如对于无法找到满足条件的 i 值的情况应该有合适的异常处理或返回值。