算法案例ppt课件

方法：,先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来。,求两个数最大公约数的方法？,1,1.3 算法案例,2,知识要点,辗转相除法（欧几里得算法） ：,所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。,3,过程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,显然37是148和37的最大公约数，也就是8251和6105的最大公约数,=37,（8251，6105） =（6105，2146）,=（2146，1813）,=（1813，333）,=（333，148）,=（148，37）,求8251和6105的最大公约数。,4,辗转相除法算法步骤：,第一步：输入两个正整数m,n(mn)； 第二步：计算m除以n所得的余数r； 第三步：m=n,n=r； 第四步：若r0,则m,n的最大公约数等于m； 否则转到第二步； 第五步：输出最大公约数m。,5,辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。,用程序框图表示出过程,6,程序框图,程序,INPUT “m,n=“;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END,7,九章算术更相减损术,算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。,第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。,8,知识要点,更相减损术,所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小的数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。,9,用更相减损术求98与63的最大公约数。,解析：由于63不是偶数，把98和63以大数减小数，并辗转相减。,按照算法步骤来求解！,10,= 7,所以，98和63的最大公约数等于7。,（98，63） =（63，35）,98-63=35,63-35=28,=（35，28）,35-28=7,=（28，7）,28-7=21,=（21，7）,21-7=14,=（14，7）,14-7=7,=（7，7）,解：,11,更相减损术算法描述：,第一步：输入两个正整数a,b(ab); 第二步：若a不等于b ,则执行第三步；否则转 到第五步； 第三步：把a-b的差赋予r; 第四步：如果br, 那么把b赋给a,把r赋给b;否 则把r赋给a，执行第二步； 第五步：输出最大公约数b。,算法步骤！,12,程序框图,程序,INPUT “a,b=“;a,b WHILE ab r=a-b IF br THEN a=b b=r ELSE a=r END IF WEND PRINT b END,13,知识要点,秦九韶算法,所谓秦九韶算法，就是求一个n次多项式的值的方法。,14,要求多项式的值，应该先算最内层的一次多项式的值，即,然后，由内到外逐层计算一次多项式的值，即,这种将求一个n次多项式f（x）的值转化成求n个一次多项式的值的方法，称为秦九韶算法。,15,例2 已知一个五次多项式为,用秦九韶算法求这个多项式当x = 5的值。,解：,将多项式变形：,按由里到外的顺序，依此计算一次多项式当x = 5时的值：,所以，当x = 5时，多项式的值等于17255.2,你从中看到了怎样的规律？怎么用程序框图来描述呢？,16,算法步骤：,第一步：输入多项式次数n、最高次项的系数an和x的值。,第二步：将v的值初始化为an，将i的值初始化为1。,第三步：输入i次项的系数an-i。,第四步：v=vx +an-i, i=i+1。,第五步：判断i是否小于或等于n，若是，则返回第三步；否则，输出多项式的值v。,17,开始,输入f (x)的系数： a0、a1、a2、a3、a4、a5,输入x0,n=0,v=a5,v= vx0+a5-n,n=n+1,n 5?,输出v,结束,否,是,18,进位制是人们为了计数和运算方便而约定的计数系统。,比如：,满二进一，就是二进制； 满十进一，就是十进制； 满十二进一，就是十二进制； 满六十进一，就是六十进制,“满几进一”就是几进制，几进制的基数就是几。,进位制与基数：,19,一般地，若k是一个大于1的整数，那么以k 为基数的k进制可以表示为一串数字连写在一起 的形式：,总结,七进制的13，写成13(7)；二进制的10，写成10(2),例如：,20,其它进制数化成十进制数公式,方法,21,二进制：,二进制数与十进制数的转换：,提示,在电子计算机中，数是以二进制的形式表示的。二进制数每个数位只可能取两个不同的数码，0和1。,22,把二进制数110011（2）化为十进制数。,=51,（1）二进制数化为十进制数：,上述方法可以推广为把k进制数化为十进制数的算法。,23,（2）十进制数化为二进制数：,把89化为二进制数。,把上式各步所得的余数 从下到上排列， 得到89=1011001（2）,除2取余法,可以推广为把十进制数化为k进制数的算法，称为除k取余法。,解：,24,1.辗转相除法与更相减损法： （1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。 （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0而得到，而更相减损术则以减数与差相等而得到的。,25,2.秦九韶算法计算多项式的值及程序设计； 3.数字排序法中的常见的两种排序法直接插入排序法与冒泡排序法； 4.冒泡法排序的计算机程序设计； 5.注意循环语句的使用与算法的循环次数，对算法进行改进。,26,1(2009年广东卷文)某篮球队6名主力队员在最近三场比赛中投进的三分球个数如下表所示：,下图（右）是统计该6名队员在最近三场比赛中投进的三分球总数的程序框图，则图中判断框应填 ，输出的s=_ 。 (注：框图中的赋值符号“=”也可以写成“”或“：=”),27,答案: i6, a1+a2+a3+ +a6,解析: 顺为是统计该6名队员在最近三场比赛中投进的三分球总数的程序框图，所图中判断框应填i6,输出s=a1+a2+a3+ +a6。,28,29,2(2009山东卷理)执行右边的程序框图，输出的T=_。,30,30,按照程序框图依次执行为S=5,n=2,T=2; S=10,n=4,T=2+4=6;S=15,n=6,T=6+6=12; S=20,n=8,T=12+8=20;S=25,n=10,T=20+10=30S,输出T=30。,解析:,31,1.用更相减损术求下列两数的最大公约数： （1）（225，135） （2）（98，196） （3）（72，168） （4）（153，119）,45,98,24,17,32,2设计利用秦九韶算法计算5次多项式,当,时的值程序和的程序框图。,解：,INPUT “a1,a2,a3,a4,a5=”;a1,a2,a3,a4,a5 INPUT “x0=”;x0 n=1 v=a5 IF n=5 THEN n=n+1 v=x0 +a5-n PRINT “v=”;v END IF END,33,程序框图：,34,1.(1) 45 ; (2) 98 ; (3) 24 ; (4) 17 ； 2. 2881.75； 3.略； 4.略。,练习1.3（第36页）,35,36,