恩佐2登录 > SEO技术 > 算法的优化_图

算法的优化_图

admin SEO技术 2020年01月15日

  算法的优化_计算机软件及应用_IT/计算机_专业资料。算法的优化 学习目标 知识目标 理解算法优化的意义。 技能目标 学会用不同的算法来解决问题,并能对算法进行 优化。 情感目标 学会对视角分析问题,能利用高效的方法解决问 题,养成细致缜密思考问

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

标签: seo算法