算法设计与分析课件：概论、第一章、第二章.ppt

课程学习方法课程学习方法1.课堂精讲，课外多练，参考题解，精做（解题）报课堂精讲，课外多练，参考题解，精做（解题）报告，提高程序设计能力，提高程序调试能力，提高告，提高程序设计能力，提高程序调试能力，提高算法分析和优化能力算法分析和优化能力;2.基本作业：基本作业：SICILY上完成指定题目，完成典型题目上完成指定题目，完成典型题目的解题报告；的解题报告；3.考试：考试：ACM方式方式,网上自动测评网上自动测评,诚信是诚信是IT人立足之本人立足之本!课程学习方法课程学习方法算法设计与应用（机试）情况及分析：算法设计与应用（机试）情况及分析：CS题数：题数：10 9 8 7 6 5 4 3 2 1 0 总总04级级 2 0 2 4 19 19 30 24 53 8 11 17505级级 0 0 2 3 2 2 8 15 35 21 11 9906级级 0 0 0 5 3 9 16 33 16 14 11 10507级级 0 0 1 5 10 24 53 31 28 14 12 17808级级 7 6 4 6 4 6 9 14 14 14 16 10009级级 0 0 1 8 7 7 28 60 19 4 0 134 10级级 0 2 3 9 9 17 32 40 3 4 2 123课程学习方法课程学习方法算法设计与应用（机试）情况及分析：算法设计与应用（机试）情况及分析：SS大三上学期大三上学期题数：题数：10 9 8 7 6 5 4 3 2 1 0 总总07级级 0 0 0 4 3 4 3 21 41 52 57 18509级级 2 2 3 6 5 14 26 18 9 5 1 9110级级 0 0 1 2 2 6 13 25 27 19 4 9911级级 0 1 2 1 7 20 35 85 7 2 0 160课程学习方法课程学习方法l说明：说明：l1.04-08级大三上学期，级大三上学期，09-10级大二下；级大二下；l2.04-07级校级校ICPC集训队员免考（集训队员免考（04级级8人，人，05级级7人，人，06级级3人，人，07级级4人）人）课程学习方法课程学习方法3.作业扩展内容：中大作业扩展内容：中大OJ、国内、国内OJ,每周一赛题目，每周一赛题目，HUST虚拟虚拟OJ上练习题上练习题;4.主要OJ:http:/soj.me =http:/Poj :Poj :http:/http:/Zou :Zou :http:/http:/HUST OJHUST OJ：http:/http:/本课程学习方法本课程学习方法hoj:hoj:http:/http:/ :Uva :http:/acm.uva.es/p/http:/acm.uva.es/p/本课程学习方法本课程学习方法5.解题报告格式：解题报告格式：原题中文大意原题中文大意;算法思想及解题用到的主要数据结构算法思想及解题用到的主要数据结构;详细解题思路详细解题思路;逐步求精算法描述（含过程及变量说明）逐步求精算法描述（含过程及变量说明）;程序注释清单（重要过程的说明）程序注释清单（重要过程的说明）;测试数据（测试数据（5-10组有梯度的测试数据组有梯度的测试数据,要考虑边界条件）要考虑边界条件）;对时间复杂度，空间复杂度方面的分析、估算及程序优化对时间复杂度，空间复杂度方面的分析、估算及程序优化的分析和改进的分析和改进.本课程学习方法本课程学习方法教材教材 1 刘汝佳、黄亮，算法艺术与信息学竞赛（第刘汝佳、黄亮，算法艺术与信息学竞赛（第1版），北京：版），北京：清华大学出版社，清华大学出版社，2004，ISBN 7-302-07800-92 Thomas H.Cormen;Charles E.Leiserson;Ronald L.Rivest;Clifford Stein.Introduction to Algorithms,2th Ed.The MIT Press,2001,ISBN 978-0-262-33293-3影印版：算法导论（第二版），北京：高等教育出版社，影印版：算法导论（第二版），北京：高等教育出版社，2007，ISBN 978-7-040-11050-0中译版：潘金贵等译，算法导论（第中译版：潘金贵等译，算法导论（第2版），北京：机械版），北京：机械工业出版社，工业出版社，2006，ISBN 7-111-18777-6 本课程学习方法本课程学习方法参考资料参考资料1.国际大学生程序设计竞赛教程国际大学生程序设计竞赛教程 郭嵩郭嵩山、崔昊、吴汉荣、陈明睿编著山、崔昊、吴汉荣、陈明睿编著 北京大学出北京大学出版社版社 2000.122.国际大学生程序设计竞赛例题解（一）国际大学生程序设计竞赛例题解（一）数论、计算几何、数论、计算几何、搜索算法专集搜索算法专集,郭嵩山、李郭嵩山、李志业、金涛、梁锋编著志业、金涛、梁锋编著 电子工业出版社电子工业出版社 2006.5本课程学习方法本课程学习方法3.国际大学生程序设计竞赛例题解（二）国际大学生程序设计竞赛例题解（二）广广东省大学生程序设计竞赛试题东省大学生程序设计竞赛试题(2003-2005),郭郭嵩山、黎俊瑜、林祺颖著嵩山、黎俊瑜、林祺颖著 电子工业出版社电子工业出版社 2006.54.国际大学生程序设计竞赛例题解（三）国际大学生程序设计竞赛例题解（三）图论、动态规划算法、综合题图论、动态规划算法、综合题专集专集,郭嵩山、郭嵩山、关沛勇、蔡文志、梁锋编著关沛勇、蔡文志、梁锋编著 电子工业出版社电子工业出版社 2007.7本课程学习方法本课程学习方法4.国际大学生程序设计竞赛例题解（四）国际大学生程序设计竞赛例题解（四）广广东省信息学奥林匹克竞赛试题东省信息学奥林匹克竞赛试题(2003-2006),郭郭嵩山、张惠东、林祺颖、莫瑜著嵩山、张惠东、林祺颖、莫瑜著 电子工业出电子工业出版社版社 2008.25.国际大学生程序设计竞赛例题解（五）国际大学生程序设计竞赛例题解（五）广广东省大学生程序设计竞赛试题东省大学生程序设计竞赛试题(2006-2007),郭郭嵩山、张子臻、王磊、汤振东著嵩山、张子臻、王磊、汤振东著 电子工业出电子工业出版社版社 2008.11本课程学习方法本课程学习方法6.国际大学生程序设计竞赛例题解（六）国际大学生程序设计竞赛例题解（六）广广东省大学生程序设计竞赛试题东省大学生程序设计竞赛试题(2008-2009),郭郭嵩山、翁雨键、梁志荣、吴毅著嵩山、翁雨键、梁志荣、吴毅著 电子工业出电子工业出版社版社 2010.57.国际大学生程序设计竞赛例题解（七）国际大学生程序设计竞赛例题解（七）中中山大学山大学ICPC集训队内部选拔赛试题集训队内部选拔赛试题(2005-2006),郭嵩山、刘祖立、刘曦、涂德健著郭嵩山、刘祖立、刘曦、涂德健著 电电子工业出版社子工业出版社 2010.7本课程学习方法本课程学习方法 8.国际大学生程序设计竞赛例题解（八）国际大学生程序设计竞赛例题解（八）广东省广东省信息学奥林匹克竞赛试题信息学奥林匹克竞赛试题(2007-2009),郭嵩山、陈宇郭嵩山、陈宇恒、张钊毅、周贤豪著恒、张钊毅、周贤豪著 电子工业出版社电子工业出版社 2011.109.郭嵩山、陈才斌、赵浩泉、江泽斌：国际大学生程序郭嵩山、陈才斌、赵浩泉、江泽斌：国际大学生程序设计竞赛中山大学内部选拔真题解（一）（设计竞赛中山大学内部选拔真题解（一）（2007-2008），人民邮电出版社，），人民邮电出版社，2012年年11月月 10.郭嵩山、陈元训、蔡奕林、梁晓聪：国际大学生程郭嵩山、陈元训、蔡奕林、梁晓聪：国际大学生程序设计竞赛中山大学内部选拔真题解（二）（序设计竞赛中山大学内部选拔真题解（二）（2009-2010），人民邮电出版社，），人民邮电出版社，2013年年1月月本课程学习方法本课程学习方法大餐后的甜品（学完本课程后选读，面试须读）大餐后的甜品（学完本课程后选读，面试须读）l11.由几个年轻的微软软件工程师著：编程之由几个年轻的微软软件工程师著：编程之美美微软技术面试心得微软技术面试心得 电子工业出版社电子工业出版社 2008.3第一章第一章算法设计常用到的基本策略程序的灵魂程序的灵魂l数据结构+算法=程序l算法设计思想l算法分析：从时空、适用范围来分析，重点考虑时间效率和空间开销l复杂度分析l复杂度等级：多项式算法、指数级算法l五个重要的策略：一一 对应的策略对应的策略l将问题对应成另一个易于思考的问题lA问题-B问题 B有现成算法，从而求解一一 对应的策略对应的策略l例例1.1 哥尼斯堡七桥问题（一笔画问题，七桥四块陆地）哥尼斯堡七桥问题（一笔画问题，七桥四块陆地）l从一块陆地出发，每次过一桥，且只能过一次，最后回到出发从一块陆地出发，每次过一桥，且只能过一次，最后回到出发点，问是否存在这样的途径点，问是否存在这样的途径l哥尼斯堡七桥问题哥尼斯堡七桥问题-欧拉回路欧拉回路l结论：从图上的一点出发又回到该点，连接该点的线（边）必结论：从图上的一点出发又回到该点，连接该点的线（边）必须是偶数才能满足条件。

须是偶数才能满足条件l而七桥问题中，所有定点的度（连结边的条数）皆为奇数，故而七桥问题中，所有定点的度（连结边的条数）皆为奇数，故无解无解一一 对应的策略对应的策略l例例1.2 一种游戏，给出一种游戏，给出n(n为自然数），然后给为自然数），然后给出出2n个自然数，例如个自然数，例如n=4，2n=8个数是个数是7 9 3 6 4 2 5 3，游戏双方为，游戏双方为A，B（计（计算机）只允许从给出数列的两头取数，算机）只允许从给出数列的两头取数，以取完数之和最大者为胜，以取完数之和最大者为胜，A可以先取，可以先取，如两者和相等仍算如两者和相等仍算A胜胜一一 对应的策略对应的策略l方案方案1第一步第一步 A取取7 B取取9 余余3 6 4 2 5 3第二步第二步 A取右取右3 B取取5 余余3 6 4 2 第三步第三步 A取取2 B取取4 余余3 6第四步第四步 A取取6 B取取3 结果：结果：A=7+3+2+6=18 A输输 B=9+5+4+3=21一一 对应的策略对应的策略l观察观察2n个数，奇偶为上述数之和有大小之分，个数，奇偶为上述数之和有大小之分，取偶数位位置可获胜取偶数位位置可获胜 7 9 3 6 4 2 5 3A取取 3 9 2 6 A胜胜B取取7 5 4 3 取数问题对应成按奇偶对应规则取数可获问题解取数问题对应成按奇偶对应规则取数可获问题解一一 对应的策略对应的策略l方案方案2第一步第一步 A取取7 B取取9 余余3 6 4 2 5 3第二步第二步 A取左取左3 B取取6 余余4 2 5 3第三步第三步 A取取4 B取取2 余余5 3第四步第四步 A取取5 B取取3 结果：结果：A=7+3+4+5=19 A输输 B=9+6+2+3=20二二 大化小的策略（分治策略）大化小的策略（分治策略）l规模大问题，求解较难，将规模大规模大问题，求解较难，将规模大问题化为若干规模较小问题来求解，问题化为若干规模较小问题来求解，然后进行结果归并，这种即为分治然后进行结果归并，这种即为分治策略。

策略二二 大化小的策略（分治策略）大化小的策略（分治策略）l例例1.3 求一组数的最大值和最小值求一组数的最大值和最小值l设数的个数为设数的个数为n（规模参数），存在数组（规模参数），存在数组A1Anl算法：算法：min:=A1;max:=A1;for i:=2 to n do begin if Aimax then max:=Ai;if Ai2的规模，采用一分为二缩小其规模，最后结的规模，采用一分为二缩小其规模，最后结果必分为规模果必分为规模n=1或或n=2的情况，则最后用一次比较可的情况，则最后用一次比较可求出求出max，min，再进行归纳，最大值中归并出最大，再进行归纳，最大值中归并出最大值，最小值中归并出最小值值，最小值中归并出最小值ln=1时，时，max=min=A1;ln=2时，。