数列求值

发表于 | 分类于 ， ， | 阅读数 次

链接:数列求值

Description

  • 对于一个含有 n+2个元素的数列A0, A1, … , An，满足这样的递归公式: Ai = (Ai-1 + Ai+1) /2 - Ci 1≤i≤n
  • 现在我们知道A0, An+1和C1, C2, … , Cn
  • 现在请你帮忙计算A1的值。

    Input

  • 第一行输入一个整数n(1≤n≤1000)。
  • 第二行输入两个数A0, An+1，接着是 n个数据分别是C1, C2, … , Cn。所有的数据均是两位小数的浮点数。

    Output

  • 输出A1的值，结果保留两位小数。

    Sample Input

    1
    50.50 25.50
    10.15
2
-756.89 52.52
172.22 67.17

Sample Output

27.85
-761.49

题解

  • 根据公式可以推导出
  • A(2)==2A(1)-A(0)+2C(1) 先不看后面的C
  • A(3)==2A(2)-A(1)==3A(1)-2*A(0)
  • .
  • .
  • .
  • A(n+1)==(n+1)A(1)-nA(0)
  • 由于我们已知A(n+1) 看起来好像只需要这个公式就可以求出A(1) 然而还有我们忽略的C
  • 由于未知A(1) 先将A(1)看成0 然后根据这个式子地推出A(n+1)暂时命名为tp,跟正确的A(n+1)相差的只有(n+1)*A(1)
  • 剩下的就不用说了吧。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e3+11;
int n;
double tp,f[N],c;

int main(){
    cin>>n;
    cin>>f[0]>>tp;
    rep(i,2,n+1){
        cin>>c;
        f[i]=2*f[i-1]-f[i-2]+2*c;
    }
    printf("%.2lf\n",(tp-f[n+1])/(n+1));
    return 0;
}