还剩6页未读,继续阅读
文本内容:
2019-2020年高中数学
1.4算法案例第2课时教案(苏教版必修3)重点难点重点通过案例分析理解辗转相除法与更相减损术求最大公约数的方法,体会算法思想.难点把辗转相除法与更相减损术的方法转换成程序框图与程序语言.学习要求1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析.2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.【课堂互动】问题写出求两个正整数abab的最大公约数的一个算法
1.辗转相除法公元前3世纪,欧几里得介绍了求两个正整数abab的最大公约数的方法,求出一列数,这列数从第三项开始,每一项都是前两项相除所得的余数(即),余数等于0的前一项,即是a和b的最大公约数,这种方法称为“欧几里得辗转相除法”例1求两个正数8251和6105的最大公约数.(分析8251与6105两数都比较大,而且没有明显的公约数,如能把它们都变小一点,根据已有的知识即可求出最大公约数)【解】8251=6105×1+2146显然8251和的2146最大公约数也必是2146的约数,同样6105与2146的公约数也必是8251的约数,所以8251与6105的最大公约数也是6105与2146的最大公约数.6105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0则37为8251与6105的最大公约数.【小结】以上我们求最大公约数的方法就是欧几里得辗转相除法.其求最大公约数的步骤如下第一步用较大的数除以较小的数得到一个商和一个余数;[来源:..K]第二步若,则为的最大公约数;若,则用除数除以余数得到一个商和一个余数;第三步若,则为的最大公约数;若,则用除数除以余数得到一个商和一个余数;……依次计算直至,此时所得到的即为所求的最大公约数.【练习】求a=204,b=85的最大公约数,步骤为S1204÷85的余数为34,S285÷34的余数为17,S334÷17的余数为0所以它们的最大公约数为17算法描述计算出a÷b的余数r,若r=0,则b为a,b的最大公约数;若r≠0,则把前面的除数b作为新的被除数,把余数r作为新的除数(a,b要重新赋值,a←b,b←r),继续进行上述运算,直到余数为0用While循环语句,循环的执行条件是r≠0,当r=0时,循环终止,此时的除数即为所求的最大公约数算法如下:S1输入两个正整数abab;S2若Moda,b=0,则转S3;否则,r←Modab,a←b,b←r,转S2S3输出最大公约数b.【流程图】[来源:shulihua.netZ#X#X#K][来.om]【伪代码】
2.更相减损法[]我国早期也有解决求最大公约数问题的算法,就是更相减损术.[来源:Zxxk]更相减损术求最大公约数的步骤如下可半者半之,不可半者,副置分母之数,以少减多,更相减损,求其等也,以等数约之.[来.om]翻译出来为第一步任意给出两个正数判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.第二步以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数.继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数.再从这个角度看一下“求a=204,b=85的最大公约数”的问题,S1步可以等价为等式S2步可以等价为等式这两步从减法的角度可以理解为204-85,所得的差与减式中的较小数比较,再用大的数减小的数,循环执行以上步骤直到结果为0此时减数就是a和b的最大公约数这一算法根据它的特点,也可以用循环语句完成参考代码/a放较大的数,b放较小的数IfabThenm←aa←bb←m/交换a,b中的数EndIf/确保a是a,b中较大的数r←a–b/两数相减Whiler≠0IfbrThena←bb←rElsea←r[来.om]EndIfr←a–b/确保相减后仍用较大的数减去较小的数EndWhilePrintb用“更相减损法”求多于两个数的最大公约数就可以显示出其优越性【小结】比较辗转相除法与更相减损术的区别
(1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显.
(2)从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术则以减数与差相等而得到.【追踪训练】
1.分析下面一段代码的目的ReadmnWhilem/n≠Intm/nc←m-Intm/n×nm←nn←cEndWhilePrintnIntx表示不超过x的最大整数【解】求m,n的最大公约数
2.用辗转相除法求下列各组数的最大公约数
(1)225135;
(2)
98196.
3.用更相减损法求下列各组数的最大公约数
(31)72168;
(2)
153119.
4.现有长度为360cm和780cm两种规格的钢筋若干.要焊接一批正方形模型.问:怎样才能保证正方体体积最大且不浪费思路点拨:正方体的所有棱长都相等故必须将钢筋剪裁成长度相等的钢筋条;又必须不浪费这就说明必须剪后无剩余.于是为了保证正方体的体积最大故剪的钢筋的最大长度为360cm和780cm的最大公约数可用更相减损术求最大公约数.[.XK]第11课时算法案例2分层训练
1、阅读下列代码,写出该代码的运行结果t←1n←3s←0Whiles10t←t×ns←s+tEndWhile[来源:.]Prints答[来源:学*科*网]
2、设计一个计算1×3×5×7×9的算法.下面给出了程序的一部分,则在横线上不能填入下面数据中的S←lI←3WhileIS←S×II←I+2End.lePrintSA.9B.9.5C.10D.
10.
53、下列一段伪代码执行结束后S的目的是S←0a←lForIFromlTo4a←2aS←S+aEndForA.计算2+22+23+24B.计算2+22+23C.计算23D.计算
244.先用不同的算法计算,再比较其优劣
5.已知△ABC中,试写出作△ABC的一个算法
6.用条件语句表示输入x的值,通过计算y的值
7.写出求中最大数的一个算法
8、一球从l00m高度落下,每次落地后反弹回原高度的一半,再落下,在第十次落地时,共经过多少路程第十次下落多高思考运用
9.我国古代劳动人民对不定方程的研究作出过重要贡献,其中《张丘建算经》中的百鸡问题就是一个很有影响力的问题“今有鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一凡百钱买百鸡,问鸡翁、母、雏各几何?”其意思是一只公鸡的价钱是五钱,一只母鸡的价钱是三钱,三只小鸡的价钱是一钱现在用一百钱买一百鸡,可以买公鸡、母鸡、小鸡各几个?这是一个不定方程的整数解问题,假设公鸡x只,母鸡y只,小鸡z只,首先,可以大致得到x在1至20之间,y在1至33之间,z=100-x-y可以确定根据上述算法思想,画出求解的流程图,并写出相应的伪代码开始b←rYN结束输入a,ba←br←ModabModab≠0输出bReadabWhileModab≠0r←Modaba←bb←rEndWhilePrintb。