中国古代数学中的算法案例.pptVIP

中国古代数学中的算法案例1

最大公约数2

定义如果有一个自然数a能被自然数b整除，那么称a为b的倍数，b为a的约数。几个自然数公有的约数，叫做这几个自然数的公约数。公约数中最大的一个公约数，称为这几个自然数的最大公约数。3

求得最大公约数的方法辗转相除法〔欧几里得算法〕4

5

简介6

如何使用求98与63的最大公约数。解：由于63不是偶数，把98和63以大数减小数，并辗转相减：98-63=3563-35=2835-28=728-7=2121-7=1414-7=7∴98和63的最大公约数等于7。7

得与有相同的公约数理论依据8

算法表示S1：输入两个正数a,b(ab)；S2：如果a≠b，那么执行S3，否那么转到S5；S3：将a-b的值赋予r；S4：假设br，那么把b赋予a，把r赋予b，否那么把r赋予a，重新执行S2；S5：输出最大公约数b.9

输出bYN输入a,ba≠b结束开始abb=b－aa=a－bYN10

程序：a=input(“a=〞)；b=input(“b=〞)；whileabifa=ba=a－b;elseb=b－a；endendprint(%io(2),b,“两数的最大公约数为：〞)11

辗转相除法12

辗转相除法辗转相除法最早出现在欧几里得的几何原本中〔大约公元前300年〕，所以它是现在仍在使用的算法中最早出现的。欧几里得13

如何使用以求288和123的最大公约数为例，操作如下：S1：288÷123=2……42S2：123÷42=2……39S3：42÷39=1……3S4：39÷3=13∴3就是288和123的最大公约数。这是一个辗转相处的过程……14

理论依据得与有相同的公约数15

第一步：输入两个正整数a，b〔a＞b〕;第二步：求出a÷b的余数r；第三步：令a=b，b=r，假设r≠0，重复第二步；第四步：输出最大公约数a.16

17

18

19

20

计算方法第一，从半径为1的圆内接正六边形开始，计算它的面积S6；第二，逐步加倍圆内接正多边形的边数，分别计算圆内接正十二边形，正二十四边形，正四十八边形，…的面积，到一定的边数〔设为2m〕为止，得到一列递增的数，S6，S12，S24，S48，…，S2n.第三，S2n近似等于圆面积。21

下面的关键是找出正n边形的面积与正2n边形的面积之间的关系，以便递推。设圆的半径为1，正n边形的边长AB为xn，弦心距OG为hn；面积为Sn，根据勾股定理，得：22

容易知道x6=1,正2n边形的面积等于正n边形的面积加上n个等腰三角形的面积，即于是由求得S12=3；S24≈3.105828；……23

按照这样的思路，刘徽把圆内接正多边形的面积一直算到了正3072边形，并由此而求得了圆周率为3.14和3.1416这两个近似数值。这个结果是当时世界上圆周率计算的最精确的数据。24

n=6;x=1;s=6*sqrt(3)/4;fori=1:1:5h=sqrt(1－(x/2)^2);s=s+n*x*(1－h)/2;n=2*n;x=sqrt((x/2)^2+(1－h)^2);endprint(%io(2),n,s)程序编写25

秦九韶算法26

人物介绍27

成就28

一个一元n次多项式函数:P(x)=anxn+an-1xn-1+……+a1x+ao当知道x值时，我们可以按顺序一项一项的计算，然后相加，求出P(x)秦九韶算法29

设有n+1项的n次函数，即：再将括号内的前n-1项提取公因数x,得:将前n项提取公因数x?，得:秦九韶算法30

如此反复提取公因数x??，最后将函数化为:令......那么：fn即为所求秦九韶算法31

怎样用程序框图表示秦九韶算法？观察秦九韶算法的数学模型，计算vk时要用到fk－1的值，假设令f0=an，我们可以得到下面的递推公式：f0=anfk=fk－1·x+an－k(k=1,2,…,n)这是一个在秦九韶算法中反复执行的步骤，可以用循环结构来实现。32

开始输入x,n;a0,a1,a2,…,ank=k－1f=f*x+ak输出S结束k=n,f=an开始输入x,n;a0,a1,a2,…,ank0是否33

Scilab语言：x=input(x=);n=input(n=);result=input(Thefirstxishu);f