算法程序设计精彩案例.doc

一题多解，体会算法的艺术青岛二中臧方青2009年7月19日 15:22 浏览：101 专家浏览：3 | 评论：24 专家评论：0收藏李志杰于09-7-20 15:24推荐一题多解，激发学生的深度思考，将算法的艺术体现在学生面前。推荐。纪慧英于09-7-20 10:23推荐藏老师的“一题多解，体会算法的艺术”教学案例设计精妙，符合新课程理念，值得借鉴！特别适合各地重点中学且对算法有一定基础的学生。本节课我们要通过对一个题目的不同程度的算法分析，体会算法艺术的精妙之处。一：活动目的1.学生通过对题目的分析体验思维的快乐。2.根据问题学生要分析出自己的算法。3.通过同一问题不同算法的对比，体会算法艺术。二：活动任务为了美化奥帆中心，我们准备了一些长度不等的木棍制作装饰品。木棍的长度范围为1到100cm的整数，且同种长度的木棍有足够多，任意挑出一根木棍，现在让你按照下面的规则组合装饰品，请你计算一下一共可以组合成多少种不同的装饰品。规则如下：（1） 这根木棍本身就可以作为一个装饰品。（2） 在这根木棍左边可以加上一条木棍，形成一个新的装饰品，但该木棍的长度不能超过原木棍的一半。（3） 在任意一个装饰品左边都可以做和（2）操作一样的操作，即可以在一个装饰品的左边添加木棍形成新的装饰品，但是新添加的木棍不能超过原装饰品最左边木棍长度的一半。（4） 直到不能再添加为止。提示：如果我们拿出一根长度为4cm的木棍，那么形成的不同种类的装饰品有4种：木棍图示三：活动过程1.分析题目理解题意。2.分组交流和探究。全班3-5人一组，就以下问题进行交流和探究：（1）我对题目的理解是什么？（2）我提出地解决方法是什么？（3）我的方法可以归结为什么算法？3.任务分析。根据小组活动的结果，确定程序的整体功能要求，对程序的实现划分模块，并画出程序流程图。4.设计算法。根据小组交流结果，拟定程序的设计思路和步骤，如有问题可以请教老师或同学。四：参考资料。在这里，同学们可以参考下面的算法分析，完成你的程序，并体验算法的魅力。算法一：数学解析法。设木棍的长度为为n,让k=n，则根据题目给出的条件，我们可以做如下处理：则：f(n)=f(n-2)+k/2。算法二：递归。由于当前能加的数只与最左边的数有关，因此无论之前的数是什么，只要最左边的数相同，接下来的放法数就相同，所以，我们可以这样书写代码： Function calc(I as long) as long; Dim j as long ,ans as long; ans=1; for j=1 to i div 2 Ans=ans+calc(i) Next i End sub算法三：记忆化搜索。算法二中普通递归算法是效率低下的，因为同样的对于i，多次计算了calc(i)能不能记录一下calc(i)，使得只计算一次？同学们观察下面的代码： Dim f(100) as long; Function calc(I as long) as long; Dim j as long if fi=0 then fi:=1 for j=1 to i div 2 Fi=fi+calc(i) Next i End if Calc=Fi End;算法三依然是可以简化的，这要用到更高级的算法思想，同学们应该体验到了算法不仅仅是技巧，更是富有艺术性的，希望同学们在将来的学习中继续研究，取得更大的进步。五：活动评价。每位同学都应该通过自身的研究获同学的交流完成本次综合实践活动，并对算法的艺术性有充分的理解和体验，教师可以通过小组交流等方式进行评价。精彩实例让程序设计奇妙无穷 FOR-NEXT循环语句的教学案例青岛二中胡芳2009年7月20日 13:11 浏览：37 专家浏览：6 | 评论：12 专家评论：0收藏李爱霞于09-7-20 15:38推荐算法与程序设计一直是教学实施中的一个难题，胡老师在本案例中，集趣味性、适宜的知识体系建构、创新精神培养、归纳与总结能力的提升、团队合作、自主探究能力的培养于一体，成就了堪称经典的一节课！对教学有多角度李志杰于09-7-20 15:35推荐由学生感兴趣的图形绘制引入，例题也能考虑的学生的兴趣，作业提供了多重选择，考虑的学生的个性发展。在介绍For-Next语句的同时，穿插了穷举等算法，妙。值得推荐。纪慧英于09-7-20 15:19推荐胡老师在吃透了新课程理念的情况下，根据自己学生的特点，设计了这个令所有老师看了后都拍手叫好的课例。她引导学生温故知新，引导学生自主探究，引导学生热烈讨论引导学生慢慢地爱上了算法与程序设计。在此一、教材依据 本课题选自山东教育出版社算法与程序设计第二章程序设计的基础知识的第3节循环结构FOR-NEXT语句。 二、设计思想 程序设计的教学一向是中学信息技术课堂的一个难题，其困难之处并不在于知识深奥，而是在于学生始终对学习提不起兴趣。与形象生动、富于趣味的网页设计、动画制作相比，程序设计需要理解和记忆的知识点很多，而且知识之间逻辑性强、环环相扣，又较多地讨论与数学相关的问题，趣味性差，因而学生难免会觉得枯燥。经过新课程改革这些年的教学实践与研究，我发现只要课堂的教学案例能富于趣味性，充满了探究的乐趣，学生的思维就会被调动起来，注意力就可以较长时间保持在课堂教学上，课堂教学就会取得不错的效果。三、教学目标 知识与能力：学会使用FOR-NEXT语句并能运用其解决学习生活中的简单问题。过程与方法：在一系列小任务的驱动过程中，学生学会自主探究、合作学习，不断提高学生认识问题解决问题的能力。情感、态度、价值观： 教师激发并不断鼓励学生，使学生在自主探究过程中不断得到肯定并保有继续研究的勇气和毅力；学生在合作学习的过程中，感受到团队精神的力量，并在解决问题过程中获得成功的体验。四、教学重点 引导学生灵活的运用FOR-NEXT语句来解决问题五、教学难点 激发学生自主探究合作学习的愿望，通过学生自身的努力掌握运用FOR-NEXT语句解决问题的方法六、教学准备 多媒体机房（投影）、教学课件。 七、教学过程 （一）、新课的引入学生对图形图像的兴趣和关注远远大于文字和公式，因此，我首先呈现给学生两幅图像：画一个圆的程序界面（图1）和画十个同心圆的程序界面（图2）。我提示说：“画一个圆的程序我们在顺序结构中已经学过，画十个圆的程序你能不能完成呢？”学生们有的在讨论，有的马上就动手制作。短短的两三分钟就有相当一部分同学完成并争相演示给我看，他们采用的办法多是将原来画圆的语句（图3）复制并粘贴了9遍并修改了参数来实现的（图4），另外一些同学不屑于这种简单的办法却一时也拿不出更好的办法。这时候，教师的态度尤为重要，一方面我肯定了采用“笨”办法解决问题的学生，在没有找到更好的办法只要是能解决问题的办法就是好办法，另一方面，我也不忘鼓励学生探究，“如果题目让我们画100个圆、1000个圆怎么办？”急不可待的同学打开了书开始自学起今天要学习的FOR-NEXT语句，并试着开发程序，待到大约一半同学完成的时候，我也大屏幕投影展示了FOR-NEXT循环语句以及画十个圆的程序代码（图5），并与学生讨论总结。（二）、课堂教学的全面展开FOR-NEXT语句是计数循环语句，即事先已知循环要重复多少次。这个语句本身并没有什么知识上的难度，关键在于灵活的运用该语句来解决各种各样的问题。紧接着，我给出了两个思考题：例1 求解1+1/2+1/3+1/n，n的值由键盘输入。例2 笼子里放有若干只鸡和若干只兔，现发现笼子中共有头的个数为m个，共有爪子的个数为n只，请求出笼中鸡兔各有多少只？这两个题目中既有纯粹的数学题，也有趣味性的生活题，在知识的运用和解决问题的能力上又体现了难度的变化。我并不要求学生按照顺序来做题，而是可以二者选其一。学生们兴致勃勃地开始了思考实践，我在学生中巡视了一圈，粗略地统计了一下，一多半的学生选择了“鸡兔同笼”一题，看来学生们还是更喜欢趣味性的题目，这和我课前的预测基本一致。不断有学生举手示意做好了，我认真看了学生的程序界面和代码，做得好的加以表扬并鼓励他再研究另一题，做得还可以改进的，我与学生讨论提出修改的建议，我在继续等待，等待每一位学生至少完成一个题目。学生需要被尊重，学生需要被肯定，学生需要用他们自己的智慧解决问题而不是被打断或被告知，看着他们认真的样子，我只有选择等待。越来越多的学生举手示意，渐渐的我已经看不过来学生的作品了，就请学生上讲台演示并讲解。每一个题目，我先请一位学生讲解，如有不同解法就上台补充。第一个题目，大家解法一致（如图6、图7），我引导学生进行了小结，第一题可以看出循环进行了n次，作为表示循环次数的控制变量i，不仅表示循环的次数，更是可以直接参与运算。第二题程序界面的设计大同小异（图8），而代码的编写出现了两种方法，在学生们陈述完，我进行了总结。方法1（图9）是利用以前学过的顺序结构的知识来解决的，方法2（图10）是利用这节课学习的循环结构的知识来解决的。在这里我们可以看出，循环控制变量表示的不仅是循环最多能进行的次数，还可用来代表一种动物（比如说鸡）可能的数目，这种方法我们称之为穷举法。从这里我们可以看到循环结构FOR-NEXT语句的使用是非常灵活的。我及时地肯定了学生的努力，并赞扬了他们勇于探究的精神。此时，学生好像并不满足，他们在等待更大的挑战，难道要亮出我的“杀手锏”？（三）、课堂教学的升华我是有所准备的，我知道这是一群智力高超、热爱挑战的学生。我把一个新的难题抛给了学生：例1 向桌面掷若干次硬币，利用随机函数编制程序，分别求出硬币正面向上、反面向上的次数和他们与总次数的比。沉默小声讨论，看到我的默许，学生就同位两人或前后四人讨论，讨论激烈地进行着，但学生们并没有开始动手制作的意思，我知道一定有问题困扰着他们。我提示说：“这是一道颇有难度并有着一定复杂度的题目，我们似乎并不能很直接地找到方法来求解，但我们同学都已经有了一些想法，谁愿意谈谈？”沉默还是沉默，这是一群荣誉感很强的学生，他们总是乐于和别人分享他们成功的经验，却不愿在别人面前显示自己的不足或暂时的困境，我启发学生：“一个人的智慧是有限的，而集体的力量是无穷的，让我们来分享思路，合作学习吧。如果你的想法是正确的，同学们就可以给以确定，我们就可以在你的基础上继续作深入地探究，你就是我们的奠基石；如果你的想法还不太成熟，也请你大胆地说出来，也许交流可以使我们彼此之间都会得到一些启示，你就是我们的指明灯。”沉默终于有人勇敢地站起来了，“我认为可以将硬币正面向上、反面向上数值化，抽象成两个数，比如1和2。我们知道随机函数可以产生任意一个随机数，但怎么让其每次只产生1或2，循环的次数设定为多少次合理呢？这个问题我还没想明白。”他的回答刚结束，教室就爆发了热烈的掌声，同学们的肯定，鼓励了更多的学生发言。一位学生说：“根据随机函数的用法，我觉得产生1和2两个随机数不如产生0和1两个随机数方便，我觉得任意两个不同的整数都可以代表硬币正面向上、反面向上两种情况。”又一位学生总结到：“我们可以使用循环结构来处理，在循环中每次产生一个随机数0或1，并进行统计。至于循环要进行多少次，我觉得应该不是一个确定的值，而且这个值应该大一些，因为题目除了要统计0和1分别出现的次数，还要求出他们与总次数之比，好像是为了让我们验证一个现象。”终于，课代表沉不住气了：“我认为这是一个概率验证的问题，随着实验次数越来越多，正面、反面向上的次数应越来越趋向于各占一半的比例。我们应该让循环次数由100变为1000、10000、100000，来观察和验证这一现象。”一次次的掌声响起，在全体学生的努力下，我们终于理清了思路，找到了解题的钥匙。学生们似乎知道下课时间快到了，争分夺秒地开始编制程序，程序界面的精心设计、代码的准确编写、语法错误的修改、多组测试数据反复验证程序，这道难题终于变成了学生们手下一个完美的作品（如下图）。（四）、课堂小结像以往的每一节课一样，我准备了课堂总结，但这节课似乎像是学生们自导自演的一部精彩的电影，我愿意将让它在最完美的时候戛然而止。但学生们好像还在等待我说一些不是总结、不是表扬也不是结束的话。我忽然想起其实我还多准备了几个题目，要不要留给学生，我的脑子在快速地争论着，以往学生不太欢迎课下还留思考题或作业，我决定看看学生的反应。我说：“刚才我们整个团队经过共同的努力，征服了一个又一个的困难，取得了阶段性的胜利。但前进的路上并不总是有朋友相助，同样的困难可能会一次一次地出现，你自己一个人能行吗？”看到学生们跃跃欲试的样子，我用大屏幕投影展示了三个题目。现在你的任务来了，你愿意接受挑战吗？1求解1！+2！+n！2猴子摘了一堆枣，第一天吃了一半，还嫌不过瘾，又吃了一个；第二天又吃了剩下的一半零一个；以后每天如此。到第十天，猴子一看只剩下一个了。问最初有多少个枣子？3一个筛子有6个面，每个面上分别刻有1、2、3、4、5、6个点，随意向桌面投掷，如果各面是均匀的，