程序框图 案例

《程序框图 案例》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法案例(一)辗转相除法与更相减损术1.短除法求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所有的商是两个互质的数为止,然后把所有的处暑连乘起来.2.穷举法(也叫枚举法)穷举法求两个正整数的最大公约数的解题步骤:从两个较小的数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数.3.辗转相除法(1)辗转相除法:该算法又称欧几里得算法,就是对于给定的两个正整数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成一对新数,继续上面的除法,直到余数为零,此时处暑就是所求两正整数的最大公约数.(2)算法步骤:以求正整数的最大公约数为例.第

2、一步,输入两个正整数.第二步,判断的大小,让表示较大的数,表示较小的数.第三步,计算除以的余数.第四步,让.第五步,如果,则的最大公约数等于;否则返回第三步.14(3)辗转相除法的程序框图及程序开始Yr=mMODn输出nYN输入两个正整数m,nr=0结束m>nx=nn=mm=xNm=nn=r程序框图：程序：INPUT“m=”;mINPUT“n=”;nIFm>nTHENx=mm=nn=xENDIFr=mMODnWHILEr<>0r=mMODnm=nn=rWENDPRINTnEND1414(4)程序1为:INPUT“m,n=”;m,nIFm

3、MODnm=nn=rLOOPUNTILr=0PRINTmEND程序2为:INPUT“m,n=”;m,nIFm0r=mMODnm=nn=rWENDPRINTmEND144.更项减损术(1)更项减损术:我国早期也有解决求最大公约数问题的算法,就是更相减损术.《九章算术》是中国古代的数学专著,其中的“更相减损术”也可以来用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子子之数,以少减多,更相减损,求其等也.以等数约之.”(2)算法步骤:第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用约简之;若不是,执行第二

4、步.第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减去小数,继续这个操作,直到所得的数相等为止.则这个数(等数)或这个数与约简数的乘积就是所求的最大公约数.(3)程序框图为:略14(4)程序为:INPUT“m,n=”;m,nIFmnIFd>nTHENm=dELSEm=nn=dENDIFd=m-nWENDd=2^k*dPRINTdEND14(二)秦九韶算法1.怎么求多项式当时的值?一个自然的做法是把代入多

5、项式,急速各项的值,然后把它们加起来,这时,我们一共做了次乘法运算,次加法运算.另一种算法是先计算的值,然后计算的值,这样每次都可以利用上一次计算的结构,这时,我们一共做了次乘法运算,次加法运算.第二种做法与第一种做法相比,乘法的运算此时减少了,因而能够提高运算效率,对于计算机来说,做一次乘法运算所用的时间比做一次加法运算要长得多,所以采用第二种算法,计算机能更快地得到结果.2.求多项式的值时,常用秦九韶算法,这种算法的运算次数较少,是多项式求值比较先进的算法,其实质是转化为求个一次多项式的值,共进行次乘法运算和次加法运算.3.秦九韶算法(1)改写多项式:设,,,.(2)算法步骤:第一

6、步,输入多项式次数,最高次项的系数和的值.第二步,.第三步,输入次项的系数.第四步,.第五步,判断是否大于等于,若是,则返回第三步;否则,输出多项式的值.14(3)程序框图为:略(4)程序为:INPUT“n=”;nINPUT“an=”;aINPUT“x=”;xv=ai=n-1WHILEi>=0PRINT“i=”;iINPUT“ai=”;av=v*x+ai=i-1WENDPRINTvEND14(三)进位制算法1.定义:人们为了计数和运算方面而约定的计数系统,“满进一”就是进制,是基数(其中是大于的整数).进制的数可以表示为一串数字连写在一起的形式.2.在日常生活中,我们最熟悉、最常用的是

7、十进制.除此之外还有二进制,七进制,八进制,十二进制,十六进制,六十进制等.3.非十进制的进制数(共有位)化为十进制数的计算公式为:(1)算法步骤:第一步,输入的值.第二步,.第三步,.第四步,判断是否成立,若是,则执行第五步;否则,返回第三步.第五步,输出的值.(2)程序框图为:略(3)程序为:INPUT“a,k,n=”;a,k,nb=0i=1t=aMOD10DOb=b+t*k^(i-1)a=a10t=aMOD10i=i+1LOOPUNTI