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

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