首页 > 其他 > 详细

Simple calculations

时间:2014-07-13 00:01:33      阅读:465      评论:0      收藏:0      [点我收藏+]

Description
有一个包含n+2个元素的数列a0, a1, ..., an+1 (n <= 3000, -1000 <= ai <=1000)。它们之间满足ai = (ai-1 + ai+1)/2 - ci (i=1, 2, ..., n)。现在给出a0, an+1, c1, ... , cn.。请编写程序计算出a1。

Input
输入的第一行是一个整数n。接下去的两行分别是a0和an+1,(精确到小数点后两位)再接下去的n行是ci(精确到小数点后两位),每个数字占一行。

Output
输出a1 ,其格式与 a0 相同。

Sample Input
1
50.50
25.50
10.15


Sample Output
27.85

 

解题思路:

一开始想用递归来求,可是数据挺大的,n<=3000,所以便想找找其中的规律,看看能不能列出一个算式让a[1]用a[0],a[n+1]和c[1~n]来表示。
首先可以列出以下算式:
2 * a[1] = a[0] + a[2] - 2 * c[1]

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

等式两边分别相加可得:
2 * (a[1] + ... + a[n]) = (a[0] + ... + a[n-1]) + (a[2] + ... + a[n+1]) - 2 * (c[1] + ... + c[n])

移项后得:
a[1] + a[n] = a[0] + a[n+1] - 2 * (c[1] + ... + c[n])

让下标n从1~n,列出以上算式:
a[1] + a[1] = a[0] + a[2] - 2 * c[1]

a[1] + a[2] = a[0] + a[3] - 2 * (c[1] + c[2])

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

等式两边分别相加后得:
(n + 1) * a[1] = n * a[0] + a[n+1] - 2 * (c[1] + (c[1] + c[2]) + ... + (c[1] + c[2] + ... +c[n])) 

AC代码:

#include<stdio.h>
#define MAX_NUM 3005
int main()
{
    double a[MAX_NUM], c[MAX_NUM];
    int n;
    scanf("%d", &n);
    scanf("%lf%lf", &a[0], &a[n+1]);
    for(int i = 1; i <= n; i++)
        scanf("%lf", &c[i]);
    int j = 1;
    double sum_1 = 0, sum_2 = 0;
    for(int i = 1; i <= n ; i++)
    {
        for(; j <= i; j++)
        {
            sum_1 += c[j];   
        }
        sum_2 += sum_1;
    }
    a[1] = (n * a[0] + a[n + 1] - 2 * sum_2) / (n + 1); 
    printf("%.2lf\n", a[1]);
    return 0;
}


Simple calculations,布布扣,bubuko.com

Simple calculations

原文:http://blog.csdn.net/userluoxuan/article/details/37700133

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!