算法的优化.pptx

第3课 算法的优化我阅读我思考：田忌赛马 孙膑是战国时期著名的军事家。齐国的将军田忌经常同齐威王赛马。马分上、中、下三等，在比赛时，总是以上等马对上等马，中等马对中等马，下等马对下等马。齐威王每个等级的马都要比田忌的强，所以田忌总是输。田忌齐威王活动一 生活中算法的优化 著名数学家华罗庚先生在1964年所著的统筹方法平话里举了一个“烧水泡茶”的例子：一个人口渴了，想泡一壶茶喝，需要洗水壶1分钟、烧开水15分钟、洗茶壶1分钟、洗茶杯2分钟、拿茶叶1分钟。他怎样才能在最短的时间喝上茶水呢？做一做：李明从早上起床到上学前这段时间，要做以下几件事：叠被（2分钟）、洗脸(3分钟）、刷牙（2分钟）、刷锅（1分钟）、煮鸡蛋（10分钟）、吃早点（10分钟）。请你为李明设计一套最节约时间的方案。刷锅1分钟煮鸡蛋10分钟叠被2分钟洗脸3分钟刷牙2分钟吃早点10分钟加油站达到同一目的可以用多种不同的方法。但方法不同，解决问题的效率也会有差别。在解 决实际问题时，我们要尽可能选择高效的算我们要尽可能选择高效的算法。法。试一试：一位商人有9枚银币，其中有一枚略轻，是假银币，你能用天平（不用砝码）将假银币找出来吗？请给出最优化的算法。读一读蚂蚁的视力较差，但却能在黑暗的世界中快速找到食物，而且可以找到从洞穴到食物的最短路径。蚂蚁是如何做到的呢？研究表明：蚂蚁在行走过程中会释放种称为“信息素”的挥发性化学物质，用来标识自己的行走路径。在寻找食物的过程中，蚂蚁会根据信息素的浓度选择行走的方向，并最终到达食物所在的地方。排序算法的优化 所谓“排序”，就是使 一串记录按照其中的某个或某些关键字的大小递增或递减排列的操作。例：将12 -3 4 8 -5顺序排列出来，人工是如何排序的呢？请用自然语言说一说排序的算法过程。冒泡排序 第1轮排序后 -3 4 8 -5 12第2轮排序后 -3 4 -5 8 12第3轮排序后 -3 -5 4 8 12第4轮排序后 -5 -3 4 8 12 5个数据经个数据经过过4轮排序后就轮排序后就形成了从小到形成了从小到大的顺序。由大的顺序。由于小的数如气于小的数如气泡一般逐层上泡一般逐层上冒，而大的数冒，而大的数逐层下沉，因逐层下沉，因此这此这 种排序的种排序的方法被形象地方法被形象地比喻成比喻成“冒泡冒泡排序法排序法”。排序：12-3 8-54 计算机有许多对数据排序的方 法，其中“冒泡排序法”是排序的 常用方法。以给出的5个数据为例，在比较时，首先将第1个数与第2个数比较，如果第1个数大于第2 个 数，则交换两个数的位置，接着比较第2个数与第3个数。依此类推，直到最后两个数比较完毕。数据从左到右比较一遍为一轮排序，每轮排序都把需要排序的数据列中最大的数据交换到最后位直。这种排序将一直进行到全部数据都有序、没有交换为止。快速排序法是冒泡排序法的一种改进。它的基本思想是：1.把一组需要排序的数据分成两部分，让其中一部分的所有数据都比另外一部分的所有数据小。2.按第1步方法对这两部分数据分别进行多次快速排序，直到完全将数据按要求排序。活动三 查找的算法优化一、顺序查找二、二分查找我实践我创新1.某市的出租车计价规则为：在不考虑延时等待的情况下，起步价为11元，可以行驶3千米；接下来的7千米，每千米为2元；如果超过10千米，则剩余的路程每千米3元。不到 1 千米的按1千米计算。若路程为26千米，如何乘车才会使费用最少？（1）每3千米换车 （2）每10千米换车 （3）不换车 （4）组合换车等2.请利用冒泡排序法对下列7个数进行排序，并写出排序过程。81 35 97 23 48 16 55小结：同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。评价一个算法是否优秀，可以从以下几个方面进行考虑，如运行需要的时间、内存资源的消耗、正确性、可读性、容错性能等。时间耗费：执行算法所需要的计算工作量。空间占用：算法需要消耗的内存空间。正确性：评价一个算法优劣的最重要的标准。可读性：一个算法可供人们阅读的容易程度。容错性：一个算法对不合理数据输人的反应能力和处理能力，也称为“容错性”。