算法案例1.3.1算法案例.ppt

文档介绍：,主要从算法步骤、?在程序设计中基本的算法语句有哪几种?2.“求两个正整数的最大公约数”是数学中的一个基础性问题,它有各种解决办法,我们以此为案例,(一):辗转相除法思考1:18与30的最大公约数是多少?你是怎样得到的?先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,:对于8251与6105这两个数,由于其公有的质因数较大,=6105×1+2146,那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系?思考3:又6105=2146×2+1813,同理,,你能得到8251与6105这两个数的最大公约数吗?2146=1813×1+333,148=37×4+=148×2+37,1813=333×5+148,8251=6105×1+2146,6105=2146×2+1813,思考4:,用辗转相除法求两个正整数m,n的最大公约数,可以用什么逻辑结构来构造算法?其算法步骤如何设计?第一步,给定两个正整数m,n(m>n).第二步,,m=n,n=,若r=0,则m,n的最大公约数等 于m;否则,:该算法的程序框图如何表示?开始输入m,n求m除以n的余数rm=nn=rr=0?是输出m结束否思考6:该程序框图对应的程序如何表述?INPUTm,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND开始输入m,n求m除以n的余数rm=nn=rr=0?是输出m结束否思考7:如果用当型循环结构构造算法,则用辗转相除法求两个正整数m,n的最大公约数的程序框图和程序分别如何表示?