第14课 算法效率比一比（教案）2024-2025学年五年级上册信息技术人教版

第14 课算法效率比一比 一、教学目标 1.知道解决同一个问题可以有不同的算法，不同的算法具有不同的效率。 2.通过实例比较和算法分析，了解算法执行的关键步骤和执行次数，体会算法存在的效率差异。 二、教学重点与难点 教学重点 1.理解不同算法的效率差异。 2.分析算法的关键步骤和执行次数。 教学难点 1.准确评估不同算法的效率。 2.选择合适的算法解决问题。 三、教学准备 1.多媒体课件，包含不同算法的示例、效率比较等内容。 2.纸、笔，供学生进行分析和计算。 四、教学过程 （一）导入新课 师：同学们，在我们解决问题的时候，往往可以有多种方法。就像我们去学校，可以走路、骑自行车、坐公交车等。在计算机编程中，解决同一个问题也可以有不同的算法。那么，不同的算法会有什么不同呢？今天我们就来一起比较一下算法的效率。 （二）新课讲解 1.引出不同算法解决同一个问题的概念 师：我们以一个简单的问题为例，计算从1到100的和。大家想想，可以用哪些方法来解决这个问题呢？ 生：可以一个一个地加起来。 生：还可以用公式（首项+末项）×项数÷2。 师：非常好！这就是两种不同的算法来解决同一个问题。我们先来看看第一种算法，一个一个地加起来。 2.分析第一种算法：逐个相加 （1）描述算法过程 师：这种算法的过程很简单，就是从1开始，依次加上2、3、4……一直加到100。 我们可以用Python语言来实现这个算法： total=0 for I in range(1,101): total+=i print(total) （2）分析关键步骤和执行次数 师：在这个算法中，关键步骤就是每次的加法运算。执行次数是多少呢？我们可以分析一下。 因为要从1加到100，一共要进行100次加法运算。所以这个算法的执行次数是100次。 3.分析第二种算法：使用公式 （1）描述算法过程 师：第二种算法是使用公式（首项+末项）×项数÷2。在这个问题中，首项是1，末项是100，项数是100。 我们可以用Python语言来实现这个算法： sum=(1+100)*100//2 print(sum) （2）分析关键步骤和执行次数 师：在这个算法中，关键步骤就是一次加法、一次乘法和一次除法运算。执行次数只有这三次。 4.比较两种算法的效率 （1）从执行次数角度比较 师：我们可以明显看出，第一种算法需要进行100次加法运算，而第二种算法只需要进行一次加法、一次乘法和一次除法运算。从执行次数上来说，第二种算法远远少于第一种算法。 （2）从实际运行时间角度比较 师：我们可以在计算机上运行这两种算法，看看它们实际的运行时间。虽然这个时间可能会因为计算机的性能不同而有所差异，但是一般来说，第二种算法的运行时间会比第一种算法短很多。 5.拓展不同算法解决其他问题的例子 （1）排序问题 师：比如我们要对一个列表中的数字进行排序。可以使用冒泡排序算法，也可以使用快速排序算法。 冒泡排序算法的基本思想是：每次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。这样一遍一遍地比较和交换，直到整个列表都有序为止。 快速排序算法的基本思想是：先从列表中选取一个元素作为基准值，然后把列表分成两部分，一部分比基准值小，一部分比基准值大。然后对这两部分分别进行快速排序，直到整个列表都有序为止。 （2）查找问题 师：再比如我们要在一个列表中查找一个特定的元素。可以使用顺序查找算法，也可以使用二分查找算法。 顺序查找算法就是从列表的第一个元素开始，依次比较每个元素，直到找到目标元素或者遍历完整个列表。 二分查找算法是针对有序列表的，每次取中间元素进行比较，如果目标元素等于中间元素，就找到了；如果目标元素小于中间元素，就在左边的子列表中继续查找；如果目标元素大于中间元素，就在右边的子列表中继续查找。 （三）巩固练习 1.基础练习 （1）让学生用两种不同的算法计算从1到50的和，并比较它们的执行次数和运行时间。 第一种算法：逐个相加。 total=0 for I in range(1,51): total+=i print(total) 第二种算法：使用公式。 sum=(1+50)*50//2 print(sum) 学生通过分析可以得出，第一种算法需要进行50次加法运算，执行次数较多；第二种算法只需要进行一次加法、一次乘法和一次除法运算，执行次数较少。在实际运行时间上，第二种算法也会比第一种算法短。 （2）给出一个包含10个数字的列表，让学生分别用顺序查找算法和二分查找算法查找一个特定的数字，并记录它们的执行次数和运行时间。 顺序查找算法： list=[2,5,8,11,14,17,20,23,26,29] target=17 found=False for num in list: if num==target: found=True break if found: print("找到了目标数字。") else: print("没有找到目标数字。") 二分查找算法： list=[2,5,8,11,14,17,20,23,26,29] target=17 left=0 right=len(list)-1 while left<=right: mid=(left+right)//2 if list[mid]==target: print("找到了目标数字。") break elif list[mid]<target: left=mid+1 else: right=mid-1 if left>right: print("没有找到目标数字。") 学生通过实践可以发现，顺序查找算法需要依次比较每个数字，最坏情况下需要比较10次；而二分查找算法每次都将查找范围缩小一半，最多需要比较4次。在运行时间上，二分查找算法也会更快。 2.拓展练习 （1）让学生思考如何改进冒泡排序算法，使其效率更高。 学生可以提出一些改进的方法，比如在某次遍历中如果没有发生交换，就说明列表已经有序，可以提前结束排序。或者可以记录最后一次交换的位置，下次遍历只需要到这个位置即可。 （2）给出一个更大的列表，让学生分别用不同的排序算法（如选择排序、插入排序、归并排序等）对其进行排序，并比较它们的效率。 选择排序算法： list=[12,5,18,3,21,8,15,6,24,10] for I in range(len(list)): min_index=i for j in range(i+1,len(list)): if list[j]<list[min_index]: min_index=j list[i],list[min_index]=list[min_index],list[i] print(list) 插入排序算法： Def merge_sort(list): If len(list)<=1: Return list mid=len(list)//2 left=merge_sort(list[:mid]) right=merge_sort(list[mid:]) return merge(left,right) def merge(left,right): result=[] i=j=0 while i<len(left) and j<len(right): if left[i]<right[j]: result.append(left[i]) i+=1 else: result.append(right[j]) j+=1 result.extend(left[i:]) result.extend(right[j:]) return result list=[12,5,18,3,21,8,15,6,24,10] sorted_list=merge_sort(list) print(sorted_list) 学生通过对不同排序算法的实践和比较，可以发现不同算法的效率差异，并且在实际应用中可以根据数据规模和特点选择合适的排序算法。 3.综合练习 （1）将学生分成小组，每个小组选择一个问题，设计多种不同的算法来解决这个问题，并比较它们的效率。然后，每个小组推选一位代表向全班同学展示自己小组的问题和解决方案，并进行讲解。 例如，一个小组选择的问题是计算两个矩阵的乘积。小组可以设计不同的算法，如直接按照矩阵乘法的定义进行计算，或者使用分治法等。然后比较这些算法的执行次数、运行时间等效率指标。 （2）让学生讨论在实际编程中，如何选择合适的算法来解决问题。 学生可以从问题的特点、数据规模、时间和空间复杂度等方面进行讨论，得出在选择算法时需要综合考虑各种因素，以达到最优的解决方案。 （四）课堂小结 1.回顾本节课的主要内容 师：同学们，今天我们学习了算法效率的比较。我们知道了解决同一个问题可以有不同的算法，不同的算法具有不同的效率。我们通过实例比较和算法分析，了解了算法执行的关键步骤和执行次数，体会了算法存在的效率差异。 2.强调重点和难点 师：本节课的重点是理解不同算法的效率差异，分析算法的关键步骤和执行次数。难点是准确评估不同算法的效率，选择合适的算法解决问题。希望同学们在课后能够多做一些练习，加深对这些知识的理解和掌握。 （五）作业布置 1.完成课后练习中的相关题目。 2.自己选择一个问题，设计多种不同的算法来解决这个问题，并比较它们的效率。 五、板书设计 1.不同算法解决同一问题 2.算法效率比较方法 3.关键步骤与执行次数 4.实例分析（求和、排序、查找等） 六、课后反思 在本节课的教学中，通过具体的例子引出不同算法解决同一个问题的概念，让学生直观地感受到算法效率的差异。在新课讲解环节，详细地分析了不同算法的过程、关键步骤和执行次数，使学生深入理解算法效率的影响因素。在巩固练习环节，设计了多种形式的练习，包括基础练习、拓展练习和综合练习，让学生在实践中比较不同算法的效率，提高了学生的分析问题和解决问题的能力。 然而，在教学过程中也发现了一些问题。部分学生在理解复杂算法的过程和效率分析时还有一些困难，需要在今后的教学中进一步加强引导。另外，在小组合作练习中，有些小组的讨论不够深入，需要在今后的教学中加强小组合作的指导，提高学生的合作能力和思维深度。 总的来说，本节课的教学目标基本达成，学生对算法效率的比较有了初步的认识和理解。在今后的教学中，要继续关注学生的学习情况，及时调整教学方法，提高教学效果。 学科网（北京）股份有限公司 $$