川教版八上信息技术3.3 常见的策略(优化) 教学课件.pptx
四川省教育科学研究院八年级上册信息技术,第三单元:生活中的策略思维 第三节:常见的策略,NOW.,让我先来cosplay一下 体育老师!,超级英雄排队,超级英雄排队,抽象为数字比较大小,第一趟,第二趟,第三趟,第四趟,第五趟,排序完成,WIFI信号满格,策略,什么是策略?,策略 = 算法 = 解决问题的有限步骤的序列,程序 = 算法+数据结构 算法是程序的灵魂 -唐纳德.克努斯,排序算法(Sorting algorithm),冒泡排序(Bubble Sort) 算法思想: 第一趟两两比较相邻记录,反序则交换,第一趟排序的结果可以将最大的元素,交换到最后的位置,固定住最大的元素. 第二趟两两比较相邻记录,反序则交换,第二趟排序的结果可以将第二大的元素,交换到最后的位置,固定住第二大的元素. .重复以上操作直到最小的元素被固定住,排序完成.,两两比较,反则交换,学生活动:,利用刚学的冒泡排序的方法再来一次排队,冒泡排序效率分析,排队主要的时间花在了什么地方呢?,交换,比较,衡量算法效率的标准 时间复杂度 空间复杂度,冒泡排序效率分析,如何提高排序的效率?,减少交换,减少比较,更快的排序方法快速排序(Quick Sort),算法思想: 1随机选取一位同学作为基准值,所有比基准值矮的同学都站在他的左边,所有比基准值高的同学都站在他的右边,本轮被选为基准值的同学固定住位置,当前位置即为排序完成后的位置. 2对基准值左边的同学应用以上策略. 3对基准值右边的同学应用以上策略. 4直到被固定的同学的左右两边的人数之和小于2,排序完成,快速排序视频演示,祖师爷和祖师奶奶,-,祖师奶奶教你用纸笔演练算法,两两比较 反则交换,纸笔演算视频演示,题目,请将以下序列按从小到大的次序排列: 9 3 7 5 2,编程解决问题的一般步骤,明确输入|输出 抽象出数学模型 编写算法 把算法利用一种计算机编程语言转化为程序 测试及调试程序,直到程序能够得到预期的结果为止,编程实现,编程实现,作业,查阅资料了解其他排序算法: 如 插入排序 选择排序 希尔排序 堆排序 基数排序等 查阅资料了解其他算法思想: 如 贪心算法 枚举算法 动态规划算法等,thinks for watching