2.辗转相除法───求两正整数的最大公约数一、预备知识2.最大公约数、最小公倍数1.商、余数1.短除法3.相关符号 二、求最大公约数的方法3.更相减损术§74辗转相除法与更相减损术三、编程三大语言三结构五种语句三案例高考 主流是框图循环结构是重点辗转相除法与更相减损术进位制秦九韶算法注4:注1:自然语言框图程序设计 语言注2:顺序结构条件结构循环结构输入语句注3:赋值语句输出语句条件语句循环语句───求最大 公约数───求多项式的值框图的画法是次要的重点是要能看懂框图输入语句INPUT“提示内容”;变量输出语句PR INT“提示内容”;表达式赋值语句变量=表达式条件语句IF条件THEN步骤AENDIFIF条件 THEN步骤AELSE步骤BENDIF循环体满足条件?否是循环体满足条件?否是DO 循环体LOOPUNTIL条件WHILE条件循环体WEND循环语句2.辗转相除法───求两正整数 的最大公约数一、预备知识2.最大公约数、最小公倍数1.商、余数1.短除法3.相关符号二、求最大公约数的方法 3.更相减损术§74辗转相除法与更相减损术三、编程一、预备知识2.最大公约数、最小公倍数1.商、余数3. 相关符号练习1相关符号(1)课本P:29练习2…a=x\10b=xMOD10…练习1相关符号 (2)课本P:45程序…q=a\kr=aMODk…1.短除法二、求最大公约数的方法参:课本P:34练 习2短除法求下面两个正整数的最大公约数:(2)72和84的最大公约数2555357故最大公约数为5故最大公约数为 12(1)求25和35的最大公约数72236844221821367数字较小短除法公质因数连续除除 到所有商互质除数连乘是答案2.辗转相除法1.短除法二、求最大公约数的方法参:课本P:34参:课本P:34 练习3.辗转相除法求两个正整数的最大公约数:(1)72和84(2)225和13584=72×1+1272=12×6+0 12是最大公约数225=135×1+90135=90×1+4590=45×2+045是最大公约数大除小余换大 辗转除何时停0或11互质0除数即答案8251=6105×1+21466105=2146×2+181 32146=1813×1+3331813=333×5+148333=148×2+37148=37×4+037是最大公约 数(3)8251和6105练习4课本P:45练习1练习3.辗转相除法求两个正整数的最大公约数:大除小余 换大辗转除何时停0或11互质0除数即答案2.辗转相除法1.短除法二、求最大公约数的方法3.更 相减损术参:课本P:34参:课本P:34参:课本P:36练习5.更相减损术求两个正整数的最大公约数:(1) 课本P:36例1……98与63……(1)由于63不是偶数,不可半;但98是偶数,可半呢;实际上可半时也可不半,只不 过操作量大一些而已大减小差换大连续减何时停两相等即答案若可半可省功98-63=35故最大公约数为714- 7=763-35=2835-28=728-7=2121-7=1463-49=14故最大公约数为714-7=749 -14=3535-14=2121-14=7将98半之;即求63与49的…大减小差换大连续减何时停两相等即答案 若可半可省功练习5.更相减损术求两个正整数的最大公约数:(2)课本P:45练习1大减小差换大连续减何时停两相 等即答案若可半可省功注:辗转相除法与更相减损术的异同点1.辗转相除法以除法运算为主3.两法本质上都是递推,都可用循环结 构编程更相减损术以减法运算为主2.辗转相除法当除法运算余数为O或1时终止运算更相减损术当减法运算差为O时终止运算(1) 、算法步骤:第一步:输入两个正整数m,n(m>n).第二步:计算m除以n所得的余数r.第三步:m=n,n=r.第四步:若r =0,则m,n的最大公约数等于m;否则转到第二步.第五步:输出最大公约数m.三、编程练习 6(1)课本P:35思考(2)、程序框图:开始输入m,nr=mMODnm=nr=0?是否 n=r输出m结束(3)、程序:INPUT“m,n=“;m,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND |
|