算法的优化

算法的优化学习目标知识目标理解算法优化的意义。技能目标学会用不同的算法来解决问题，并能对算法进行优化。情感目标学会对视角分析问题，能利用高效的方法解决问题，养成细致缜密思考问题的习惯。材料一•孙膑是战国时期著名的军事家。齐国的将军田忌经常同齐威王赛马。马分上、中、下三等，在比赛时，总是以上等马对上等马，中等马对中等马，下等马对下等马。齐威王每一个等级的马都要比田忌的强，所以田忌总是输。孙膑给田忌出了个主意，比赛时，让他以下等马对齐威王的上等马，再以上等马对他的中等马，最后以中等马对他的下等马。比赛结束，田忌以三局两胜的战绩取得了胜利。同样的马匹，仅仅调换了比赛顺序，就得到了反败为胜的结果。从算法角度讲，孙膑的策略是一种经过优化的算法。自我探究•这个材料说明了什么？什么叫做算法的优化？知识回顾•算法是做某件事情或解决某一问题的方法、步骤、过程和程序。探索新知•算法的优化指的就是用最优化的方法来解决问题。最优化方法是一种数学方法，它就是研究在给定的条件下如何寻求某些因素的组合、统筹、替代、转换等，以使某一指标（或结果）达到最优的一些学科的总称。它包括生活中的算法优化、排序的算法优化和查找的算法优化。材料二：•著名数学家华罗庚先生在1964年所著的《统筹方法平话》里举了一个“烧水泡茶”的例子：一个人口渴了，想泡一壶茶喝，需要烧开水、洗茶具、拿茶叶。他怎样才能在最短的时间喝上茶水呢？小组讨论•你能为“烧水泡茶”提供几种解决方案?你认为哪种方案是最快捷的？为什么？算法比较方法一：①烧水②水烧开同时，洗茶壶，洗茶杯，拿茶具（16分钟）③沏茶方法二：①烧水②水烧开之前，洗茶壶，洗茶杯，拿茶具（20分钟）③沏茶方法三：①烧水②水烧开之后，洗茶壶，洗茶杯，拿茶具（20分钟）③沏茶材料三：•李明从早上起床到上学前这段时间，要做以下几件事：叠被（2分钟）、洗脸（3分钟）、刷牙（2分钟）、刷锅（1分钟）、煮鸡蛋（10分钟）、吃早点（10分钟）。小组讨论：请你为李明设计一套最节省时间的方案。解决方法•首先，刷锅；•然后，煮鸡蛋的同时，叠被，洗脸，刷牙；•最后，吃早点。（共21分钟）材料四：•某车间只有一台高精度的机床，常常出现很多零件同时要求用这台机床加工的情况。现有6个零件要求加工，每个零件加工耗时如下表所示。零件加工耗时（小时）零件加工耗时（小时）11.840.82251.230.561.6试一试•按照怎样的顺序来加工零件，才能使这6个零件在车间里停留的平均时间最少？问题点拨：所谓排序，就是使一串记录按照其中的某个或某些关键字的大小递增或递减排列的操作。排序问题是指在一定的约束条件下对工件和机器按时间进行分配和安排次序，使某一个或某一些目标达到最优。工件是被加工的对象，是要完成的任务；机器是提供加工的对象，是完成任务所需要的资源。排序问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。解析：•对于一台机器N个零件的排序问题，只要可加工的零件数越大，配上加工的时间越少，即按加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使每个零件停留的平均时间越少。练一练一位商人有9个银币，其中有一枚略轻，是假银币。能用天平（不用砝码）将假银币找出来吗？请给出最优化的算法。算法分析•算法一：•①任取2枚银元分别放在天平的两边，如果天平左右不平衡，则轻的那一边就是假银元；如果天平平衡，则进行第二步。•②取下右边的银元，然后把剩下的7枚银元依次放在右边进行称量，直到天平不平衡，偏轻的那一边就是假银元．算法二：•①任取两枚银元分别放在天平的两端，如果天平左右不平衡，则轻的那一边是假银元；否则进行第二步。•②重复执行第一步，如果前4次天平都平衡，则剩下的那一枚是假银元。•算法三：•①把9枚银元平均分成3组，每组3枚．②先将其中两组放在天平的两边，如果天平左右不平衡，那么假银元就在轻的那一组；如果天平左右平衡，则假银元就在未称量的那一组内。•③取出含有假银元的那一组，从中任取2枚银元放在天平左右两边进行称量，如果天平左右不平衡，则轻的那一边是假银元；如果天平左右平衡，则未称的那一枚就是假银元．想一想蚂蚁的视力较差，但却能在黑暗的世界中快速找到食物，而且可以找到从洞穴到事物的最短路径。小组探究，你知道蚂蚁是如何做到的吗？研究表明：蚂蚁在行走过程中会释放一种称为“信息素”的挥发性化学物质，用来标识自己的行走路径。在寻找食物的过程中，蚂蚁会根据信息素的浓度选择行走的方向，并最终到达食物所在的地方。一点通起先，由于地面上没有信息素，因此蚂蚁们的行走路径是随机的，可以理解为“地毯式”搜寻食物。蚂蚁们在行走的过程中会不断的释放信息素，标识自己的行走路径。随着时间的推移，有若干只蚂蚁找到了食物，此时便存在若干条从洞穴到食物的路径。由于蚂蚁的行为路径是随机分布的，长路径上的信息素随着时间的流逝浓度要比短路径上的低，因此在单位时间内，短路径上的蚂蚁数量要比长路径上的蚂蚁数量多，信息素浓度也就越来越高。这为后面的蚂蚁们提供了明确的方向指引，越来越多的蚂蚁会聚集到最短的路径上去。小组讨论•畅所欲言，你所了解的模仿生物行为的算法有哪些呢？请举例说明。群体智能优化算法主要模拟了昆虫、兽群、鸟群和鱼群的群集行为，这些群体按照一种合作的方式寻找食物，群体中的每个成员通过学习它自身的经验和其他成员的经验来不断地改变搜索的方向。群体智能优化算法的突出特点就是利用了种群的群体智慧进行协同搜索，从而在解空间内找到最优解。模拟生物理想自由分布模型的萤火虫算法………材料五将12、-3、4、8、-5按由小到大的顺序排列出来，人工是如何排序的呢？请用自然语言说一说排序的算法过程。尝试使用“冒泡排序”的算法对数字进行排序。你知道吗？计算机有很多对数据排序的方法，其中“冒泡排序法”是排序的常用方法。以给出的5个数据为例，在比较时，首先将第1个数和第2个数比较，如果第1个数大于第2个数，则交换两个数的位置，接着比较第2个数与第3个数。依次类推，直到最后两个数比较完毕。数据从左到右比较一遍为一轮排序，每轮排序都把需要排序的数据列中最大的数据交换位置到最后位置。这种排序将一直进行到全部数据都有序、没有交换为止。分析第一轮：（-3、4、8、-5）12第二轮：（-3、4、-5）812第三轮：（-3、-5）4812第四轮：（-5）-34812第五轮：-5、-3、4、8、12试一试模拟计算机使用冒泡排序法对数据“11、-2、4、9、-6”进行排序，写出每轮排序结果。根据排序过程，讨论：5个数在冒泡排序过程中经过了多少次比较？最多需要进行多少次交换？材料六图书管理员的一项重要工作是把学生还回来的书（如100本）按编号顺序放入书架。如果你是管理员，应如何快速将这些书放回书架呢？传统方法：一本一本按编号还回到对应书架。要放回100本书，需要跑（）次。快速排序法：先从这堆书中随便挑出一本，把比它编号小的放左边，比它编号大的放右边。分成两堆后，再分步直到所有的书都按序号排好。最后把从小到大排序后的书按照书架顺序归类，每个书架跑一次，这样并不需要跑很多次就完成了。“分治”思想，先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序。自我探究什么是查找？定义查找是在大量信息中寻找一个特定的信息元素。在计算机应用中，查找是常用的基本算法。用关键字标识一个数据元素，查找时根据给定的某个值，在表中确定一个关键字的值等于给定值的数据元素。在计算机中进行查找的方法是根据表中的记录组织结构确定的。快速高效的查找到需要的信息，是对计算机查找功能的一个重要要求。分类Ⅰ顺序查找从第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功；如果最后一个元素仍没有目标元素，则查找失败。Ⅱ二分查找先找有序数列的中点，利用中点将范围分为两部分，再经比较不断找中点并一步一步逼近目标，最后按要求确定一个较小范围。想一想中央电视台曾经有一档节目，要求选手在限定时间内猜中某一物品的售价。如果猜中，就把物品奖励给选手。例如：猜一种手机的价格，手机价格在500~1000之间。选手开始报价：“1000元”主持人回答：“高了”。——800元。——低了。——880元。——高了。——850元。——猜中了。表面看，看猜价格具有很大的碰运气的成分。实际上游戏，报价过程具有一定的技巧性。想一想这个技巧的什么。你知道吗？同一个问题，可用不同的算法解决，而一个算法质量的优劣将影响到算法乃至程序的效率。评价一个算法是否优秀，可以从一下的几个方面进行考虑：①时间耗费:执行算法所需要的工作量。②空间占用：消耗的内存空间。③正确性：评价一个算法优劣的最重要的标准。④可读性：一个算法可供人们阅读的容易程度。⑤容错性：一个算法对不合理数据输入的反应能力和处理能力。你收获到了什么？