14算法案例.ppt

1、1.4算法案例,在我国古代算书孙子算经中有这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”,分别写出除数3、5、7的两两公倍数.,意思是，“一个数除以3余2，除以5余3，除以7余2.求适合这个条件的最小数.”这个问题称为“孙子问题”.,一个正整数m什么时候满足方程？,如何依次检索正整数？,该循环何时结束？,如何用自然语言描述该算法？,int(x)表示不超过x的最大整数，例如int(2.7)=2， Int(2)=2，int(2.7)3.,mod(a,b)表示a除以b的余数.,m 2 While Mod (m,3)2 Or Mod (m,5)3 Or Mod

2、(m,7)2 m m1 End While Print m,VBA程序中使用了符号“_”表示下一行和该行是一个完整的语句,Mod (m,3)在VBA中用m Mod 3表示,3 5,9 15,在小学，我们学过求两个正整数的最大公约数的方法，先用两个数公有的质因数连续去除，一直到所得的商是互质数为止，然后把所以的除数乘起来，例如，求18与30的最大共约数：,18 30,2,3,所以，18与30的最大共约数是：23=6.,利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数？,观察上面的式子，

3、你有什么发现？你的发现，对我们解决“求8251与6105的最大公约数”的问题有什么帮助？,8251610512146;,6105214621813;,214618131333;,333148237;,1483740.,练习1：利用辗转相除法求两数4081与20723的最大公约数.,(53),20723=40815+318; 4081=31812+265; 318=2651+53; 265=535+0.,例2 写出求两个正整数a,b(ab)的最大公约数的一个算法.,欧几里得辗转相除法找出a,b的最大公约数的步骤是: 计算ab的余数r,若r=0,则b为a,b的最大公约数;

4、 若r0,则把前面的除数b作为新的被除数,把r作为新的除数,继续运算,直到余数为0,此时的除数即为a,b的最大公约数.,如求a=204,b=85的最大公约数.,20485,余数为r1=34,即204=852+34,8534,余数为r2=17,即85=342+17,3417,余数为r3=0,即34=172,因此,204与85的最大公约数为17,以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.,请用自然语言描述该算法!,S1 输入两个正整数a,b（ab）； S2 若Mod（a,b）0，则输出最大公约数b，算法结束； 否则r Mod（a,b）

5、，a b，br，转S2,S1 输入两个正整数a，b（ab）； S2 r Mod（a,b） S3 a b S4 br， S5 若r不等于0，转S2 S6 输出最大公约数a,.,.,比较当型循环和直到型循环，说说各自的优点和缺点！,问题： 用二分法求方程x22x10的近似解（精确到0.1）,首先画出函数f(x)x22x1的图象，从图象上可以发现： 方程x22x10的一个根x1在区间(1，0)内，另一个根x2在区间(2，3)内,据函数图象，我们发现： f(2)10，即f(2)f(3)0，即f(2)f(2.5)0， 故近似解在区间(2，2.5)内,通过依次取区间中点的方法，将根所在的区间逐步缩小，并列

6、出表格：,直到区间两个端点值精确到0.1时的近似值都是2.4，所以方程的一个近似解为2.4,注：由于确定近似值的方法不太方便，因此用计算机实现二分法时，常常不是给出精度，而是给出误差范围！,问题：如果方程f(x)0在某区间a，b内有一个根，如何利用二分 法搜索符合误差限制c的近似解？,S1 取a，b的中点 x0 ，将区间一分为二；,S2 若f(x0)0，则x0就是方程的根，转S4, 否则当f(a)f(x0)0，则x(a, x0)，用x0代替b, 否则用x0代替a；,S3 若|ab|不小于c，转S1；,S4 输出x0 .,例3：写出用区间二分法求方程x3x10在区间1,1.5内的一个近似解（误差

7、不超过 0.001）的一个算法,a1 b1.5 c0.001 Do x0(ab)/2 f(a)a3a1 f(x0)x03x01 If f(x0)0 Then Exit Do If f(a)f(x0) 0 Then bx0 Else ax0 End If Until |ab|c Print x0,Print x0,例 编写一个求 的近似值的算法，要求精确度不超过0.0001，写出其伪代码.,a1 b2 c0.0001 Do x0(ab)/2 f(a)a23 f(x0)x023 If f(a)f(x0)0 Then bx0 Else ax0 End If Until |ab|c Print x0,

8、练习 用二分法求解方程,求关于x的方程x220的根，精确到0.005,算法描述,第一步 令f(x)=x2-2，因为f(1)0，所以设x1=1，x2=2,第二步 令m=(x1+x2)/2，判断f(m)是否为0，若是，则m为所求，否则，则继续判断f(x1)f(m)大于0还是小于0。,第三步 若f(x1)f(m) 0则令x1=m，否则x2=m。,第四步 判断|x1-x2|0.005是否成立？若是则x1、x2之间的任意值均为满足条件的近似值；否则返回第二步。,流程图表示,1.辗转相除法:,例1 求两个正数8251和6105的最大公约数。,分析：8251与6105两数都比较大，而且没有明显的公约数，如能

9、把它们都变小一点，根据已有的知识即可求出最大公约数.,解：8251610512146,显然8251与6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。,研探新知,1.辗转相除法:,例1 求两个正数8251和6105的最大公约数。,解：8251610512146;,6105214621813; 214618131333; 333148237; 1483740.,则37为8251与6105的最大公约数。,以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算

10、法，它是由欧几里德在公元前300年左右首先提出的。,利用辗转相除法求最大公约数的步骤如下：,第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；(m=nq0+r0) 第二步：若r00，则n为m，n的最大公约数；若r00，则用除数n除以余数r0得到一个商q1和一个余数r1；(n=r0q1+r1) 第三步：若r10，则r0为m，n的最大公约数；若r10，则用除数r0除以余数r1得到一个商q2和一个余数r2；(r0=r1q2+r2) 依次计算直至rn0，此时所得到的rn-1 即为所求的最大公约数。,3.辗转相除法与更相减损术的比较:,（1）都是求最大公约数的方法，计算上辗转相除法以除法为

11、主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。 （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.,否,4. 辗转相除法的程序框图及程序:,开始,输入两个正数m,n,mn,r=m Mod n,r0,输出n,结束,m=x,m=n,n=r,否,是,是,x=n,n=m,1、求两个正整数的最大公约数,（1）求25和35的最大公约数 （2）求49和63的最大公约数,2、求8251和6105的最大公约数,所以，25和35的最大公约数为5,所以，49和63的最大公约数为7,辗转相除法（欧

12、几里得算法）,观察用辗转相除法求8251和6105的最大公约数的过程,第一步 用两数中较大的数除以较小的数，求得商和余数8251=61051+2146,结论： 8251和6105的公约数就是6105和2146的公约数，求8251和6105的最大公约数，只要求出6105和2146的公约数就可以了。,第二步 对6105和2146重复第一步的做法6105=21462+1813同理6105和2146的最大公约数也是2146和1813的最大公约数。,为什么呢？,思考：从上述的过程你体会到了什么？,完整的过程,8251=61051+2146,6105=21462+1813,2146=18131+333,1

13、813=3335+148,333=1482+37,148=374+0,例2 用辗转相除法求225和135的最大公约数,225=1351+90,135=901+45,90=452,显然37是148和37的最大公约数，也就是8251和6105的最大公约数,显然45是90和45的最大公约数，也就是225和135的最大公约数,思考1：从上面的两个例子可以看出计算的规律是什么？,S1：用大数除以小数,S2：除数变成被除数，余数变成除数,S3：重复S1，直到余数为0,辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。,m = n q r,用程序框图表示出右边的过程,r=m Mod

14、n,m = n,n = r,r=0,是,否,思考2：辗转相除法中的关键步骤是哪种逻辑结构？,九章算术更相减损术,算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,第一步：任意给顶两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。,第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。,例3 用更相减损术求98与63的最大公约数,解：由于63不是偶数，把98和63以大数减小数，并辗转相减,9863356335283528728721 21721 1477,所以，98和63的最大公约数等于7,练习：,课本P36练习第1题,孙子的解法是： 先从3和5、3和7、5和7的公倍数中相应地找出分别被7、5、3除均余1的较小数15、21、70.即 157=2余1， 215=4余1， 703=23余1. 再用找到的三个较小数分别乘以被7、5、3除所得的余数的积连加， 152+213+702=233. 最后用和233除以3、5、7三个除数的最小公倍数. 233105=2余23， 这个余数23就是合乎条件的最小数.,Read a,b i=0 While a/2int(a/2) And b/2i