2020版高中数学 第一章 算法初步 1.3 算法案例 第1课时 辗转相除法与更相减损术课件 新人教

第1课时辗转相除法与更相减损术第一章§1.3算法案例学习目标XUEXIMUBIAO1.了解辗转相除法与更相减损术中的数学原理.2.会求两个数的最大公约数.3.体会案例中的数学素养．NEIRONGSUOYIN内容索引自主学习题型探究达标检测1自主学习PARTONE知识点一辗转相除法1.辗转相除法，又叫欧几里得算法，是一种求两个正整数的的古老而有效的算法.2.辗转相除法的算法步骤第一步，给定.第二步，计算.第三步，.第四步，若r＝0，则m，n的最大公约数等于；否则，返回.最大公约数两个正整数m，n(mn)m除以n所得的余数rm＝n，n＝rm第二步思考注意到8251＝6105×1＋2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？答案显然8251与6105的公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数.知识点二更相减损术更相减损术的运算步骤第一步，任意给定两个正整数，判断它们是否都是.若是，用约简；若不是，执行.第二步，以的数减去的数，接着把所得的差与的数比较，并以大数减小数，继续这个操作，直到所得的数为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.偶数2第二步较大较小较小相等1.辗转相除法的基本步骤是用较大的数除以较小的数.()2.求最大公约数的方法除辗转相除法之外，没有其他方法.()3.编写辗转相除法的程序时，要用到循环语句.()思考辨析判断正误SIKAOBIANXIPANDUANZHENGWU√√×2题型探究PARTTWO题型一辗转相除法例1试用辗转相除法求228与1995的最大公约数.解1995＝8×228＋171，228＝1×171＋57，171＝3×57，所以228与1995的最大公约数为57.反思感悟辗转相除法的实质：对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到大数被小数除尽，则这时的小数就是原来两个正整数的最大公约数.跟踪训练1用辗转相除法求204与85的最大公约数时，需要做除法的次数是____.解析用辗转相除法可得204÷85＝2……34，85÷34＝2……17，34÷17＝2，此时可以判断204与85的最大公约数是17，做了3次除法得出结果.3题型二更相减损术解方法一612÷2＝306,396÷2＝198,306÷2＝153,198÷2＝99，∴153－99＝54,99－54＝45,54－45＝9,45－9＝36，36－9＝27,27－9＝18,18－9＝9.∴612,396的最大公约数为9×22＝36.方法二612－396＝216,396－216＝180,216－180＝36,180－36＝144,144－36＝108,108－36＝72,72－36＝36.故36为612,396的最大公约数.例2试用更相减损术求612,396的最大公约数.反思感悟更相减损术的算法步骤第一步，给定两个正整数m，n，不妨设m＞n.第二步，若m，n都是偶数，则不断用2约简，使它们不同时是偶数，约简后的两个数仍记为m，n.第三步，d＝m－n.第四步，判断“d≠n”是否成立，若是，则将n，d中的较大者记为m，较小者记为n，返回第三步；否则，2kd(k是约简整数2的个数)为所求的最大公约数.跟踪训练2用更相减损术求261和319的最大公约数.解∵319－261＝58，261－58＝203，203－58＝145，145－58＝87，87－58＝29，58－29＝29，∴319与261的最大公约数为29.典例用辗转相除法和更相减损术两种方法，求三个数72,120,168的最大公约数.核心素养之数学运算HEXINSUYANGZHISHUXUEYUNSUAN求三个正整数的最大公约数素养评析(1)求多个正整数的最大公约数，先求两个数的最大公约数，再求这个最大公约数与另一个数的最大公约数，依次类推.(2)求最大公约数，首先要设计运算方案，选择运算方法，求得运算结果，所以说，这类题目是培养学生数学核心素养的重要内容.3达标检测PARTTHREE1.1337与382的最大公约数是A.3B.382C.191D.201√解析1337＝382×3＋191,382＝191×2，所以1337与382的最大公约数是191.123452.下列各组关于最大公约数的说法中不正确的是A.16和12的最大公约数是4B.102和84的最大公约数是6C.85和357的最大公约数是34D.105和315的最大公约数是105√解析85和357的最大公约数是17.123453.用更相减损术求36与134的最大公约数，第一步应为_____________________.先除以2，得到18与67解析∵36与134都是偶数，∴第一步应为先除以2，得到18与67.4.已知a＝333，b＝24，则使得a＝bq＋r(q，r均为自然数，且0≤r＜b)成立的q和r的值分别为________.13,21解析用333除以24，商即为q，余数就是r.333÷24＝13……21.123455.用辗转相除法求85与51的最大公约数.12345解85＝51×1＋34，51＝34×1＋17，34＝17×2＋0，所以8与51的最大公约数为17.课堂小结KETANGXIAOJIE1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.