数学教材梳理算法案例

学必求其心得，业必贵于专精学必求其心得，业必贵于专精学必求其心得，业必贵于专精庖丁巧解牛知识·巧学1．几个常用函数符号求余函数Mod（m,n)：Mod（m，n）表示取m除以n的余数。如：m被3除余2，可表示为Mod（m,3)=2。取整函数Int（x)：表示取不大于x的最大整数。如：Int(2）=2，Int(2。3)=2,Int(2。6)=2.误区警示不要与四舍五入相混淆Int(-2。3）=—3。可用mInt(m/n）*n表示m除以n的余数,如m被3除余2,可表示为mInt（m/3）＊3=2。2．算法典型案例案例1：韩信点兵——孙子问题《孙子算经》中载有“物不知数"这个问题：今有物不知其数，三三数之剩二;五五数之剩三；七七数之剩二，问物几何？答曰“二十三”。这就是著名的孙子问题（记载于中国古代约公元3世纪成书的《孙子算经》,是原书卷下第26题）。这个问题可以简单地用一句话描述，即“一个正整数，被3，5,7除,余数分别为2，3，2”.设这个数为m，则可列关于x,y,z的方程组表示：联想发散这一类问题的解法可以推广成解一次同余式组的一般方法．秦九韶给出了理论上的证明，并将它定名为“大衍求一术”。这个问题的通用解法称为“中国剩余定理"。秦九韶（公元1202—1261年），南宋数学家，著《数书九章》十八卷．全书共81道题，分为九大类：大衍类、天时类、田域类、测望类、赋役类、钱谷类、营建类、军旅类、市易类。其中对“大衍求一术"（一次同余组解法）和“正负开方术"（高次方程的数值解法)等有十分深入的研究.“大衍求一术”，在世界数学史上占有崇高的地位。计算机解决:从2开始，让m依次去除，直到满足要求为止.这样，只要使用循环，由小到大依次搜索,直到找出满足条件的数即可.流程图如图1-4—1:图1-4-1案例2：辗转相除法求最大公约数辗转相除法又称欧几里得算法，就是对于给定的两个数，用较大的数除以较小的数,若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法,直到余数为零，此时的除数就是所求两数的最大公约数。误区警示这是一个反复执行的步骤,要用循环结构实现.注意循环条件的设置，此处可用直到型循环,条件为r=0，对于循环体部分，需要反复执行的是r=mMODn。要实现上述算法，在重复执行之前,要对m,n的两个变量重新赋值（m=n，n=r)，注意体会理解该递归思想。（1）算法步骤:以求正整数m,n(m＞n）的最大公约数为例。第一步:输入两个正整数m，n(m＞n）;第二步：判断m,n的大小,让m表示较大的数，n表示较小的数；第三步：计算m/n的余数r；第四步：如果r≠0，那么把n赋值给m，把r赋值给n，返回第二步；否则，执行下一步;第五步：输出最大公约数m。（2)流程图如图1-4-2图1—4-2伪代码如下：m←2WhileMod（m,3)≠2或Mod（m，5)≠3或Mod(m,7)≠2m←m+1EndWhilePrintm更相减损术更相减损术是中国古代算书《九章算术》中的一个优秀算法;更相减损术可以求最大公约数：对于给定的两个数，以其中较大的数减去较小的数,然后将差和较小的数构成一对新数，再用较大的数减去较小的数，反复执行以上步骤直到差数与较小的数相等，此时相等的两数即为所求的最大公约数，最后该最大公约数再乘以2即为所求。学法一得所求两数都是偶数时，可先除以2,再求除以2后两数的最大公约数.（1）算法步骤：以求正整数m，n的最大公约数为例，第一步:输入两个正整数m，n（m＞n)；第二步:r←m-n；第三步：如果r<n,那么m←n，n←r，否则，m←r；第四步：如果m≠n，则返回第二步，否则执行下一步；第五步：输出m。(2)程序框图如图1—4—3图1-4-3案例3：二分法求方程近似解二分法是方程求根的一种常用方法,其过程体现的就是算法思想.理论依据：我们知道，若函数f（x）在区间［x1，x2]两端点的函数值异号，即f(x1)f（x2）<0，则在区间[x1，x2］内方程f(x）=0至少有一个根。二分法是说：如果在区间［x1,x2］内f（x)=0仅有一个根x，则可以取x1与x2的中点x3=（x1+x2）/2进行判断，若f(x3)与f(x1)异号，说明有一个根在区间[x1，x3］中,否则在区间［x2,x3］中。然后按上述方法逐渐缩小有根区间,从而逼近方程f（x)=0的根.当有根区间小到一定程度时,把这个区间的中点的x值当作方程的近似根.用二分法设计求方程f(x)=0的近似根算法的基本步骤：（1）确定近似根所在的基础区间[a，b］和近似根的精确度c；(2）求有根区间的中点,判断是否满足精度要求；（3）求区间端点的函数值f（a），f(b）；（4）判断f（a)f(b）的符号，改变有根区间的下限或上限;（5）循环求近似根；（6）输出根的近似值.进位制进位制是一种记数方式,用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制.现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数。对于任何一个数，我们可以用不同的进位制来表示。一般地,若k是一个大于一的整数，那么以k为基数的k进制可以表示为：anan—1…a1a0(k)（0<an<k,0≤an-1，…，a1,a0anan-1…a2a1a0（k）=an×kn+an—1×kn—1+…+a2×k2+a1而表示各种进位制数时一般在数字右下脚加注来表示，如111001（2）表示二进制数,34（5）表示5进制数。把二进制数110011（2）化为十进制数：110011（2)=1*25+1*24+0*23+0*22+1＊21+1＊20=32+16+2+1=51。把八进制数7348（8）化为十进制数：7348（8）=7*83+3＊82+4*81+8＊80=3584+192+32+8=3816.十进制数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的。典题·热题知识点一利用辗转相除法和更相减损术解题例1分别用辗转相除法和更相减损术求下列两数的最大公约数:261，319。思路分析:使用辗转相除法可依据m=nq+r，反复执行,直到r=0为止，亦可用如下的方法，直到余数为0；用更相减损术就是根据m—n=r，反复执行，直到n=r为止。解:（1）辗转相除法：319÷261=1（余58）；261÷58=4（余29);58÷29=2（余0)。∴319与261的最大公约数是29.更相减损术:319-261=58；261—58=203；203—58=145；145—58=87；87—58=29；58-29=29.∴319与261的最大公约数是29.深化升华通过上例可以发现用辗转相除法和更相减损术求得的最大公约数是相同的，但用辗转相除法的步骤较少，而用更相减损术运算简易，却步骤较多，在解题时应灵活运用.知识点二利用函数与方程思想——二分法解题例2已知x5+x4+2x3—5x2+3x—1=0在区间［0，1］上有唯一的实数根。试求出根的近似值。要求：(1)用伪代码表示算法；(2)根的误差的绝对值要小于0。005。思路分析：回顾二分法解方程的过程，并假设所求近似值与精确解的差的绝对值不超过0。005.这就是循环语句的终止条件。解:S1S2b←1；S3S4x0←(a+b)/2;S5f（a)←a5+a4+2a3—5a2S6f（x0）←x05+x04+2x03-5x02S7Iff（x0）=0ThenGoTo140；S8Iff（a）f（x0）<0Then；S9b←x0;S10Else;S11aS12EndIf;S13If|a—b|≥cThenGoTo4;S14Printx0。方法归纳对于给定的一元方程f（x)=0，要求精确度为ε的近似解的算法如下：1。确定有解区间［a,b］（f(a）·f(b)<0)。2。取[a，b］的中点.3.计算函数f(x)在中点处的函数值f(）。4。判断函数值f（）是否为0.(1）如果为0,x=就是方程的解，问题就得到了解决。(2)如果函数值f（)不为0,则分下列两种情况:①若f(a)·f(）<0,则确定新的有解区间为(a,）;②若f（a）·f(）＞0，则确定新的有解区间为(，b）。5.判断新的有解区间的长度是否小于误差ε:（1)如果新的有解区间长度大于误差ε,则在新的有解区间的基础上重复上述步骤；(2)如果新的有解区间长度小于或等于误差ε，则取新的有解区间的中点为方程的近似解.深化升华（1）循环变量和初始条件设两个变量a，b，分别表示有解区间的左端点和右端点,初始值分别为0和1。（2）循环体算法中反复执行的部分是判断函数值f（）是否为0:①如果f（)=0,输出。②如果f（)不为0，则判断f(a）·f()的符号：（ⅰ）如果f(a)·f（)<0,b←；(ⅱ)如果f（a)·f()＞0，a←.(3)终止条件①f(）=0；②b-a〈ε.误区警示将终止条件b-a〈ε当成循环体是错误的.问题·探究交流讨论探究问题如何求两个数的最大公约数，有几种方法？探究过程：同学甲：可用辗转相除法与更相减损术。辗转相除法的理论根据是：由m=nq+r可以看出，m,n和n，r有相同的公约数。更相减损术的理论依据为:由m-n=r，得m=n+r,可以看出，m,n与n，r有相同的公约数，即二者的“算理"相似.同学乙:辗转相除法与更相减损术的区别：（1）都是求最大公约数的方法,计算上辗转相除法以除法为主，更相减