最新1.3算法案例课件ppt.ppt

《最新1.3算法案例课件ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.3算法案例1.3算法案例知识要点辗转相除法（欧几里得算法）：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。程序框图开始输入m,nr=mMODnm=nr=0?是否n=r输出m结束程序INPUT“m,n=“;m,nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND《九章算术》——更相减损术算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。第一步：任意给定

2、两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。知识要点更相减损术所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。用更相减损术求98与63的最大公约数。解析：由于63不是偶数，把98和63以大数减小数，并辗转相减。按照算法步骤来求

3、解！=7所以，98和63的最大公约数等于7。（98，63）=（63，35）98-63=3563-35=28=（35，28）35-28=7=（28，7）28-7=21=（21，7）21-7=14=（14，7）14-7=7=（7，7）解：更相减损术算法描述：第一步：输入两个正整数a,b(a>b);第二步：若a不等于b,则执行第三步；否则转到第五步；第三步：把a-b的差赋予r;第四步：如果b>r,那么把b赋给a,把r赋给b;否则把r赋给a，执行第二步；第五步：输出最大公约数b。算法步骤！a=r开始输入a,ba≠b?是否输出b结束b=ra=br=a-br

4、否是程序框图程序INPUT“a,b=“;a,bWHILEa<>br=a-bIFb>rTHENa=bb=rELSEa=rENDIFWENDPRINTbEND知识要点秦九韶算法所谓秦九韶算法，就是求一个n次多项式的值的方法。要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即这种将求一个n次多项式f（x）的值转化成求n个一次多项式的值的方法，称为秦九韶算法。例2已知一个五次多项式为用秦九韶算法求这个多项式当x=5的值。解：将多项式变形：按由里到外的顺序，依此计算一次多项式当x=5时的值：所以，当x=5时，多项式的值等于

5、17255.2你从中看到了怎样的规律？怎么用程序框图来描述呢？算法步骤：第一步：输入多项式次数n、最高次项的系数an和x的值。第二步：将v的值初始化为an，将i的值初始化为1。第三步：输入i次项的系数an-i。第四步：v=vx+an-i,i=i+1。第五步：判断i是否小于或等于n，若是，则返回第三步；否则，输出多项式的值v。开始输入f(x)的系数：a0、a1、a2、a3、a4、a5输入x0n=0v=a5v=v·x0+a5-nn=n+1n<5?输出v结束否是进位制是人们为了计数和运算方便而约定的计数系统。比如：满二进一，就是二进制；满十进一，就是十进制；

6、满十二进一，就是十二进制；满六十进一，就是六十进制“满几进一”就是几进制，几进制的基数就是几。进位制与基数：一般地，若k是一个大于1的整数，那么以k为基数的k进制可以表示为一串数字连写在一起的形式：总结七进制的13，写成13(7)；二进制的10，写成10(2)例如：其它进制数化成十进制数公式方法二进制：二进制数与十进制数的转换：提示在电子计算机中，数是以二进制的形式表示的。二进制数每个数位只可能取两个不同的数码，0和1。把二进制数110011（2）化为十进制数。=51（1）二进制数化为十进制数：上述方法可以推广为把k进制数化为十进制数的算法。（2）十进

7、制数化为二进制数：把89化为二进制数。8944221152102222222余数1011100把上式各步所得的余数从下到上排列，得到89=1011001（2）除2取余法可以推广为把十进制数化为k进制数的算法，称为除k取余法。解：1.辗转相除法与更相减损法：（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0而得到，而更相减损术则以减数与差相等而得到的。课堂小结2.秦九韶算法计算多

8、项式的值及程序设计；3.数字排序法中的常见的两种排序法直接插入排序法与冒泡排序法；4.冒泡法排