算法案例.ppt
《算法案例.ppt》由会员分享,可在线阅读,更多相关《算法案例.ppt(18页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、算算 法法 案案 例例(第一课时)1. 回顾算法的三种表述:回顾算法的三种表述:自然语言自然语言程序框图程序框图程序语言程序语言(三种逻辑结构)(三种逻辑结构)(五种基本语句)(五种基本语句)2. 思考:思考: 小学学过的求两个数最大公约数的方法?小学学过的求两个数最大公约数的方法? 先用两个公有的质因数连续去除,一直先用两个公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除到所得的商是互质数为止,然后把所有的除数连乘起来除数连乘起来.1、求两个正整数的最大公约数、求两个正整数的最大公约数(1)求)求25和和35的最大公约数的最大公约数(2)求)求49和和63的最大公约数的最大
2、公约数25(1) 5535749(2) 77639所以,所以,25和和35的最大公约数为的最大公约数为5所以,所以,49和和63的最大公约数为的最大公约数为72、除了用这种方法外还有没有其它方法?、除了用这种方法外还有没有其它方法?算出算出8256和和6105的最大公约数的最大公约数. 辗转相除法(欧几里得算法)辗转相除法(欧几里得算法)观察用辗转相除法求观察用辗转相除法求8251和和6105的最大公约数的过程的最大公约数的过程 第一步第一步 用两数中较大的数除以较小的数,求得商和余数用两数中较大的数除以较小的数,求得商和余数8251=61051+2146结论:结论: 8251和和6105的公
3、约数就是的公约数就是6105和和2146的公约数,求的公约数,求8251和和6105的最大公约数,只要求出的最大公约数,只要求出6105和和2146的公约数就可以了。的公约数就可以了。第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大公约数。的最大公约数。 完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0例例2 用辗转相除法求用辗转
4、相除法求225和和135的最大公约数的最大公约数225=1351+90135=901+4590=452显然显然37是是148和和37的最大公约数,的最大公约数,也就是也就是8251和和6105的最大公约的最大公约数数 显然显然45是是90和和45的最大公约数,也就是的最大公约数,也就是225和和135的最大公约数的最大公约数 思考思考1:从上面的两个例子可以看出计算:从上面的两个例子可以看出计算的规律是什么?的规律是什么? S1:用大数除以小数:用大数除以小数S2:除数变成被除数,余数变成除数:除数变成被除数,余数变成除数S3:重复:重复S1,直到余数为,直到余数为0 辗转相除法是一个反复执行
5、直到余数等于辗转相除法是一个反复执行直到余数等于0停止的步骤,这实际上是停止的步骤,这实际上是一个循环结构。一个循环结构。8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框图表示出右边的过程用程序框图表示出右边的过程r=m MOD nm = nn = rr=0?是否1 1、辗转相除法(欧几里得算法)、辗转相除法(欧几里得算法)(1)算理:所谓辗转相除法,就是对于给定)算理:所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数。若余的两个数,用较大的数除以
6、较小的数。若余数不为零,则将余数和较小的数构成新的一数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除对数,继续上面的除法,直到大数被小数除尽,则这时较小的数就是原来两个数的最大尽,则这时较小的数就是原来两个数的最大公约数。公约数。(2 2)算法步骤)算法步骤第一步:输入两个正整数第一步:输入两个正整数m,n(mn).第二步:计算第二步:计算m除以除以n所得的余数所得的余数r.第三步:第三步:m=n,n=r.第四步:若第四步:若r0,则则m,n的最大公约数等于的最大公约数等于m; 否则转到第二步否则转到第二步. 第五步:输出最大公约数第五步:输出最大公约数m.(3 3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 案例
限制150内