辽宁省大连市第二十四中学高三数学复习课件：《古代算法》.ppt

1、1.回顾算法的四种表示方法：（1）、自然语言（3）、程序框图（4）、程序语言（三种逻辑结构）（五种基本语句）复习引入（2）、数学语言x=5;y=20;if x2000是否3、执行如图的程序，最后一个输出的数是多少？n2000n=n+3若交换与后，最后一个输出的数是多少？19992002复习引入开始结束输入P输出nn=1,S=0n=n+1S=S+2n-1Sb,则把 a-b 的值重新赋予a；否则（a bb=baa=abYN程序框图程序语言：a=input(“a=”)；b=input(“b=”)；while abif aba=ab;else b=ba；endendprint(%io(2),a,“两数

2、的最大公约数为：”)2、辗转相除法求两个数的最大公约数，其基本步骤是带余除法m=nq+r（0rn），反复执行，直到余数r=0为止.（欧几里得算法）(78，36)(6，36)1步(288,123)(42,123)（42,39）（3,39）3步思考：你能把辗转相除法编成一个计算机程序吗？(1)、算法步骤：第一步：输入两个正整数m,n(mn).第二步：计算m除以n所得的余数r.第三步：m=n,n=r.第四步：若r0,则m,n的最大公约数等于m；否则转到第二步.第五步：输出最大公约数m.(2)、程序框图：开始输入m,n r=m MOD n m=nr=0?是否 n=r输出n结束(3)、程序：m=inpu

3、t(“m=”)n=input(“n=”)while modulo(m,n)0,r=modulo(m,n);m=n,n=r;endd=r比较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。小结二、秦九韶算法设计求多项式f(x)=5x5+3x4+2x3+3x2x+1当x=2时的函数值一般的解决方案:x=2;y=5*x5+3*x4+2*x3+3*x2

4、x+1;y设计求多项式f(x)=5x5+3x4+2x3+3x2x+1当x=2时的函数值次加法，次乘法秦九韶算法适用一般的多项式P(x)=anxn+an1xn1+a1x+a0的求值问题P(x)=anxn+an1xn1+a1x+a0=(anxn1+an1xn2+a1)x+a0 =(anxn2+an1xn3+a2)x+a1)x+a0 =(anx+an1)x+an2)x+a1)x+a0n次乘法，n次加法要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一项是什么？.（2）n次乘法和n次加法秦九韶算法的特点：得递推公式为：（1）降幂世界上多项式求值最先进算法用秦九韶算法求函数在处函数值时，问（1）、几次加法？几次乘法？（2）、求缺项用“0”补位！课堂小结一、古代数学 “寓理于算”把解决的问题“算法化”二、算法语句为学习计算机知识打下基础三、程序框图为高考服务