资源简介

(共35张PPT)
常见的策略
川教版
八年级上
新知导入
03
常见策略
3
4
1
2
7
6
8
5
作为一名体育委员，需要把如右图所示的8位同学，按照身高依次增高的顺序，从左到右排序，你该怎么做?
新知讲解
3
4
1
2
7
6
8
5
03
常见策略
总体思路：
选取一位同学，比这个同学矮的放在他左边，比这个同学高的放在他右边，并固定每一轮已选取过的同学。继续对左右两边的同学执行上述过程，直到选取的同学左右两边未固定人数之和小于2。
排队过程：
随机选取4号同学为基准。
新知讲解
03
常见策略
从右向左开始，依次将矮于4号的2号、1号同学放在左边，4号同学固定住。
3
4
1
2
7
6
8
5
4号左边的同学再重复上述步骤，可以固定住1、2、3号同学。
3
4
1
2
7
6
8
5
新知讲解
03
常见策略
取6号同学为基准，将矮于6号的5号同学放在左边，大于6号的7号同学放在最右边，此时6号同学固定住，5号同学左右两边未固定人数之和为0，5号同学也固定住。
3
4
1
2
7
6
8
5
3
4
1
2
7
6
8
5
新知讲解
03
常见策略
以8号同学为基准，将矮于他的7号同学放在左边，此时8号同学固定住。7号同学左右两边未固定人数之和为0，7号同学也固定住，此时所有同学排序完成。
3
4
1
2
7
6
8
5
3
4
1
2
7
6
8
5
新知讲解
03
常见策略
总体思路：
从左向右，依次两两比较，如果左边同学高于右边同学，就交换位置。重复执行上述过程，直到有一轮没有任何一个同学移动位置。
3
4
1
2
7
6
8
5
排队过程：
新知讲解
03
常见策略
第一轮交换位置的结果如下，可以将最高的8号同学固定在最右侧。
第二轮交换位置的结果如下，可以将7号同学固定。
3
4
1
2
7
6
8
5
3
4
1
2
7
6
8
5
新知讲解
03
常见策略
第三轮交换位置的结果如下，可以将6号同学固定。
第四轮没有任何一个同学需要交换位置，所有同学排序完成。
3
4
1
2
7
6
8
5
新知讲解
03
常见策略
总体思路:
每次选择当前队伍的最矮的同学，并把他放在当前队伍的最左侧。
每重复一次上述过程，当前队伍中就排除上一轮移动的同学，队伍长度便减一，直到没有同学可以移动。
排队过程:
第一轮排序，将最矮的1号同学和最左侧的3号同学交换位置，当前队伍去掉1号同学。
3
4
1
2
7
6
8
5
新知讲解
第二轮排序，将最矮的2号同学和最左侧的4号同学交换位置，当前队伍再去掉2号同学。
第三轮排序，3号同学在当前队伍中最矮，不需要调整，当前队伍再去掉3号同学。
03
常见策略
3
4
1
2
7
6
8
5
3
4
1
2
7
6
8
5
新知讲解
03
常见策略
第四轮排序与第三轮同理。第五轮排序，5号同学与最左侧的7号同学交换位置。
第六轮排序与第三、四轮同理。第七轮排序交换7、8号同学位置，此时未排序队伍长度为1，经过第八轮排序，与第三、四、六轮同理，排序完成。
3
4
1
2
7
6
8
5
3
4
1
2
7
6
8
5
新知讲解
03
常见策略
总体思路:
从左向右，把左边第一个同学看成一个部分。拿右边的同学一次跟左边这个部分里的所有同学比较身高，如果高就站在右边，如果矮就站在左边，并把插队的同学算入左边部分。
重复执行上述过程，直到左边部分装满8个同学。
排队过程:
首先，将队伍分为有序组和无序组两部分，第一轮排序，默认将最左边的3号同学分为有序组，剩余同学为无序组。
3
4
1
2
7
6
8
5
有序组
无序组
新知讲解
03
常见策略
第二轮排序，无序组最左边的4号同学出列与有序组内的同学从右到左开始比较，与3号同学相比较，因4号同学高于3号同学，则当前排列是有序的，4号同学回到空缺位置。此时3、4号同学组成了有序组，剩余同学则为无序组。
3
4
1
2
7
6
8
5
有序组
无序组
新知讲解
03
常见策略
第三轮排序，1号同学出列比较，在有序组中从右到左依次与4号、3号同学进行比较，4号同学高于1号同学，则4号同学右移一位，3号同学也高于1号同学，则3号同学也右移一位。最终1号同学在有序组的第一个空缺位置固定下来。
有序组
3
1
2
7
6
8
5
4
无序组
3
1
2
7
6
8
5
4
有序组
无序组
新知讲解
第四轮排序，2号同学依次与4、3、1号同学比较，4、3号同学依次右移一位，2号同学与1号同学比较，由于其高于1号同学，则回到3号同学空出来的位置。
第五轮排序与第二轮同理。
03
常见策略
3
1
2
7
6
8
5
4
有序组
无序组
3
1
2
7
6
8
5
4
有序组
无序组
新知讲解
03
常见策略
第六轮排序，6号同学依次与7、4号同学比较。
第七轮排序，8号同学只与7号同学比较。
3
1
2
7
6
8
5
4
有序组
无序组
3
1
2
7
6
8
5
4
有序组
无序组
新知讲解
03
常见策略
第八轮排序，5号同学依次与8、7、6、4号同学比较，最终回到6号同学移动后空出的位置，此时有序组已有8个同学，排序完成。
3
1
2
7
6
8
5
4
有序组
新知讲解
03
常见策略
策略1
快速排序
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序源代码如下：
新知讲解
03
常见策略
策略2
排冒泡序
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
冒泡排序源代码如下：
新知讲解
03
常见策略
策略3
选择排序
第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
选择排序源代码如下：
新知讲解
03
常见策略
策略4
插入排序
每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。
插入排序源代码如下：
新知讲解
调试运行四个算法的源程序
想一想：四种排队策略，哪一种排序效率更高?
任
务
一
试一试：列出寒假中你会做的事情，并用“策略2”的思维对这些事情的重要性进行排序。
任
务
二
合作探究
提出者：由美国数学家Bellman等人
提出时间：1957年
目的：用于研究多阶段决策过程的优化问题。
作用：是解决多阶段决策问题常用的最优化方法之一
概述：这个方法简单来说，就是在当前状态下，想要进入下一阶段，什么样的选择是最优的。而且随着状态的变化，路径也会发生改变。动态规划是按照阶段划分的，把多阶段问题转化为一系列的单阶段问题，然后利用各个阶段之间的递推关系，逐个确定每个阶段的最优化决策，最终堆叠出多阶段决策的最优化决策结果。
动态规划中，前一个阶段的结果影响着后一阶段的决定。当前的决策受到之前决策的影响，下个阶段的决策也会因为这次决策而发生改变。运用动态规划的思路，就是在这条决策链里面实时调整，求得每个阶段最优的那个解。
动态规划
(
Dynamic
Programming)
在准备考试的过程中，你知道自己的目标（班级排名），也知道自己所处的阶段（在班级的大概排名)，还知道实现目标的路径（高效的学习方法和练习)。你要做的是根据整体的目标，选择每个阶段最优的行动。
举例
步骤：
①建立数学模型来描述问题
②把求解的问题分成若干个子问题
③对每个子问题求解，得到子问题的局部最优解
④把子问题的解局部最优解合成原来解问题的一个解
贪心法(
Greedy
Algorithm)：
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解
课堂练习
利用我们这节课所学策略，选择一种策略帮助老师来按大小个给每位同学安排座位
总结本节课内容
课堂总结
常见的策略
选择策略
策略1：快速排序
策略2：冒泡排序
策略3：选择排序
策略4：插入排序
常见的策略
(四种排队策略，哪一种排序效率更高？)
板书设计
https://www.21cnjy.com/help/help_extract.php中小学教育资源及组卷应用平台
川教版信息技术八年级上册《常见的策略》教学设计
课题
常见的策略
单元
第三单元
学科
信息技术
年级
八年级
学习目标
总结常见的策略选择最合适的策略
重点
了解策略的制作过程
难点
能将策略转变为伪代码
教学过程
教学环节
教师活动
学生活动
设计意图
导入新课
看视频《月入百万》在我们的生活、学习中，遇到的问题往往有各种不同的策略。选择合适的策略对于解决问题能够起到良好的促进作用，而一些策略也可以迁移到不同的问题中去。
看视频
了解生活中的策略，知道策略可以应用到不同领域
讲授新课
一
常见的策略作为一名体育委员，需要把如下图所示的8位同学，按照身高依次增高的顺序，从左到右排序，你该怎么做?
策略1：总体思路选取一位同学，比这个同学矮的放在他左边，比这个同学高的放在他右边，并固定每一轮已选取过的同学。继续对左右两边的同学执行上述过程，直到选取的同学左右两边未固定人数之和小于2。排队过程：随机选取4号同学为基准。从右向左开始，依次将矮于4号的2号、1号同学放在左边，4号同学固定住。4号左边的同学再重复上述步骤，可以固定住1、2、3号同学。取6号同学为基准，将矮于6号的5号同学放在左边，大于6号的7号同学放在最右边，此时6号同学固定住，5号同学左右两边未固定人数之和为0，5号同学也固定住。以8号同学为基准，将矮于他的7号同学放在左边，此时8号同学固定住。7号同学左右两边未固定人数之和为0，7号同学也固定住，此时所有同学排序完成。策略2：总体思路从左向右，依次两两比较，如果左边同学高于右边同学，就交换位置。重复执行上述过程，直到有一轮没有任何一个同学移动位置。排队过程:第一轮交换位置的结果如下，可以将最高的8号同学固定在最右侧。第二轮交换位置的结果如下，可以将7号同学固定。第三轮交换位置的结果如下，可以将6号同学固定。第四轮没有任何一个同学需要交换位置，所有同学排序完成。策略3：总体思路每次选择当前队伍的最矮的同学，并把他放在当前队伍的最左侧。每重复一次上述过程，当前队伍中就排除上一轮移动的同学，队伍长度便减一，直到没有同学可以移动。排队过程:第一轮排序，将最矮的1号同学和最左侧的3号同学交换位置，当前队伍去掉1号同学。第二轮排序，将最矮的2号同学和最左侧的4号同学交换位置，当前队伍再去掉2号同学。第三轮排序，3号同学在当前队伍中最矮，不需要调整，当前队伍再去掉3号同学。第四轮排序与第三轮同理。第五轮排序，5号同学与最左侧的7号同学交换位置。第六轮排序与第三、四轮同理。第七轮排序交换7、8号同学位置，此时未排序队伍长度为1，经过第八轮排序，与第三、四、六轮同理，排序完成。策略4：总体思路从左向右，把左边第一个同学看成一个部分。拿右边的同学一次跟左边这个部分里的所有同学比较身高，如果高就站在右边，如果矮就站在左边，并把插队的同学算入左边部分。重复执行上述过程，直到左边部分装满8个同学。排队过程:首先，将队伍分为有序组和无序组两部分，第一轮排序，默认将最左边的3号同学分为有序组，剩余同学为无序组。第二轮排序，无序组最左边的4号同学出列与有序组内的同学从右到左开始比较，与3号同学相比较，因4号同学高于3号同学，则当前排列是有序的，4号同学回到空缺位置。此时3、4号同学组成了有序组，剩余同学则为无序组。第三轮排序，1号同学出列比较，在有序组中从右到左依次与4号、3号同学进行比较，4号同学高于1号同学，则4号同学右移一位，3号同学也高于1号同学，则3号同学也右移一位。最终1号同学在有序组的第一个空缺位置固定下来。第四轮排序，2号同学依次与4、3、1号同学比较，4、3号同学依次右移一位，2号同学与1号同学比较，由于其高于1号同学，则回到3号同学空出来的位置。第五轮排序与第二轮同理。第六轮排序，6号同学依次与7、4号同学比较。第七轮排序，8号同学只与7号同学比较。第八轮排序，5号同学依次与8、7、6、4号同学比较，最终回到6号同学移动后空出的位置，此时有序组已有8个同学，排序完成。上述四种不同的排队策略，稍加完善就是快速排序、冒泡排序、选择排序、插入排序四种算法，它们不仅仅在体育课上可以用到，在许多排序问题中都能够使用，不过同样的策略在不同的问题中，使用的效率不尽相同。①快速排序：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。源程序如下：②冒泡排序：类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。源程序如下：③选择排序第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。源程序如下：④插入排序每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。源程序如下：二
选择策略虽然排队策略的四种方法都能够解决问题，但是它们耗费的时间和存储空间是不同的，在指定策略的时候，应尽量从全局出发进行思考。任务一想一想：四种排队策略，哪一种排序效率更高?试一试：列出寒假中你会做的事情，并用“策略2”的思维对这些事情的重要性进行排序。拓展阅读：看视频《了解动态规划》动态规划(
Dynamic
Programming)：作用：是解决多阶段决策问题常用的最优化方法之一提出时间：1957年提出者：由美国数学家Bellman等人目的：用于研究多阶段决策过程的优化问题。概述：这个方法简单来说，就是在当前状态下，想要进入下一阶段，什么样的选择是最优的。而且随着状态的变化，路径也会发生改变。动态规划是按照阶段划分的，把多阶段问题转化为一系列的单阶段问题，然后利用各个阶段之间的递推关系，逐个确定每个阶段的最优化决策，最终堆叠出多阶段决策的最优化决策结果。动态规划中，前一个阶段的结果影响着后一阶段的决定。当前的决策受到之前决策的影响，下个阶段的决策也会因为这次决策而发生改变。运用动态规划的思路，就是在这条决策链里面实时调整，求得每个阶段最优的那个解。举例：在准备考试的过程中，你知道自己的目标（班级排名），也知道自己所处的阶段（在班级的大概排名)，还知道实现目标的路径（高效的学习方法和练习)。你要做的是根据整体的目标，选择每个阶段最优的行动。看视频《贪心法》贪心法(
Greedy
Algorithm)：在对问题求解
(?https:?/??/?baike.?/?item?/?%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3?/?6693186"
\t
"https:?/??/?baike.?/?item?/?%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95?/?_blank?)时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法
(?https:?/??/?baike.?/?item?/?%E7%AE%97%E6%B3%95?/?209025"
\t
"https:?/??/?baike.?/?item?/?%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95?/?_blank?)得到的是在某种意义上的局部最优解步骤：??①建立数学模型来描述问题?②把求解的问题分成若干个子问题?③对每个子问题求解，得到子问题的局部最优解?④把子问题的解局部最优解合成原来解问题的一个解
课堂练习：利用我们这节课所学策略，选择一种策略帮助老师来按大小个给每位同学安排座位
认真听老师讲解，不断练习
小组合作完成看视频看视频
了解四种策略，知道策略的应用，深刻体会科技的不断发展给生活带来的便利学以致用，学会策略的应用了解什么是动态规划了解什么是贪心法
课堂小结
总结本节课所讲内容
学生总结概况
梳理本节课的知识点，完成学习目标，培养总结概况能力
板书设计
5
8
6
1
4
3
2
7
2
1
4
7
3
5
8
6
2
4
6
5
8
7
1
3
1
7
8
6
4
3
5
2
7
4
6
3
1
5
2
8
5
7
6
4
3
1
2
8
7
5
6
4
3
2
1
8
8
5
7
1
6
4
3
2
5
8
6
7
2
1
4
3
8
5
7
6
4
1
2
3
6
4
3
2
1
8
7
5
5
4
8
7
6
2
1
3
1
3
5
8
6
7
2
4
5
6
7
8
3
4
2
1
8
6
7
5
4
3
2
1
7
5
6
4
3
2
1
8
7
8
5
6
4
3
2
1
6
1
3
2
7
5
8
4
有序组
无序组
4
3
6
1
2
7
5
8
有序组
无序组
4
1
3
6
2
7
5
8
无序组
有序组
6
7
5
8
2
3
4
1
无序组
有序组
4
3
2
7
5
8
1
6
有序组
无序组
3
4
2
7
5
8
1
6
有序组
无序组
7
6
4
1
5
2
3
8
有序组
无序组
4
1
5
2
3
8
7
6
有序组
无序组
8
6
7
5
1
2
3
4
有序组
策略1：快速排序
策略2：冒泡排序
策略3：选择排序
策略4：插入排序
常见的策略
常见的策略
选择策略
21世纪教育网
www.21cnjy.com
精品试卷·第
2
页
（共
2
页）
HYPERLINK
"http://www.21cnjy.com/"
21世纪教育网(www.21cnjy.com)

展开更多......

收起↑