(共39张PPT)
第3节
常见的策略
在我们的生活、学习中，遇到的问题往往有各种不同的策略。选择合适的策略对于解决问题能够起到良好的促进作用，而一些策略也可以迁移到不同的问题中去。
一、常见的策略
作为一名体育委员，需要把如图3-3-1所示的8位同学，按照身高依次増高的顺序，从左到右排序，你该怎么做?
图3-3-1
八位同学身高不同
策略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、76、4号同学比较，最终回到6号学移动后空出的位置，此时有序组已有8个同学，排序完成。
上述四种不同的排队策，稍加完善就是快速排序、冒泡排序、选择排序、插入排序四种算法，它们不仅仅在体育课上可以用到，在许多排序问题中都能够使用，不过同样的策略在不同的问题中，使用的效率不尽相同。
二、选择策略
虽然排队策略的四种方法都能够解决问题，但是它们耗费的时间和存储空间是不同的，在制定策略的时候，应尽量从全局出发进行思考。
想一想:四种排队策略，哪一种排序效率更高?
试一试:列出寒假中你会做的事情，并用“策略2”的思维对这些事情的重要性进行排序。
拓展阅读
动态规划和贪心法
动态规划(
Dynamic
Programming)是解决多阶段决策问题常用的最优化方法之一，由美国数学家
Belman等人在195年提出，用于研究多阶段决策过程的优化问题。
这个方法简单来说，就是在当前状态下，想要进入下一阶段，什么样的选择是最优的。而且随着状态的变化，路径也会发生改变。动态规划是按照阶段划分的，把多阶段问题转化为一系列的单阶段问题，然后利用各个阶段之间的递推关系，逐个确定个阶段的最优化决策，最终堆叠出多阶段决策的最优化决策结果。
动态规划中，前一个阶段的结果影响着后一阶段的决定。当前的决策受到之前决策的影响，下个阶段的决策也会因为这次决策而发生改变。运用动态规划的思路，就是在这条决策链里面实时调整，求得每个阶段最优的那个解。
比如，在准备考试的过程中，你知道自己的目标(班级排名)也知道自己所处的阶段(在班级的大概排名)，还知道实现目标的路径(高效的学习方法和练习)。你要做的是根据整体的目标，选择每个阶段最优的行动。
然而现实生活中还有很多问题，并非这么理想。比如某个阶段的选择过多，又比如整体的目标不甚清晰。贪心法(
Greedy
Algorithm)是寻找最优解问题的常用方法。这种方法一般将求解过程分成若千个步骤，在每个步骤都应用贪心原则，即选取当前状态下最好的或最优的选择(局部最有利的选择)。贪心法的每次决策都以当前情况为基础并根据某个最优原则进行选择，不从整体上考虑其他各种可能的情况。即不用去计算每一种可能性，然后再得出一个最优解，而是节省大量计算资源，专注于当下，也就是俗称的“摸着石头过河”。
同样是寻求当下最优的解决方案，贪心法和动态规划的区别在于动态规划着眼于所有阶段，而贪心法仅仅关注当下最优。这就好比是去吃自助餐，采用动态规划的人会这样思考:在不影响晚上睡、消化或者体重不会大幅增重的情况下，我如何吃到总价值最大的美食?而贪心法，就是我们通常意义上的“扶墙进、扶墙出”，不管后续，在当下情况下能吃下多少就吃下多少。
当然，大多数情况下，由于选择策略的“短视”，整体的路线看起来是一个曲折的过程，而最终的目标，可能也和我们真正想要达到的目标相去甚远，但是在没有更好选择的情况下，用贪心法可以得到近似最优解。
四、课堂练习：
1、8
8的棋盘上面放着64个不同价值的礼物,每个小的棋盘上面放置一个礼物(礼物的价值大于0)
，一个人初始位置在棋盘的左上角,每次他只能向下或向右移动一步,并拿走对应棋盘上的礼物,结束位置在棋盘的右下角,请设计一个算法使其能够获得最大价值的礼物。
2、小明和小红两人按自然数顺序轮流报数,每人每次只能抱1个或2个数,谁能报出30,谁就获胜。小明想获胜,他该怎么办?
3、62根火柴,甲乙两人轮流拿,规定每人每次至少拿1根,最多拿3根,直到拿完为止,谁拿到最后一根就获胜。问:甲如何拿才能保证胜?
4、六瓶酒重量分别为(30
,
32
,
36
,
38
,
40
,
62)
,其中有五瓶啤,一瓶白。甲拿走两瓶啤,乙拿走的是甲的二倍,问哪瓶装的是白酒？
一个不错的营销策略
课堂小结
这节课，我通过学习、体验、分析生活中常见的四个排序策略，并比较、选择更高效、最合适的策略；培养了我们的信息意识和运用信息优化策略的思维方法！
板书设计
分析生活中常见的策略
常见的策略
选择合适的策略
PPT模板下载：www.1ppt.com/moban/
行业PPT模板：www.1ppt.com/hangye/
节日PPT模板：www.1ppt.com/jieri/
PPT素材下载：www.1ppt.com/sucai/
PPT背景图片：www.1ppt.com/beijing/
PPT图表下载：www.1ppt.com/tubiao/
优秀PPT下载：www.1ppt.com/xiazai/
PPT教程：
www.1ppt.com/powerpoint/
Word教程：
www.1ppt.com/word/
Excel教程：www.1ppt.com/excel/
资料下载：www.1ppt.com/ziliao/
PPT课件下载：www.1ppt.com/kejian/
范文下载：www.1ppt.com/fanwen/
试卷下载：www.1ppt.com/shiti/
教案下载：www.1ppt.com/jiaoan/
PPT论坛：www.1ppt.cn
Thanks！第3节
常见的策略
教学目标:
1.知识与技能
①总结常见的策略。
②选择最合适的策略。
2.过程与方法
通过四个排序策略体验、分析生活中常见的策略并比较、选择更高效、最合适的策略。
3.情感态度价值观
积极学习、体验、分析、掌握生活中更多的策略，比较、选择更高效的策略，培养学生的信息意识和运用信息优化策略的思维方法！
教学重难点：
①了解策略的制定过程。（重点）
②能将策路转变为伪代码。（难点）
教学过程
问题情境导入：
在我们的生活、学习中，遇到的问题往往有各种不同的策略。选择合适的策略对于解决问题能够起到良好的促进作用，而一些策略也可以迁移到不同的问题中去。
一、常见的策略
作为一名体育委员，需要把如图3-3-1所示的8位同学，按照身高依次増高的顺序，从左到右排序，你该怎么做?
图3-3-1
八位同学身高不同
策略1
总体思路:
选取一位同学，比这个同学矮的放在他左边，比这个同学高的放在他右边，并固定每一轮已选取过的同学。
继续对左右两边的同学执行上述过程，直到选取的同学左右两边未固定人数之和小于2。
排队过程:
随机选取4号同学为基准。
34127685
从右向左开始，依次将矮于4号的2号、1号同学放在左边，4号同学固定住。
31247685
4号左边的同学再重复上述步骤，可以固定住1、2、3号同学。
12347685
取6号同学为基准，将矮于6号的5号同学放在左边，大于6号的7号同学放在最右边，此时6号同学固定住，5号同学左右两边未固定人数之和为0，5号同学也固定住。
12347685
12345687
以8号同学为基准，将矮于他的7号同学放在左边，此时8号同学固定住。7号同学左右两边未固定人数之和为0，7号同学也固定住，此时所有同学排序完成。
12345687
12345678
●策略2
总体思路:
从左向右，依次两两比较、如果左边同学高于右边同学，就交换位置。
重复执行上述过程，直到有一轮没有任何一个同学移动位置。
排队过程：
34127685
第一轮交换位置的结果如下，可以将最高的8号同学固定在最右侧。
31246758
第二轮交换位置的结果如下，可以将7号同学固定。
12346578
第三轮交换位置的结果如下，可以将6号同学固定。
12345678
第四轮没有任何一个同学需要交换位置，所有同学排序完成。
策略3
总体思路:
每次选择当前队伍中的最矮的同学，并把他放在当前队伍的最左侧。每重复一次上述过程，当前队伍中就排除上一轮移动的同学，队伍长度便减一，直到没有同学可以移动。
排队过程:
第一轮排序，将最矮的1号同学和最左侧的3号同学交换位置，当前队伍去掉1号同学。
14327685
第二轮排序，将最矮的2号同学和最左侧的4号同学交换位置，当前队伍再去掉2号同学。
12347685
第三轮排序，3号同学在当前队伍中最矮，不需要调整，当前队伍再去掉3号同学。
12347685
第四轮排序与第三轮同理。第五轮排序，5号同学与最左側的7号同学交换位置。
12345687
第六轮排序与第三、四轮同理。第七轮排序交換7、8号同学位置，此时未排序队伍长度为1，经过第八轮排序，与第三、四、六轮同理，排序完成。
12345678
策略4
总体思路
从左向右，把左边第一个同学看成一个部分，拿右边的同学依次跟左边这个部分里的所有同学比较身高，如果高就站在右边，如果矮就站在左边，并把插队的同学算入左边部分。
重复执行上述过程，直到左边部分装满8个同学。
排队过程:
首先，将队伍分为有序组和无序组两部分，第一轮排序，默认将最左边的3号同学分为有序组，剩余同学为无序组。
34127685
第二轮排序，无序组最左边的4号同学出列与有序组内的同学从右到左开始比较，与3号同学相比较，因4号同学高于3号同学，则当前排列是有序的，4号同学回到空缺位置。此时3、4号同学组成了有序组，剩余同学则为无序组。
34127685
第三轮排序，1号同学出列比较，在有序组中从右到左依次与4号3号同学进行比较，4号同学高于1号同学，则4号同学右移一位，3号同学也高于1号同学，则3号同学也右移一位。最终1号同学在有序组的第一个空缺位置固定下来。
31427685
13427685
第四轮排序，2号同学依次与4、3、1号同学比较，4、3号同学依次右移一位，2号同学与1号同学比较，由于其高于1号同学，则回到3号同学空出来的位置。
12347685
第五轮排序与第二轮同理。
12347685
第六轮排序，6号同学依次与7、4号同学比较。
12346785
第七轮排序，8号同学只与7号同学比较。
12346785
第八轮排序，5号同学依次与8、76、4号同学比较，最终回到6号学移动后空出的位置，此时有序组已有8个同学，排序完成。
12345678
上述四种不同的排队策，稍加完善就是快速排序、冒泡排序、选择排序、插入排序四种算法，它们不仅仅在体育课上可以用到，在许多排序问题中都能够使用，不过同样的策略在不同的问题中，使用的效率不尽相同。
二、选择策略
虽然排队策略的四种方法都能够解决问题，但是它们耗费的时间和存储空间是不同的，在制定策略的时候，应尽量从全局出发进行思考。
想一想:四种排队策略，哪一种排序效率更高?
试一试:列出寒假中你会做的事情，并用“策略2”的思维对这些事情的重要性进行排序。
拓展阅读
动态规划和贪心法
动态规划(
Dynamic
Programming)是解决多阶段决策问题常用的最优化方法之一，由美国数学家
Belman等人在195年提出，用于研究多阶段决策过程的优化问题
这个方法简单来说，就是在当前状态下，想要进入下一阶段，什么样的选择是最优的。而且随着状态的变化，路径也会发生改变。动态规划是按照阶段划分的，把多阶段问题转化为一系列的单阶段问题，然后利用各个阶段之间的递推关系，逐个确定个阶段的最优化决策，最终堆叠出多阶段决策的最优化决策结果。
动态规划中，前一个阶段的结果影响着后一阶段的决定。当前的决策受到之前决策的影响，下个阶段的决策也会因为这次决策而发生改变。运用动态规划的思路，就是在这条决策链里面实时调整，求得每个阶段最优的那个解。
比如，在准备考试的过程中，你知道自己的目标(班级排名)也知道自己所处的阶段(在班级的大概排名)，还知道实现目标的路径(高效的学习方法和练习)。你要做的是根据整体的目标，选择每个阶段最优的行动
然而现实生活中还有很多问题，并非这么理想。比如某个阶段的选择过多，又比如整体的目标不甚清晰。贪心法(
Greedy
Algorithm)是寻找最优解问题的常用方法。这种方法一般将求解过程分成若千个步骤，在每个步骤都应用贪心原则，即选取当前状态下最好的或最优的选择(局部最有利的选择)。贪心法的每次决策都以当前情况为基础并根据某个最优原则进行选择，不从整体上考虑其他各种可能的情况。即不用去计算每一种可能性，然后再得出一个最优解，而是节省大量计算资源，专注于当下，也就是俗称的“摸着石头过河”。
同样是寻求当下最优的解决方案，贪心法和动态规划的区别在于动态规划着眼于所有阶段，而贪心法仅仅关注当下最优。这就好比是去吃自助餐，采用动态规划的人会这样思考:在不影响晚上睡、消化或者体重不会大幅增重的情况下，我如何吃到总价值最大的美食?而贪心法，就是我们通常意义上的“扶墙进、扶墙出”，不管后续，在当下情况下能吃下多少就吃下多少。
当然，大多数情况下，由于选择策略的“短视”，整体的路线看起来是一个曲折的过程，而最终的目标，可能也和我们真正想要达到的目标相去甚远，但是在没有更好选择的情况下，用贪心法可以得到近似最优解。
四、课堂练习：
1、8
8的棋盘上面放着64个不同价值的礼物,每个小的棋盘上面放置一个礼物(礼物的价值大于0)
，一个人初始位置在棋盘的左上角,每次他只能向下或向右移动一步,并拿走对应棋盘上的礼物,结束位置在棋盘的右下角,请设计一个算法使其能够获得最大价值的礼物。
2、小明和小红两人按自然数顺序轮流报数,每人每次只能抱1个或2个数,谁能报出30,
谁就获胜。小明想获胜,他该怎么办?
3、62根火柴,甲乙两人轮流拿,规定每人每次至少拿1根,最多拿3根,直到拿完为止,
谁拿到最后一根就获胜。问:甲如何拿才能保证胜?
4、六瓶酒重量分别为(30
,
32
,
36
,
38
,
40
,
62)
,其中有五瓶啤,一瓶白。甲拿走两瓶啤,乙拿
走的是甲的二倍,问哪瓶装的是白酒？
五、课堂小结
这节课，我通过学习、体验、分析生活中常见的四个排序策略，并比较、选择更高效、最合适的策略；培养了我们的信息意识和运用信息优化策略的思维方法！
六、板书设计
分析生活中常见的策略
常见的策略
选择合适的策略
