发布时间 : 星期一 文章服务类第1章算法与程序框图更新完毕开始阅读ea6785447ed5360cba1aa8114431b90d6c8589ad
说明 由莱布尼茨公式，利用循环结构，定义累加变量S，很容易得到
?的近似值，从而得4到?的近似值a。本例的难点是循环终止的条件。像本例这样求近似值的问题，循环的终止条件一般为近似值的误差，但由于所求值的精确值我们一般是不知道的（否则我们也不用求近似值了），所以近似值的误差一般是无法计算的，在这种情况下，我们一般用得到的第n个近似值（上例中的a）与第n-1个近似值（上例中的b）的差的绝对值（即|a-b|）代替误差，来作为循环终止的条件。如上例中，当|a-b|?10时，循环就终止了，此时，近似值与精确值之间的误差大约是10。
?5?5随堂练习
x?0?1?x?0，设计一个算法，任意输入一个实数x，输出函数值1.设分段函数f(x)??0??1x?0?f(x)，请画出算法的程序框图。
2.对正弦函数，我们有它的幂级数展开式
1315x2n?1nsinx= x?x+x??+(?1)+?（?∞＜x＜+∞）．
3!5!(2n?1)!利用这个公式，设计一个算法，任意输入一个实数x，计算sinx的近似值，请画出算法的程序框图。（循环终止的条件是第n个近似值与第n-1个近似值的差的绝对值小于10。
?5习题
1.利用“更相减损之术”，设计一个算法，计算2136与4528的最大公约数。
2.已知多项式函数f(x)?x?2x?3x?1，利用“秦九韶算法”，计算当x?1,2,3,?,10时，相应的函数值。画出算法的程序框图。
3.从2010年12月1日起，购买火车票时，1.2米以下儿童可免票，1.2米至1.5米的可购买半票，超过1.5米的儿童应买全价票。设计一个算法，输入儿童的身高及乘车区间的全价票价格，输出免票或者应购买的火车票的价格，画出算法的程序框图。 4. 对正弦函数，我们有它的幂级数展开式
2n?x2(?1)n2nnxcosx?1?????(?1)?????x,x?(??,?) 2!(2n)!n?0(2n)!32利用这个公式，设计一个算法，任意输入一个实数x，计算cosx的近似值，请画出算法的程序框图。（循环终止的条件是第n个近似值与第n-1个近似值的差的绝对值小于10。
?5读一读
圆周率与算法
圆的周长和直径的比值称为圆周率，记为?，它是一个常数，也是一个超越数。历史上曾采用过圆周率的多种近似值，早期大都是通过经验和测量而得到的结果，如古埃及纸草书
?4?（约公元前1700）中取?????3.1605，中国古算书《周髀算经》（ 约公元前2世纪）
?3?中有“径一而周三”的记载，即取??3。
第一个用科学方法寻求圆周率的值的人是阿基米德，他在《圆的度量》（公元前3世纪）中用正多边形逼近圆周，得到
422322???，开创了圆周率计算的几何方法（亦称古典方717法，或阿基米德方法）。
我国古代的数学家在圆周率的计算上也取得了杰出的成就。魏晋期间的数学家刘徽在注释《九章算术》（263年）时用割圆术的方法，一直算到圆内接正192边形，得到π=157/50=3.14（称为“徽率”）。刘徽的割圆术，不仅得到了π的近似值，更重要的是他给出了计算圆周率的一种科学方法。南北朝时代著名数学家祖冲之，在世界数学史上第一次将圆周率值计算到小数点后六位，即3.1415926到3.1415927之间（约5世纪下半叶），还得到两个近似分数值，密率355/113和约率22/7。他的辉煌成就比欧洲至少早了1000年。其中的密率在西方直到1573才由德国人奥托得到。
阿拉伯数学家卡西在15世纪初求得圆周率17位精确小数值，打破祖冲之保持近千年的纪录。
随着无穷连分数、无穷级数的出现，计算π值的新算法也纷纷出现，π值计算精度也迅速增加。1706年英国数学家梅钦计算π值突破100位小数大关。到1948年英国的弗格森和美国的伦奇共同发表了π的808位小数值，成为人工计算圆周率值的最高纪录。
随着电子计算机的出现，π值的计算有了突飞猛进的发展。1949年美国马里兰州阿伯丁的军队弹道研究实验室首次用计算机（ENIAC）计算π值，一下子就算到小数点后2037位。2010年，日本的近藤茂利用家用计算机和云计算相结合，计算出圆周率到小数点后5万亿位。2011年，IBM蓝色基因/P超级计算机，更是将π值计算到小数点后60万亿位。
下面列举一些计算圆周率的算法： 1. 割圆术
古人计算圆周率，一般是用割圆法。即用圆的内接或外切正多边形来逼近圆的周长。这种基于几何的算法计算量大，收敛速度慢，现在已经不太使用了。
2. 马青公式
π=16arctan1/5-4arctan1/239 ，这个公式由英国天文学教授约翰·马青于1706年发现。他利用这个公式计算到了100位的圆周率。这个公式很容易地在计算机上编程实现，半死想要计算更多的位数，比如几千万位，马青公式就力不从心了。
3. 拉马努金公式 1914年，印度天才数学家拉马努金在他的论文里发表了一系列共14条圆周率的计算公式。拉马努金公式每计算一项可以得到8位的十进制精度。1985年Gosper用这个公式计算到了圆周率的17,500,000位。
4. AGM（Arithmetic-Geometric Mean）算法
这个算法利用高斯-勒让德公式，每迭代一次将得到双倍的十进制精度。1999年9月，日本的高桥大介和金田康正用这个算法计算到了圆周率的206,158,430,000位。
5. 丘德诺夫斯基公式
1989年，大卫·丘德诺夫斯基和格雷高里·丘德诺夫斯基兄弟将拉马努金公式改良，这个公式被称为丘德诺夫斯基公式，每计算一项可以得到15位的十进制精度。丘德诺夫斯基公式十分适合计算机编程，是目前使用较多的一个公式。1994年丘德诺夫斯基兄弟利用这个公式计算到了圆周率的4,044,000,000位。
6. bailey-borwein-plouffe算法
这个公式简称BBP公式，由David Bailey, Peter Borwein和Simon Plouffe于1995年共同发表。它打破了传统的圆周率的算法，可以计算圆周率的任意第n位，而不用计算前面的n-1位。这为圆周率的分布式计算提供了可行性。 感兴趣的话，你可以进一步查找相关资料。
回顾与小结
知识框图
算法 概念 表示 基本逻辑结构 自然语言 程序框图 顺序结构 条件结构 循环结构 应用 内容要点
1.算法是指用来解决问题的一系列明确而有效的步骤，是解决问题的清晰指令。 2.一般来说，一个有效的算法应该具有下面几个特征：有穷性、可行性、确切性、输入项、输出项。
3.能够判断真假的陈述句叫做命题。我们把正确的命题称为真命题，并记它的值为“真”，错误的命题称为假命题，并记它的值为“假”，一个命题非真即假，不可能既真又假，也不可能不真不假。
4.将一些简单命题用联结词合法联结，就构成复合命题，实际上，联结词是命题逻辑的重要组成部分，常用的联结词有：非（?）、且（?）、或（?），当简单命题的值确定了，则复合命题的值也随之确定。
5. 用规定的框、带箭头的线以及说明文字来表示算法的图形，叫做算法的程序框图。我们可以用自然语言来描述算法，也可以用程序框图来描述算法，用程序框图表示算法，不仅直观、形象、容易理解，而且可以清楚地展现算法的逻辑结构。
6.算法及其程序框图有三种逻辑结构：顺序结构、条件结构和循环结构，用这些结构设计的算法及其程序框图，思路清晰，便于阅读和理解。