63-数列求值

数列求值问答

35.92%
1000ms
262144K

数列求值

对于一个含有 $个元素的数列，A0,A1,⋯AnA_0, A_1, cdots A_nA0,A1,⋯An，满足这样的递归公式$

$A_i = frac{A_{i-1} + A_{i + 1}}{2} - C_i 1 le i le nAi=2Ai−1+Ai+1−Ci 1≤i≤n$

现在我们知道 $A0,An+1A_0, A_{n + 1}A0,An+1 和 C1,C2,⋯CnC_1, C_2, cdots C_nC1,C2,⋯Cn。$

现在请你帮忙计算 $A1A_1A1 的值。$

输入格式

第一行输入一个整数

第二行输入两个数 $A0A_0A0 和 An+1A_{n+1}An+1，接着是 nnn 个数据分别是 C1,C2,⋯CnC_1,C_2, cdots C_nC1,C2,⋯Cn。所有的数据均是两位小数的浮点数。$

输出格式

输出 $A1A_1A1 的值，结果保留两位小数。$

样例输入1

1
50.50 25.50
10.15

样例输出1

27.85

样例输入2

2
-756.89 52.52
172.22 67.17

样例输出2

-761.49
思路：其实就是一个递推的过程，但是会有未知数，如果让人写的话，麻烦在于递推，因为设一个未知数就可以，刚好计算是计算机的强项，所以问题就可以解决了，但是计算机在计算时是不会允许与未知数的，
故我们要想一个变通的方法，含有未知数的就算其实分为了两部分已知和未知，所以我们将一个数分为俩个部分，进行运算就可以实现带未知数的计算，例如a.z, a.w,分别代表已知数和未知数，a.w初始为1，
即可代表x,相当于我们只需记录x前的系数即可。
我是设a[n] = x；其他的已知数的w值均为0，a[n].z = 0, a[n].w = 1.

#include <bits/stdc++.h>
using namespace std;
typedef struct node{
	double z, w;
}Node;
Node a[1005], c[1005];

Node add(Node x, Node y){
	Node ss;
	ss.z = x.z + y.z;
	ss.w = x.w + y.w;
	return ss;
}
Node jian(Node x, Node y){
	Node ss;
	ss.z = x.z - y.z;
	ss.w = x.w - y.w;
	return ss;
}

int main(){
//	std::ios::sync_with_stdio(false);
	int n;
	double a0;
	cin >> n;
	cin >> a0 >> a[n + 1].z;
	for(int i = 1; i <= n; i++){
		cin >> c[i].z;
	}
	a[n].z = 0, a[n].w = 1;
	for(int i = n; i >= 1; i--){
		Node x1 = add(a[i], a[i]);  //2a[i]
		Node x2 = add(c[i], c[i]);  //2c[i]
		Node x3 = add(x1, x2);
		a[i - 1] = jian(x3, a[i + 1]);
	}
	if(a[0].w == 0){   //a[n] = 0; 
//		cout << "an = 0" << endl; 
		a[n].z = x; 
	}
	else{
		double x = (a0 - a[0].z) / a[0].w;
		a[n].z = x;
	}
	for(int i = n; i >= 2; i--){
		Node x1 = add(a[i], a[i]);  //2a[i]
		Node x2 = add(c[i], c[i]);  //2c[i]
		Node x3 = add(x1, x2);
		a[i - 1] = jian(x3, a[i + 1]);
	}
//		cout << a[1].z << endl;
	printf("%.2lf", a[1].z);
	
	return 0;
}