算法_前言、第一章、第二章new.ppt

本课程学习方法 课堂精讲，课外多练，参考题解，提高程序设计能力，提高程序调试能力，提高算法优化能力; 考试：ACM方式,网上自动测评 04级175人:10题:2, 9题:3, 8:2,7:4,6:19,5:19,4:30,3:24,2:53, 1:8,0:11 3.作业内容：中大OJ 、国内OJ,每周一赛题目; 4.主要OJ:9/sicily/ Poi : http:// 本课程学习方法 Zju : Usaco: /usacogate Ural : http://acm.timus.ru Uva : http://acm.uva.es/p/ Ceoi : http://ceoi.inf.elte.hu/ 本课程学习方法 5.解题报告格式： 原题中方大意; 算法思想及解题用到的主要数据结构; 详细解题思路; 逐步求精算法描述（含过程及变量说明）; 程序注释清单（重要过程的说明）; 测试数据（5-10组有梯度的测试数据）; 对时间复杂度，空间复杂度方面的考虑及程序优化设想. 本课程学习方法 教材及参考资料 《国际大学生程序设计竞赛辅导教程》 郭嵩山、崔昊、吴汉荣、陈明睿编著 北京大学出版社 2000.12 《国际大学生程序设计竞赛例题解（一）》数论、计算几何、有哪些信誉好的足球投注网站算法专集,郭嵩山、李志业、金涛、梁锋编著 电子工业出版社 2006.5 本课程学习方法 3.《国际大学生程序设计竞赛例题解（二）》广东省大学生程序设计竞赛试题 2003-2005 , 郭嵩山、黎俊瑜、林祺颖著 电子工业出版社 2006.5 4. .《国际大学生程序设计竞赛例题解（三）》图论、动态规划算法、综合题专集, 郭嵩山、关沛勇、蔡文志、梁锋编著 电子工业出版社 2007.7 第一章 设计算法常用的策略 一 对应的策略 将问题对应成另一个易于思考的问题 A问题- B问题 B有现成算法，从而求解 一 对应的策略 例1.1 哥尼斯堡七桥问题（一笔画问题，七桥四块陆地） 从一块陆地出发，每次过一桥，且只能过一次，最后回到出发点，问是否存在这样的途径 哥尼斯堡七桥问题- 欧拉回路 结论：从图上的一点出发又回到该点，连接该点的线（边）必须是偶数才能满足条件。 而七桥问题中，所有定点的度（连结边的条数）皆为奇数，故无解 一 对应的策略 例1.2 一种游戏，给出n n为自然数），然后给出2n个自然数，例如n 4，2n 8个数是7 9 3 6 4 2 5 3，游戏双方为A，B（计算机）只允许从给出数列的两头取数，以取完数之和最大者为胜，A可以先取，如两者和相等仍算A胜 一 对应的策略 方案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 一 对应的策略 观察2n个数，奇偶为上述数之和有大小之分，取偶数位位置可获胜 ①②③④⑤⑥⑦⑧ 7 9 3 6 4 2 5 3 A取 3 9 2 6 A胜 B取7 5 4 3 取数问题对应成按奇偶对应规则取数可获问题解 一 对应的策略 方案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 二 大化小的策略（分治策略） 规模大问题，求解较难，将规模大问题化为若干规模较小问题来求解，然后进行结果归并，这种也成为分治策略。 二 大化小的策略（分治策略） 例1.3 求一组数的最大值和最小值 设数的个数为n（规模参数），存在数组A[1]…A[n] 算法： min: A[1]; max: A[1]; for i: 2 to n do begin if A[i] max then max: A[i]; if A[i] min then min: A[i]; end; 二 大化小的策略（分治策略） 对于n 2的规模，采用一分为二缩小其规模，最后结果必分为规模n 1或n 2的情况，则最后用一次比较可求出max，min，再进行归纳，最大值中归并出最大值，最小值中归并出最小值 n 1时，max min A[1]; n 2时，if A[1] A[2] then min: A[2];max: A[1]; else max: A[2];min: A[1]; 二 大化小的策略（分治策略） 上例中i从2开始，每个数要比较两次方能决定到i的最大和最小值，采用分治方法，比较次数可减少 如n 4，只用比较4次 本例赋具体值 N 9，A[1]