2017-2018版高中数学第一章算法初步1.4算法案例学案版3

学必求其心得，业必贵于专精学必求其心得，业必贵于专精PAGE20学必求其心得，业必贵于专精PAGE1.4算法案例学习目标1。理解解决“韩信点兵—孙子问题”的算法思想；2。理解辗转相除法与更相减损术的数学原理；3。能用伪代码实现二分法求方程的近似解．知识点一本节涉及的内置函数就像木工不必自己造锯一样,VB也把一些常用基础工具做成内置函数，以备使用者直接调用，下面是本节涉及的内置函数：函数功能例子Mod（a,b)得到a除以b的余数Mod(9，2）＝1Val(）将字符串转换为数值Int（x）表示不超过x的最大整数Int(3.9)＝3知识点二“韩信点兵一孙子问题”的数学本质思考“三三数之剩二”是什么意思?如何用代数式表示？梳理“韩信点兵-孙子问题”是求关于x,y，z的一次不定方程组________________的正整数解．知识点三辗转相除法与更相减损术的算法原理思考我们知道204＝85×2＋34。为什么204与85的最大公约数就是85与34的最大公约数？梳理一般地,有2种算法求两个正整数的最大公约数：(1)辗转相除法的运算步骤：第一步，给定__________________．第二步，计算__________________．第三步，____________.第四步，若r＝0，则m，n的最大公约数等于______；否则，返回__________．(2）更相减损术的运算步骤：第一步，任意给定两个正整数，判断它们是否都是______．若是,用____约简；若不是,执行________．第二步，以________的数减去________的数，接着把所得的差与________的数比较，并以大数减小数，继续这个操作,直到所得的数________为止,则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数．知识点四二分法的实现思考你还能回忆起二分法的作用和原理吗?梳理求方程f(x）＝0在区间[a，b］上的近似解的步骤为：S1取［a,b］的中点x0＝eq\f（1,2)(a＋b),将区间一分为二．S2若________，则x0就是方程的根，否则判断根x*在x0的左侧还是右侧：若____________，则x*∈(x0，b），以x0代替a;若____________，则x*∈(a,x0）,以x0代替b.S3若|a－b｜<c，计算终止，此时____________，否则转______．类型一“韩信点兵—-孙子问题”例1韩信是秦末汉初的著名军事家．据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么办法,不要逐个报数，就能知道场上士兵的人数．韩信先令士兵排成3列纵队进行操练，结果有2人多余;接着他立刻下令将队形改为5列纵队，这一改，又多出3人；随后他又下令改为7列纵队，这一次又剩下2人无法成整列．结果在场的人哈哈大笑，韩信看此情形，立刻报告共有士兵2333人．众人都愣了，不知韩信用什么办法这么快清点出准确人数的．这个故事却引出一个著名的数学问题，即闻名世界的“孙子问题”．最早出现在我国《算经十书》之一的《孙子算经》中．原文是:“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二．问物几何？答曰:二十三．”所以人们将这种问题的通用解法称为“孙子剩余定理”或“中国剩余定理"．设有物m个，则其本质为由方程组eq\b\lc\{\rc\（\a\vs4\al\co1(m＝3x＋2，，m＝5y＋3，,m＝7z＋2)）求m的正整数解．试为此问题编写流程图和伪代码．反思与感悟此算法的本质是从最小2开始,逐个实验是否满足方程组,对人而言是个笨法,但很适合计算机，以上程序求出的是m的最小值．跟踪训练1有一堆围棋子，五个五个地数，最后余下2个;七个七个地数，最后余下3个；九个九个地数，最后余下4个．请用伪代码表示“求出这堆棋子至少有多少个"的一种算法．类型二辗转相除法的现代实现例2你能根据“欧几里得辗转相除法"设计一种求两个正整数a,b（a〉b)的最大公约数的一个算法吗？并画出流程图，编写伪代码．反思与感悟利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．跟踪训练2用辗转相除法和更相减损术求261和319的最大公约数．类型三求方程f（x)＝0近似解的算法例3画出用区间二分法求方程x3－x－1＝0在区间[1，1.5]上的一个近似解(误差不超过0.001）的一个算法流程图并编写伪代码．反思与感悟在此算法中用到了条件语句和循环语句，所以用“Do”是因为要执行再判断是否满足条件，因为不知循环次数，所以也不宜用“For”语句．跟踪训练3改造例3中伪代码，用来求f（x）＝lnx＋2x－1在区间[a,b］上的一个近似解（误差不超过c）．1．m是一正整数，对两个正整数a,b，若a－b是m的倍数，则称模m同余，用符号a≡b（Modm）表示．则a≡5（Mod27）中，a的取值最小为________．2．用更相减损术求36与134的最大公约数，第一步应为__________________________．3．求方程x＝5y＋3（其中y为自然数）的所有小于100的x的正整数解，用伪代码表示．4．求两个正数8251和6105的最大公约数．1．求两个正整数的最大公约数时，用辗转相除法进行设计的关键是：将“辗转”的过程用循环语句表示．为了避免求循环次数(对两个具体的正整数，循环次数可以求出，但会使程序更为复杂），最好使用“While"语句．2．用二分法求方程近似解，必须先判断方程在给定区间上是否有解．3．二分法的过程是一个多次重复的过程，故可用循环结构处理．4．二分法过程中需要对中点(端点)处函数值的符号进行判定，故实现算法需用选择结构,即用条件语句进行分支选择．

答案精析问题导学知识点二思考“三三数之剩二”意思是一堆东西,三个三个地分组，余二个．设这堆东西数目为m，则m＝3x＋2,其中x指组数．梳理eq\b\lc\｛\rc\（\a\vs4\al\co1(m＝3x＋2，,m＝5y＋3，,m＝7z＋2）)知识点三思考设204与85的最大公约数为a，则a能整除204，故能整除85×2＋34.又因为a也是85的约数,故a能整除85×2，所以a必能整除34,即a是34的约数，从而是85与34的最大公约数,显然，204与85的公约数问题转化成了85与34的公约数问题，问题难度降低了．梳理(1）两个正整数m，n（m>n）m除以n所得的余数rm←n,n←rm第二步(2）偶数2第二步较大较小较小相等知识点四思考二分法是用来求方程近似解的，其原理是先确定一个解所在的大致区间，然后借助零点存在定理，不断缩小这个区间．梳理f（x0）＝0f（a)f(x0)〉0f（a)f（x0)<0x*≈x0S1题型探究例1解流程图为伪代码为m←2WhileMod(m，3）≠2orMod（m，5）≠3orMod(m,7)≠2m←m＋1EndWhilePrintm跟踪训练1解算法的伪代码如下：m←2WhileMod（m，5）≠2orMod（m，7)≠3orMod（m，9）≠4m←m＋1EndWhilePrintm例2解算法如下：S1输入两个正整数a,b；S2若Mod（a,b)≠0,那么转S3，否则转S6;S3r←Mod(a,b)；S4a←b；S5b←r，转S2；S6输出b。流程图如图:伪代码如下：Reada，bWhileModa,b≠0r←Moda，ba←bb←rEndWhilePrintb跟踪训练2解辗转相除法：319÷261＝1（余58）,261÷58＝4（余29），58÷29＝2（余0）,所以319与261的最大公约数为29。更相减损术:319－261＝58，261－58＝203，203－58＝145,145－58＝87,87－58＝29，58－29＝29，29－29＝0,所以319与261的最大公约数是29.例3解流程图如图：伪代码如图:a←1b←1。5c←0.001Dox0←fa←a3－a－1fx0←－x0－1Iffx0＝0ThenExitDoIffafx0<0Thenb←x0Elsea←x0EndIfUntil｜a－b｜〈cEndDoPrintx0跟踪训练3解伪代码如图：Reada，b，cDox0←fa←lna＋2a－1fx0←lnx0＋2x0－1Iffx0＝0ThenExitDoIffafx0<0Thenb←x0Elsea←x0EndIfUntil|a－b|〈cEndDoPrintx0当堂训练1．322．先除以2，得到18与67解析∵36与134都是偶数，∴第一步应为：先除以2，得到18与67。3．解算法的伪代码如图：y←0x←0Whilex<100x←5y＋3Printxy←y＋1EndWhile4．解825