算法算法概述详解.pptx

1计算机算法设计与分析主讲人:袁运浩E-mail:******@:48节上课:1-16周成绩:卷面成绩(70%)+平时成绩(30%)教材:计算机算法设计与分析,王晓东,电子工业出版社,2012参考书:(1)算法设计与分析,郑宗汉,郑晓明,清华大学出版社(2)算法导论,,***出版社33主要内容介绍第1章 算法概述第2章 递归与分治策略第3章 动态规划第4章 贪心算法第5章 回溯法第6章 分支限界法44意念与现实(1):一个例子给你一个无限容积的罐子和无限个球,球从1开始连续编号★在差1分钟到零点时:将标号为1~10的10个球放进罐子,然后将10号球从罐子里拿出。★在差1/2分钟到零点时:将标号为11~20的10个球放进罐子,然后将20号球从罐子里拿出。★在差1/4分钟到零点时:将标号为21~30的10个球放进罐子,然后将30号球从罐子里拿出。★……就这样将游戏进行下去。假定放球和取球不占时间,请问,当时钟指向零点时,罐子里还剩多少个球?55意念与现实(2):一个例子这个答案很直接:无穷多个球!所有编号不是10n(n≥1)的球在放进罐子里后就不会再拿出来;而在到达零点之前这种放球、取球的次数是无限的。因此,罐子里面的球在零点时将是无数个。你很确信这个答案吗?现在来让我们改变拿球的方式,将每次拿10、20、30…号球分别变为拿1、2、3…号球,即第x次拿球,所拿出来的球的编号是x。结果又会怎样呢?这个时候,神奇的事情发生了。这个罐子里面的球数将为0。对于任意一个球,设其编号为n,则在差(1/2)n-1分钟到零点时该球将被取出。也就是说,对于任意球n,在零点时它都不在罐子里。因此,零点时罐子里球的个数为0。66意念与现实(3):一个例子对于有些人来说,这个答案似乎不可接受。但又确实找不到驳斥的办法。你能找出来吗?也许这个答案是合理的,因为拿球顺序的变化使得算法发生了变化,即我们实际上讨论的是两个算法。可仔细一想又觉得不对,因为两个算法都是每次放进10个球,拿出1个球,即从根本上说,这是两个一样的算法,怎么会有截然相反的结果呢?77意念与现实(4):一个例子如果我们再次改变试验中拿球的方式,将拿某个特定标号的球改为取出任意标号的球,即在差1分钟到零点时,将标号为1~10的10个球放进罐子,然后从罐子里任意拿出一个球;在差1/2分钟到零点时,将标号为11~20的10个球放进罐子,然后从罐子里任意拿出一个球;在差1/4分钟到零点时,将标号为21~30的10个球放进罐子,然后从罐子里任意拿出一个球……这种拿球方式又将产生何种结果呢?答案是仍然是0太不可思议了吧!这三个本质相同的算法怎么有如此匪夷所思的结果呢?如果非要说这三个算法有什么不同,就是拿球时的标号不同。但难道标号的不同使最后球的数量发生了变化?88意念与现实(5):一个例子没错,就是这个标号对结果产生了深远影响。从某种意义上说,标号是虚的,它只存在于我们的想象中,但确实对现实结果产生了影响,即我们的思维使算法发生了变化。或许从另一个角度来看,这个问题就是:没有就是无穷,无穷就是没有。它们之间也许根本没有什么不同,它们的不同只存在于人们的想象或者意念中。也许这是为什么无穷的符号是由两个0连接而成的,从左右两面看都是无有,而从中间看则是无穷。从这个意义上说,算法是一种思维方式(AlgorithmicThinking),或者说一种哲学。9一个最简单的算法: