1.3算法案例课〔3课时).ppt

v1=anx+an-1, v2=v1x+an-2, v3=v2x+an-3, ……, vn=vn-1x+a0. 观察上述秦九韶算法中的n个一次式,可见vk的计算要用到vk-1的值. 若令v0=an,得 v0=an, vK=vK-1x+an-k(k=1,2,……,n） 这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现. [问题]画出程序框图,表示用秦九韶算法求5次多项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0 (x0是任意实数)时的值的过程,然后写出程序. 否 程序框图 开始 输入a0,a1,a2,a3,a4,a5 输入x0 n≤5? n=1 v=a5 v=vx0+a5-n n=n+1 输出v 结束 是 INPUT a0, a1, a2, a3, a4, a5 INPUT x0 n=1 v=a5 WHILE n=5 v=vx0+a5-n n=n+1 WEND PRINT v END 程序 INPUT “n=”；n INPUT “an=”;an INPUT “x=”; x V=an i=n-1 DO PRINT “i=”;i INPUT “ai=”;ai v=v*x+ai i=i-1 LOOP UNTIL i0 PRINT v END 算法程序如右所示： 作业: 课本P48页习题1.3A组T2 算法案例 （第三课时） 一、进位制 1、什么是进位制？ 2、最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明． 进位制是人们为了计数和运算方便 而约定的记数系统。 1、我们了解十进制吗？所谓的十进制，它是如何构成的？ 十进制由两个部分构成 例如：3721 其它进位制的数又是如何的呢？ 第一、它有0、1、2、3、4、5、6、7、8、9十个数字； 第二、它有“权位”，即从右往左为个位、十位、百位、千位等等。 (用10个数字来记数，称基数为10) 表示有：1个1，2个十， 7个百即7个10的平方， 3个千即3个10的立方 算 法 案 例 金太阳新课标资源网 （第一课时） 1、求两个正整数的最大公约数(短除法) （1）求25和35的最大公约数 （2）求225和135的最大公约数 2、求8251和6105的最大公约数 25 （1） 5 5 35 7 所以，25和35的最大公约数为5 所以，225和135的最大公约数为45 辗转相除法（欧几里得算法） 观察用辗转相除法求8251和6105的最大公约数的过程 第一步 用两数中较大的数除以较小的数，求得商和余数8251=6105×1+2146 结论： 8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。 第二步 对6105和2146重复第一步的做法6105=2146×2+1813同理6105和2146的最大公约数也是2146和1813的最大公约数。 完整的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 例2 用辗转相除法求225和135的最大公约数 225=135×1+90 135=90×1+45 90=45×2 显然37是148和37的最大公约数，也就是8251和6105的最大公约数 显然45是90和45的最大公约数，也就是225和135的最大公约数 思考1：从上面的两个例子可以看出计算的规律是什么？ S1：用大数除以小数 S2：除数变成被除数，余数变成除数 S3：重复S1，直到余数为0 思考：你能把辗转相除法求任意两个正整数m,n(mn)的最大公约数编成一个计算机程序吗？ §1.3.1算法案例---辗转相除法和更相减损术 写算法步骤： 第一步，给定两个正整数m,n 第二步，计算m除以n的余数为r 第三步，m=n,n=r 第四步，若r=0,则m,n的最大公约数等于m,否则，返回第二步。 §1.3.1算法案例---辗转相除法和更相减损术 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 m = n × q ＋ r 用程序框图表示出右边的过程 r=m MOD n m = n n = r r=0? 是 否 INPUT m , n DO