(
课件网) 第3课 算法的优化 信息技术青岛-出卷网-初中第三册 同样的马，为什么结果不一样了？ 田忌 齐威王 上 中 下 上 中 下 学习目标： 理解算法优化的意义 学会用不同的算法来解决问题，并能对算法进行优化 学会多视角分析问题，能利用高效的方法解决问题，养成细致缜密思考问题的习惯 活动一 生活中算法的优化 华 罗 庚 你能为“烧水泡茶”提供几种解决方案？ 你认为哪种方案是最快捷的？ 洗水壶1分钟 烧开水15分钟 洗茶壶1分钟 洗茶杯2分钟 拿茶叶1分钟 泡茶1分钟 洗水壶1分钟 拿茶叶1分钟 洗茶杯2分钟 洗茶壶1分钟 烧开水15分钟 泡茶1分钟 思考： 探讨对统筹方法的认识和应用。 尝试列举生活中应用统筹方法的实例。 李明从早上起床到上学前这段时间要做以下几件事： 叠被（2分钟）、洗脸（3分钟）、刷牙（2分钟）、 刷锅（1分钟）、煮鸡蛋（10分钟）、吃早点（10分钟） 学以致用 聪明的你能为李明同学设计一套最节约时间的方案吗？ 一位商人有9枚银币，其中有一枚略轻，是假银币，你能用天平（不用法码）将假银币找出来吗？ 请给出最优化的算法。 如何找出假银币 蚂蚁的视图较差，但却能在黑暗的世界中快速找到食物，而且可以找到从洞穴到食物的最短路径。蚂蚁是如何做到的呢？ 神奇的蚂蚁 活动二 排序的算法优化 排序的关键是比较。我们生活中常见的比较有大小、多少、轻重等。这些比较都是基于数字的比较。数字的排序是计算机科学中算法研究的一个重点。 【想一想】 将12、-3、4、+8、-5按由小到大的顺序排列出来， 人工是如何排序的呢？请用自然语言说一说排序的算法过程。 4 8 -5 原始数据 第一轮 12 -3 第一轮结束 第二轮 12 -3 4 8 -5 12 -3 4 8 -5 -3 4 第二轮结束 冒泡排序法 试一试 请你模拟计算机使用冒泡排序法对数据“11、-2、4、+9、-6”进行排序，写出每轮排序的结果 第一轮：-2、4、9、-6、11 第二轮：-2、4、-6、9、11 第三轮：-2、-6、4、9、11 第四轮：-6、-2、4、9、11 【快速排序法】 图书管理员的一项重要工作是把学生还回来的书(如100本)按编号顺序放人书架。如果你是管理员，应如何快速将这些书放回书架呢 2.经过算法优化的方法(快速排序法) 先从这堆书里随便挑出一本，把比它编号小的（ ） ，比它编号大的放右边。分成两堆后，再（ ）步骤，直到所有的书都按序号排好。 再把从小到大排序后的书按照书架顺序归类，每个书架跑一次，这样并不需要跑很多次就完成了。 1.传统方法 一本一本按照编号还回到对应书架。要放回100本书，需要跑（ ）次。 【思考】 经过排放图书，你能总结快速排序的思想么？ 100 放左边 重复 练一练 请你模拟计算机使用快速排序法对数据“11、-2、4、+9、-6”进行排序，写出每轮排序的结果 第一轮：-2、4、9、-6、11 第二轮：-6、-2、4、9、11 以11为基准值，比11小的放在左边 以-2为基准值，比-2小的放在左边，大的放右边 活动三 查找的算法优化 【查找的算法优化】 中央电视台曾经有一档节目，要求选手在限定时间内猜中某一物品的售价。如果猜中，就把物品奖励给选手。例如:猜一种手机的价格，手机价格在500--1000之间。选手开始报价:"1000元。”主持人回答:“高了。” —800元。 —低了。 —880元 —高了。 —850元。 —猜中了。 【思考】 猜价格具有一定的技巧性，你知道这种技巧么？ 二分查找是先找有序数列的中点，利用中点将范围分为两部分，再经比较不断找中点并一步一步逼近目标，最后按要求确定一个较小范围。 【想一想】 从某水库闸房到防洪指挥部的电话线路发生了故障。这是一条10千米长的线路，如何迅速查出故障所在 如果沿着线路一小段一小段查找，困难很多。抢修工人每查一个点就要爬一次电线杆。 ... ...
