资源描述：
《高中数学第1章算法初步1.4算法案例知识导引学案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1．4 算法案例案例探究有一个故事是讲唐代大官杨埙提拔官员的经过．他让两个资格职位相同的候选人解答下面这个问题，谁先答出就提拔谁．“有人在林中散步，无意中听到几个强盗在商量怎样分配抢来的布匹．若每人分6匹，就剩5匹；若每人分7匹，就差8匹．问共有强盗几个？布匹多少？”你能用一个简单算式求出强盗个数和布匹数吗？解析：这个问题可看作二元一次方程组问题．问题的特点是给出两种分配方案，一种分法分不完，一种分法不够分．中国古代的《九章算术》一书中搜集了许多这类问题，各题都有完整的解法，后人称这种算法为——“盈不足术”．这种算法可以概括为两句口诀：有余加不足，大减小来除．公式：（
2、盈+不足）÷两次所得之差=人数，每人所得数×人数+盈=物品总数，求得强盗有（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的最大公约数
3、；若r≠0，则把前面的除数b作为新的被除数，把余数r7作为新的除数，继续运算，直到余数为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的最大公约数，这
4、种方法叫做欧几里得辗转相除法，其算法如下：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=0ThenGoto8040Else50a←b60b←r70Goto2080Printb90End7思维启示：（1）每行语句前边有一个数字，我们称这个数字为行号，它的作用表示该行在伪代码中的位置和执行顺序．（2）If语句和Goto语句两个语句可结合能够实现循环．变式训练：用辗转相除法、更相减损术求228，
5、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=575
6、7-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；否
7、则，令x2=m．第四步：判断
8、x1-x2
9、<0．005是否成立？若是，则x1,x2之间的任意取值均为满足条件的近似根；若否，则返回第二步．解：流程图如图：7伪代码：10f(x)←x∧2-220Read“输入误差ε和初值x1,x2”；ε,x1,x230 m←(x1+x2)/240Iff(m)=0ThenGoto11050Iff(x1)f(m)>0Then60x1←m70Else80x2←m90EndIf100IfABS(x1-x2)>=εThenGoto30110Printm【例3】相传在远古时代有一片森林，栖息着3种动物，凤凰、麒麟和九头鸟．凤凰有1
