题目 1168: 简单计算（先数学计算，递推得结论，然后再做题）

解题思路:

注意事项:

参考代码:

1.列出基本递推关系式子：

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]

2.要输入数据有：n,  a[0],  a[n+1],  以及  c[1]~~c[n];

3.求a[1];

4.分析题目：

（1）n<=3000,说明不可以用递归，否则栈溢出；

（2）数列a[]中，输入的是数据只是第一个数a[0]和最后一个数a[n+1]，用上面基本递推式子，发现中间有好多未知量，说明得根据递推式子，求a[1],和a[0],a[n+1],c[i]间的关系；

5.求关系

递推关系两遍同时乘以2，把分母2消除以便推导即：

2*a[n] = a[n-1]  + a[n+1] -2*c[n]

为了推导方便先假设n=5，则有一下式子

2*a[1]=a[0]+a[2]-2*c[1]

2*a[2]=a[1]+a[3]-2*c[2]

2*a[3]=a[2]+a[4]-2*c[3]

2*a[4]=a[3]+a[5]-2*c[4]

2*a[5]=a[4]+a[6]-2*c[5]

把以上式子加起来，可消元得到：

a[1]+a[5]=a[0]+a[6]-2*(sum(1~5))

这里sum(1~5)=c[1]+c[2]+....+c[5]

走到上面发现式子里面还有个未知量a[5],想办法把a[5]也消去；

返回第2步，令n=4，把式子加起来，可消元得到：

a[1]+a[4]=a[0]+a[5]-2*(sum(1~4))

再令n=3，把式子加起来，可消元得到：

a[1]+a[3]=a[0]+a[4]-2*(sum(1~3))

直到n=1

a[1]+a[1]=a[0]+a[2]-2*(sum(1~1))

把以上得到的所有式子罗列出来：

                            a[1] + a[5] = a[0] + a[6]- 2*(sum(1~5))
                            a[1] + a[4] = a[0] + a[5]- 2*(sum(1~4))
                            a[1] + a[3] = a[0] + a[4]- 2*(sum(1~3))
                            a[1] + a[2]=  a[0] + a[3]- 2*(sum(1~2))
                            a[1] + a[1] = a[0] + a[2]- 2*(sum(1~1))

再把这些式子加起来，消元得到：

   6*a[1]  =5*a[0]  +  a[6]  -  2*(sumx(1~5))

这里sumx(1~5)=sum(1~1)+sum(1~2)+sum(1~3)...+sum(1~5)  即：

       sumx(1~5)=c[1]+(c[1]+c[2])+(c[1]+c[2]+c[3])+.....+（c[1]+c[2]+..+c[5])

 11.最终：a[1] = ( 5*a[0] + a[6] - 2*(sumx(1~5)) )/6

 12.据归纳法当n=n时；

    a[1] = (  n*a[0]  +  a[n+1]  -  2*( sumx(1~n) )  )  /  (n+1)