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