精华内容
下载资源
问答
  • 自适应Simpson公式

    2019-10-06 22:43:28
    参考刘汝佳<算法指南>P163 #include<cstdio> #include<cmath> double a; double F(double x){ return sqrt(1+4*a*a*x*x);...double simpson(double a,double b) { double c=a+(b-a...

    参考刘汝佳<算法指南>P163

    #include<cstdio>
    #include<cmath>
    double a;
    double F(double x){
        return sqrt(1+4*a*a*x*x);
    }
    double simpson(double a,double b)
    {
        double c=a+(b-a)/2;
        return (F(a)+4*F(c)+F(b))*(b-a)/6;
    }
    double asr(double a,double b,double eps,double A)
    {
        double c=a+(b-a)/2;
        double L=simpson(a,c),R=simpson(c,b);
        if(fabs(L+R-A)<=15*eps) return L+R+(L+R-A)/15.0;
        return asr(a,c,eps/2,L)+asr(c,b,eps/2,R); 
    }
    double ASR(double a,double b,double eps){
        return asr(a,b,eps,simpson(a,b));
    }
    double parabola_arc_length(double w,double h)
    {
        a=4.0*h/(w*w);
        return ASR(0,w/2,1e-5)*2;
    }
    int main()
    {
        int T;
        scanf("%d",&T);
        for(int cas=1;cas<=T;cas++){
            int D,H,B,L;
            scanf("%d%d%d%d",&D,&H,&B,&L);
            int n=(B+D-1)/D;
            double D1=(double)B/n;
            double L1=(double)L/n;
            double x=0,y=H;
            while(y-x>1e-5){
                double m=x+(y-x)/2;
                if(parabola_arc_length(D1,m)<L1) x=m;
                else y=m;
            }
            if(cas>1) printf("\n");
            printf("Case %d:\n%.2lf\n",cas,H-x);
        }    
    }

     

    转载于:https://www.cnblogs.com/freinds/p/6406291.html

    展开全文
  •  对于求积分,很早的时候大概是大一第一个学期的时候,学Python时候LWW老师就曾经给我们讲过一个叫Simpson公式以及自适应Simpson公式的东西。当时呢学着觉得也没啥用,不就是算个积分吗,用处不大……  然后这题...

    1806: Toll

          Time Limit: 5 Sec     Memory Limit: 128 Mb     Submitted: 302     Solved: 91     SpecialJudge


    Description

     In ICPCCamp, there are n cities and m unidirectional roads between cities. The i-th road goes from the ai-th city to the bi-th city. For each pair of cities u and v, there is at most one road from u to v.
    As traffic in ICPCCamp is becoming heavier, toll of the roads also varies. At time t, one should pay (ci⋅t+di) dollars to travel along the i-th road.
    Bobo living in the 1-st city would like to go to the n-th city. He wants to know the average money he must spend at least if he starts from city 1 at t∈[0,T]. Note that since Bobo's car is super-fast, traveling on the roads costs him no time.
    Formally, if f(t) is the minimum money he should pay from city 1 to city n at time t, Bobo would like to find


    Input

    The first line contains 3 integers n,m,T (2≤n≤10,1≤m≤n(n-1),1≤T≤104).
    The i-th of the following m lines contains 4 integers ai,bi,ci,di (1≤ai,bi≤n,ai≠bi,0≤ci,di≤103).
    It is guaranteed that Bobo is able to drive from city 1 to city n.

    Output

     A floating number denotes the answer. It will be considered correct if its absolute or relative error does not exceed 10-6.

    Sample Input

    3 3 2
    1 2 1 0
    2 3 1 0
    1 3 1 1
    3 3 2
    1 2 1 0
    2 3 1 0
    1 3 0 5
    

    Sample Output

    1.75000000
    2.00000000
    

    Hint

    Source

    湖南省第十二届大学生计算机程序设计竞赛



            最短路,但是费用随着时间而变化,问最小费用关于时间积分的平均数。
            对于求积分,很早的时候大概是大一第一个学期的时候,学Python时候LWW老师就曾经给我们讲过一个叫Simpson公式以及自适应Simpson公式的东西。当时呢学着觉得也没啥用,不就是算个积分吗,用处不大……
            然后这题就是一个计算积分的题目,正好就用到了自适应Simpson公式。所谓Simpon公式,就是指对于函数f(x)在一个区间[l,r]上的积分,可以近似等于(r-l)*(f(l)+f(r)+f(mid)/6。所谓近似,就是指可以有误差,很显然这个误差一般来说非常的大,所以我们要用自适应的方式。那么什么是自适应Simpson公式呢?其实就是说自己设置一个eps,运用二分的思想,当Simpson(l,mid)+Simpson(mid,r)与Simpson(l,r)的查大于eps的时候,自动判定为误差过大,于是继续把区间分细,对区间[l,mid]和[mid,r]使用自适应Simpson公式计算,然后返回两者之和。一直这样递归下去就可以得到误差为eps的结果。至于时间复杂度这个我真的不知道……有没有哪位dalao能告诉我。具体见代码:
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    #include<queue>
    #define eps 1e-8
    #define N 100
    using namespace std;
    
    typedef pair<double,int> P;
    struct Edge{int y,c,d;};
    vector<Edge> g[N];
    const int INF=1e9;
    double d[N];
    int m,n,T;
    
    inline double dijkstra(double t)
    {
        priority_queue<P,vector<P>,greater<P> > q;
        for(int i=1;i<=n;i++) d[i]=INF;
        d[1]=0; q.push(P(0,1));
        while (!q.empty())
        {
            int j=q.top().second;
            double w=q.top().first;
            q.pop(); if (w-d[j]>eps) continue;
            for(int k=0;k<g[j].size();k++)
            {
                int y=g[j][k].y;
                double dist=w+g[j][k].c*t+g[j][k].d;
                if (d[y]-dist>eps) {d[y]=dist; q.push(P(d[y],y));}
            }
        }
        return d[n];
    }
    
    double simpson(double l,double r)
    {
        double mid=(l+r)/2.0;
        return (r-l)*(dijkstra(l)+dijkstra(r)+4*dijkstra(mid))/6.0;
    }
    
    double rsimpson(double l,double r)
    {
        double mid=(l+r)/2.0;
        double A=simpson(l,r);
        double L=simpson(l,mid);
        double R=simpson(mid,r);
        if (fabs(A-L-R)>=eps) return rsimpson(l,mid)+rsimpson(mid,r);
                         else return A;
    }
    
    int main()
    {
        while(~scanf("%d%d%d",&n,&m,&T))
        {
            memset(g,0,sizeof(g));
            for(int i=1;i<=m;i++)
            {
                int u,v,x,y;
                scanf("%d%d%d%d",&u,&v,&x,&y);
                g[u].push_back(Edge{v,x,y});
            }
            printf("%.7f\n",(double)rsimpson(0,T)/T);
        }
        return 0;
    }
    

    展开全文
  • 自适应simpson公式解定积分

    千次阅读 2014-04-28 21:09:56
    //则直接使用保存的simpson值不用再调用simpson函数, //若改变则调用函数并保存修改后的值 //eps为自定义精度 double asr(double a,double b,double eps,double A) { double c=a+(b-a)/2; double L=simpson(a,c),...


    来自白书

    反正基础就是极限思想嘛,simpson原理没深究了,当做模板用吧

    求定积分:



    #include<stdio.h>
    #include<string.h>
    #include<math.h>
    double f(double x)
    {
        return x;//自定义函数
    }
    double simpson(double a,double b)
    {
        double c=a+(b-a)/2;
        return (f(a)+4*f(c)+f(b))*(b-a)/6;
    }
    //递归过程,可以保存la,rb,和simpson的值,若la,rb未变
    //则直接使用保存的simpson值不用再调用simpson函数,
    //若改变则调用函数并保存修改后的值
    //eps为自定义精度
    double asr(double a,double b,double eps,double A)
    {
        double c=a+(b-a)/2;
        double L=simpson(a,c),R=simpson(c,b);
        if(fabs(L+R-A)<=15*eps) return L+R+(L+R-A)/15.0;
        return asr(a,c,eps/2,L)+asr(c,b,eps/2,R);
    }
    double asr_main(double a,double b,double eps)
    {
        return asr(a,b,eps,simpson(a,b));
    }
    int main()
    {
        printf("%lf\n",asr_main(0,100,1e-5));
        return 0;
    }



    la 3485 Bridge

    #include<stdio.h>
    #include<string.h>
    #include<math.h>
    double a;
    double f(double x)
    {
        return sqrt(1+4*a*a*x*x);
    }
    double simpson(double a,double b)
    {
        double c=a+(b-a)/2;
        return (f(a)+4*f(c)+f(b))*(b-a)/6;
    }
    double asr(double a,double b,double eps,double A)
    {
        double c=a+(b-a)/2;
        double L=simpson(a,c),R=simpson(c,b);
        if(fabs(L+R-A)<=15*eps) return L+R+(L+R-A)/15.0;
        return asr(a,c,eps/2,L)+asr(c,b,eps/2,R);
    }
    double asr_main(double a,double b,double eps)
    {
        return asr(a,b,eps,simpson(a,b));
    }
    double solve(double w,double h)
    {
        a=4*h/(w*w);
        return asr_main(0,w/2,1e-5)*2;
    }
    int main()
    {
        double h,d,b,l;
        int n,cas;
        scanf("%d",&cas);
        for(int i=1;i<=cas;i++)
        {
            scanf("%lf%lf%lf%lf",&d,&h,&b,&l);
            n=(b+d-1)/d;
            double dd=b/n;
            double ll=l/n;
            double x=0,y=h;
            while(x+1e-9<y)
            {
                double m=x+(y-x)/2;
                if(solve(dd,m)<ll) x=m;
                else y=m;
            }
            if(i!=1) printf("\n");
            printf("Case %d:\n%.2lf\n",i,h-x);
        }
        return 0;
    }


    展开全文
  • // 用自适应Simpson公式计算宽度为w,高度为h的抛物线长 double parabola_arc_length(double w, double h) { a=4.0*h/(w*w); // 修改全局变量a,从而改变全局函数F的行为 return asr(0,w/2,1e-9)*2; } int main(){...

    A suspension bridge suspends the roadway from huge main cables, which extend from one end of the bridge to the other. These cables rest on top of high towers and are secured at each end by anchorages. The towers enable the main cables to be draped over long distances.

    Suppose that the maximum distance between two neighboring towers is D, and that the distance from the top of a tower to the roadway is H. Also suppose that the shape of a cable between any two neighboring towers is the same symmetric parabola (as shown in the figure). Now given B, the length of the bridge and L, the total length of the cables, you are asked to calculate the distance between the roadway and the lowest point of the cable, with minimum number of towers built (Assume that there are always two towers built at the two ends of a bridge).

    \epsfbox{p3485.eps}

    Input 

    Standard input will contain multiple test cases. The first line of the input is a single integer T (1$ \le$T$ \le$10) which is the number of test cases. T test cases follow, each preceded by a single blank line.

    For each test case, 4 positive integers are given on a single line.

    D
    - the maximum distance between two neighboring towers;
    H
    - the distance from the top of a tower to the roadway;
    B
    - the length of the bridge; and
    L
    - the total length of the cables.

    It is guaranteed that B$ \le$L. The cable will always be above the roadway.

    Output 

    Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

    For each test case, print the distance between the roadway and the lowest point of the cable, as is described in the problem. The value must be accurate up to two decimal places.

    Sample Input 

    2
    
    20 101 400 4042
    
    1 2 3 4
    

    Sample Output 

    Case 1:
    1.00
    
    Case 2:
    1.60
    

      桥上摆放等距的塔,塔高H,相邻的塔距离不超过D,塔之间绳子是抛物线。桥长B,绳子总长L,求建最少的塔时绳子下端离地的高度。

      塔数目最小时,间隔数为ceil(B/D),每个间隔的宽度D1=B/n,每段绳子长L1=L/n。设每段绳子宽度为w,高h,抛物线方程f(x)=ax^2=4h/(w^2),二分枚举h,知道算出的抛物线长度为L1,最后答案就是H-h。

      问题就在于抛物线长度怎么算。弧长积分公式∫a到b√(1+(f'(x))^2),可以积出来,但是不会积的话就可以用simpson公式。

      递归算左右两部分的simpson值,如果和整体的simpson值误差小到一定精度就返回。

      有一点不明白的是白书上的那个误差小于15eps就返回L+R+误差/15,为什么这样就能保证误差小于eps。。

    #include<iostream>
    #include<algorithm>
    #include<queue>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<cstring>
    #include<stack>
    #define INF 0x3f3f3f3f
    #define MAXN 10010
    #define MAXM 110
    #define MOD 1000000007
    #define MAXNODE 4*MAXN
    //#define eps 1e-9
    using namespace std;
    typedef long long LL;
    int T,D,B,H,L;
    double a;
    //simpson公式用到的函数
    double F(double x) {
      return sqrt(1+4*a*a*x*x);
    }
    //三点simpson法。这里要求F是一个全局函数
    double simpson(double a, double b) {
      double c=a+(b-a)/2;
      return (F(a)+4*F(c)+F(b))*(b-a)/6;
    }
    //自适应Simpson公式(递归过程)。已知整个区间[a,b]上的三点simpson值A
    double asr(double a, double b, double eps, double A) {
      double c= a+(b-a)/2;
      double L=simpson(a,c),R=simpson(c,b);
      if(fabs(L+R-A)<=15*eps) return L+R+(L+R-A)/15;
      return asr(a,c,eps/2,L) + asr(c,b,eps/2,R);
    }
    //自适应Simpson公式(主过程)
    double asr(double a,double b,double eps) {
      return asr(a,b,eps,simpson(a,b));
    }
    
    // 用自适应Simpson公式计算宽度为w,高度为h的抛物线长
    double parabola_arc_length(double w, double h) {
      a=4.0*h/(w*w); // 修改全局变量a,从而改变全局函数F的行为
      return asr(0,w/2,1e-9)*2;
    }
    int main(){
        freopen("in.txt","r",stdin);
        int cas=0;
        scanf("%d",&T);
        while(T--){
            scanf("%d%d%d%d",&D,&H,&B,&L);
            int n=(B+D-1)/D;
            double D1=(double)B/n,L1=(double)L/n,l=0,r=H;
            while(r-l>1e-9){
                double mid=l+(r-l)/2;
                if(parabola_arc_length(D1,mid)<L1) l=mid;
                else r=mid;
            }
            printf("Case %d:\n%.2lf\n",++cas,H-l);
            if(T) puts("");
        }
        return 0;
    }
    


    展开全文
  • 可导函数f(x)在区间[a,b]上的弧长:有公式(无法打出来),可以用微元法来推导,公式中的积分部分用自适应Simpson公式来求 【代码】 #include #include #include double w,h,_a;//_a:设 F(x)=_a*x^2 ...
  • 数值积分课程需编制自适应Simpson公式,此代码采用递归函数,函数中采用了fcnchk函数,matlab6.5及以下版本会报错,只需将函数定义语句改成inline函数即可
  • 自适应Simpson

    2019-12-04 13:08:53
    Simpson是什么呢? 就是如果我们要求一个积分,但是里面的f(x)十分麻烦,于是我们就需要用...Simpson公式: 例题:Simpson例题 AC代码: #pragma GCC optimize(2) #include<bits/stdc++.h> //#define int lo...
  • 自适应simpson 积分

    2017-10-02 20:43:13
    自适应simpson 积分求在区间[a,b]内f(x)的积分
  • Simpson&自适应Simpson

    2019-05-31 21:43:22
    Simpson公式: ∫lrf(x)dx≈(r−l)(f(l)+f(r)+4f(l+r2))6\int^{r}_{l}f(x)dx\approx\frac{(r-l)(f(l)+f(r)+4f(\frac{l+r}{2}))}{6}∫lr​f(x)dx≈6(r−l)(f(l)+f(r)+4f(2l+r​))​ inline double simpson(double l...
  • 自适应Simpson积分

    2017-08-16 20:56:00
    自适应Simpson积分 作用  如标题所示,这玩意就是当你不会微积分的时候来求积分的。  总所周知,积分的定义就是函数的某一段与坐标轴之间的面积。  那么,自适应Simpson积分就是一种可以再某些精度下计算出较为...
  • c++自适应simpson源码

    2008-06-26 10:11:06
    使用自适应simpson算法求积分的源码
  • 自适应simpson积分

    千次阅读 2016-07-09 22:04:49
    ACM模版自适应simpson积分const double eps = 1e-6; // 积分精度// 被积函数 double F(double x) { double ans; // 被积函数 // ... // ans = x * exp(x); // 椭圆为例 return ans; }// 三点simpson法,这里要求...
  • luogu 自适应Simpson1

    2018-08-22 19:51:00
    自适应simpson1 题意 求一个定积分 (可以手推公式,但是我不想推怎么办) 解法 用一个又一个的二次函数覆盖原函数,则可以近似的得到原函数的积分。(这就是Simpson) 模板在下面: #include <iostream> #...
  • 自适应Simpson算法

    2010-04-18 21:58:08
    simpson自适应算法 下的 实现 代码
  • hdu 1724 题意: ...1. 自适应simpson,精度不是很高,所以eps要设小一点。 2. romberg,精度很好,但效率不是很高。自适应simpson: /*hdu 1724 题意: 求椭圆面积, x^2/a^2+y^2/b^2=1, 给出a,b,
  • 学习笔记: 自适应Simpson积分

    千次阅读 2013-03-05 18:39:55
    看了一些大牛的博客,终于对自适应Simpson积分有了初步的了解。 Q:自适应Simpson积分是用来做什么的? A:用来求积分啊! Q:它和一般的微积分有什么区别? A:不能求出精确解,但是可以近似地求出不可导图像的...
  • 学习笔记: 自适应Simpson积分+例题

    千次阅读 2019-01-15 22:13:56
    参考bloghttps://blog.csdn.net/lunch__/article/...这个东西对于三次以下的函数是正确的,但是对于三次以上的函数我们可以将其近似为低次函数套用Simpson公式,这个东西学名好像叫自适应Simpson积分。 昨天AC...
  • 格林公式的具体意义,只要理解了围道积分的定义然后在纸上画一画一个简单情况就懂啦 简单地讲就是,对于我们需要求面积的平面单联通图形,它的轮廓线上的所有点可以被分为两部分 一部分是“面向原点”的,一部分是...
  • 【HDU1724】Ellipse-自适应Simpson积分法
  • 我就不讲Simpson了 Green Formula 对平面单联通区域 D \rm D D 及其正向轮廓线 L \rm L L (分段光滑),且 P , Q P,Q P , Q 在 D \rm D D 上有一阶连续偏导 ∬ D ( ∂ Q ∂ x − ∂ P ∂ y ) d x d ...
  • 何为自适应Simpson法 自适应辛普森算法(Adaptive Simpson′s rule)是一类近似算法(Approximation algorithm),主要用于在信息计算时求较难反导的函数的定积分。其思想是利用二次函数曲线来不断**拟合(Overfitting)所...
  • simpson公式是用于积分求解的比较简单的方法(有模板都简单…… 下面是simpson公式(很明显 这个公式的证明我并不会…… (盗图…… 因为一段函数基本不可能很规则 所以我们要用自适应积分的方法 找了一道很水...
  • 【HDU4498】Function Curve-分段+自适应Simpson积分法

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 366
精华内容 146
关键字:

自适应的simpson公式