题目描述
有一个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行为c[i](同样是两位小数), 每行一个数.
输出
输出为a[1], 格式与a[0], a[n+1]相同.
样例输入
1
50.50
25.50
10.15
样例输出
27.85
大家可以自行先动脑思考然后上机提交,下面是一位大神的优秀题解分享给大家:
==============================================================
解题思路:
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.求关系
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)
参考代码:
#include <stdio.h>
#include <malloc.h>
/*-----------------------------------------------------*/
void traceback( double *A, double *C, int n );
void input( double *A0, double *An_add1, double *C, int n );
double sumx( double *C, int n );
void function( double A0, double An_add1, double *C, int n );
int main()
{
double *C;
int n;
double A0, An_add1; //分别代表a[0], a[n+1]
while ( scanf( "%d", &n ) != EOF )
{
C = (double *) malloc( (n + 1) * sizeof(double) ); //为c[]开辟空间
input( &A0, &An_add1, C, n ); //输入n, a[0], a[n+1], 以及 c[1]~~c[n];
function( A0, An_add1, C, n ); //运行
}
return(0);
}
/*-----------------------------------------------------*/
void function( double A0, double An_add1, double *C, int n )
{
double A1 = (n * A0 + An_add1 - 2 * sumx( C, n ) ) / (n + 1); //求A1
printf( "%.2lf\n", A1 ); //输出A1
}
/*-----------------------------------------------------*/
void input( double *A0, double *An_add1, double *C, int n )
{
scanf( "%lf%lf", A0, An_add1 ); //输入a[0], a[n+1]
for ( int i = 1; i <= n; i++ ) //输入c[1]~~c[n]
scanf( "%lf", &C[i] );
}
/*-----------------------------------------------------*/
double sumx( double *C, int n )
{
double sum = 0;
for ( int i = 1; i <= n; i++ ) //求推导公式中的sumx(1~n)
{
for ( int j = 1; j <= i; j++ )
sum += C[j];
}
return(sum); //返回sumx(1~n)
}
来自 我们网站的Manchester大神,可以点击阅读全文看大神的博客!