人教B版必修三 辗转相除法 学案.doc

要点阐述辗转相除法（1）辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法（2）辗转相除法的算法步骤第一步，给定 两个正整数m，n(mn)第二步，计算 m除以n所得的余数r第三步， mn，nr第四步，若r0，则m，n的最大公约数等于 m ；否则，返回第二步典型例题【例】用辗转相除法求204，168，186三个数的最大公约数 【答案】6小试牛刀1下列说法中正确的有（）辗转相除法也叫欧几里得算法；辗转相除法的基本步骤是用较大的数除以较小的数；求最大公约数的方法，除辗转相除法之外，没有其他方法；编写辗转相除法的程序，要用到循环语句a1个b2个c3个d4个【答案】c【解析】不正确，因为除了辗转相除法，还有其他方法，如更相减损术故选c 2用“辗转相除法”求得459和357的最大公约数是（ ）a3b9c17d51【答案】d3若表示不超过的最大整数（如，），则下列程序的功能为 input “x，y=”；x，ym=xn=ydoc=m-int（m/n） nm=nn=cloop until m/n=int（m/n）print nend【答案】求与的最大公约数【解析】该程序实质为辗转相除法，主要用于求两个正数的最大公约数其中：与用辗转相除法求两个正数的最大公约数的程序中所表达的含义是一样的，都是表示除以的余数为0，就是除以的余数，即为所以该程序的功能是求与的最大公约数4运行下面的程序，当输入n840和m1764时，输出结果是()a84b12 c168d252【答案】a【解析】1764840284,8408410，1764与840的最大公约数为845下列程序的功能为 【答案】146用辗转相除法分别求下列各组数的最大公约数：（1）80与36；（2）288与123【解析】（1）由辗转相除法，80=362+8，36=84+4，8=42，故80与36的最大公约数是4（2）由辗转相除法，288=1232+42，123=422+39，42=391+3，39=313，故288与123的最大公约数是3【归纳总结】由除法的性质知，对于任意两个正整数，上述除法步骤总可以在有限步之后完成，从而总可以用辗转相除法求出它们的最大公约数考题速递11 037和425的最大公约数是 ()a51b17 c9d3【答案】b2辗转相除法程序中有一空请填上input “a,b=”;a,bdor=_a=bb=rloop until r=0print aend【答案】a mod b【解析】mod用来表示a除以b的余数3若表示不超过的最大整数（如，），则下列程序的功能为 input “x，y=”；x，ym=xn=ydoc=m-int（m/n） nm=nn=cloop until m/n=int（m/n）print nend【答案】求与的最大公约数【解析】该程序实质为辗转相除法，主要用于求两个正数的最大公约数其中：与用辗转相除法求两个正数的最大公约数的程序中所表达的含义是一样的，都是表示除以的余数为0，就是除以的余数，即为所以该程序的功能是求与的最大公约数4用辗转相除法求下列两数的最大公约数（1）294,84；（2）228,1 995数文化古算世界据说有一次汉高祖刘邦在众大臣的簇拥下来到练兵场，刘邦问韩信有什么方法，不要逐个报数，就能知道场上的士兵的个数韩信先令士兵排成3列纵队，结果有2个人多余；接着立即下令将队形改为5列纵队，这一改，又多出3人；