资源简介

(共19张PPT)
第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千米长的线路，如何迅速查出故障所在 如果沿着线路一小段一小段查找，困难很多。抢修工人每查一个点就要爬一次电线杆。想一想:抢修工人怎样工作最合理
实践创新
1.某市的出租车计价规则为:在不考虑延时等待的情况下，起步价为11元，可以行驶3千米;接下来的7千米，每千米为2元;如果超过10千米，则剩余的路程每千米3元。不到1千米的按1千米计算。若路程为26千米，如何乘车才会使费用最少
2.一份20页的试卷，打印了2份，打印出来的页码排序为:"1,、1、 2、2、3、3、4、4……20, 20"。传统的分开方法为左一张反扣，右一张反扣，以此类推，需要翻动40次才能完全将两份试卷分开。你能否提供一种更高效的方法来减少翻动次数
小结
生活中算法的优化
排序的算法优化
查找的算法优化

展开更多......

收起↑