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