《用穷举法解决问题》教学设计

来源:用户上传      作者: 张　丽

　　教学分析
　　
　　1.教学目标
　　知识与技能：了解什么是穷举法及其特点，以及用穷举法设计算法的基本过程；能够根据具体问题的要求，使用穷举法设计算法。
　　过程和方法：运用观察、发现、归纳、应用的方法，发展学生的归纳思维；培养学生独立探究与自主发现的学习能力。
　　情感态度与价值观：了解算法和程序设计在计算机解决问题过程中的重要性；体验将算法转变为程序的过程，享受计算机解决问题的快乐。
　　
　　2.教学重点和难点
　　重点：用穷举算法解决问题的一般步骤；能根据具体问题的要求，提高运用穷举算法解决问题的能力。
　　难点：通过观察、类比多种方式培养学生归纳思维。
　　
　　教学过程
　　
　　1.创设情境激趣引入
　　教师活动：某同学用自己的QQ号登录，可他记不清密码了，你能帮他找回密码吗？他的密码是一个5位数，67□□8，其中百位和十位上的数字他不记得了，但他还记得该数能够被78整除，也能被67整除。你能帮他设计一个算法求出该密码吗？希望大家能在学习完下面这个例子后就可以解决这个问题。
　　设计意图：成功的教学不是强制，而是激发学生的学习兴趣，该导入正是从学生感兴趣的事情着手的。
　　
　　2.观察―发现―归纳―应用
　　(1)观察。
　　教师活动：逐语句调试以下程序，分析程序的执行过程，让学生填写下表，指出此程序功能。
　　For i=100 to 999
　　a=int(i /100)
　　b=int(i /10) mod 10
　　C=i mod 10
　　If a^3+b^3+c^3=ithen
　　Printi
　　Endif
　　Next i
　　(2)发现。
　　教师引导：在分析上一程序过程中，你能发现什么？
　　学生发现：①通过分析程序的执行过程，可看出变量a存放的是一个三位的自然数百位上的数字，变量b存放的是其十位上的数字，变量c存放的是其个位上的数字；②一个三位的自然数，若满足百位的立方、十位的立方与个位的立方之和等于它本身，就输出；③此程序的功能是输出100～999之间的自然数。
　　教师总结：此程序的特点是将求解对象一一列举出来，然后逐一加以分析、处理，并验证结果是否满足给定的条件。当穷举完所有对象，问题将最终得以解决。我们把这种算法称之为穷举法。
　　
　　教师引导：对于此题，某同学给出了另一种解法，请分析程序的执行过程，说出他采用的是什么算法，比较哪一种方法的效率更高，为什么？
　　For a=1 to 9
　　 For b=0 to 9
　　For c=0 to 9
　　 If a^3+b^3+c^3=a*100+b*10+c then
　　Print a*100+b*10+c
　　 Endif
　　Next c
　　 Next b
　　Next a
　　学生发现：第二种方法依然采用的是穷举算法。在第一个程序中，循环的次数是900次，每次循环要执行四条语句。而在第二个程序中，循环的次数是9×10×10=900次，但每次循环只执行一条语句，所以第二个程序的执行效率高。
　　(3)归纳。
　　教师活动：通过“输出自然数”这一例子，能归纳出用穷举法解决问题的步骤吗？
　　学生归纳：①确定穷举对象及搜索范围：用循环或循环嵌套实现；②写出符合问题解的条件：用IF语句实现；③尽可能缩小搜索范围，减少程序运行时间，提高程序的执行效率。
　　(4)应用。
　　教师活动：现在我们反回头来看刚开始时让大家思考的那道找回QQ密码的题，在编程实现之前，我们先来分析回答以下几个和此题相关的问题：①穷举的对象是什么？其搜索的范围是什么？②符合问题解的条件是什么？③你有方法减小搜索范围，提高程序的执行效率吗？
　　学生活动：①穷举的对象是密码，其搜索的范围是67008～67998；②符合问题解的条件是：此数既能被78整除，也能被67整除。
　　学生活动：在用自然语言描述其算法后，编程实现，帮助某同学找回QQ密码。
　　师生互动：在编程过程中，你遇到哪些困难？你是如何解决的？
　　设计意图：从一个学生熟悉的例子着手，让学生在观察中发现，在发现中质疑，在质疑中归纳，在归纳中解决问题。学生增长知识的过程是轻松愉快的。
　　
　　3.对比归纳，深化思维
　　(1)判断下列两题能否用穷举算法解决，为什么？通过分析，你能归纳出哪些能用穷举法解决，哪些不能用穷举法解决？
　　①在一个直角三角形中，三条边a、b、c的长度都为整数，且一条直角边a的长度已确定，斜边c的长度不能超过某数I，找出满足条件的所有直角三角形。
　　②使用一根长度为L厘米的铁丝，制作一个面积为S的矩形框，要求，计算出满足这种条件的矩形的高h和宽w。
　　学生归纳：通过两题的对比分析，穷举算法适用的条件是：有明显的穷举范围且求解对象应该是有限的；可以按某种规则列举对象；有穷举规则；一时找不出解决问题的更好途径时。
　　(2)《孙子算经》中有许多有趣的数学题，“鸡兔同笼”问题就是一个典型的例子。原题是：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？”
　　①此题能用穷举算法解决吗？若能，请编程实现。
　　学生活动：首先用自然语言描述用穷举算法解决，然后在此基础上编程实现。
　　②此题还可以用其他算法解决吗？若能，请编程实现。
　　问题分析：此题可用现在的方程来解，可以设鸡有x只，兔有y只。根据题目条件，因为1只鸡有1个头和2只脚，一只兔有1个头和4只脚，所以可列出这样一个二元一次方程组。
　　学生活动：用解析法编程实现。
　　③通过以上问题分析，归纳穷举算法的优点与缺点。
　　学生活动：比较两种不同算法，归纳出穷举算法的优点及缺点。
　　设计意图：学生的头脑不是一个需要填满的容器，而是一个需要燃烧的火把。通过对比、分析、归纳，引导学生的思维活动向纵深发展，由表及里，培养学生良好的思维习惯。

转载注明来源:https://www.xzbu.com/9/view-1031930.htm