数学 1.3算法案例1课件 新人教A版必修3 课件.ppt

1.3算法案例(1)表示算法的三种方式：315辗转相除法（欧几里得算法）完整的过程一、辗转相除法（欧几里得算法）.第四步若r=0则mn的最大公约数等于m;否则返回第二步开始INPUTmn问题6:如果用当型循环结构构造算法求两个正整数mn的最大公约数的程序框图和程序分别如何表示？开始练习《九章算术》——更相减损术2、更相减损术例用更相减损术求98与63的最大公约数.辗转相除法与更相减损术的比较:1：用辗转相除法求80和36的最大公约数并用更相减损术检验所得结果．分析：将80作为大数36作为小数执行辗转相除法和更相减损术的步骤即可．解：用辗转相除法：80＝36×2＋836＝8×4＋48＝4×2＋0.故80和36的最大公约数是4.2.求三个数175、100、75的最大公约数．分析：求三个数的最大公约数时可以先求出其中两个数的最大公约数用这个最大公约数再与第三个数求最大公约数所得结果就是这三个数的最大公约数．解：(辗转相除法)：先求175与100的最大公约数：175＝100×1＋75100＝75×1＋2575＝25×3.∴175与100的最大公约数是25.以下再求25与75的最大公约数：75＝25×3∴25和75的最大公约数是25.故25是75和25的最大公约数也就是175、100、75的最大公约数．1.用辗转相除法计算60与48的最大公约数时需要做的除法次数是()A．1B．2C．3D．4解析：∵60＝48×1＋1248＝12×4＋0.∴仅需要两步运算．答案：B2用辗转相除法求294和84的最大公约数时需要做除法的次数是()A．1B．2C．3D．4解析：294＝84×3＋4284＝42×2.故需做2次除法．答案：B3求378和90的最大公约数．解：∵378＝90×4＋1890＝18×5∴378和90的最大公约数是18.4：求三个数324243108的最大公约数．解：：先求324与243的最大公约数324＝243×1＋81243＝81×3∴324与243的最大公约数为81.下面再求108与81的最大公约数：108＝81＋2781＝27×3.∴108与81的最大公约数是27.故324243108的最大公约数为27.1.辗转相除法就是对于给定的两个正整数用较大的数除以较小的数若余数不为零则将余数和较小的数构成新的一对数继续上面的除法直到大数被小数除尽为止这时的较小的数即为原来两个数的最大公约数.3、辗转相除法与更相减损术的区别（1）都是求最大公约数的方法计算上辗转相除法以除法为主更相减损术以减法为主计算次数上辗转相除法计算次数相对较少特别当两个数字大小区别较大时计算次数的区别较明显.（2）从结果体现形式来看辗转相除法体现结果是以相除余数为0则得到而更相减损术则以减数与差相等而得到.