算法案例
教学目标：1理解算法案例的算法步骤和程序框图2引导学生得出自己设计的算法程序3体会算法的基本思想提高逻辑思维能力发展有条理地思考与数学表达能力
教学重点：引导学生得出自己设计的算法步骤、程序框图和算法程序
教学难点：体会算法的基本思想提高逻辑思维能力发展有条理地思考与数学表达能力
教学过程：一、引入
前面我们学习了算法步骤、程序框图和算法语句今天我们将通过学习辗转相除法与更项减损术秦九韶算法排序进位制等案例来进一步体会算法的思想二、讲授新课一辗转相除法与更相减损术1短除法
求两个正整数的最大公约数的步骤先用两个数公有的质因数连续去除一直除到所有的商是两个互质的数为止然后把所有的处暑连乘起来2穷举法也叫枚举法
穷举法求两个正整数的最大公约数的解题步骤从两个较小的数开始由大到小列举直到找到公约数立即中断列举得到的公约数便是最大公约数3辗转相除法
1辗转相除法该算法又称欧几里得算法就是对于给定的两个正整数用较大的数除以较小的数若余数不为零则将余数和较小的数构成一对新数继续上面的除法直到余数为零此时处暑就是所求两正整数的最大公约数
2算法步骤以求正整数m
的最大公约数为例第一步输入两个正整数m
第二步判断m
的大小让m表示较大的数
表示较小的数第三步计算m除以
的余数第四步让m
r第五步如果r0则m
的最大公约数等于m否则返回第三步
3程序框图为略
f4程序1为INPUT“m
”m
IFm
THENtmm
tENDIFDOrmMOD
m
rLOOPUNTILr0PRINTmEND
程序2为INPUT“m
”m
IFm
THEN
tmm
tENDIFr1WHILEr0rmMOD
m
rWENDPRINTmEND
f4更项减损术1更项减损术我国早期也有解决求最大公约数问题的算法就是更相减损术《九
章算术》是中国古代的数学专著其中的“更相减损术”也可以来用来求两个数的最大公约数即“可半者半之不可半者副置分母、子子之数以少减多更相减损求其等也以等数约之”
2算法步骤
第一步任意给定两个正整数判断它们是否都是偶数若是用2约简之若不是
执行第二步第二步以较大的数减去较小的数接着把所得的差与较小的数比较并以大数
减去小数继续这个操作直到所得的数相等为止则这个数等数或这个数与约简数的乘积就是所求的最大公约数3程序框图为略4程序为INPUT“m
”m
IFm
THENtmm
tENDIFk0WHILEmMOD20AND
MOD20mm2
2kk1WENDdm
WHILEd
IFd
THENmdELSEm
dr