算法案例（一课时）.pptVIP

算 法 案 例;案例1 辗转相除法与更相减损术;1. 回顾算法的三种表述：;2. 思考：;1、求两个正整数的最大公约数;辗转相除法（欧几里得算法）;完整的过程; 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。;1、辗转相除法（欧几里得算法）;（2）算法步骤;（3）程序框图;《九章算术》——更相减损术 ;2、更相减损术;（2）算法步骤;（3）程序框图;例3 用更相减损术求98与63的最大公约数;例3、求324、243、135这三个数的最大公约数。;比较辗转相除法与更相减损术的区别 （1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。 （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到;案例2 秦九韶算法;1. 回顾算法的三种表述：;案例2、秦九韶算法;计算多项式ｆ(ｘ) =ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１当x = 5的值;算法1：;《数书九章》——秦九韶算法;要求多项式的值，应该先算最内层的一次多项式的值，即;算法步骤：;程序框图：;特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可。;例2 已知一个五次多项式为;程序框图：;课堂小结： 1、秦九韶算法的方法和步骤 2、秦九韶算法的程序框图;k进制化十进制;知识探究(一):进位制的概念 ; 如二进制可使用的数字有0和1,基数是2; 十进制可使用的数字有0,1,2,…,8,9等十个数字,基数是10; 十六进制可使用的数字或符号有0~9等10个数字以及A~F等6个字母(规定字母A~F对应10~15),十六进制的基数是16.;思考2:十进制使用0～9十个数字，那么五进制、七进制分别使用哪些数字？ ;思考4:十进制数4528表示的数可以写成4×103+5×102+2×101+8×100，依此类比，二进制数110011（2）,八进制数 7342（8）分别可以写成什么式子？;思考5:一般地，如何将k进制数 anan-1…a1a0(k)写成各数位上的数字与基数k的幂的乘积之和的形式？;知识探究(二):k进制化十进制的算法 ;思考3:把二进制?? 化为十进制数b的算法步骤如何设计？;思考4:按照上述思路，把k进制数 化为十进制数b的算法步骤如何设计？;思考5:上述把k进制数 化为十进制数b的算法的程序框图如何表示？ ;思考6:该程序框图对应的程序如何表述？; 例1 将下列各进制数化为十进制数. （1）10303（4） ； （2）1234（5）.; 例2 已知10b1（2）=a02（3）,求数字a，b的值.; 1. k进制数使用0～（k-1）共k个数字，但左侧第一个数位上的数字（首位数字）不为0.