【优秀题解】1168题【简单计算】题解

题目描述

有一个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.求关系

  1. 递推关系两遍同时乘以2,把分母2消除以便推导即:
  2. 2*a[n] = a[n-1] + a[n+1] -2*c[n]
  3. 为了推导方便先假设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]
  4. 把以上式子加起来,可消元得到: a[1]+a[5]=a[0]+a[6]-2*(sum(1~5)) 这里sum(1~5)=c[1]+c[2]+....+c[5]
  5. 走到上面发现式子里面还有个未知量a[5],想办法把a[5]也消去;
  6. 返回第2步,令n=4,把式子加起来,可消元得到: a[1]+a[4]=a[0]+a[5]-2*(sum(1~4))
  7. 再令n=3,把式子加起来,可消元得到: a[1]+a[3]=a[0]+a[4]-2*(sum(1~3))
  8. 直到n=1 a[1]+a[1]=a[0]+a[2]-2*(sum(1~1))
  9. 把以上得到的所有式子罗列出来: 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)) 再把这些式子加起来,消元得到:
  10. 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)

参考代码:

#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大神,可以点击阅读全文看大神的博客!

原文发布于微信公众号 - 编程范(dotcpp)

原文发表时间:2018-01-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏有趣的Python和你

微信好友全头像直接上图代码代码分析

1443
来自专栏云时之间

深度学习与神经网络:制作数据集,完成应用(1)

在这一篇文章里,我们将继续上一篇文章的工作,并且在上一篇文章的前提下加入数据集的制作,最终我们将完成这个全连接神经网络的小栗子.

8306
来自专栏CSDN技术头条

使用Go语言来理解Tensorflow

【译者注】本文通过一个简单的Go绑定实例,让读者一步一步地学习到Tensorflow有关ID、作用域、类型等方面的知识。以下是译文。 Tensorflow并不是...

27110
来自专栏编程

说说正则表达式的使用

今日分享:正则表达式 一:正则表达式的定义及用途 正则表达式是一种特殊的字符串,字符串中的每个字符都含有特定的意义。使用者通过将正则中不同的字符组合成不同的字符...

1998
来自专栏数据结构与算法

22:因子分解

22:因子分解 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 输入一个数,输出其素因子分解表达式。 输入输入一个整数...

34112
来自专栏GopherCoder

Python 强化训练:第二篇

1695
来自专栏CreateAMind

深度学习框架TensorFlow 官方文档中文版

823
来自专栏mathor

LeetCode130. 被围绕的区域

 bfs题,主函数中枚举每一个起点,如果是'O'就开始bfs搜索,首先将'O'变为'X',然后将周围是'O'都入队。这里有个地方要注意,如果'O'并不是被...

1012
来自专栏Laoqi's Linux运维专列

正则扩展练习

grep命令的-P选项: 最典型的用法是,匹配指定字符串之间的字符。 比如,我们想在一句话(Hello,my name is aming.)中匹配中间的一段字符...

4136
来自专栏云时之间

深度学习与神经网络:制作数据集,完成应用(1)

2154

扫码关注云+社区

领取腾讯云代金券