Posted on 2010-08-06 16:52
MiYu 閱讀(1011)
評論(3) 編輯 收藏 引用 所屬分類:
ACM ( 雜題 ) 、
ACM ( 數論 )
MiYu原創, 轉帖請注明 : 轉載自
______________白白の屋題目地址:
http://acm.hdu.edu.cn/showproblem.php?pid=2086
題目描述:
Problem Description
有如下方程：Ai = (Ai-1 + Ai+1)/2 - Ci (i = 1, 2, 3, 
. n).
若給出A0, An+1, 和 C1, C2, ..Cn.
請編程計算A1 = ?
Input
輸入包括多個測試實例。
對于每個實例，首先是一個正整數n,(n <= 3000); 然后是2個數a0, an+1.接下來的n行每行有一個數ci(i = 1, .n);輸入以文件結束符結束。
Output
對于每個測試實例，用一行輸出所求得的a1(保留2位小數).
Sample Input
1
50.00
25.00
10.00
2
50.00
25.00
10.00
20.00
Sample Output
27.50
15.00
這道題的關鍵在于公式的推導, 公式推出來問題就解決了:
Ai = (Ai-1 + Ai+1)/2 - Ci (i = 1, 2, 3, . n). 用A5做示范，就能猜測出公式來。證明方法可以采用數學歸納法。這里證明從略。
A5 = (A4 + A6) / 2 - C5
A4 = (A3 + A5) / 2 - C4 = A3 / 2 + A4 / 4 + A6 / 4 - C5 / 2 - C4
=>A4 = 2A3/3 + A6/3 - 2C5/3 - 4C4/3
A3 = (A2 + A4) / 2 - C3 = A2 / 2 + A3 / 3 + A6 / 6 - C5 / 3 - 2C4 / 3 - C3
=>A3 = 3A2/4 + A6/4 - C5/2 - C4 - 3C3/2
A2 = (A1 + A3) / 2 - C2 = A1 / 2 + 3A2 / 8 + A6 / 8 - C5 / 4 - C4 / 2 - 3C3 / 4 - C2
=>A2 = 4A1/5 + A6/5 - 2C5/5 - 4C4/5 - 6C3/5 - 8C2/5
A1 = (A0 + A2) / 2 - C1 = A0 / 2 + 2A1 / 5 + A6 / 10 - C5 / 5 - 2C4 / 5 - 3C3 / 5 - 4C2 / 5 - C1
=>A1 = 5A0/6 + A6/6 - C5/3 - 2C4/3 - C3 - 4C2/3 - 5C1/3
算到這里，我想你已經總結出公式了:
A1 = (n * A0 + An+1 - 2 * Cn - 4 * Cn-1 - - 2 * i * Cn-i+1 - 2 * n * C1) / (n + 1)
代碼如下 :
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
#include <stdio.h>
int main ()
{
int n, i;
double a0, an1, a1;
double c[3000];
while ( scanf ( "%d", &n) != EOF )
{
scanf ( "%lf%lf", &a0, &an1 );
for ( i = 0; i < n; i++ )
{
scanf("%lf", c + i);
}
a1 = n * a0 + an1;
for ( i = 1; i <= n; i++ )
{
a1 -= 2 * i * c[n - i];
}
printf ( "%.2f\n", a1 / ( n + 1 ) );
}
return 0;
}