资源描述：
《高中数学第1章算法初步14算法案例教材梳理导学案苏教版必修3》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、1.4算法案例庖丁巧解牛知识•巧学1.几个常用函数符号求余函数Mod(m,n):Mod(m,n)表示取m除以n的余数.如：m被3除余2,可表示为Mod(m,3)=2.取整函数Int(x):表示取不大于x的最大整数.如:Tnt(2)=2,Int(2.3)=2,Tnt(2.6)=2.误区警示不要与四舍五入相混淆Int(-2.3)=-3.可用mlnt(m/n)*n表示m除以n的余数,如m被3除余2,可表示为mint(m/3)*3=2.2.算法典型案例案例1：韩信点兵一一孙子问题《孙子算经》中载有“物不知数”这个问题:今有物不知其数，三三数之剩二；五五数
2、之剩三；七七数之剩二，问物几何？答曰“二十三”•这就是著名的孙子问题(记载于中国古代约公元3世纪成书的《孙子算经》，是原书卷下第26题).这个问题可以简单地用一句话描述，即“一个正整数，被3,5,7除，余数分别为2,m=3兀+2;3,2”.设这个数为m,则可列关于x,y,z的方程组表示:*m=5y+3;m=7z+2.联想发散这一类问题的解法可以推广成解一次同余式组的一般方法.秦九韶给出了理论上的证明，并将它定名为“大衍求一术”.这个问题的通用解法称为“屮国剩余定理”.秦九韶(公元1202-1261年)，南宋数学家，著《数书九章》十八卷.全书共81
3、道题，分为九大类：大衍类、天时类、田域类、测望类、赋役类、钱谷类、营建类、军旅类、市易类.其屮对“大衍求一术”(一次同余组解法)和“正负开方术”(高次方程的数值解法)等有十分深入的研究•“大衍求一术”，在世界数学史上占有崇高的地位.计算机解决：从2开始，让m依次去除，直到满足要求为止.这样，只要使用循环，由小到大依次搜索，直到找出满足条件的数即可.流程图如图1-4-1：图1-4-1案例2：辗转相除法求最大公约数辗转相除法又称欧几里得算法，就是对于给定的两个数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直
4、到余数为零，此时的除数就是所求两数的最大公约数.误区警示这是一个反复执行的步骤，要用循环结构实现•注意循环条件的设置，此处可用直到型循环，条件为卢0,対于循环体部分，需要反复执行的是r-mMODn.要实现上述算法，在重复执行之前，耍对m,n的两个变量重新赋值(ni二n,n二r),注意体会理解该递归思想.(1)算法步骤：以求正整数m,n(m>n)的最大公约数为例.第一步：输入两个正整数m,n(m>n)；第二步：判断m,n的大小，让m表示较大的数，n表示较小的数；第三步：计算ni/n的余数r；第四步：如果r^O,那么把n赋值给m,把r赋值给n,返回第
5、二步；否则，执行下一步；第五步：输出最大公约数m.(2)流程图如图1-4-2L输出加/丽图1-4-2伪代码如下：叶2WhileMod(m,3)H2或Mod(m,5)H3或Mod(m,7)H2m*-m+1EndWhilePrintm更相减损术更相减损术是中国古代算书《九章算术》中的一个优秀算法；更相减损术可以求最大公约数：対于给定的两个数，以其中较大的数减去较小的数，然后将差和较小的数构成一対新数，再用较大的数减去较小的数，反复执行以上步骤直到差数与较小的数相等，此时相等的两数即为所求的最大公约数，最后该最大公约数再乘以2即为所求.学法一得所求两数
6、都是偶数时，可先除以2,再求除以2后两数的最大公约数.(1)算法步骤：以求正整数的最大公约数为例，第一步：输入两个正整数m,n(m>n)；第二步：r^m-n;第三步：如果那么in—n,n—r,否则，in—t;第四步：如果mHn,则返回第二步，否则执行下一步；第五步：输出m.(2)程序框图如图1-4-3[w/输人加屮/图1-4-3案例3：二分法求方程近似解二分法是方程求根的一种常用方法，其过程体现的就是算法思想.理论依据：我们知道，若函数f(x)在区间［xbx2］两端点的函数值异号，即f(Xi)f(X2)<0,则在区间［xbx2］内方程f(x)=O
7、至少有一个根.二分法是说：如果在区间Lxbx2］内f(x)=0仅有一个根X,则可以取Xi与X2的中点X3=(Xi+X2)/2进行判断,若f(xj与f(xj异号，说明有一个根在区间［X
8、,X：J中，否则在区间［X2,X訂中.然后按上述方法逐渐缩小有根区间，从而逼近方程f(x)=0的根.当有根区间小到一定程度时，把这个区间的中点的x值当作方程的近似根.用二分法设计求方程f(x)二0的近似根算法的基本步骤：(1)确定近似根所在的基础区间［a,b］和近似根的精确度c；(2)求有根区间的中点，判断是否满足精度要求；(3)求区间端点的函数值f(a),f(b)
9、；(4)判断f(a)f(b)的符号，改变有根区间的下限或上限；(5)循环求近似根；(6)输出根的近似值.进位制进位制是一种记数方式，用有
