新普金娱乐网址


Python模块:time模块详解(转)

二零一六 最佳天文 Linux 发行版排名榜

数学笔记9——Newton迭代法

  • 二月 26, 2019
  • 天文
  • 没有评论

  牛顿迭代法(Newton’s
method)又称之为Newton-拉夫逊(拉弗森)方法(Newton-Raphson
method),它是Newton在17世纪提出的一种在实数域和复数域上好像求解方程的方法。

岁月范围: 3 s

以身作则1:求解平方根

  先来看怎么着用Newton迭代法求解5的平方根。在总计器上的结果是2.236067…

  难点得以当作解方程x2=5,上面尝试用Newton迭代法求解。

  首先令f(x)= x2 – 5 =
0,那是正统步骤,取得3个新函数,令该函数为0。那是2个抛物线:

图片 1

  抛物线与x轴的交点x就是方程的解,它比2稍大学一年级些。

  现在在x=2处对f(x)做切线:

图片 2

f(x)的切线

图片 3

切线与x轴的交点

  x0=2,y0=
x02 – 5 = -1,设k是切线斜率:

图片 4

  在x1处做f(x)的切线,重复下边步骤,

图片 5

  那正是Newton迭代法的公式。通过作图能够看出,每一遍迭代,x都将更近乎最后解。

 

  f’(x)=2x,将公式代入指标方程f(x)=x2-5:

图片 6

  已经分外接近总括器的结果。

 空间范围: 6五千KB

示例2:2cosx=3x

  解方程2cosx=3x

图片 7

  由图像可知,方程存在唯一解。

  f(x)=2cosx-3x=0,f’(x)=-2sinx-3,x0=π/6≈0.52

图片 8

 标题等级 : 钻石
Diamond

注意事项

  Newton迭代法差不多能够求解全部方程,但它依旧有一部分范围。

  通过前三个例子能够看到,在运用Newton迭代法时,需求采纳一个较为解接近真实解的x0作为迭代基数,x0怎样抉择呢?一句参考是:“f’无法太小,f’’不可能太大,x0要在x附近”,那犹如要凭经验和感觉了,没有啥样太好的方法;实际上,假诺x0和x的出入过大,或者会博得一个没谱的解。

  设第n次迭代的误差是En=|x-xn|,那么需求满意En+1<En。假使选用和计算都毋庸置疑,误差减少的快慢将相当快。

  以总计5的平方根为例,借使选用x0=-2,结果将偏向于-2.236067…;若是接纳x0=0,则f’(0)=0,无法继续迭代,函数曲线如下图所示:

图片 9

选料了不当的x0

标题叙述 Description

代码示例:Newton迭代法开平方

  设x2=a,则f(x)=
x2-a,根据Newton迭代法公式:

图片 10

 1 const float EPS = 0.00001; 
 2 double sqrt(double x) { 
 3     if(x == 0) 
 4         return 0; 
 5     double result = x; 
 6     double lastValue; 
 7     do{ 
 8         lastValue = result; 
 9         result = result / 2.0f + x / 2.0f / result; 
10     }while(abs(result - lastValue) > EPS);
11     return (double)result;
12  } 

   上边方法开平方会相当的慢,但 https://www.2cto.com/kf/201206/137256.html
中涉嫌了一个更快的法子。

  1998年四月,美利哥id
Software公司宣布了名为“雷王之锤III”的电子游戏。它是首先个协理软件加快的玩乐,取得了大幅成功。(由于影响力过大,文化部于二〇〇〇年将它列入了地下5日游名单)雷公之锤III并不是id
Software集团的首先次成功。早在一九九二年始发,这家集团就以“毁灭战士”类别游戏名闻天下。一九九四年,“毁灭战士”的安装数当先了当时微软的windows
95。据传Bill盖茨才曾经考虑买下id software。(id
software公司新兴被推出过“上古卷轴”连串的Bethesda集团买下)

  id
Software所得到的成功一点都不小程度上要归功于它的老祖宗John·卡马克。马克尔也是二个资深的程序员,他是id
Software游戏引擎的要害管理者。
回到刚才提到的雷王之锤,马克尔是开源软件的主动带动者,他于二〇〇五年通知了雷王之锤III的源代码。至此人们得以通过钻研那款游戏引擎的源文件来查阅它成功的机要。

  在其间二个名字为q_math.c的文书中发觉了之类代码段:

 1 float Q_rsqrt( float number ) { 
 2     long i; float x2, y; const float threehalfs = 1.5F;
 3     x2 = number * 0.5F; 
 4     y = number; 
 5     i = * ( long * ) &y; // evil floating point bit level hacking 
 6     i = 0x5f3759df - ( i >> 1 ); // what the fuck? 
 7     y = * ( float * ) &i; 
 8     y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration 
 9     // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
10     #ifndef Q3_VM #
11     ifdef __linux__ assert( !isnan(y) ); // bk010122 - FPE?
12     #endif
13     #endif return y; 
14 }

  那段代码的职能就是求number的平方根,并且重返它的尾数。

  经过测试,它的频率比上述Newton法程序要快几十倍。也比c++标准库的sqrt()函数要快一些倍。此段代码有二个出人意料的语句:

  i = 0x5f3759df – ( i >> 1 ); //
what the fuck? 

  没错,一般的求平方根都以如此循环迭代算的可是卡马克(quake3笔者)真正牛B的地点是他选用了贰个机密的常数0x5f3759df
来计量那多少个预计值,正是大家加注释的那一行,那一行算出的值非凡相近1/sqrt(n),这样我们只必要3遍Newton迭代就足以达到规定的标准大家所须要的精度。可以吗如若那么些还不算NB,接着看:

  普渡大学的物农学家ChrisLomont看精通后觉得有趣,决定要钻探一下卡马克弄出来的这些揣测值有啥奥秘。Lomont也是个牛人,在精研未来从理论上也演绎出3个最佳预计值,和卡马克的数字10分类似,
0x5f37642f。卡马克真牛,他是外星人吗?

  神话并没有在此地截至。Lomont计算出结果现在尤其惬意,于是拿自身总括出的开头值和卡马克的地下数字做比赛,看看什么人的数字能够更快更精确的求得平方根。结果是卡马克赢了…
何人也不知道卡马克是怎么找到那几个数字的。

  最后Lomont怒了,选取暴力情势叁个数字1个数字试过来,终于找到1个比卡马克数字要好上那么一丁点的数字,即便事实上那多个数字所发生的结果格外接近,那么些暴力得出的数字是0x5f375a86。

  Lomont为此写下一篇故事集,”法斯特 Inverse
Square Root”。

  杂文下载地址:

  http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf

  http://www.matrix67.com/data/InvSqrt.pdf

小明是一名天文胃痛友,他喜爱深夜看个别。那天,他从天猫上买下来了三个尖端望远镜。他百般戏谑,于是她午夜去操场上看个别。

向牛顿致敬

  Newton是近代科学的先驱者,智力商数290,在几个世界都有别致的到位。

  他在1687年见报的杂文《自然定律》里,对万有动力和三小运动定律进行了描述。那一个描述奠定了后头多少个百年里物理世界的没错理念,并变成了当代工程学的基础。他通过论证开普勒行星运动定律与她的重力理论间的一致性,呈现了地面物体与宇宙的移位都服从着同一的当然定律;为太阳中央说提供了有力的申辩扶助,并推进了未可厚非革命。

  在力学上,Newton注解了动量和角动量守恒的法则,提议Newton运动定律[1]  。在光学上,他证明了反光望远镜,并依据对三棱镜将白光发散成可知光谱的洞察,发展出了颜色理论。他还系统地球表面述了温度下跌定律,并切磋了音速。

  在数学上,Newton与戈特Fried·威尔iam·莱布尼茨分享了前进出微积分学的得体。他也证实了广义二项式定理,建议了“Newton法”以趋近函数的零点,并为幂级数的研究做出了贡献。

  在历史学上,Newton提议金本位制度。

  在天文成上,Newton1672年制定了反光望远镜。他还用万有重力原理表明潮汐的各样气象,提议潮汐的尺寸不但同月球的位相有关,而且同太阳的方位有关。Newton预言地球不是正球体。

  在文学成上,Newton的历史学思想基本属于自发的唯物论,他肯定时间、空间的客观存在。就如历史上全数伟大人物一致,Newton固然对全人类作出了了不起的进献,但她也不可能不受时期的界定。例如,他把时光、空间作为是同运动着的物质相脱离的东西,提议了所谓相对时间和相对空间的定义;他对那么些权且不可能解释的自然现象总结为上帝的配置,提议任何行星都以在某种外来的“第壹拉引力”作用下才早先运动的传教。《自然管理学的数学原理》Newton最根本的行文,1687年出版。

  向伟大的Newton致敬!

分化的星星发出分裂的光,他的望远镜能够总结出观望到的不难发出的光的数值W。小明当然想尽量地多看看个别,于是她每看到一颗星星,就要看看她事先有没有看过那颗星星。但是他看的个别太多了,他有史以来数可是来,于是她让你援助。

总结

  1. Newton迭代法的公式:
  2. 注意事项,f’不能够太小,f’’不可能太大,x0要在x附近

    作者:我是8位的

  出处:http://www.cnblogs.com/bigmonkey

  本文以读书、研究和分享为主,如需转发,请联系本身,标明作者和出处,非商业用途! 

 

输入描述 Input Description

共有两行,第3行唯有三个整数,为小明观测到的个其余多寡n。第3行有n个整数,每三个整数由二个空格隔离,分别为小明观测到每颗星星的光的数值W[1]-W[n]。

输出描述 Output Description

只有一行,这一行共有n个数字0或1。0意味对应的少数从前未曾观测到,1表示对应的点滴此前曾经看过了。专注:数字之间从未空格!

样例输入 Sample Input

5

1 5 5 4 1

样例输出 萨姆ple Output

00101

数据范围及提醒 Data Size & Hint

样例是频仍是骗人的,本题中

30%的数据,0<n≤5000。

20%的数据,-20000≤W≤20000。

60%的数据,0<n≤50000。

100%的数据,0<n≤500000;-2000000000≤W≤2000000000。

哈希 点击传送

35分 WA+RE代码存档 (数组开小,没考虑负数)

图片 11图片 12

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define mo 13831

using namespace std;

int tot,head[100001],n,i,w;
struct node
{
    int next,to;
}e[100001];
bool hash(int k)
{
    int h=0;
    while(k)
    {
        h=h*13+k;
        k/=10;
    }
    h=h%mo;
    for(i=head[h];i;i=e[i].next)
    {
        if(e[i].to==w)
        return true;
    }
    tot++;
    e[tot].next=head[h];
    e[tot].to=w;
    head[h]=tot;
    return false;
}
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>w;
        if(hash(w))
        cout<<"1";
        else cout<<"0";
    }
}
/*
运行结果
测试点#1.in 结果:AC 内存使用量: 492kB 时间使用量: 13ms 
测试点#2.in 结果:AC 内存使用量: 364kB 时间使用量: 13ms 
测试点#3.in 结果:AC 内存使用量: 360kB 时间使用量: 13ms 
测试点#4.in 结果:RE 内存使用量: 876kB 时间使用量: 33ms 
测试点#5.in 结果:RE 内存使用量: 872kB 时间使用量: 61ms 
测试点#6.in 结果:WA 内存使用量: 1260kB 时间使用量: 142ms 
测试点#large.in 结果:RE 内存使用量: 872kB 时间使用量: 58ms 
测试点#large2.in 结果:RE 内存使用量: 360kB 时间使用量: 9ms 
测试点#large3.in 结果:RE 内存使用量: 616kB 时间使用量: 16ms 
*/

View Code

6八分 RE代码 (数组开小)

图片 13图片 14

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define mo 13831

using namespace std;

int tot,head[100001],n,i,w;
struct node
{
    int next,to;
}e[100001];
bool hash(int k)
{
    int h=0;
    while(k)
    {
        h=h*13+k;
        k/=10;
    }
    h=h%mo;
    if(h<0) h=h*(-1);
    h+=233;//应该随便加一个质数就好 。
    for(i=head[h];i;i=e[i].next)
    {
        if(e[i].to==w)
        return true;
    }
    tot++;
    e[tot].next=head[h];
    e[tot].to=w;
    head[h]=tot;
    return false;
}
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>w;
        if(hash(w))
        cout<<"1";
        else cout<<"0";
    }
}
/*
运行结果
测试点#1.in 结果:AC 内存使用量: 364kB 时间使用量: 12ms 
测试点#2.in 结果:AC 内存使用量: 360kB 时间使用量: 11ms 
测试点#3.in 结果:AC 内存使用量: 364kB 时间使用量: 11ms 
测试点#4.in 结果:AC 内存使用量: 1004kB 时间使用量: 134ms 
测试点#5.in 结果:AC 内存使用量: 1132kB 时间使用量: 137ms 
测试点#6.in 结果:AC 内存使用量: 1260kB 时间使用量: 138ms 
测试点#large.in 结果:RE 内存使用量: 2412kB 时间使用量: 298ms 
测试点#large2.in 结果:RE 内存使用量: 2412kB 时间使用量: 299ms 
测试点#large3.in 结果:RE 内存使用量: 2284kB 时间使用量: 293ms 
*/

View Code

九十六分 哈希代码 正是太慢了 = =| 长度575B 时间5404ms

图片 15图片 16

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define mo 13831

using namespace std;

int tot,head[1000001],n,i,w;
struct node
{
    int next,to;
}e[1000001];
bool hash(int k)
{
    int h=0;
    while(k)
    {
        h=h*13+k;
        k/=10;
    }
    h=h%mo;
    if(h<0) h=h*(-1);
    h+=233;
    for(i=head[h];i;i=e[i].next)
    {
        if(e[i].to==w)
        return true;
    }
    tot++;
    e[tot].next=head[h];
    e[tot].to=w;
    head[h]=tot;
    return false;
}
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>w;
        if(hash(w))
        cout<<"1";
        else cout<<"0";
    }
}

View Code

一百分 STL代码 更慢但归纳了非但某个。。代码长度179B 时日 6559ms

图片 17图片 18

#include <iostream>
#include <map>

using namespace std;
map<int,int>q;
int main()
{
    int n;
    cin>>n;
    int a;
    while(n--)
    {
        cin>>a;
        cout<<q[a];
        q[a]=1;
    }
}

View Code

 

相关文章

No Comments, Be The First!
近期评论
    分类目录
    功能
    网站地图xml地图