1.3算法案例课3课时.ppt

算 法 案 例;1、求两个正整数的最大公约数(短除法);辗转相除法（欧几里得算法）;完整的过程;思考：你能把辗转相除法求任意两个正整数m,n(mn)的最大公约数编成一个计算机程序吗？;写算法步骤：; 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。;画程序框图;编制程序:;当型结构：;《九章算术》——更相减损术 ;例3 用更相减损术求 225 与 135 的最大公约数;INPUT a,b WHILE ab IF ab THEN a=a-b ELSE b=b-a END IF WEND PRINT a END;练习： 用辗转相除法求 294 与84的最大公约数，再用更相减损术验证。;算 法 案 例;计算多项式ｆ（ｘ） =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x = 5的值;[问题1]设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值的算法,并写出程序.; 这析计算上述多项式的值,一共需要9次乘法运算,5次加法运算.; [问题3]能否探索更好的算法,来解决任意多项式的求值问题?;《数书九章》——秦九韶算法;设;要求多项式的值，应该先算最内层的一次多项式的值，即; 点评:秦九韶算法是求一元多项式的值的一种方法. 它的特点是:把求一个n次多项式的值转化为求n个一次多项式的值,通过这种转化,把运算的次数由至多n(n+1)/2次乘法运算和至多n次加法运算,减少为n次乘法运算和至多n次加法运算,大大提高了运算效率.;例3:用秦九韶算法求多项式 f(x)=2x5-5x4-4x3+3x2-6x+7当x=5时的值.;2 -5 -4 3 -6 7;2 -5 0 -4 3 -6 0;练习：;v1=anx+an-1,;否;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、 二进制;二、二进制与十进制的转换;练习; 例2 已知10b1（2）=a02（3）,求数字a，b的值.;将k进制数a转换为十进制数(共有 n位)的程序;2、十进制转换为二进制 ;;2、十进制转换为二进制;练习;例3 把89化为五进制数;设计一个程序，实现“除k取余法”;思考题??? 如何将101（2） 化为五进制数？