【OJ】关于某种规律数组的简单计算问题

本文主要是介绍【OJ】关于某种规律数组的简单计算问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

有一个n+2个元素a[0], a[1], …, a[n+1] (n <= 3000, -1000 <= a[i] <=1000)构成的数列.
已知对i=1, 2, …, n有a[i] = (a[i-1] + a[i+1])/2 - c[i].
给定a0, a[n+1], c[1], … , c[n]. 写一个程序计算a[1].

输入

第一行是整数n. 接下来两行是a[0]和a[n+1], 其小数点后有两位数字. 其后的n行为ci, 每行一个数.

输出

输出为a[1], 格式与a[0], a[n+1]相同.

样例输入

样例输出

27.85

分析过程

问题分析：关于这种的题目，也就是说数组中第 i 项跟前面的一项和后面的一项都有等式关系这样的问题，第一反应就是递归了，但是我用递归的方式检测数据是符合条件的。但是却一直提示说 内存超限 。
所以我不得不研究数学公式了，这不是等差数列，也不是等比数列，似乎没有什么规律可循，其实不然，用草稿纸多算算，可以得到结论如下：

a[1] = (a[0]+a[2])/2 - c[1]
a[2] = (a[1]+a[3])/2 - c[2]
a[3] = (a[2]+a[4])/2 - c[3]
...
a[n] = (a[n-1]+a[n+1])/2 - c[n]

左边全部加起来，右边也全部都加起来，等式依然成立，可以算出结论如下：

a[1]+a[n] = a[0] + a[n+1] - 2*Tn  (其中Tn = c[1] + c[2] + ... + c[n])

接着我们把 a[n] 中的n写成n-1，则下面的等式一定也成立（n>=2）

a[1]+a[n-1] = a[0]+a[n] - 2*Tn-1

把上面那两个式子对应加起来，可以得到

2*a[1] + a[n-1] = 2*a[0]+a[n+1] -2*(Tn+Tn-1)

类似地，可以得到结论如下：

3*a[1] + a[n-2] = 3*a[0]+a[n+1] - 2*(Tn+Tn-1+Tn-2)
....
n*a[1] + a[1] = n*a[0]+a[n+1] - 2*(Tn+Tn-1+Tn-2+...+T1)

所以可以得出结论为：

a[1] = (n*a[0]+a[n+1]-2*(Tn+Tn-1+Tn-2+...+T1))/(n+1)

所以这个题目代入这个公式进行计算就好了。

解题代码

#include <iostream>
#include <cstdio>
using namespace std;// 计算数组中前size项之和
double Tn(double c[], int size)
{double result = 0.00;int i;for(i=1; i<=size; i++){result += c[i];}return result;
}// 记数组前i项的和为Ti 而Sn则是把所有的Ti加起来
double Sn(double c[], int n)
{int i;double result=0.00;for(i=1; i<=n; i++){result += Tn(c,i);}return result;
}// written by smileyan
int main()
{int n,i;double a[3002];double c[3000];cin>>n;cin>>a[0]>>a[n+1];for(i=1; i<=n; i++){cin>>c[i];}// 单纯地套公式计算就好了，是不是很简单？ 谢谢支持Smileyan！double y = (double((double)n*a[0]+(double)a[n+1])-2*Sn(c,n))/(n+1);printf("%.2lf\n",y);return 0;
}