第3课 算法的优化 课件(共26张PPT) 2022—2023学年青岛版初中信息技术第三册

资源下载
  1. 二一教育资源

第3课 算法的优化 课件(共26张PPT) 2022—2023学年青岛版初中信息技术第三册

资源简介

(共26张PPT)
同样的马,为什么结果不一样了?
想一想:
假如你是孙膑,
你有什么好办法
取胜吗?
信息技术青岛出版社初中第三册
算 法 的


学习目标:
理解算法优化的意义
学会用不同的算法来解决问题,并能对算法进行优化
学会多视角分析问题,能利用高效的方法解决问题,养成细致缜密思考问题
的习惯
1
生活中算法的优化
自主探究:
任务一:
一个人口渴了,想泡一壶茶喝,需要烧开水、洗茶具、拿茶叶。
他怎么才能在最短的时间喝上茶水呢?
洗水壶1分钟
1、你能为“烧水泡茶”提供几种解
烧开水15分钟
洗茶壶1分钟
决方案?
2、你认为哪种方案是最快捷的?
洗茶杯2分钟
拿茶叶1分钟
华 罗 庚
统筹方法与算法
方案一:
洗水壶1分钟
烧开水15分钟
洗茶壶1分钟
洗茶杯1分钟
拿茶叶1分钟
泡茶
共用时19分钟
方案二:
烧开水15分钟
洗茶壶1分钟
洗茶杯1分钟
拿茶叶1分钟
共用时16分钟
泡茶
结论:统筹方法与算法相结合,可以优化算法流程!
洗水壶1分钟
节约时间
任务二:
李明从早上起床到上学前这段时间要做以下几件事:
叠被子(2分钟)、洗脸(3分钟)、刷牙(2分钟)、
刷锅(1分钟)、煮鸡蛋(10分钟)、吃早点(10分钟)
聪明的你能为李明同学设计一套最节约时间的方案吗?
如何找出假银币
任务三:
一位商人有9枚银币,其中有一枚略轻,是假银币,你能用天平
(不用法码)将假银币找出来吗?
请给出最优化的算法。
最佳算法:
1、将银币分成3份,设为ABC;
2、先称A和B,若平衡的话假银币就在C中,不平衡的话就在轻的那份中;,
3、再在假银币堆里再随机拿出两个银币称,平衡的话假银币就是剩下的那个,不平衡的话,轻的那个就是假的!
共用到2次称量
神奇的蚂蚁
蚂蚁的视图较差,但却能在黑暗的世界中快速找到食物,而且可以找到从
洞穴到食物的最短路径。蚂蚁是如何做到的呢?
蚁群算法
蚂蚁在行走的过程中会释放
一种称为“信息素”的挥发性
化学物质,用来标识自己的行
走路径。在寻找食物的过程中,
蚂蚁会根据信息素的浓度选择
行走的方向,并最终以最短路
径找到食物。
观察一下
图2
图1
2
排序的算法优化
自主探究:
任务四:
1、认真阅读教材P16,探究什么是排序?这些排序分别依据什么?排序的
关键是什么?
排序:就是使一串记录按照其中的某个或某些关键字的大小递增或递减排列的操作。
比较:排序的关键是比较,生活中常见比较大小、多少、轻重等
自主探究:
将10、5、4、8、3按由小到大的顺序排列出来, 人工是如何排序的呢?请
用自然语言说一说排序的算法过程。
10、5、4、8、3
第四轮
第一轮
第三轮
第二轮
5、10、4、8、3
4、5、8、3、10
5、4、10、8、3
5、4、8、10、3
5、4、8、3、10
4、5、8、3、10
4、5、3、8、10
4、5、3、8、10
4、3、5、8、10
3、4、5、8、10
精彩呈现:
3、认真阅读教材p16(加油站)内容,冒泡排序执行步骤思想是什么呢?
首先将第1个数与第2个数比较,如果第1个数大于第2个数,则交换两个
数的位置,接着比较第2个与第3个数。依此类推,直到最后两个数比较
完毕。
想一想
任务七:
图书管理员的一项重要工作是把学生还回来的书(如100本)按编号顺序放入书
架。如果你是管理员,应如何快速将这些书放回书架呢?
1、传统方法:
一本一本按照编号还回到对应书架。要放回100本书,需要跑( )次。
2、认真阅读教材P17,探究计算机又是用什么方法对这些数据排序的呢?
快速排序
100
快速排序法
思想:
选择一个基准值,通过一趟排序,将待排序队列分为三部分,小于等于基准值的一
部分,基准值,大于等于基准值的一部分。然后用同样的方法递归的排序小于等于基
准值的一部分和大于等于基准值的一部分。
自主探究:
具体实现:
图示:
选择基准值
1,选择最边上(左右都可以)
2,随机法
3,三数取中法
对于2,3,选好基准值后,再把基准值交换到最边上
遍历整个区间,分割成三部分
一个从左边开始(begin),一个从右边开始
(end)
过程中保证左边值都比基准值小
右边都比基准值大
如果遇到不符合的情况,进行交换后继续
最后把基准值交换到中间
合作交流:
小游戏--猜价格
某件物品价格在100—1000之间,你几次能猜中该物品的价格?
该物品的价格为:700
3
查找的算法优化
自主探究:
任务八:
1、认真阅读教材P18,探究什么是查找

查找:就是在大量信息中寻找一个特定的信息元素。
2、认真阅读教材P18,探究计算机是用什么方法来快速查询信息的?
①顺序查找:是从第一个元素开始一个一个向下查找,如果有和目标一致的元素,查找成功;如果到最后一个元素扔没有目标元素,则查找失败。
②二分查找:则是先找有序列的中点,利用中点将范围分为两部分,再经比较不断
找中点并一步一步逼近目标,最后按要求确定一个较小范围。
合作交流:
幸运52
中央电视台曾经有一档节目,要求选手在限定时间内猜
中某一物品的售价。如果猜中,就把物品奖励给对手。
现在有一款手机,价格在500~1000之间。请问手机的价
格是多少?
二分查找
低了
低了
(1000+500)/2=7
(1000+750)/2=8
(1000+875)/2=937.5
50
75




低了
(750+500)/2=62
(750+625)/2=687.
(875+750)/2=812.5
5
5


(625+500)/2=562.5
二分查找
梳理总结
生活中算法的优化
排序的算法优化
冒泡排序
快速排序
查找的算法优化
顺序查找
二分查找
我实践我创新
一份20页的试卷,打印了2份,打印出来的页码排序为:“1、1、2、2、3、
3、4、4……20、20”。传统的分开方法为左一张反扣,右一张反扣,以此
类推,需要翻动40次才能完全将两份试卷分开。
你能否提供一种更高效的方法来减少翻动次数?
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 …………
18 18 19 19 20 20
智能时代 追逐梦想
同学们,老师相信,在你们当中一定有未来
的任正非、乔布斯。在这个智能时代,大胆追求
梦想,虽然梦想遥不可及,但只要你努力就一定
会梦想成真。

展开更多......

收起↑

资源预览