数据结构与算法实习 课程目的 (一)概论 配合“数据结构与算法”主课,提高实际动 能力和程序设计的 ●基本数据结构 北京大学信息科学技术学院 ·线性表向量、串、栈和队列)、二又树、 张铭 ADT、STL zhang@db.pku.edu.cn 综合应用程序 排序、检索、文件、索引等技术 tp: db. pku. edu. cn/zhang/ds/shixi 20079.12 程序设计实践和技巧 课程内容 ●C++编程技术补充 ●基本算法 标准模板库STL的基本概念 枚举法、贪心法 C++流处理 ●程序设计实践和技巧 递归、回溯、搜索与分支限界 分治法、动态规划 风格、设计和实现 界面、排错 ●问题建模 测试、性能和可扩展性 数学建模、软件模型 成绩评定办法考勤 平时:20% ●可以申请自学,必须写出书面申请 考勤、开卷随堂测试、课堂表现 ·AcM作业:20% ◆自学的同学可以不来听课 北大AcM结果、源程序、实习报告 ◆同样交作业、上机题、考试 ●综合上机题:40% 实习课也不要迟到早退、旷课 源程序、实习报告 ◆有事提前请假 期末考试20% ◆1/3旷课得不到学分 ●有附加题 任何一项表现突出都可以*+ 分 ◆“不及格
1 数据结构与算法实习 （一）概论 北京大学信息科学技术学院 张 铭 mzhang@db.pku.edu.cn http://db.pku.edu.cn/mzhang/ds/shixi/ 2007.9.12 课程目的 配合“数据结构与算法”主课，提高实际动 手能力和程序设计的质量 z 基本数据结构 z 线性表(向量、串、栈和队列)、二叉树、 树、图等 z ADT、STL z 综合应用程序 z 排序、检索、文件、索引等技术 z 程序设计实践和技巧 课程内容 z C++编程技术补充 z 标准模板库 STL的基本概念 z C++流处理 z 程序设计实践和技巧 z 风格、设计和实现 z 界面、排错 z 测试、性能和可扩展性 z 基本算法 z 枚举法、贪心法 z 递归、回溯、搜索与分支限界 z 分治法、动态规划 z问题建模 z 数学建模、软件模型 成绩评定办法 z 平时：20% z 考勤、开卷随堂测试、课堂表现 z ACM作业：20% z 北大ACM结果、源程序、实习报告 z 综合上机题：40% z 源程序、实习报告 z 期末考试 20% z 有附加题 任何一项表现突出都可以 +++分 考 勤 z 可以申请自学，必须写出书面申请 自学的同学可以不来听课 同样交作业、上机题、考试 z 实习课也不要迟到早退、旷课 有事提前请假 1/3旷课得不到学分 “不及格
作业要求 上机题编程风格 实习课3道大综合实习,7道 ACM 诚实代码保证 “诚实代码” 内部文档要求 ●要调试 ●过程代码要求 ●要提交上机报告 ●面向对象的代码要求 按时提交作业,严禁抄袭 诚信 ftp提交电子版 端正学习态度、调动学习兴趣 计分标准10分,期末加权。规则: ◆提倡讨论,但严禁抄袭 ◆可以讨论思路 准时提交,满分可达10分(个别加 ◆但要亲自动手实现 分) ◆发现抄袭,严肃查处 2.延迟3天之内提交,满分可达7分; 3.延迟7天之内提交,满分可达3分 ◆掏翥芬和諮麥翥夯次作业或上机题计双倍 4.7天之后提交或不交,得分-5分 ◆以后的作业题会得到重点检查 抄袭得-20分 ◆严重的期评将给予不及格处理 上机题提交要求 课程资源 打包后 建议命名式 ·数据结构与算法(信息学院) .http:/ldb.pku.edu.cn/mzhang/ds/ 包中须含有: ·数据结构实习〔计算机和智能专业强化) ·1. readme. txt文件 程序运行环境、编译运行步骤、程序功能等 课程谷 ·2诚实代码保证、源程序以及相关的项目和 .http:/db.cs.pku.edu.cn/mzhang/ds/bbs/ 资源文 足够注释 ◆注册:h学号xx或其他班要求的 偺查源文性的时件取J要的w 课作业提交 orojidsoLproi@fusion grids,cn ·3.上机实习总结报告
2 作业要求 z实习课3道大综合实习，7道 ACM z“诚实代码” z要调试 z要提交上机报告 上机题编程风格 z诚实代码保证 z内部文档要求 z过程代码要求 z面向对象的代码要求 按时提交作业，严禁抄袭 z ftp提交电子版 z 计分标准10分，期末加权。规则： 1. 准时提交，满分可达10分（个别加 分）； 2. 延迟3天之内提交，满分可达7分； 3. 延迟7天之内提交，满分可达3分； 4. 7天之后提交或不交，得分 - 5分； 5. 抄袭得 – 20分。 诚 信 z端正学习态度、调动学习兴趣 提倡讨论，但严禁抄袭 可以讨论思路 但要亲自动手实现 发现抄袭，严肃查处 抄袭者和被抄袭者本次作业或上机题计双倍 倒扣分，即得 - 20分 以后的作业题会得到重点检查 严重的期评将给予不及格处理 上机题提交要求 z 打包后提交，建议命名式： z 00308096张宁1.zip 包中须含有： z 1. readme.txt文件 z 程序运行环境、编译运行步骤、程序功能等 z 2. 诚实代码保证、源程序以及相关的项目和 资源文件、足够注释 z 例如，VC++中的.dsw, .dsp文件，rc目录中的 图像资源文件；Jbuilder中的.jpr或.jpx文件，特 殊的Java包等等 z 3. 上机实习总结报告 课程资源 z 数据结构与算法（信息学院） http://db.pku.edu.cn/mzhang/DS/ z 数据结构实习（计算机和智能专业强化） http://db.pku.edu.cn/mzhang/DS/shixi/ z 课程答疑 http://db.cs.pku.edu.cn/mzhang/ds/bbs/ 在实习版块 注册：h-学号xxx 或 其他班要求的 z 实习课作业提交 ftp://ds_proj:ds07proj@fusion.grids.cn
教材 ·1张铭 ,《数据结构与算法 Charles eleiserson 社, 04-017829 熟尊章蹂、螽尊膏出社:额。4 据结 評实肌蕾薨3年猾骨 叠设第素丢a防击 ·4.M.H. Alsuwaiyel, 版社影 酸狂骑夯3年打潸计与分析),清华大学出 于φ大竽备法引年1计与分 助教 主题 组长组员 面向对象技术 毛泵吴迪 ·邢国 实习总助教 sTL和c++ 钱昊巨程 调试和测试技术 赖博彦陈学轩丁羽 ·Te:13146717633;82179629 陈醒王瑞超 归和回溯 王子琪谭裕韦 张阜东 图、搜索、剪枝姚金宇黄柏影陈琪 ·哈立久 动态规划 杨涛金鑫李昂周金果 算法优化 李森贾由 王位亭—学院 数学建模技术汪瑜婧雷涛罗睿辞 数据结构与算法应用陈志杰冯熙铉张策 实习课程进度W鱻 实习课程进度(2/2) ·9月12日第一周数据结构与算法实习简介—张铭 ·9月19日 周算法(一):穷举法 ·11月7日第九周算法(五):动 算法(二):回测 态规划—张阜东 10月10日第五周算法(三):贪心法,算法优化一刘 ·11月14日第十周习题讨论,布置 ·10月 表漫序法实(),凤格,设计和实 大实习,讨论项目管理——陈长城 ·层甭七厘珠 设计实践(二):STL的基本概念 ·11月21日第十一周程序设计实践 ·10月31日第八周算法(四):分治法陈长城 (三):界面和排错——王栋 ·11月28日第十二周程序设计实践 (加),洲性能和可把屈性
3 教材 z 1. 张铭、赵海燕、王腾蛟，《数据结构与算法 －－学习指导与习题解析》，高等教育出版 社，2005年 9月。ISBN 7-04-017829-X。 z 2. 许卓群、杨冬青、唐世渭、张铭，《数据结 构与算法》，高等教育出版社，2004年7月。 z 3. Brian W.Kernigham 著，裘宗燕 译，《程 序设计实践》，机械工业出版社，2003年9月。 z 4. M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 电子工业出版社影 印，2003年1月。 z 5. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, 高等教育出版社影印，2002年5 月。 z 6. Donald E.Knuth 著，苏运霖 译，《计算机 程序设计艺术，第1卷基本算法》，国防工业出 版社，2002年。 z 7. 王晓东，《算法设计与分析》，清华大学出 版社，2003年1月。 z 8. 卢开澄，《计算机算法导引——设计与分 析》，清华大学出版社，1996年11月。 助教 z 邢国峰——实习总助教 z Email: holdenxing@gmail.com z Tel:13146717633;82179629. z 陈长城 z 刘培 z 张阜东 z 王栋 z 喻立久 z 杨宇 z 高壮 z 王位春——学院总助教 数据结构与算法应用 陈志杰 冯熙铉 张策 数学建模技术 汪瑜婧 雷涛 罗睿辞 算法优化 李森 贾由 动态规划 杨涛 金鑫 李昂 周金果 图、搜索、剪枝 姚金宇 黄柏彤 陈琪 递归和回溯 王子琪 谭裕韦 陈学轩 丁羽 陈醒 王瑞超 调试和测试技术 赖博彦 STL和C++ 钱昊 巨程 面向对象技术 毛琛 吴迪 主题 组长 组员 实习课程进度(1/2) z 9月12日 第一周 数据结构与算法实习简介——张铭 z 9月19日 第二周 算法（一）：穷举法——张铭 z 9月26日 第三周 算法（二）：回溯法——张铭 z 10月3日 第四周 国庆放假 z 10月10日 第五周 算法（三）：贪心法, 算法优化——刘 培 z 10月17日 第六周 程序设计实践（一）：风格、设计和实 现，面向对象技术——高壮 z 10月24日 第七周 程序设计实践（二）：STL的基本概念 和常用容器——张阜东 z 10月31日 第八周 算法（四）：分治法——陈长城 实习课程进度(2/2) z 11月7日 第九周 算法（五）：动 态规划——张阜东 z 11月14日 第十周 习题讨论，布置 大实习，讨论项目管理——陈长城 z 11月21日 第十一周 程序设计实践 （三）：界面和排错——王栋 z 11月28日 第十二周 程序设计实践 （四）：测试、性能和可扩展性—
程序设计实践和技巧|「风格、设计和实现 ●风格、设计和实现 风格 ●程序的境界 ●文件结构、版式、命名、注释. ●界面、排错 程序员的素质 ●程序的境界 ●测试、性能和可扩展性 设计和实现 界面( (interface)与排错 问题求解 ●用户界面、程序接口 ·数学建模、问题建模 字符界面:菜单型,命令行型 ·数据结构抽象 ·简单、清晰、规范、统 棒性 效率分析 排错 禱鞏獯辯聽沟解决预期规模间恩的 注意程序风格(避免全局变量、不用 互相冲突的需求和约束条件之间寻 ·排错的时间至少跟写程序一样长 不要去怀疑编译器和库函数 反复试验,推倒重来,直至 读程序,而不是马上去改程序 ·不要过于依赖 debug工具 测试、性能和可扩展性 霾禧狂的矚的用系统的方法发现程序中 ●在总体设计上要注意代码风格、 黑盒测试 可复用性和可扩展性 白盒测试 性能优化 ●在关键段要牺牲上面的内容来追 ·编译、代码、算法优化 可扩展性 求性能 ·敦件复用 ●性能和可扩展性是相互矛盾的 ·紧町标准 平台无关
4 程序设计实践和技巧 z风格、设计和实现 z程序的境界 z界面、排错 z测试、性能和可扩展性 风格、设计和实现 z风格 z 文件结构、版式、命名、注释…… z 程序员的素质 z 程序的境界 设计和实现 z 问题求解 z 数学建模、问题建模 z 数据结构抽象 z 算法抽象 z 效率分析 z 选择能在合理时间内解决预期规模问题的 简单算法和数据结构 z 在一些互相冲突的需求和约束条件之间寻 找平衡 z 反复试验，推倒重来，直至…… 界面(interface)与排错 z 用户界面、程序接口 z 字符界面：菜单型，命令行型 z 简单、清晰、规范、统一 z 鲁棒性 z 排错 z 注意程序风格（避免全局变量、不用 goto……） z 排错的时间至少跟写程序一样长 z 不要去怀疑编译器和库函数 z 读程序，而不是马上去改程序 z 不要过于依赖debug工具 测试、性能和可扩展性 z 测试(Testing)：用系统的方法来发现程序中可 能存在的隐藏的bug z 黑盒测试 z 白盒测试 z 性能优化 z 编译、代码、算法优化 z 可扩展性 z 软件复用 z 紧盯标准 z 平台无关 z在总体设计上要注意代码风格、 可复用性和可扩展性 z在关键段要牺牲上面的内容来追 求性能 z 性能和可扩展性是相互矛盾的
sTL中的容器「sTL中的容器 °8°8 顺序容器 vector deque[ list stack queue priority 关联容器 ueue et. multiset map, multimap 容器适配器 容器 Containers 基本算法 八皇后问题 问题的状态空间 ●在8×8格的国际象棋棋盘上摆 ●穷举法 放8个皇后,使其不能互相攻击 回溯、搜索 任意两个皇后都不处于同一行、 贪心法 同一列或同一斜线上 递归分治 ●问有多少种摆法? 动态规划 八皇后问题的一个解 四皇后的解空间树 Q @@的@的@的的回 324 0@ g@8
5 STL中的容器 顺序容器 关联容器 容器 Containers vector deque list set, multiset map, multimap STL中的容器 容器适配器 stack queue priority _queue 基本算法 z问题的状态空间 z穷举法 z回溯、搜索 z贪心法 z递归分治 z动态规划 八皇后问题 z在8×8格的国际象棋棋盘上摆 放8个皇后，使其不能互相攻击 z 任意两个皇后都不处于同一行、 同一列或同一斜线上 z问有多少种摆法？ 八皇后问题的一个解 Q Q Q Q Q Q Q Q 四皇后的解空间树
状态空间明 解空间树 °8°8 根(root):问题的起点 问题状态( problem states):树中结点 ·状态空间( state space):由根结点到其它 结点的所有路径 ·解状态( solution states)S:由根到S的路 径确定了解空间中的一个元组 谷案状态( answer states)S:由根到s的路 径确定了这问题的一个解(即,它满足隐式约 穷举法(枚举法) 穷举法的代价 ·4个皇后各占一行,穷举每一行上 ·穷举问题域的所有解,找到所有最佳解 可能占有的列 减少穷举次数 共有44=256种情况 穷举的变量 ●枚举时,可以排除直观不符合条件 注意穷举的顺序 的情况,减小候选集 减少判断每种情况的时间 ·有4!=24种情况 时间代价最高 ·问题规模n,搜索空间Σ,总搜索时间是: ●最后输出合理的解 指数级时间代价 四后问题求解 八皇后问题的表示馨 回溯算法 棋盘行列、皇后依次编上0,1,,7号 ·A[0.n-1[0.n]表示n×n棋盘上的格 行号从上至下、列号从左到右依次编号为0, 八后问题的全部解向量为(x0,x )。 x表示皇后所处的列数 ·对任何0≤K8,及,有x≠x 状态空间缩小为在8! 可行则进,不行则换 没有两个皇后在同一斜线上(斜率为土1) 换不成则退 重点! 6
6 状态空间 ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● 解空间树 z 根（root）：问题的起点 z 问题状态（problem states）：树中结点 z 状态空间（state space）：由根结点到其它 结点的所有路径 z 解状态（solution states）S：由根到S的路 径确定了解空间中的一个元组 z 答案状态（answer states）S：由根到S的路 径确定了这问题的一个解（即，它满足隐式约 束条件） 穷举法（枚举法） z 4个皇后各占一行，穷举每一行上 可能占有的列 z 共有44 ＝ 256种情况 z 枚举时，可以排除直观不符合条件 的情况，减小候选集 z 有4! ＝ 24种情况 z 最后输出合理的解 穷举法的代价 z 穷举问题域的所有解，找到所有最佳解 z 减少穷举次数 z 穷举的变量 z 注意穷举的顺序 z 减少判断每种情况的时间 z 时间代价最高 z 问题规模n，搜索空间Σ，总搜索时间是： z T= |Σ| ×t，O(n!) = O(nn)，O(2n) z 指数级时间代价 四后问题求解 z 回溯算法 可行则进，不行则换 换不成则退 八皇后问题的表示 z 棋盘行列、皇后依次编上0, 1,…，7号 z A[0..n-1][0..n-1] 表示n×n棋盘上的格 z 行号从上至下、列号从左到右依次编号为0, 1,…，n-1 z 八后问题的全部解向量为(x0, x1,…，x7)。 z xi 表示皇后i所处的列数 z 对任何0≤i, j<8，及i≠j，有xi ≠xj z 状态空间缩小为在8! z 没有两个皇后在同一斜线上（斜率为±1 ） z 重点！
斜率+1,i+j={0,1,,14 斜率1,i={7,6,…,7 01234567 01234567 0 l 456 7团团区 7 皇后的控制范围 试探安排八个皇后 ●第个皇后时,前面几个皇后在各列、 ·从第0行开始,逐步安排每行皇后 各对角线上的占用情况 ·对第个皇后,找正确的位置(设为第列 bool A[n];∥前0.i-1行皇后占用列 ·A]、B[+]、c[于7]都没有被占用 bool e[2n1];∥斜率为+1的对角线 ·标记A]、B[+、C[于7为被占用状态 继续安排下一个皇后(第|1个 bool c[2+n-1];∥斜率为-1,c[ij7 ●否则,如果找不到合适位置,应该退回 (即“回溯)到第|-1行的皇后,重新安排 前面的安排不太合理 回溯过程 回溯法的框架 如果8个皇后都排好了,则打印这种方案 ·问题的解n元组(xX (k)【∥初始调 retry(0) 染璽蒼鹞空葬委排痨渎溯,重新试 置X〖k为第 可能值 e(Xk可能值没有试完) 设置X[k]所涉及的标 訂甸试探男奕第颔狀蒌复A (X[0],X1],…,Xn-1】)是解) 打印一组解; 种回溯过程将逐步返回 使得各行的皇后都能试探到各种可能的摆法 回溯,抹去X涉及的标记; 取下一个可能的X值
7 斜率+1，i+j={0, 1, …, 14} 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 斜率-1，i-j={-7, 6, …, 7} 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 皇后的控制范围 z 第i个皇后时，前面几个皇后在各列、 各对角线上的占用情况 bool A[n]; // 前0..i-1行皇后占用列 bool B[2*n-1]; // 斜率为+1的对角线 bool C[2*n-1]; // 斜率为-1， C[i-j+7] 试探安排八个皇后 z 从第0行开始，逐步安排每行皇后。 z 对第i个皇后，找正确的位置(设为第j列 z A[j]、B[i+j]、C[i-j+7]都没有被占用 z 标记A[j]、B[i+j]、C[i-j+7]为被占用状态 z 继续安排下一个皇后(第i+1个) z 否则，如果找不到合适位置，应该退回 (即“回溯”)到第i-1行的皇后，重新安排 z 前面的安排不太合理 回溯过程 z 如果8个皇后都排好了，则打印这种方案 z 为了找到其它方案，应该回溯，重新试 探皇后的下一种安排方法 z 抹掉前面试探留下的标记，即恢复A[j]、 B[i+j]、C[i-j+7]为未被占用状态 z 这种回溯过程将逐步返回 z 使得各行的皇后都能试探到各种可能的摆法 回溯法的框架 z 问题的解n元组(x0, x1,…，xn-1)： void rectry(k) { // 初始调rectry(0); 置X[k]为第一个可能值； while (X[k]可能值没有试完) { 设置X[k]所涉及的标记; if ((X[0], X[1]，…，X[n-1])是解) 打印一组解; else rectry(k+1); 回溯，抹去X[k]涉及的标记； 取下一个可能的X[k]值; } }
八皇后的递归算法 贪心法 void queen(int)【 问题的状态空间很大时,穷举法 for (=0; j0,w>0,v>0,=1…,n ·输出: ●按照单位重量的价值从高到低对物 品排序 0≤x1≤1i=1 尽量装入“价值/重量”比最高的物 目标函数ma∑vx 品 直到不能装入一个整物品为止 约束条件 ●最后根据背包重量极限装入部分物品
8 八皇后的递归算法 void queen(int i) { int j; for (j=0; j0, wi >0, vi >0, i=1,…, n z 输出： 目标函数 约束条件 ∑= n i i i v x 1 max ∑= ≤ n i i i w x c 1 0 ≤ xi ≤ 1 i = 1,2,..., n 贪心法求解背包问题 z 按照单位重量的价值从高到低对物 品排序 z 尽量装入 “价值/重量”比最高的物 品 z 直到不能装入一个整物品为止 z 最后根据背包重量极限装入部分物品
最小生成树 贪心法 对图G=v,E)的每一条 边e∈E赋以相应的实数 权o(e),得到一个网 最小生成树Prm算法 络,记为N=Vv,E,W 算法Prim(G,E 设T=(VE)是N的一个生 (215354成树包括原图所有顶点 l.S←{1 2. while js②do 的连通树),树T的权为 3.从S中选择j使得到S中顶点的边权最小 N中权最小的生成树称为 N的最小生成树。 贪心法 贪心法 最小生成树Prim算法 ●最小生成树 Krusca算法 算法 Kruskal(G,W) 1.按照权从小到大顺序排序G中的边 2.fori← 1 to m do 3.如果e的两个端点不在同一个连通分 则将e加到T中 贪心法 贪心法一般原则 最小生成树 Kruskal算法 贪心法得到的可能是最优解 ·最小生成树 部分背包问题 贪心法是否求得最优解需要数学证明 问题规模太大,最优解代价太高时,用贪 ·地图着色 ·巡回售货员问题
9 最小生成树 1 2 3 4 5 6 6 5 5 5 1 3 6 4 6 2 对图G=(V, E) 的每一条 边 赋以相应的实数 权 ，得到一个网 络，记为N=(V, E, W) 设T=(V, E’)是N的一个生 成树(包括原图所有顶点 的连通树)，树T的权为 N中权最小的生成树称为 N的最小生成树。 e∈ E ω(e) ∑∈ = ' ( ) ( ) e E W T ω e 贪心法 z最小生成树Prim算法 贪心法 z最小生成树Prim算法 1 2 3 4 5 6 6 5 5 5 1 3 6 4 6 2 1 2 3 4 5 6 1 4 4 2 2 5 5 3 贪心法 z最小生成树Kruscal算法 贪心法 z最小生成树Kruskal算法 1 2 3 4 5 6 6 5 5 5 1 3 6 4 6 2 1 2 3 4 5 6 1 3 2 4 5 贪心法一般原则 z 贪心法得到的可能是最优解 z 最小生成树 z Huffman树 z 部分背包问题 z 贪心法是否求得最优解需要数学证明 z 问题规模太大，最优解代价太高时，用贪 心法求近似解 z 地图着色 z 巡回售货员问题
递归分治算法 动态规划法问题 分治策略的实例——归并排序 ●某一类递归问题,如果直接用递归实 现,可能会导致极低的效率 往往是o(2) 回回回回画回回凹 ●上一级问题可以利用那些更小子问题的 结果,例如 分 合 Fibonacci问题 合数问题 二分搜索、BST查找和插入 Hanoi问题不是动态规划问题 sTL里面的 quick sort—快速排序 递归的效率 递归调用树 C=O -1+C >n>0 n=0或m= ●c(m,n) C32) ·两个子问题cm-1,n)和c(m-1,n-1) 回 2)=1C(2 2D)(20) 递归了 回回圆可回 递归法 递推法 int comb(int m, int n)( intc[m];∥假设初值为0矩阵 int comb(int m, int n) if(m=n)‖(n==0) return1;∥处理边界,递归出口 int i,j (m=n)‖(m==0))cm]=1;递归出口 H+)∥递推 return comb(m-1, n)+comb(m-1, n-1) 时间代价O(2m2) ·时间代价o(mn)
10 递归分治算法 z分治策略的实例——归并排序 421 24 5143 541 35 97 87 789 二分搜索、BST查找和插入 STL里面的quick_sort——快速排序 z分 z治 z合 动态规划法问题 z 某一类递归问题，如果直接用递归实 现，可能会导致极低的效率 z 往往是Ｏ(2n) z 上一级问题可以利用那些更小子问题的 结果，例如 z Fibonacci问题 z 组合数问题 z Hanoi问题不是动态规划问题 递归的效率 z C(m,n) z 两个子问题C(m-1,n) 和 C(m-1,n-1) 1 1 1, 0 1, 0 nn n mm m n m C C C mn C n mn − − − ⎧ ⎫ ⎪ ⎪ = + >> ⎨ ⎬ ⎪ ⎪ ⎩ ⎭ = == 或 递归 递归调用树 C(5,3) C(4,2) C(2,2) = 1 C(2,1) C(3,2) C(4,3) C(3,3) =1 C(3,1) C(2,2) = 1 C(2,1) C(3,2) C(1,1) = 1 C(1,0) = 1 C(1,1) = 1 C(1,0) = 1 C(2,1) C(2,0) =1 C(1,1) = 1 C(1,0) = 1 递归法 int comb(int m, int n) { if ((m==n) || (n==0)) return 1; //处理边界，递归出口 else return comb(m-1,n)+comb(m-1,n-1); } z时间代价O(2m-2n) 递推法 int c[m][n]; // 假设初值为0矩阵 int comb(int m, int n) { int i,j; if ((m==n) || (n==0)) c[m][n] = 1; //递归出口 else for (i=1; i<=m; i++) // 递推计算 for (j=0; j<=i,j<=n; j++) if ((i==j) || (j==0)) c[i][j] = 1; else [i][j] = c[i-1][j] + c[i-1][j-1]; } z 时间代价O(mn)
