算法案例 辗转相除法 更相减损术 秦九韶算法 进位制
算法案例 • 辗转相除法 • 更相减损术 • 秦九韶算法 • 进位制
辗转相除法
辗转相除法
求两个正整数的最大公约数 (1)求25和35的最大公约数 (2)求49和63的最大公约数 (1)52535 5 所以,25和35的最大公约数为5 2、求8251和6105的最大公约数
1、求两个正整数的最大公约数 （1）求25和35的最大公约数 （2）求49和63的最大公约数 2、求8251和6105的最大公约数 （1） 5 25 5 35 7 所以，25和35的最大公约数为5
辗转相除法(欧几里得算法) 观察用辗转相除法求8251和6105的最大公约数的过程 第一步用两数中较大的数除以较小的数,求得商和余数 8251=6105×1+2146 结论:8251和6105的公约数就是6105和2146的公约数,求8251和6105 的最大公约数,只要求出6105和2146的公约数就可以了 为什么呢? 第二步对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公约数
辗转相除法（欧几里得算法） 观察用辗转相除法求8251和6105的最大公约数的过程 第一步用两数中较大的数除以较小的数，求得商和余数 8251=6105×1+2146 结论：8251和6105的公约数就是6105和2146的公约数，求8251和6105 的最大公约数，只要求出6105和2146的公约数就可以了。 第二步对6105和2146重复第一步的做法 6105=2146×2+1813 同理6105和2146的最大公约数也是2146和1813的最大公约数
完整的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 思考1:从上面的两个例子可以看出计 算的规律是什么? 148=37×4+0 s:用大数除以小数 显然37是148和37的最大公约s2:除数变成被除数,余数变成除数 数,也就是8251和6105的最大 公约数 s3:重复1,直到余数为0
完整的过程 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 显然37是148和37的最大公约 数，也就是8251和6105的最大 公约数 思考1：从上面的两个例子可以看出计 算的规律是什么？ S1：用大数除以小数 S2：除数变成被除数，余数变成除数 S3：重复S1，直到余数为0
思构A氯湘除法中天是顺题装构 辗转相除法是一个反复执行直到余数等于0停止 的步骤,这实际上是一个循环结构。m=n×q+r 用程序框图表示出右边的过程8251-6105×1+2146 r=m mod n 6105=2146×2+1813 m=n 2146=1813×1+333 n=r 1813=333×5+148 ? 否 是 333=148×2+3 148=37×4+0
辗转相除法是一个反复执行直到余数等于0停止 的步骤，这实际上是一个循环结构。 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 m = n × q ＋ r 用程序框图表示出右边的过程 r=m MOD n m = n n = r r=0? 是 否
《九章算术》一一更相减损术 算理:可半者半之,不可半者,副置分母、子之数, 以少减多,更相减损,求其等也,以等数约之 第一步:任意给顶两个正整数;判断他们是否都是 偶数。若是,则用2约简;若不是则执行第二步。 第二步:以较大的数减较小的数,接着把所得的差 与较小的数比较,并以大数减小数。继续这个操作, 直到所得的减数和差相等为止,则这个等数就是所 求的最大公约数
《九章算术》——更相减损术 算理：可半者半之，不可半者，副置分母、子之数， 以少减多，更相减损，求其等也，以等数约之。 第一步：任意给顶两个正整数；判断他们是否都是 偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差 与较小的数比较，并以大数减小数。继续这个操作， 直到所得的减数和差相等为止，则这个等数就是所 求的最大公约数
例3用更相减损术求98与63的最大公约数 解:由于63不是偶数,把9和63 以大数减小数,并辗转相减 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以,98和63的最大公约数等于7
例3 用更相减损术求98与63的最大公约数 解：由于63不是偶数，把98和63 以大数减小数，并辗转相减 98－63＝35 63－35＝28 35－28＝7 28－7＝21 21－7＝14 14－7＝7 所以，98和63的最大公约数等于7
秦九韶算法 求多项式(x)=2x55x44X3+3x2-6x+7当 X=5时的值。 这种算法用了几次乘法?几次加法? 一共做了15次乘法5次加法 优点是简单易懂;缺点是不通用不能 解决任意多项多求值问题而且计算效率不高
这种算法用了几次乘法？几次加法？
能否探索更好的算法 f(x)=2X554x3+3x2-6X+70 V1=VnX5=2×55=5 =(2X4.5X4X2+3x-6)x+7 =V1X-4=5×5-4=21 =(2x3-5x24X+3)X-6)x+7 V2=V2X+3=21×5+3=108 =(2x25X-4)x+3)X-6)X+7 V4=V3x-6=108×56=534 =(2X×-5)X4)X+3)x-6)X+7 5=V4X+7=534×5+7=2677 这种算法用了几次乘法?几次加法? 5次乘法,5次加法
这种算法用了几次乘法？几次加法？ 5次乘法，5次加法