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

1、开始学案学案7 7中国古代数学中的中国古代数学中的算法案例算法案例学点一学点二 1. 1.用两数中较大的数减去较小的数用两数中较大的数减去较小的数, ,再用再用 和和 构成新的一对数构成新的一对数, ,再用大数减小数再用大数减小数, ,以同样的操以同样的操作一直做下去作一直做下去, ,直到产生直到产生 , ,这个数就是最这个数就是最大公约数大公约数. . 2. 2.古希腊求两个正整数的最大公约数的方法是古希腊求两个正整数的最大公约数的方法是: : 用较大的数除以较小的数所得用较大的数除以较小的数所得的的 和和 构成新的一对数构成新的一对数, ,继续做上面的继续做上面的除法除法, ,直到大数被小

2、数除尽直到大数被小数除尽, ,这个较小的数就是最大公约数这个较小的数就是最大公约数. . 3. 3.割圆术是我国魏晋时期的数学家割圆术是我国魏晋时期的数学家 在注九章在注九章算术中采用算术中采用 . . 的一种方法的一种方法. . 返回目录返回目录差数差数较小的数较小的数一对相等的数一对相等的数辗转相除法辗转相除法( (欧几里得算法欧几里得算法) )余数余数较小的数较小的数刘徽刘徽正多边形面积逐渐逼近圆面积的算法计算正多边形面积逐渐逼近圆面积的算法计算圆周率圆周率3.3.把一个把一个n n次多项式次多项式f f( (x x)=)=a an nx xn n a an nx xn na a1 1x

3、 x a a0 0改写成如下形式改写成如下形式: : f f( (x x)= )= a an nx xn na an nx xn na a1 1x xa a0 0= = . .= = . . = = . . 求多项式的值时求多项式的值时, ,首先计算最内层括号内一次多项式首先计算最内层括号内一次多项式的值的值, ,即即v v1 1= = . . 然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值, ,即即 v v2 2= = , , v v3 3= = , , v vn n= = , ,( (a an nx xn n-1-1a an nx xn n2 2a a1 1) )x

4、xa a0 0 (a an nx xn n-2-2a an nx xn n3 3+a a2 2) )x xa a1 1) )x xa a0 0 v v0 0 x xa an nv v2 2x xa an n3 3v v1 1x xa an n2 2v vn n-1-1x xa a0 0返回目录返回目录(（( (a an nx xa an n) )x x a an n2 2 ) )x xa a1 1) )x xa a0 0 返回目录返回目录这样这样, ,求求n n次多项式次多项式f f( (x x) )的值就转化为的值就转化为. .上述方法称为秦九韶算法上述方法称为秦九韶算法. .观察上述秦九韶

5、算法中的观察上述秦九韶算法中的n n个一次式个一次式, ,可见可见v vk k的计算要的计算要用到用到v vk k-1-1的值的值. .若令若令v v0 0= =a an n, ,我们可以得到公式我们可以得到公式: : . .这是一个在秦九韶算法中反复执行的步骤这是一个在秦九韶算法中反复执行的步骤, ,因此可用因此可用 来实现来实现. .求求n n个一次多项式的值个一次多项式的值 v vo o=a=an nv vk k=v=vk-k-1 1x+ax+an-kn-k( (k=k=1,2,1,2,n n) )循环结构循环结构 返回目录返回目录学点一学点一 求最大公约数求最大公约数 用更相减损之术求

6、用更相减损之术求9898和和6363的最大公约数的最大公约数. . 【分析】【分析】由于由于6363不是偶数不是偶数, ,把把9898和和6363以大数减小数以大数减小数, ,并并辗转相减辗转相减. . 【解析】【解析】98-63=35,63-35=28,35-28=7,28-7=14,14-98-63=35,63-35=28,35-28=7,28-7=14,14-7=77=7，所以，所以9898和和6363的最大公约数为的最大公约数为7.7. 【评析】等值算法是当大数减去小数的差等于小数时【评析】等值算法是当大数减去小数的差等于小数时停止减法停止减法, ,较小的数就是所求的最大公约数较小的数

7、就是所求的最大公约数. .设计程序设计程序, ,求两正整数求两正整数m m, ,n n的最小公倍数的最小公倍数. . 解：由于解：由于m m, ,n n的最小公倍数的最小公倍数, ,即为即为m m与与n n的乘积除以的乘积除以m m与与n n的最大公约数的最大公约数. .因此因此, ,可先求出可先求出m m与与n n的最大公约数的最大公约数, ,再用再用m m n n去除以这个最大公约数即可去除以这个最大公约数即可. . 程序如下程序如下: : m=input(“m=”) m=input(“m=”) n=input(“n=”) n=input(“n=”) S=m S=m* *n;n; whil

8、e mn while mn if mn if mn m=m-n; m=m-n; else else n=n-m; n=n-m; end end end end T= T= print(%io(2),T) print(%io(2),T);ms返回目录返回目录返回目录返回目录学点二学点二 秦九韶算法秦九韶算法用秦九韶算法求多项式用秦九韶算法求多项式f f( (x x)=7)=7x x7 7+6+6x x6 6+5+5x x5 5+4+4x x4 4+3+3x x3 3+2+2x x2 2+ +x x在在x x=3=3时的值时的值. . 【分析】【分析】明确项数与次数明确项数与次数正确改写所给多项式

9、正确改写所给多项式从从内向外逐次求值内向外逐次求值. . 【解析】【解析】f f( (x x)=(7)=(7x x+6)+6)x x+5)+5)x x+4)+4)x x+3)+3)x x+2)+2)x x+1)+1)x x, , v v0 0=7=7， v v1 1=7=73+6=27,3+6=27, v v2 2=27=273+5=86,3+5=86, v v3 3=86=863+4=262,3+4=262, v v4 4=262=2623+3=789,3+3=789, v v5 5=789=7893+2=2 369,3+2=2 369, v v6 6=2 369=2 3693+1=7 10

10、8,3+1=7 108, v v7 7=7 108=7 1083=21 324,3=21 324, f f(3)=21 324.(3)=21 324.返回目录返回目录 【评析】利用秦九韶算法计算多项式的值关键是能正【评析】利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写确地将所给多项式改写, ,然后由内向外逐次计算然后由内向外逐次计算, ,由于后项由于后项计算需用到前项的结果计算需用到前项的结果, ,故应认真、细心故应认真、细心, ,确保中间结果的确保中间结果的准确性准确性. .返回目录返回目录求多项式求多项式f f( (x x)=)=x x5 5+5+5x x4 4+10+10 x

11、 x3 3+10+10 x x2 2+5+5x x+1+1当当x x=-2=-2时的值时的值. . 解：先改写多项式解：先改写多项式, ,再由内向外计算再由内向外计算. . f f( (x x)=)=x x5 5+5+5x x4 4+10+10 x x3 3+10+10 x x2 2+5+5x x+1+1=(=(x x+5)+5)x x+10)+10)x x+10)+10)x x+5)+5)x x+1.+1.而而x x=-2,=-2,所以有所以有: :v v0 0=1,=1,v v1 1= =v v0 0 x x+ +a a4 4=1=1(-2)+5=3,(-2)+5=3,v v2 2= =v

12、 vx x+ +a a3 3=3=3(-2)+10=4,(-2)+10=4,v v3 3= =v v2 2x x+ +a a2 2=4=4(-2)+10=2,(-2)+10=2,v v4 4= =v v3 3x x+ +a a1 1=2=2(-2)+5=1,(-2)+5=1,v v5 5= =v v4 4x x+ +a a0 0=1=1(-2)+1=-1.(-2)+1=-1. 1. 1.如何理解三个算法案例如何理解三个算法案例? ? (1)(1)更相减损之术更相减损之术 所谓更相减损之术所谓更相减损之术, ,就是对于给定的两个数就是对于给定的两个数, ,以两数中以两数中较大的数减去较小的数较大

13、的数减去较小的数, ,然后将所得的差和较小的数构成一然后将所得的差和较小的数构成一对新数对新数, ,再用这对新数中的较大的数减去较小的数再用这对新数中的较大的数减去较小的数, ,反复执反复执行此步骤直到差数和较小的数相等为止行此步骤直到差数和较小的数相等为止, ,此时相等的数便为此时相等的数便为原来两个数的最大公约数原来两个数的最大公约数. . 所谓辗转相除法所谓辗转相除法, ,就是对于给定的两个数就是对于给定的两个数, ,用较大的数用较大的数除以较小的数除以较小的数, ,若余数不为零若余数不为零, ,则将余数和较小的数构成新则将余数和较小的数构成新的一对数的一对数, ,继续上面的除法继续上面

14、的除法, ,直到大数被小数除尽直到大数被小数除尽, ,这时较小这时较小的数就是原来两个数的最大公约数的数就是原来两个数的最大公约数. . 返回目录返回目录返回目录返回目录 (2) (2)割圆术割圆术 是数学上最重要的常数之一是数学上最重要的常数之一, ,我国古代数学家在割圆我国古代数学家在割圆术上取得了巨大的成就术上取得了巨大的成就. .通过学习割圆术通过学习割圆术, ,同学们可以尝试同学们可以尝试着计算着计算的近似值的近似值. .特别将不足近似值和过剩近似值相结合特别将不足近似值和过剩近似值相结合, ,通过近似值的上下限通过近似值的上下限S S2 2n n S S S S2 2n n+(+(

15、S S2 2n n- -S Sn n)()(n n=6,12,).=6,12,). (3) (3)秦九韶算法秦九韶算法 秦九韶算法是求一元秦九韶算法是求一元n n次多项式的一种算法次多项式的一种算法, ,通过一次通过一次多项式的反复计算多项式的反复计算, ,逐步得出高次多项式的值逐步得出高次多项式的值, ,对于一个对于一个n n次次多项式多项式, ,只需做只需做n n次乘法和次乘法和n n次加法即可次加法即可. .返回目录返回目录 2. 2.中国古代数学中的算法案例学习的意义是什么中国古代数学中的算法案例学习的意义是什么? ? 我国古代数学中算法的内容十分丰富我国古代数学中算法的内容十分丰富,

16、 ,成就辉煌成就辉煌. .课本课本中的更相减损之术、割圆术、秦九韶算法，就是很好的代中的更相减损之术、割圆术、秦九韶算法，就是很好的代表表. .我国古代数学主要特征是算法化我国古代数学主要特征是算法化, ,现代信息技术的发展现代信息技术的发展也使算法焕发了生机也使算法焕发了生机. .通过本部分的学习通过本部分的学习, ,体会中国古代数体会中国古代数学对世界数学发展的贡献学对世界数学发展的贡献, ,增强民族自豪感增强民族自豪感, ,努力学习努力学习, ,为国为国家的发展贡献力量家的发展贡献力量. . 1. 1.学习更相减损之术与辗转相除法时学习更相减损之术与辗转相除法时, ,要注意两种方要注意两

17、种方法的相通之处法的相通之处. . 2. 2.要深切体会刘徽的要深切体会刘徽的“割之弥细，所失弥少割之弥细，所失弥少”的思想的思想方法方法, ,利用正多边形面积随边数增多利用正多边形面积随边数增多, ,逐渐逼近圆面积来计逐渐逼近圆面积来计算圆周率算圆周率. 3. 3.学习秦九韶算法时学习秦九韶算法时, ,注意通过分析秦九韶算法的运注意通过分析秦九韶算法的运算次数算次数, ,感悟算法思想的优越性和先进性感悟算法思想的优越性和先进性, ,算法的关键是采算法的关键是采用逐步提出因式用逐步提出因式x x的方法对多项式进行改写的方法对多项式进行改写. . 学习过程中应注意研究分析教材中三个例子的算法设学习过程中应注意研究分析教材中三个例子的算法设计思路计思路, ,体会算法的道理所在体会算法的道理所在. .比较一下第二个和第三个例