1、高考资源网提供高考试题、高考模拟题，发布高考信息题本站投稿专用信箱：ks5u，来信请注明投稿，一经采纳，待遇从优1.3 算法案例(1)教学目标（1）介绍中国古代算法的案例韩信点兵孙子问题；（2）用三种方法熟练的表示一个算法；（3）让学生感受算法的意义和价值教学重点、难点:不定方程解法的算法教学过程一、问题情境(韩信点兵-孙子问题)： 韩信是秦末汉初的著名军事家。据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么方法，不要逐个报数，就能知道场上的士兵的人数。 韩信先令士兵排成3列纵队，结果有2个人多余；接着立即下令将队形改为5列纵队，这一改，又多出3人；随后他又下令改为7列纵队，这次
2、又剩下2人无法成整行。 在场的人都哈哈大笑，以为韩信不能清点出准确的人数，不料笑声刚落，韩信高声报告共有士兵2333人。众人听了一愣，不知道韩信用什么方法这么快就能得出正确的结果的。同学们，你知道吗？背景说明:1类似的问题最早出现在我国的算经十书之一的孙子算经中原文是：“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？答曰：二十三”2孙子算经的作者及确实着作年代均不可考，不过根据考证，着作年代不会在晋朝之後，以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。中国剩余定理（Chinese Remainder The
3、orem）在近代抽象代数学中占有一席非常重要的地位；3该问题的完整的表述，后来经过宋朝数学家秦九韶的推广，又发现了一种算法，叫做“大衍求一术”。在中国还流传着这么一首歌诀： 三人同行七十稀， 五树梅花廿一枝， 七子团圆月正半， 除百零五便得知。它的意思是说：将某数（正整数）除以3所得的余数乘以70，除以5所得的余数乘以21，除以7所得的余数乘以15，再将所得的三个积相加，并逐次减去105，减到差小于105为止。 所得结果就是某数的最小正整数值。用上面的歌诀来算孙子算经中的问题，便得到算式： 270+321+215=233， 2331052=23，即所求物品最少是23件。二.算法设计思想: “孙
4、子问题”相当于求关于的不定方程组的的正整数解； 设所求的数为，根据题意应该同时满足下列三个条件：被3除后余2，即；被5除后余3，即；被7除后余2，即；用自然语言可以将算法写为： 如果且且则执行,否则执行; 输出三.流程图和伪代码:输出且且开始结束 伪代码： DO Loop Until且且 Print 注：这里的解题的过程中运用的DO循环语句和课本上的解题略有区别请注意辨别！四、回顾小结：1中国数学在世界数学史上的巨大贡献； 2实际问题的分析和解决问题过程；3算法的表示及语句的运用；五、课外作业：课本第31页第3题1.3 算法案例(2)教学目标：（1）理解辗转相除法与更相减损术中蕴含的数学原理，
5、并能根据这些原理进行算法分析；（2）基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序；教学重点：理解辗转相除法与更相减损术求最大公约数的方法教学难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言教学过程一、问题情境在初中，我们已经学过求最大公约数的知识，你能求出18与30的公约数吗？我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数？这就是我们这一堂课所要探讨的内容二、算法设计思想：1.辗转相除法：例1求两个正数8251和6105的最大公约数（分析：
6、8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数）解：8251610512146显然8251和的2146最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数6105214621813214618131333181333351483331482371483740则37为8251与6105的最大公约数以上我们求最大公约数的方法就是辗转相除法也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的利用辗转相除法求最大公约数的步骤如下：第
7、一步：用较大的数除以较小的数得到一个商和一个余数；第二步：若，则为的最大公约数；若，则用除数除以余数得到一个商和一个余数；第三步：若，则为的最大公约数；若，则用除数除以余数得到一个商和一个余数；依次计算直至，此时所得到的即为所求的最大公约数练习：利用辗转相除法求两数4081与20723的最大公约数（答案：53）2.更相减损术我国早期也有解决求最大公约数问题的算法，就是更相减损术更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母之数，以少减多，更相减损，求其等也，以等数约之翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步：以较大的数
8、减去较小的数，接着把较小的数与所得的差比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数例2 用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：9863356335283528728721217141477所以，98与63的最大公约数是7练习：用更相减损术求两个正数84与72的最大公约数（答案：12）3.比较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显（
9、2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到三. 辗转相除法的流程图及伪代码利用辗转相除法与更相减损术的计算算法，我们可以设计出程序框图以及BSAIC程序来在计算机上实现辗转相除法与更相减损术求最大公约数，下面由同学们设计相应框图并相互之间检查框图与程序的正确性，并在计算机上验证自己的结果（1）辗转相除法的程序框图及程序程序框图：输出b开始输入a,b结束伪代码:用较大的数除以较小的数，得到除式，直到.四、回顾小结：1辗转相除法与更相减损术中蕴含的数学原理及算法语言的表示；2函数的含义五、课外作业：课本第31页第2 ；课本第35页第131.
10、3 算法案例(3)教学目标（1）二分法主要是采用了循环结构处理问题要会分析类似的问题；（2）GoTo语句的认识及其他语句的进一步熟悉；（3）能由流程图分析出期所含有的结构并用为代码表示出相应的算法教学重点二分法的算法思想和算法表示教学过程一、问题情境 必修1中我们学习了二分法求方程的近似解，大家还能想起二分法的求解步骤吗？二、案例讲解：案例：写出用区间二分法求解方程在区间内的一个近似解（误差不超过0.001）的一个算法 （）算法设计思想：如图，如果估计出方程在某区间内有一个根，就能用二分法搜索求得符合误差限制的近似解（）算法步骤可以表示为：取的中点，间区间一分为二；若，则就是方程的根，否则判断
11、根在的左侧还是后侧；若，则，以代替；若，则，以代替；若，计算终止，此时，否则转（）流程图：（4）伪代码1：结束开始Read a，b，cWhile And If 0 Then Else End If End While Print 伪代码2：10 Read 20 30 40 50 If Then GoTo 12060 If Then 70 80 Else90 100 End If110 If Then GoTo 20120 Print 二分搜索的过程是一个多次重复的过程，故可以用循环结构来处理（代码1），课本解法是采用语句实现的（代码2）。 三、回顾小结：1二分法的算法和用伪代码表示该算法；2语句的使用；3解决实际问题的过程：分析画流程图写伪代码。四、课外作业：课本复习题的第1题,课本复习题的第10题补充一个三位数的十位和个位的数字互换，得到的一个新的三位数，新、旧两个三位数都能被4整除；设计一个算法，求满足条件的三位数的个数，并写出伪代码。共6页 第6页
