211算法的基本思想

2.1.1算法案例教学目标（1）介绍中国古代算法的案例－韩信点兵－孙子问题；（2）用三种方法熟练的表示一个算法；（3）让学生感受算法的意义和价值．教学重点、难点:不定方程解法的算法．教学过程一、判断是否是素数例1在给定素数表的条件下，请你设计一个算法，将936分成素因数的乘积.解：算法步骤如下：1.判断936是否为素数：否。2.确定936的最小素因数：2。936=24683.判断468是否为素数：否。4.确定468的最小素因数：2。936=22234。5.判断234是否为素数：否。6.确定234的最小素因数：2。936=222117。7.判断117是否为素数：否。8.确定117的最小素因数：3。936=222339。9.判断39是否为素数：否。10.确定39的最小素因数：3。936=2223313。11.判断13是否为素数：13是素数，所以分解结束。12.分解结果是：936=2223313。二、求最大公因数问题例2设计一个算法求228和285的最大公因数及最小公倍数。解：（1）求最大公因数，步骤如下：1.先将228进行素因数分解：228=22×3×19.2.将285进行素因数分解：285=3×5×19.3.确定它们的公共素因数：3，19.4.确定公共素因数3，19的指数分别为：1，1.5.228和285的最大公因数为：57.（2）求最小公倍数，步骤如下：1.先将228进行素因数分解：228=22×3×19.2.将285进行素因数分解：285=3×5×19.3.确定它们所有素因数：2，3，5，7，19.4.确定他们所有素因数的最高指数：2，1，1，1.5.228和285的最小公倍数为：1140.三、“韩信点兵”问题：（1）案例：韩信是秦末汉初的著名军事家。据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么方法，不要逐个报数，就能知道场上的士兵的人数。韩信先令士兵排成3列纵队，结果有2个人多余；接着立即下令将队形改为5列纵队，这一改，又多出3人；随后他又下令改为7列纵队，这次又剩下2人无法成整行。在场的人都哈哈大笑，以为韩信不能清点出准确的人数，不料笑声刚落，韩信高声报告共有士兵2333人。众人听了一愣，不知道韩信用什么方法这么快就能得出正确的结果的。同学们，你知道吗？背景说明:1．类似的问题最早出现在我国的《算经十书》之一的《孙子算经》中原文是：“今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？答曰：「二十三」”2．孙子算经的作者及确实着作年代均不可考，不过根据考证，着作年代不会在晋朝之後，以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。中国剩余定理（ChineseRemainderTheorem）在近代抽象代数学中占有一席非常重要的地位；3．该问题的完整的表述，后来经过宋朝数学家秦九韶的推广，又发现了一种算法，叫做“大衍求一术”。在中国还流传着这么一首歌诀：三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。它的意思是说：将某数（正整数）除以3所得的余数乘以70，除以5所得的余数乘以21，除以7所得的余数乘以15，再将所得的三个积相加，并逐次减去105，减到差小于105为止。所得结果就是某数的最小正整数值。用上面的歌诀来算《孙子算经》中的问题，便得到算式：2×70+3×21+2×15=233，233－105×2=23，即所求物品最少是23件。（2）.算法设计思想:“孙子问题”相当于求关于,,xyz的不定方程组的325372mxmymz的正整数解；设所求的数为m，根据题意m应该同时满足下列三个条件：①m被3除后余2，即mod(,3)2m；②m被5除后余3，即mod(,5)3m；③m被7除后余2，即mod(,7)2m；用自然语言可以将算法写为：1S1m2S1mm3S如果mod(,3)2m且mod(,5)3m且mod(,7)2m则执行4S,否则执行2S;4S输出m三、回顾小结：1．中国数学在世界数学史上的巨大贡献；2．实际问题的分析和解决问题过程；3．算法的表示及语句的运用；四、课外作业：