Question

求解C语言基础题？

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

本关任务：使用栈将递归函数转化为非递归函数。

一定要用栈呀，讲思路就行了。有代码的话更好。

Answer 1

第x站新增人数为第x-2站上车人数，上车人数为第x-2和第x-1上车人数之和。
第一站 新增 a 上车a 出站车上人数 a

第二站 新增 0 上车b 出站车上人数 a
第三站 新增 a 上车a+b 出站车上人数 2a
第四站 新增 b 上车a+2b 出站车上人数 2a+b
第五站 新增 a+b 上车2a+3b 出站车上人数 3a+2b
第六站 新增 a+2b 上车3a+5b 出站车上人数4a+4b
第七站 新增 2a+3b 上车5a+8b 出站车上人数6a+7b
第八站 新增 3a+5b 上车8a+13b 出站车上人数9a+12b
其实很容易找到出站车上人数 a, b系数之间的规律。a的系数a[i]=a[i-1]+a[i-2]-1，b的系数b[i]=b[i-1]+b[i-2]+1在i>=4之后都成立。如果你想把递归方法变成非递归方法，可以利用这些系数规律来求。
我这里给你举例递归方式，程序不是为了更快执行效率，而是为了展示思路，所以本身没有任何优化。
基本思路就是递归方式求a[i]和b[i], 通过求得的结果分推出b的值。a b的的值确定之后就可以轻易得到x站开出时车上的人数。
// 程序没有经过严格测试，如果有错误自行修复。

#include <stdio.h>
// ================================================================
// 如果第二站上下车人数为零
int up1(int index) {
if(index == 1) return 1; // 第一站上车
if(index == 2) return 0; // 第二站上车
return up1(index-1)+up1(index-2);
}
int down1(int index) {
if(index < 3) return 0;
return up1(index-1);
}
int sum1(int index) { // index站出站人数
int sum = 0;
for(int i = 1; i <= index; i++)
sum += up1(i) - down1(i);
return sum;
}
// ================================================================
// 如果第一站总人数为零
int up2(int index) {
if(index == 1) return 0;
if(index == 2) return 1;
return up2(index-1)+up2(index-2);
}
int down2(int index) {
if(index == 1) return 0;
if(index == 2) return 1;
return up2(index-1);
}
int sum2(int index) { // index站出站人数
int sum = 0;
for(int i = 1; i <= index; i++)
sum += up2(i) - down2(i);
return sum;
}

int main()
{
// 请注意m实际是第n-1站开出的人数
int a, b=0, m, n, x;
scanf("%d%d%d%d",&a,&n,&m,&x);
printf("\na=%d\tn=%d\tm=%d\tx=%d\n",a,n,m,x);
int m1 = sum1(n-1);
int m2 = sum2(n-1);
// 如果b为负数，或者无法整除，表明数据错误。检错自行添加
b = (m-a*m1)/m2;
int x1 = sum1(x);
int x2 = sum2(x);
int total = a*x1+b*x2;
printf("\n第%d站开出时车上的人数%d\n",x,total);
}