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

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