前言
上次写博客居然都快是两年前了啊,总觉得荒废了好多时间,不过这是我活该吧. 中间我考了一个中考.在高中加入了信息竞赛的培训班(虽然就四个人),不过在编程这块也算走上正轨了吧. 这是课上提到的一题,还挺有意思的,于是我就在周末花了一点时间写掉了这题. 那么下面正式开始
1.题目解析
| 题目链接:[P1011 [NOIP1998 提高组] 车站 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P1011) |
火车从始发站（称为第 1 站）开出，在始发站上车的人数为a，然后到达第 2 站，在第 2 站有人上、下车，但上、下车的人数相同，因此在第 2 站开出时（即在到达第 3 站之前）车上的人数保持为 a 人。从第 3 站起（包括第 3 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 n−1 站），都满足此规律。现给出的条件是：共有 n 个车站，始发站上车的人数为 a，最后一站下车的人数是 m（全部下车）。试问 x 站开出时车上的人数是多少？
总体来讲就是个普及难度,不是很难,不过再难我应该也做不来了,所以来看题目.
此时我们读题,发现其实最主要的 难点 在于第二站的上车和下车的人数不知道,这样的题目题目对于我们来说就需要逆向去解决了.
不过对于这种一看有规律的题目,最好是画一个图
因为第二站上车下车的人数不知道,所以不妨设为t
Δ:离站后车上的人的变化量
那么此时观察规律(你们可以自己多写两组),不难得出Δ的值其实是一个斐波那契数列 不过此时仍然有一些难点要解决,由于t的值未知,那么对delta直接进行斐波那契的运算显然是不可行的,那么此时再次观察规律,得a与t的系数都是一个特殊的斐波那契
其中a的系数的数列为: 0 1 0 1 1 2 3 … t的系数的数列为: 0 0 1 1 2 3 5 …
后面就主要注意Δ值的下标和站数的关系就可以了
至此题目的所有难点都解析完了,接下来看用递归实现的代码解析
2.代码解析
(1) 递归实现斐波那契数列
首先是a的系数的斐波那契 此时封装成一个函数,便于后续的使用
int fib_a(int n)
{
if (n == 1)
return 1;//特判
if (n == 2)
return 0;//特判
return fib_a(n - 1) + fib_a(n - 2);//斐波那契递归
}
虽然数列是 0 1 0 …但是斐波那契是从第2,3个数开始的,所以出于便于理解,这里将第2,3个数作为数列的第一个数字开始
x的系数同理,只不过注意这里第一个数是0,第二个数是1
int fib_x(int x)
{
if (x == 1)
return 0;//特判
if (x == 2)
return 1;//特判
return fib_x(x - 1) + fib_x(x - 2);//斐波那契递归
}
(2)计算每站未知数系数的函数实现
在实现斐波那契后,我们得到的只是每站的delta中未知数的系数.
而最终与m相关联的出站后人数是之前所有delta和初始值的累加,所以为了方便处理,封装一个函数实现
先看a的系数
int p_a(int n)//输入第几站
{
int ans = 1;//人初始a的系数为一
for(int i =2;i<n;i++)
{
ans += fib_a(i-1);//累加delta
}
return ans;
}
由于第一站没有delta且第二个delta为零,所以n为一或二时特判,从第三站开始累加.特别注意的是数列中数位与i的关系为 数位=i-1
x系数的计算完全同理,但是要注意x系数的初始值为0
(3)t与答案的计算
t = (m - p_a(n-1)*a) / p_x(n-1);//计算t
int ans = a*p_a(x) + t*p_x(x);//计算答案
既然已经得到每站a与x的系数,那么根据题目,m是n-1站的人数,所以在下标处输入n-1,计算出t后,就很容易得出了.(不过这里好像有点不严谨,n在等于1或2时t是无意义的,测试点应该没有给这种数据,我觉得题目应该让n>=3,不然会有点歧义)
3.源码
#include <iostream>
using namespace std;
int fib_a(int n)
{
if (n == 1)
return 1;
if (n == 2)
return 0;
return fib_a(n - 1) + fib_a(n - 2);
}
int fib_x(int x)
{
if (x == 1)
return 0;
if (x == 2)
return 1;
return fib_x(x - 1) + fib_x(x - 2);
}
int p_a(int n)
{
int ans = 1;
for(int i =2;i<n;i++)
{
ans += fib_a(i-1);
}
return ans;
}
int p_x(int n)
{
int ans = 0;
for(int i = 2;i<n;i++)
{
ans += fib_x(i-1);
}
return ans;
}
int main()
{
int a, n, m, x, t;
cin >> a >> n >> m >> x;
t = (m - p_a(n-1)*a) / p_x(n-1);
int ans = a*p_a(x) + t*p_x(x);
cout<<ans;
return 0;
}
后面也没什么好说的了,送大家一张美图吧
