资源描述：
《高中数学第1章算法初步14算法案例知识导引学案苏教版必修3》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、1.4算法案例案例探究有一个故事是讲唐代大官杨损提拔官员的经过.他让两个资格职位相同的候选人解答下面这个问题，谁先答出就提拔谁.“有人在林中散步，无意中听到几个强盗在商量怎样分配抢来的布匹.若每人分6匹，就剩5匹；若每人分7匹，就差8匹.问共有强盗儿个？布匹多少？”你能用一个简单算式求出强盗个数和布匹数吗？解析：这个问题可看作二元一次方程组问题•问题的特点是给出两种分配方案，一种分法分不完，一种分法不够分.中国古代的《九章算术》一书中搜集了许多这类问题，各题都有完整的解法，后人称这种算法为一一“盈不足术”•这种算法可以概
2、括为两句口诀：有余加不足，大减小来除.公式：(盈+不足)一两次所得之差二人数，每人所得数X人数+盈二物品总数，求得强盗有(8+5)4-(7-6)=13(人)，布匹有6X13+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.欧几里得辗
3、转相除法找出a,b的最大公约数的步骤是:计算11!a-b的余数r,若r=0,则b为a,b的最大公约数；若rHO,则把前面的除数b作为新的被除数，把余数r作为新的除数，继续运算，直到余数为0,此时的除数即为正整数a,b的最大公约数.1.秦九韶算法是我国南宋数学家秦九韶在他的代表作《数书九章》屮提出的一种用于计算一次同余式组的方法，称作大衍求一术.疑难剖析【例1】输入两个正整数a和b(a>b),求它们的最大公约数.思路分析：求两个正整数a、b(a>b)的最大公约数，可以归结为求一数列：a,b,rb1*2,•••,rni,rn
4、,rn-i,0此数列的首项与第二项是a和b,从笫三项开始的各项，分别是前两项相除所得的余数,如果余数为0,它的前项E即是a和b的最大公约数，这种方法叫做欧几里得辗转相除法,其算法如下：S1输入a,b(a>b)S2求a/b的余数r；S3如果rHO,则将b-*a,r-*b,再次求a/b的余数r,转至S2；S4输出最大公约数B.解：流程图如下：/输出b/伪代码如下：10Reada,b20r*-Mod(a,b)30Ifr=0ThenGoto8040Else50a*-b60b*-r70Goto2080Printb90End思维启示
5、：(1)每行语句前边有一个数字，我们称这个数字为行号，它的作用表示该行在伪代码中的位置和执行顺序.(2)If语句和Goto语句两个语句可结合能够实现循环.变式训练：用辗转相除法、更相减损术求228,1995最大公约数.分析：使用辗转相除法，我们就根据a=nb+r这个式子，反复执行，直到一0为止.用更相减损术我们就根据r=a-b这个式子，反复执行就可.解：所以有以下解法：用辗转相除法：1995=8X228+171228=1X171+57171=3X57+0所以：57就是228和1995的最大公约数.用更相减损术：1995-
6、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的近似根的算法.思路分析：回顾二分法解方程的过程，并假设所求近似根与精确解的差的绝对值不超
7、过0.005,则不难设计出以下步骤：第一步：令f(x)=x-2.因为f(1)<0,f⑵>0,所以设x产1,X2=2・第二步：令呼士竺，判断f(m)是否为0.若是，则m为所求；若否，则继续判断2f(xi)・f(m)大于0还是小于0.第三步：若f(xj・f(m)>0,则令Xi=m；否则,令X2=m・第四步：判断
8、x-x2
9、<0.005是否成立？若是，则xi,刈之间的任意取值均为满足条件的近似根；若否，则返回第二步.解：流程图如图：伪4f弋码：10f(x)-xA2-220Read“输入误差£和初值Xi,X2”；xbx230m*
10、-(xl+x2)/240Tff(m)=0ThenGotono50Iff(xi)f(m)>0Then60Xl—Hl70Else80x2—m90EndIf100IfABS(xl-x2)>=eThenGoto30110Printm【例3】相传在远古时代有一片森林，栖息着3种动物，凤凰、麒麟和九头鸟.凤凰有1只头2只脚，麒麟
