高中数学 第1章 算法初步 1.4 算法案例知识导引学案 苏教版必修3.doc

14算法案例案例探究 有一个故事是讲唐代大官杨埙提拔官员的经过他让两个资格职位相同的候选人解答下面这个问题，谁先答出就提拔谁“有人在林中散步，无意中听到几个强盗在商量怎样分配抢来的布匹若每人分6匹，就剩5匹；若每人分7匹，就差8匹问共有强盗几个？布匹多少？”你能用一个简单算式求出强盗个数和布匹数吗？ 解析：这个问题可看作二元一次方程组问题问题的特点是给出两种分配方案，一种分法分不完，一种分法不够分 中国古代的九章算术一书中搜集了许多这类问题，各题都有完整的解法，后人称这种算法为“盈不足术” 这种算法可以概括为两句口诀：有余加不足，大减小来除 公式：（盈+不足）两次所得之差=人数， 每人所得数人数+盈=物品总数， 求得强盗有（8+5）(7-6)=13（人），布匹有613+5=83（匹） 伪代码： read a,b,c,d x(a+b)/(d-c) ycx+a print x,y流程图：自学导引 1int(x)表示不超过x的最大整数 2mod(a,b)表示a除以b所得的余数，称b为模 3辗转相除法是用于求两个数的最大公约数的一种方法，这种算法由欧几里得在公元前300年左右首先提出，因而又叫欧几里得辗转相除法 4欧几里得辗转相除法找出a,b的最大公约数的步骤是：计算出ab的余数r，若r=0，则b为a,b的最大公约数；若r0，则把前面的除数b作为新的被除数，把余数r作为新的除数，继续运算，直到余数为0，此时的除数即为正整数a,b的最大公约数 5秦九韶算法是我国南宋数学家秦九韶在他的代表作数书九章中提出的一种用于计算一次同余式组的方法，称作大衍求一术疑难剖析 【例1】 输入两个正整数a和b（ab），求它们的最大公约数 思路分析：求两个正整数a、b(ab)的最大公约数，可以归结为求一数列： a,b,r1,r2,rn-1,rn,rn-1,0 此数列的首项与第二项是a和b，从第三项开始的各项，分别是前两项相除所得的余数，如果余数为0，它的前项rn-1即是a和b的最大公约数，这种方法叫做欧几里得辗转相除法，其算法如下： s1输入a,b(ab) s2求a/b的余数r； s3如果r0，则将ba,rb，再次求a/b的余数r，转至s2； s4输出最大公约数b解：流程图如下： 伪代码如下： 10 read a,b 20 rmod(a,b) 30 if r=0 then goto 80 40 else 50 ab 60 br 70 goto 20 80 print b 90 end 思维启示：（1）每行语句前边有一个数字，我们称这个数字为行号，它的作用表示该行在伪代码中的位置和执行顺序 （2）if语句和goto语句两个语句可结合能够实现循环 变式训练：用辗转相除法、更相减损术求228，1 995最大公约数 分析：使用辗转相除法，我们就根据a=nb+r这个式子，反复执行，直到r=0为止用更相减损术我们就根据r=a-b这个式子，反复执行就可 解：所以有以下解法： 用辗转相除法： 1 995=8228+171 228=1171+57 171=357+0 所以：57就是228和1 995的最大公约数 用更相减损术： 1 995-228=1 767 1 767-228=1 539 1 539-228=1 311 1 311-228=1 083 1 083-228=855 855-228=627 627-228=399 399-228=171 228-171=57 171-57=114 114-57=57 57-57=0 则57就是228，1 995的最大公约数 思维启示：由该题可以看出，辗转相除法得最大公约数步骤较少，而更相减损术运算简易，两种方法各有所长 【例2】 用二分法设计一个求方程x2-2=0的近似根的算法 思路分析：回顾二分法解方程的过程，并假设所求近似根与精确解的差的绝对值不超过0005，则不难设计出以下步骤： 第一步：令f(x)=x2-2因为f(1)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 then 60 x1m 70 else 80 x2m 90 end if 100 if abs (x1-x2)= then goto 30 110 print m 【例3】 相传在远古时代有一片森林，栖息着3种动物，凤凰、麒麟和九头鸟凤凰有1只头2只脚，麒麟是1只头4只脚，九头鸟有9只头2只脚它们这3种动物的头加起来一共是100只，脚加起来也正好是100只，问森林中各生活着多少只凤凰、麒麟和九头鸟？ 思路分析：假设凤凰的只数为x，麒麟的只数为y，九头鸟的只数为z，那么， （1）凤凰的只数x可能的取值为150，如果用伪代码表示，就应该如下：for x=1 to 50 step 1 （2）麒麟的只数y可能的取值为125，如果用伪代码表示，就应该如下： for y=1 to 25 step 1 （3）如果知道了凤凰和麒麟的只数后，那么九头鸟的只数就应该如下：z=(100-x-y)/9 如何考虑x、y、z三个变量之间的关系？ 当凤凰x=1时（只在开始时），变量麒麟y的取值可以从125，让变量y从1开始取值（例如：y的值为1）； 通过（100-x-y）/9表达式，计算出z的值； 完成上述步骤后，x、y、z三个变量都取到了自己相应的值，但是这三个值是否是正确的解呢？我们必须通过以下的两个条件来判断： x+y+9z=100 and 2x+4y+2z=100 如果全部满足，就输出x、y、z的值，如果不满足，就让y值加1，然后重复步骤（2）到步骤（4），直至y的取值超过25； 然后让x的取值加1后，重复步骤（1）到步骤（5）的操作，直至x的取值超过50为止，退出算法 解：流程图和伪代码如下： for x from 1 to 50 for y from 1 to 25 z(100-x-y)/9 if 2x+4y+2z=100 then print x,y,z end forend for拓展迁移【拓展点】 意大利数学家菲波契，在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项就是年底应有兔子对数，我们可以先确定