数学知识导引算法案例

学必求其心得，业必贵于专精学必求其心得，业必贵于专精学必求其心得，业必贵于专精5．4算法案例案例探究有一个故事是讲唐代大官杨埙提拔官员的经过．他让两个资格职位相同的候选人解答下面这个问题，谁先答出就提拔谁．“有人在林中散步，无意中听到几个强盗在商量怎样分配抢来的布匹．若每人分6匹,就剩5匹；若每人分7匹,就差8匹．问共有强盗几个？布匹多少？”你能用一个简单算式求出强盗个数和布匹数吗?解析:这个问题可看作二元一次方程组问题．问题的特点是给出两种分配方案，一种分法分不完，一种分法不够分．中国古代的《九章算术》一书中搜集了许多这类问题，各题都有完整的解法，后人称这种算法为—-“盈不足术”．这种算法可以概括为两句口诀：有余加不足，大减小来除．公式：(盈+不足）÷两次所得之差=人数，每人所得数×人数+盈=物品总数，求得强盗有（8+5）÷（7—6)=13（人)，布匹有6×13+5=83（匹）．伪代码：Reada,b,c，dx←(a+b)/(d-c)y←cx+aPrintx，y流程图：自学导引1．int(x)表示不超过x的最大整数．2．mod(a，b)表示a除以b所得的余数,称b为模．3．辗转相除法是用于求两个数的最大公约数的一种方法,这种算法由欧几里得在公元前300年左右首先提出，因而又叫欧几里得辗转相除法．4．欧几里得辗转相除法找出a，b的最大公约数的步骤是：计算出a÷b的余数r，若r=0，则b为a,b的最大公约数；若r≠0，则把前面的除数b作为新的被除数，把余数r作为新的除数，继续运算，直到余数为0，此时的除数即为正整数a，b的最大公约数．5．秦九韶算法是我国南宋数学家秦九韶在他的代表作《数书九章》中提出的一种用于计算一次同余式组的方法，称作大衍求一术．疑难剖析【例1】输入两个正整数a和b（a>b）,求它们的最大公约数．思路分析：求两个正整数a、b(a〉b）的最大公约数，可以归结为求一数列：a,b,r1，r2，…，rn-1，rn,rn—1，0此数列的首项与第二项是a和b,从第三项开始的各项,分别是前两项相除所得的余数，如果余数为0,它的前项rn-1即是a和b的最大公约数，这种方法叫做欧几里得辗转相除法，其算法如下：S1输入a,b(a＞b)S2求a/b的余数r；S3如果r≠0，则将b→a,r→b,再次求a/b的余数r，转至S2；S4输出最大公约数B．解：流程图如下：伪代码如下：10Reada，b20r←Mod(a，b)30Ifr=0ThenGoto8040Else50a60b←r70Goto2080Printb90End思维启示：（1）每行语句前边有一个数字，我们称这个数字为行号，它的作用表示该行在伪代码中的位置和执行顺序．(2）If语句和Goto语句两个语句可结合能够实现循环．变式训练:用辗转相除法、更相减损术求228,1995最大公约数．分析:使用辗转相除法，我们就根据a=nb+r这个式子，反复执行，直到r=0为止．用更相减损术我们就根据r=a-b这个式子，反复执行就可．解:所以有以下解法:用辗转相除法：1995=8×228+171228=1×171+57171=3×57+0所以：57就是228和1995的最大公约数．用更相减损术：1995-228=17671767-228=15391539-228=13111311—228=10831083-228=855855—228=627627-228=399399-228=171228-171=57171-57=114114—57=5757—57=0则57就是228,1995的最大公约数．思维启示：由该题可以看出，辗转相除法得最大公约数步骤较少，而更相减损术运算简易，两种方法各有所长．【例2】用二分法设计一个求方程x2-2=0的近似根的算法．思路分析：回顾二分法解方程的过程，并假设所求近似根与精确解的差的绝对值不超过0．005,则不难设计出以下步骤:第一步：令f（x)=x2—2．因为f(1）〈0，f（2)>0，所以设x1=1,x2=2．第二步：令m=，判断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之间的任意取值均为满足条件的近似根;若否，则返回第二步．解：流程图如图：伪代码：10f（x）←x∧20Read“输入误差ε和初值x1,x2”；ε，x1，x30m←(x1+x2)/240Iff（m)=0ThenGoto11050Iff（x1)f（m）〉0Then60x1←m70Else80x2←m90EndIf100IfABS(x1-x2）〉=εThenGoto30110Printm【例3】相传在远古时代有一片森林，栖息着3种动物，凤凰、麒麟和九头鸟．凤凰有1只头2只脚,麒麟是1只头4只脚，九头鸟有9只头2只脚．它们这3种动物的头加起来一共是100只，脚加起来也正好是100只,问森林中各生活着多少只凤凰、麒麟和九头鸟？思路分析：假设凤凰的只数为x，麒麟的只数为y,九头鸟的只数为z，那么，（1)凤凰的只数x可能的取值为1～50，如果用伪代码表示，就应该如下：Forx=1To50Step1(2）麒麟的只数y可能的取值为1~25，如果用伪代码表示，就应该如下：Fory=1To25Step1（3）如果知道了凤凰和麒麟的只数后,那么九头鸟的只数就应该如下：z=（100-x—y）/9．如何考虑x、y、z三个变量之间的关系？当凤凰x=1时(只在开始时），变量麒麟y的取值可以从1～25，让变量y从1开始取值（例如:y的值为1）；通过(100-x-y）/9表达式,计算出z的值；完成上述步骤后,x、y、z三个变量都取到了自己相应的值，但是这三个值是否是正确的解呢？我们必须通过以下的两个条件来判断：x+y+9×z=100And2×x+4×y+2×z=100．如果全部满足，就输出x、y、z的值,如果不满足，就让y值加1，然后重复步骤（2）到步骤（4)，直至y的取值超过25；然后让x的取值加1后，重复步骤（1）到步骤（5)的操作，直至x的取值超过50为止，退出算法．解：流程图和伪代码如下:Forxfrom1to50Foryfrom1to25z←（100-x-y）/9If2x+4y+2z=100thenPrintx，y,zEndforEndfor拓展迁移【拓展点】意大利数学家菲波契，在1202年出版的一书里提出了这样的一个问题：一对兔子饲养到第二个月进入成年，第三个月生一对小兔,以后每个月生一对小兔,所生小兔能全部存活并且也是第二个月成年，第三个月生一对小兔,以后每月生一对小兔，这样下去到年底应有多少对兔子．思路分析:根据题意可知，第一个月有1对小兔,第二个月有1对成年兔子，第三个月有两对兔子，从第三个月开始,每个月的兔子对数是前面两个月兔子对数的和，设第N个月有F对兔子，第N—1个月有S对兔子,第N-2个月有Q对兔子，则有F=S+Q，一个月后，即第N+1个月时，式中变量S的新值应变第N个月兔子的对数（F的旧值)，变量Q的新值应变为N—1个月兔子的对数（S的旧值），这样，用S+Q求出变量F的新值就是N+1个月兔子的数，依此类推，可以得到一个数序列，数序列的第12项就是年底应有兔子对数,我们可以先确定前两个月的兔子对数均为1，