人教版高中数学算法案例课件2 新课标 人教 必修3(A).ppt

算法案例2021/8/9 星期一11、辗转相除法（欧几里得算法）（1）算理：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。案例1、辗转相除法与更相减损术2021/8/9 星期一2（2）算法步骤）算法步骤第一步：输入两个正整数第一步：输入两个正整数a,b(ab);第二步：把第二步：把a/b的余数赋给的余数赋给r;第三步：如果第三步：如果r 0,那么把那么把b赋给赋给a,把把r赋给赋给b,转转到第二步到第二步;否则转到第四步；否则转到第四步；第四步：输出最大公约数第四步：输出最大公约数b.2021/8/9 星期一3（3）程序框图）程序框图（4）程序）程序INPUT “a,b=“;a,bDO r=a MOD b a=b b=rLOOP UNTIL r=0PRINT aEND开始开始输入输入a,b r=a MOD b a=br=0?是是否否 b=r 输出输出a结束结束2021/8/9 星期一42、更相减损术、更相减损术（1）算理）算理：所谓更相减损术，就是对于给定：所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。来两个数的最大公约数。2021/8/9 星期一5（2）算法步骤）算法步骤第一步：输入两个正整数第一步：输入两个正整数a,b(ab);第二步：若第二步：若a不等于不等于b,则执行第三步；否则转则执行第三步；否则转到第五步；到第五步；第三步：把第三步：把a-b的差赋予的差赋予r;第四步：如果第四步：如果br,那么把那么把b赋给赋给a,把把r赋给赋给b;否否则把则把r赋给赋给a，执行第二步；，执行第二步；第五步：输出最大公约数第五步：输出最大公约数b.2021/8/9 星期一6例例1、用更相减损术求、用更相减损术求98和和63的最大公约数。的最大公约数。2021/8/9 星期一72.更相减损术更相减损术例例2 用更相减损术求用更相减损术求 98 与与 63 的的最大公约数最大公约数.98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以所以,98 和和 63 的最大公约数等于的最大公约数等于7.2021/8/9 星期一8