资源简介

(共29张PPT)
第3课 算法的优化
1.理解算法优化的意义
2.学会用不同的算法来解决问题，并能对算法进行优化
3.学会多视角分析问题，能利用高效的办法解决问题，养成细致缜密思考问题的习惯
学习目标
田忌
齐威王
上
下
下
上
中
中
你对孙膑赛马的做法有什么想法？
活动一 生活中算法的优化
活动一 生活中算法的优化
著名数学家华罗庚先生“烧水泡茶"
它的整个过程有五道基本工序：
想一想
烧开水（15分钟）
洗茶壶（1分钟）
洗茶杯（2分钟）
拿茶叶（1分钟）
洗水壶（1分钟）
泡茶
如何在最短的时间喝上茶水呢？
活动一 生活中算法的优化
你能为“烧水泡茶”提供几种解决方案？你认为那种方案是最快捷的？为什么？
李明从早上起床到上学前这段时间，要做以下几件事:叠被(2分钟)、洗脸(3分钟)、刷牙(2分钟)、刷锅(1分钟)、煮鸡蛋(10分钟)、吃早点(10分钟)。
活动一 生活中算法的优化
做一做
请你为李明设计一套最节约时间的方案
刷锅1分钟——煮鸡蛋10分钟（同时叠被2分、洗脸3分、刷牙2分）——吃早点10分，总用时21分钟
统筹方法
统筹方法是一种可以工作效率、安排工作进程的数学方法，应用广泛。统筹方法的作用是把工序安排好，避免窝工，“缩短工时，提高工作效率”。
结合P14加油站思考：
1.什么是统筹方法？
2.对于统筹方法的应用，你觉得对你有什么帮助？
3.生活中哪些地方可以用到统筹方法？请举例说明。
一位商人有9枚银币，其中有1枚略轻，是假硬币，你能用天平（不用砝码）将假硬币找出来吗？请给出最优化的算法。
活动一 生活中算法的优化
试一试
活动一 生活中算法的优化
第一步
第二步
活动一 生活中算法的优化
第三步
活动一 生活中算法的优化
第一步：等分三份
第二步：随机选取两份，用天平称，可确定假币在哪一份中
2.1 相等，则假币在剩余一份中
2.2 不等，则假币在轻的一份中
第三步：在已确定有假币的一份中，任选两枚，用天平称
3.1 相等，则最后剩下的那枚是假币
3.2 不等，则轻的那枚是假币
活动一 生活中算法的优化
蚂蚁的视力较差，但却能在黑暗的世界中快速找到事物，而且可以找到从洞穴到食物的最短路径。蚂蚁是如何做到的呢？
读一读
最优化方法
你能列举生活中最优化的例子吗？
1.企业会考虑“在一定成本下，如何使利润最大化”；
2.考虑如何花最少的钱办最多的事。
算法大家庭
冒泡排序
快速排序
顺序查找
二分查找法
活动二 排序的算法优化
活动二 排序的算法优化——冒泡排序
将12、-3、4、8、-5按由小到大的顺序排列出来，人工是如何排序的？请用自然语言说一说排序的算法过程。
第一轮
12、 -3、 4、 8、 -5
想一想
-3、 12、 4、 8、 -5
-3、 4、 12、 8、 -5
-3、 4、 8、 12、 -5
-3、 4、 8、 -5、 12
活动二 排序的算法优化——冒泡排序
1.相邻两个数比较
2.前者大于后者则交换位置，否则位置不变
活动二 排序的算法优化——冒泡排序
第2轮排序的结果为：
（-3、_________、-5）
第3轮排序的结果为：
（-3、_________）
第4轮排序的结果为：
（-5、 -3、 4、 8、 12）
12
8
12
试一试
4
8
-5
4
活动二 排序的算法优化——冒泡排序
根据上面的排序过程，小组讨论一下：
5个数在冒泡排序过程中经过了多少轮比较？
n个数据就比较n-1轮
活动二 排序的算法优化
图书管理员的一项重要工作是把学生还回来的书(如100本)按编号顺序放人书架。如果你是管理员，应如何快速将这些书放回书架呢
试一试
传统方法
经过算法优化的方法（快速排序法）
活动二 排序的算法优化
传统方法
经过算法优化的方法（快速排序法）
一本一本按照编号还回到对应书架。要放回100本书，需要跑（ ）次。
先从这堆书里随便挑出一本，把比它编号小的（ ） ，比它编号大的放右边。分成两堆后，再（ ）步骤，直到所有的书都按序号排好。
再把从小到大排序后的书按照书架顺序归类，每个书架跑一次，这样并不需要跑很多次就完成了。
100
放左边
重复该
活动二 排序的算法优化
编号50
1-49
51-100
编号25
1-24
26-50
编号75
51-74
76-100
【思考】
经过排放图书,你能总结快速排序的思想么？
活动二 排序的算法优化——快速排序法
最高效
“分治”思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序。
44 75 23 43 55 12 64 77 33
23 43 12 33 44 75 55 64 77
23 43 12 33
44
75 55 64 77
23
12
43
33
44
75
55
64
77
43
33
12
23
55
64
77
75
44
活动三 查找的算法优化
13500
节目：选手限定时间内猜某一物品的售价。猜中则把物品奖励给选手。
智能手表的价格，价格在500~1000之间。
想一想
碰运气
报价技巧
请小组设计出一种快速可行的猜价方案
活动三 查找的算法优化
活动三 查找的算法优化——顺序查找
顺序查找：
从第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功，如果到最后一个元素仍没有目标元素，则查找失败。
500元
600元
700元
800元
...
...
...
活动三 查找的算法优化——顺序查找
二分查找法：
先找有序数列的中点，利用中点将范围分为两部分，再经比较不断找中点并一步一步逼近目标，最后按要求确定一个较小范围。
500
1000
750
875
820
感谢各位观看

展开更多......

收起↑