资源描述
1.3算法案例,第一课时,问题提出,1.研究一个实际问题的算法,主要从算法步骤、程序框图和编写程序三方面展开.在程序框图中算法的基本逻辑结构有哪几种?在程序设计中基本的算法语句有哪几种?,2.“求两个正整数的最大公约数”是数学中的一个基础性问题,它有各种解决办法,我们以此为案例,对该问题的算法作一些探究.,辗转相除法与更相减损术,复习引入,1、MOD表示什么意思?aMODbab(ab是正整数),a=b*q+r,(0n,若m-n=k,则m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理,可求得98与63的最大公约数为多少?,98-63=35,,14-7=7.,21-7=14,,28-7=21,,35-28=7,,63-35=28,,二、更相减损术,可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也,以等数约之。,第一步:任意给定两个正整数;判断他们是否都是偶数。若是,则用2约简;若不是则执行第二步。,第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止,则这个等数就是所求的最大公约数。,(1)、九章算术中的更相减损术:,(2)、现代数学中的更相减损术:,1、用更相减损术求两个正数84与72的最大公约数,练习:,思路分析:先约简,再求21与18的最大公约数,然后乘以两次约简的质因数4。,2、求324、243、135这三个数的最大公约数。,思路分析:求三个数的最大公约数可以先求出两个数的最大公约数,第三个数与前两个数的最大公约数的最大公约数即为所求。,比较辗转相除法与更相减损术的区别(1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显。(2)从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术则以减数与差相等而得到。,小结,思考题,1、用当型循环结构写出算法;2、试写出更相减损术的算法程序;3、试写出求两个正整数m、n的最小公倍数的程序。,评价一个算法好坏的一个重要标志是运算的次数,如果一个算法从理论上需要超出计算机允许范围内的运算次数,那么这样的算法就只能是一个理论算法.在多项式求值的各种算法中,秦九韶算法是一个优秀算法.,
展开阅读全文