《《算法案例ppt》ppt课件》由会员分享，可在线阅读，更多相关《《算法案例ppt》ppt课件（69页珍藏版）》请在金锄头文库上搜索。
1、1.3算法案例1.3算法案例1.3.1辗转相除法和更相减损术123.2秦九韶算法1.3.3k进制化十进制1.3.4十进制化k进制1.3.1辗转相除法和更相减损术复习1.研究一个实际问题的算法,主要从哪几方面展开?算法步骤、程序框图和编写程序三方面展开.2.在程序框囹中算法的基本逻辑结构有哪几种?顺序结构、条件结构、循环结构3.在程序设计中基本的算法语句有哪几种?输入语句、输出语句、赋值语句、条件语句、循环语句情境创设。韩信是秦未汉初的著名军事家.据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什么方法,不要逐个报数,就能知道场上的士兵的人数,韩信先后士兵排成3列纵队,结果有2人多余,
2、接着下金排成5列纵队,结果又多出3人,随后他又下令改为7列纵队这次又剩下2人无法成整行.在场的人都哈帕八吴以为韩信不能清点出准确的人数,不料笑声刚落,韩信高声报告共有士兵2333人.众人吻了一楞,不知道韩信用什么方法这么快就能得到正确的结果的.今天,我们将以这些古典案例的思想,设计出适宜计算机的运行程序,提高我们对基本算法结构和算法语句在实际中的运用能力.探究一,槌转相除法思考1:在小学中我们是如何求出两个正整数的最大公约数的呢?例、求18与24的最大公约数:解:218“24_用公有质因数2除,口不3【9_12用公有质因数3除,短除法3|ii4一3和4互质不阿了得:18和24最大公约数是:2X
3、3一6求以下几组正整数的最大公约数。(注:若整数m和n满足n整除m,则Cm,n=n。用(m,n)来表示m和n的最大公约数。)(1)(C18,30)6:;(2)(24,16)8(3)(63,63)63;(4)(72,88:(5)(301,133)7;想一想,如何求8251与6105的最大公约数?思考2:对于8251与6105这两个数,它们的最大公约数是多少?你是怎样得到的?由于它们公有的质因数较大,利用上选方法求最大公约数就比较困难.有没有其它的方法可以较简单的找出它们的最大公约数呢?思考3:注意到8251=6105X1+2146,那么8251与6105这两个数的公约数和6105与2146的公约
4、数有什么关系?我们发现6105=2146X2+1813,同理,6105与2146的公约数和2146与1813的公约数相等.思考4:重复上述操作,你能得到8251与6105这两个数的最大公约数团?8251=6105X1+2146,“1813=333X5+1486105=2146X2+1813,“333=148X24+37,2146=1813X1+333,“148=37X4+0.定义:所谓的辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,继续上面的除法,目到大数被小数除尽,则这是较小的数就是原来两个数的最大公约精思考4:辗转相除直到何时结束?主要运用的是哪种算法结构?辗转相除法是一个反复执行直到余数等于0停止的步骤,这实际上是一个循环结构辗转相除法求两个数的最大公约数,其算法可以描述如下:D输入两个正整数m和nt;求余数r:计算m除以n,将所得余数存放到变量r中;更新被除数和余数:mzn,nzr,判断余数r是否为0:若余数为0则输出结果,否则转向第)步继续循环执行。如此循环,直到得到结果。思考5:你能把辗转相除法编成一个计算机程序吗?第一步,给定两个正整数m,n(mn).第二步,计算mn除以n所得的余数r.第三步,mzn,n=r.第四步,芊r=0,则m,n的内大公约数等于m;否则,返回第二步.
