算法1_算法求解基础

1、算法设计与分析算法设计与分析张怡婷张怡婷Email:Phoneh1.2课前简介课前简介u课程学时：课程学时：48学时学时(40+8)u平时成绩考核办法：平时成绩考核办法：u点名点名u作业作业u实验报告实验报告u考试时间、方式考试时间、方式1919周（之前），闭卷周（之前），闭卷u答疑时间、地点答疑时间、地点周二中午周二中午12:30-13:3012:30-13:30，教，教2-3162-316学习要求：学习要求：u预习预习u动手实现动手实现u上课认真听讲，在书上课认真听讲，在书上作适当的标记和注释上作适当的标记和注释u课后复习课后复习u随堂提问随堂提问u课堂练习课堂练

2、习u算法学习报告算法学习报告?ch1.3算法与数据结构的关系算法与数据结构的关系u算法是算法是数据结构数据结构的灵魂：的灵魂：不了解不了解施加于数据上的算法施加于数据上的算法就无法决定如何构造就无法决定如何构造数据数据。u反之，反之，数据结构数据结构又是算法的基础：又是算法的基础：算法算法的结构和选择又常常在很大程度上的结构和选择又常常在很大程度上依赖于数据结构依赖于数据结构。算法算法+数据结构数据结构=程序程序ch1.4教学过程中常发现很多同学，不是去掌握算法背后的思想，而是钻牛角尖，针对某个算法反复的思考，或者只是掌握了几个具体的算法就沾沾自喜。学习算法不外乎两个目的：学习算法不外乎两个目

3、的：一是一是了解了解各种算法，在遇到问题时能灵活的应用所掌各种算法，在遇到问题时能灵活的应用所掌握的方法技巧；握的方法技巧；二是研究算法二是研究算法设计设计技术，当没有现成可用的算法时，技术，当没有现成可用的算法时，能够创造出问题的求解方法。能够创造出问题的求解方法。算法怎么学？算法怎么学？前者很实际，后者很重要。前者很实际，后者很重要。ch1.5u课程主要章节内容：课程主要章节内容：uCh1 算法问题求解基础算法问题求解基础uCh2 算法分析基础（算法复杂度概念）算法分析基础（算法复杂度概念）u算法设计策略、算法分析和证明算法设计策略、算法分析和证明Ch5 分治法分治法Ch6 贪心法贪心法C

4、h7 动态规划法动态规划法Ch8 回溯法回溯法Ch9 分枝限界法分枝限界法uCh10 NP完全问题完全问题uCh13 密码算法密码算法课程内容课程内容ch1.6课程学习目标课程学习目标uLearning to solve real problems that arise frequently in computer application学习计算机应用中求解实际问题的有效算法学习计算机应用中求解实际问题的有效算法uLearning the basic principles and techniques used for answering the question: “How good, or

5、, how bad is the algorithm”学习评价算法好学习评价算法好/坏的基本原理和技巧坏的基本原理和技巧uGetting to know a group of “very difficult problems” categorized as “NP-Complete”学习学习NP-Complete问题的相关理论和算法问题的相关理论和算法ch1.7课程参考书课程参考书u ClassicsuDonald E.Knuth. The Art of Computer ProgrammingVol.1 Fundamental Algorithms基本算法基本算法Vol.2 Seminume

6、rical Algorithms半数字化算法半数字化算法Vol.3 Sorting and Searching排序与搜索排序与搜索u Popular textbooksuThomas H.Cormen, etc. Introduction to AlgorithmsuAlfred V.Aho,John E.Hopcroft,Jeffrey D.Ullman. The Design and Analysis of Computer AlgorithmsuUdi Manber. Introduction to Algorithms-A Creative ApproachuRobert Sedgew

7、ick. Algorithms in C/C+(with different versions using different programming languages)u Advanced mathematical techniquesuGraham, Knuth, etc. Concrete Mathematics: A Foundation for Computer Science二合一数学（连续数学二合一数学（连续数学+离散数学）离散数学）ch1.8u其他参考书其他参考书1 1 王晓东王晓东. .计算机算法设计与分析计算机算法设计与分析. .电子工业出版社，电子工业出版社，2001.

8、2001.2 2 Jon BentleyJon Bentley著，黄倩著，黄倩, ,钱丽艳译，钱丽艳译，编程珠玑（第编程珠玑（第2 2版）版）. .人民邮电出版人民邮电出版社，社，2008. 2008. 3 3 卢开澄，计算机算法导引卢开澄，计算机算法导引设计与分析设计与分析. .清华大学出版社，清华大学出版社，1996.1996.4 Jon Kleinberg, Eva Tardos4 Jon Kleinberg, Eva Tardos著，张立昂，屈婉玲著，张立昂，屈婉玲 译，算法设计译，算法设计. .清清华大学出版社，华大学出版社，2007.2007.u网上学习资料网上学习资料MIT Op

9、enCourseWare | Electrical Engineering and Computer Science（MIT开放式课件 | 电气工程与计算机科学）http:/ (注册账号注册账号-相应课程相应课程-下载下载)ch1.9上机安排上机安排u上机时间和地点上机时间和地点u分治策略分治策略第第6 6周周二周周二 （4 4月月2 2日）日） 第第1 1大节（大节（ 8:00- 9:358:00- 9:35）u动态规划法动态规划法第第1010周周二（周周二（4 4月月 30 30 日）日） 第第1 1大节（大节（ 8:00- 9:358:00- 9:35）

10、u回溯法回溯法第第1313周周二（周周二（5 5月月2121日）日） 第第1 1大节（大节（ 8:00- 9:358:00- 9:35）u密码算法密码算法第第1414周周二（周周二（5 5月月2828日）第日）第1 1大节（大节（ 8:00- 9:358:00- 9:35）地点：地点：教教2-3162-316（软件与信息安全实验室）（软件与信息安全实验室）u先修课程：先修课程： 高级语言程序设计、面向对象程序设计、数据结构高级语言程序设计、面向对象程序设计、数据结构ch1.10第第1章章 算法问题求解基础算法问题求解基础u学习要点：学习要点：u理解算法的概念。理解算法的概念。u理解什么是程序，

11、程序与算法的区别和内在联系。理解什么是程序，程序与算法的区别和内在联系。u章节内容：章节内容：u1.1 算法概述算法概述u1.3 算法设计与分析算法设计与分析ch1.11uAn Arabian mathematician AbAbud Allh Muhammad ibn Ms al-Khwrizm (c.780-c.850?) wrote the famous “Persian text-book” titled Kitb al-jabr wal-muqbala”AlgebraAlgorismAlgorithmAlgorithm的由来的由来Arithmeticch1.121.1 算法概述算法概

12、述uAn algorithm is a precise description of the process of solving a problem, consisting of finite number of instructions which can be executed mechanically and produce a deterministic result.算法是对某个问题求解方案的完整而明确的描述，是指算法是对某个问题求解方案的完整而明确的描述，是指令的有限序列。令的有限序列。uFive important features:uFiniteness有穷性（算法必须总能在

13、执行有限步之后终止）有穷性（算法必须总能在执行有限步之后终止）uDefiniteness确定性（组成算法的每一条指令都是清晰，无歧义确定性（组成算法的每一条指令都是清晰，无歧义的）的）uInput输入（算法有零个或多个外部提供的输入量）输入（算法有零个或多个外部提供的输入量）uOutput输出（算法至少产生一个输出量）输出（算法至少产生一个输出量）uEffectiveness可行性（算法的每一条指令必须足够基本，能够可行性（算法的每一条指令必须足够基本，能够通过已经实现的基本运算执行有限次来实现）通过已经实现的基本运算执行有限次来实现）“计算机科学是一门研究算法的科学计算机科学是一门研究算法的

14、科学”ch1.13算法与程序算法与程序程序程序(Program)是算法用某种程序设计语言的具体实现。是算法用某种程序设计语言的具体实现。算法算法必须可终止，必须可终止，程序程序却没有这一限制。却没有这一限制。即：即：程序可以不满足算法的性质程序可以不满足算法的性质(5)“有穷性有穷性”。例如：例如：操作系统操作系统是一个在无限循环中执行的是一个在无限循环中执行的程序程序，却不是，却不是算法算法。因因此操作系统是使用计算机语言描述的一个计算过程，而不是此操作系统是使用计算机语言描述的一个计算过程，而不是一个算法。一个算法。ch1.14算法描述算法描述描述一个算法可以用描述一个算法可以用自然语言自

15、然语言、流程图流程图、伪代码伪代码和和程序设计程序设计语言语言。ch1.15经典算法举例经典算法举例欧几里德算法（辗转相除法）：欧几里德算法（辗转相除法）：求两整数求两整数m和和n的最大公约数的最大公约数(0mn) Swap(m,n);return RGcd(m,n); 程序程序1-1 1-1 欧几里德算法（递归）欧几里德算法（递归）void Swap(int &a,int &b)int c=a;a=b;b=c;ch1.20程序程序1-2 1-2 欧几里德算法（迭代）欧几里德算法（迭代）void Swap(int &a,int &b)int c=a;a=b;b=

16、c;int Gcd(int m,int n)if (m=0) return n;if (n=0) return m;if (mn) Swap(m,n);while (m0) int c=n%m; n=m; m=c;return n;程序设计语言描述程序设计语言描述（迭代）：（迭代）：ch1.21可见：可见：一个问题可以设计不同的算法来求解。一个问题可以设计不同的算法来求解。同一个算法可采用不同的形式来表示。同一个算法可采用不同的形式来表示。程序程序1-3 连续整数检测连续整数检测int Gcd(int m,int n)if (m=0) return n;if (n=0) return m;in

17、t t=mn?n:m;while (m%t|n%t) t-;return t;程序设计语言描述程序设计语言描述（连续整数检测）：（连续整数检测）：ch1.22小思考小思考若不事先比较若不事先比较m和和n的大小，如何实现欧几里德算法？的大小，如何实现欧几里德算法？int Gcd(int m,int n) while (m!=0 & n!=0) if (mn) m%=n;else n%=m; return m+n;程序是否一定会在有限步之内终止？程序是否一定会在有限步之内终止？ch1.23小思考小思考m*n /Gcd(m,n)如何求最小公倍数？如何求最小公倍数？ch1.24算法的重要性（算

18、法的重要性（ Algorithm Everywhere ）uApplicationsuHuman Genome Project: identifying 100000 genes in human DNA, determining the sequences of the 3 billion chemical base pairs that make up human DNA, storing this information in databases, and developing tools for data analysis. （卡普卡普Karp -华盛顿）华盛顿）uInternet s

19、ervice: e.g. routing the datauElectronic commerce: public-key cryptography and digital signaturesuSystemsuHardwareuOperating systemsuCompilers（克努特（克努特Knuth-LR(k)文法）文法）ch1.25假设某一负责人交给你一个很难的任务，几天后询问你问题解决了没有。可能会发生如下图这样的情况：问：“交给你的问题，解决方案设计出来了吗？”答：“我找不到一个有效的算法来解决它，没能完成任务。”ch1.26问：“交给你的问题，解决方案设计出来了吗？”答： “

20、我找不到一个有效的算法来解决它，因为这样的算法是不存在的。”不过，要证明一个问不过，要证明一个问题不存在有效算法，题不存在有效算法，往往跟寻找有效算法往往跟寻找有效算法一样难。一样难。ch1.27问：“交给你的问题，解决方案设计出来了吗？”答： “我找不到一个有效的算法来解决它，但不是我不行，因为所有这些名人也都找不到解决它的有效算法。”ch1.28Philosophy of Problem SolvingTo deal with those To deal with those which cant be solvedwhich cant be solved, we , we comprom

21、isecompromise；To deal with those To deal with those which can be solvedwhich can be solved, we , we try our besttry our best；To To distinguishdistinguish between the two classes, we use our wit. between the two classes, we use our wit.ch1.29算法与图灵奖算法与图灵奖超过超过1/3的的Turing奖获奖者其成果与算法有关奖获奖者其成果与算法有关u1974 -

22、Donald Knuth(Stanford): “The Art of Computer Programming”u1976 - Michael Rabin(Hebrew) & Dana Scott(Oxford): Nondeterministic Finite State Automata (NDFSA)u1982 - Stephen Cook(Toronto): Satisfiability of Proposition Calculus is NP-completeu1985 - Richard Karp(UC Berkley): Branch-and-Bound Method

23、u1986 - John Hopcroft(Cornell) & Robert Tarjan (Princeton): Graph algorithmsch1.30u1993 - Juris Hartmanis(Cornell) & Richard Stearns (SUNY Albany): Computational Complexity Theoryu1995 - Manual Blum(UC Berkeley): Complexity of recursive functions and its application in information securityu2

24、000 - Stephen Yau(Princeton): Random algorithm, complexity of communicationu2002 Ronald Rivest(MIT), Adi Shamir (Weizmann), Leonard Adleman(USC): RSA algorithm 算法与图灵奖算法与图灵奖超过超过1/3的的Turing奖获奖者其成果与算法有关奖获奖者其成果与算法有关ch1.31有趣的算法问题有趣的算法问题u背包问题背包问题1（物品可分割）：（物品可分割）：有一旅行者要从有一旅行者要从n n种物品中选取不超过种物品中选取不超过b b公斤重的行

25、李随身携带，要求总价公斤重的行李随身携带，要求总价值最大。值最大。例：设背包的容量为例：设背包的容量为5050千克。物品千克。物品1 1重重1010千克，价值千克，价值6060元；物品元；物品2 2重重2020千克，千克，价值价值100100元；物品元；物品3 3重重3030千克，价值千克，价值120120元。求总价值最大。元。求总价值最大。u背包问题背包问题2（物品不可分割）：（物品不可分割）：设有设有n=8n=8个体积分别为个体积分别为5454，4545，4343，2929，2323，2121，1414，1 1的物体和一个容积的物体和一个容积为为C=110C=110的背包，问选择哪几个物体

26、装入背包可以使其装的最满。的背包，问选择哪几个物体装入背包可以使其装的最满。ch1.32有趣的算法问题有趣的算法问题u约瑟夫环（约瑟夫环（Josephus cycle）编号为编号为1 1，2 2，3 3，n n的的n n个人按顺时针方向围坐一圈。个人按顺时针方向围坐一圈。任选一个正整数作为报数上限任选一个正整数作为报数上限m m，从第一个人开始按顺时针，从第一个人开始按顺时针方向自方向自1 1开始顺序报数，报到开始顺序报数，报到m m时停止报数，报时停止报数，报m m的人出列。的人出列。从他在顺时针方向上的下一个人开始重新从从他在顺时针方向上的下一个人开始重新从1 1报数，如此下报数，如此下去

27、，直到最后圈中只剩下最后一个人（胜利者）。请设计程去，直到最后圈中只剩下最后一个人（胜利者）。请设计程序输出胜利者。序输出胜利者。 一般解法：用链表实现一般解法：用链表实现数学解法：数学解法：void main() int n, m, i, s=0; scanf(%d%d, &n, &m); for (i=2; in) Swap(m,n);return RGcd(m,n); int RGcd(int m,int n) /欧几里德欧几里德递归递归算法算法if (m=0) return n; /终止条件终止条件return RGcd(n%m,m);ch1.381.3 算法设计与分析

28、算法设计与分析u如何设计算法如何设计算法选择算法设计策略选择算法设计策略所求问题符合某种所求问题符合某种算法设计策略算法设计策略处理的问题特性。处理的问题特性。u如何表示算法如何表示算法描述算法描述算法自然语言、流程图、伪代码、程序设计语言。本书中使用自然语言、流程图、伪代码、程序设计语言。本书中使用C/C+语言语言描述。描述。u如何确认算法如何确认算法正确性证明正确性证明对于所有合法的输入，能在有限时间内输出正确的结果，称算法是对于所有合法的输入，能在有限时间内输出正确的结果，称算法是正确正确的。的。 确认一个算法是否正确的活动，称为确认一个算法是否正确的活动，称为算法确认算法确认；（大多数

29、情况下，人们通过（大多数情况下，人们通过程序测试程序测试和和调试调试来排错进行算法的正确性证明）来排错进行算法的正确性证明） 使用使用数学方法数学方法证明算法的正确性，称为证明算法的正确性，称为算法证明算法证明；（常用的算法正确性证明方法为（常用的算法正确性证明方法为数学归纳法数学归纳法。如：。如：P9证明程序证明程序1-1的正确性的正确性）u如何分析算法如何分析算法算法分析指对算法的算法分析指对算法的执行执行时间时间和所需和所需空间空间的估算。的估算。 设计出复杂性尽可能低的算法，或对现有的算法进行改进；设计出复杂性尽可能低的算法，或对现有的算法进行改进； （设计算法设计算法） 从解决同一问

30、题的多种算法中选出复杂性最低者。从解决同一问题的多种算法中选出复杂性最低者。 （选择算法选择算法）那么，如何证明算法是那么，如何证明算法是不正确不正确的？的？ch1.39u算法问题的求解过程算法问题的求解过程(Problem Solving)理解问题理解问题选择算法设计策略选择算法设计策略（确定数据结构）（确定数据结构）设计算法设计算法正确性证明正确性证明分析算法分析算法编写程序代码编写程序代码ch1.40补充：数学归纳法（例补充：数学归纳法（例1）证明：平面上任意条直线构成的区域可以仅使用两证明：平面上任意条直线构成的区域可以仅使用两种颜色进行着色。种颜色进行着色。证明：显然，直线数目证明：

31、显然，直线数目n=1时可以仅需两种颜色进行着色。时可以仅需两种颜色进行着色。假设假设平面上小于平面上小于n条直线构成的区域能仅用两种颜色来着色。条直线构成的区域能仅用两种颜色来着色。n那么考虑那么考虑n条直线时的情况，在添加第条直线时的情况，在添加第n条直线后条直线后如何对原如何对原着色方案进行修改着色方案进行修改：根据区域位于第根据区域位于第n条直线的哪一侧，可以把这些区域分成两条直线的哪一侧，可以把这些区域分成两组，保留其中一组区域的颜色，反转另一组区域的颜色。组，保留其中一组区域的颜色，反转另一组区域的颜色。ch1.41补充：数学归纳法（例补充：数学归纳法（例1）证明：平面上任意条直线构

32、成的区域可以仅使用两证明：平面上任意条直线构成的区域可以仅使用两种颜色进行着色。种颜色进行着色。n现证该方案为有效着色：现证该方案为有效着色： 考察两个相邻区域考察两个相邻区域R1和和R2。 如果这两个区域都在第如果这两个区域都在第n条直线的条直线的同侧同侧，那么根据归纳假，那么根据归纳假设，它们在添上第设，它们在添上第n条直线之前颜色就不同。虽然它们可能条直线之前颜色就不同。虽然它们可能需要改变着色，但无论如何它们的颜色仍然是不同的。需要改变着色，但无论如何它们的颜色仍然是不同的。 如果这两个区域的如果这两个区域的公共边是第公共边是第n条直线的一部分条直线的一部分，那么在，那么在添上第添上第

33、n条直线前它们属于同一区域。既然反转了其中一个条直线前它们属于同一区域。既然反转了其中一个区域的颜色，那么现在它们的颜色一定不同。区域的颜色，那么现在它们的颜色一定不同。ch1.42补充：数学归纳法（例补充：数学归纳法（例2）证明下面猜想：下面三角形中第证明下面猜想：下面三角形中第i行的和是行的和是i3。11=538=+971127=+1315191764=+2927252123125=+思路：要证明第思路：要证明第i行的和是行的和是i3，只需证明第，只需证明第(i+1)行和第行和第i行的行的差是差是(i+1)3-i3。ch1.43补充：数学归纳法（例补充：数学归纳法（例2）11=538=+9

34、71127=+1315191764=+2927252123125=+证明：证明：由于这些数都是按序排列的奇数，且第由于这些数都是按序排列的奇数，且第i行有行有i个数个数。所。所以第以第(i+1)行第行第1个数和第个数和第i行第行第1个数相差个数相差2i。同样，第。同样，第2个数，个数，第第3个数，第个数，第4个数均是这样个数均是这样.一共有一共有i个差，每个差个差，每个差2i。另外，。另外，第第(i+1)行末尾的最后一个数行末尾的最后一个数，不与上一行的任何一个数相匹，不与上一行的任何一个数相匹配。配。因此，这两行的差就是因此，这两行的差就是2i2加上第加上第(i+1)行的最后一个数。行的最后

35、一个数。因此因此仅需证明仅需证明第第(i+1)行的最后一个数值为行的最后一个数值为(i+1)3-i3-2i2=i2+3i+1导出命题（将一个求和的问题规约成了求某一项的问题）导出命题（将一个求和的问题规约成了求某一项的问题）ch1.44补充：数学归纳法（例补充：数学归纳法（例2）11=538=+971127=+1315191764=+2927252123125=+证明：上述命题对证明：上述命题对i=1时成立。时成立。则则只要证明第（只要证明第（i+1）行的最后一个数和第）行的最后一个数和第i行的最后一个数之行的最后一个数之差等于差等于i2+3i+1-(i-1)2+3(i-1)+1=2i+2即可

36、即可。而我们已经得到第而我们已经得到第(i+1)行和第行和第i行的对应项的差是行的对应项的差是2i。因此第因此第(i+1)行最后一个数与第行最后一个数与第i行的最后一个数的差是行的最后一个数的差是2i+2，猜测成立，证明完成。猜测成立，证明完成。证明嵌套的归纳假设：第（证明嵌套的归纳假设：第（i+1）行的最后一个数是）行的最后一个数是i2+3i+1。ch1.45补充：数学归纳法（例补充：数学归纳法（例3）证明（欧拉公式）：任意一张连通平面图的节点数证明（欧拉公式）：任意一张连通平面图的节点数(V)、边数边数(E)和面数和面数(F)的关系可由公式的关系可由公式V+F=E+2表示。表示。又如：上图

37、包含又如：上图包含11个节点、个节点、19条边和条边和10个面。个面。如：正方形包含如：正方形包含4个节点、个节点、4条边和条边和2个面。个面。ch1.46补充：数学归纳法（例补充：数学归纳法（例3）证明（欧拉公式）：任意一张连通平面图的节点数证明（欧拉公式）：任意一张连通平面图的节点数(V)、边数边数(E)和面数和面数(F)的关系可由公式的关系可由公式V+F=E+2表示。表示。证明：证明：首先考察只有首先考察只有一个面一个面的图。这样的图不包含回路，否的图。这样的图不包含回路，否则，回路至少构成一个面，回路以外构成另一个面。则，回路至少构成一个面，回路以外构成另一个面。这种连通无回路的图被称

38、为这种连通无回路的图被称为树树，现证明对任意树，现证明对任意树V+1=E+2成立：成立：（也即只需证明：（也即只需证明：有有V个顶点的树有个顶点的树有V-1条边条边即可。）即可。）证明：显然，有证明：显然，有1个顶点的树有个顶点的树有0条边。条边。假设有假设有n个顶点的树有个顶点的树有n-1条边成立，则考察有条边成立，则考察有n+1个节点个节点的树：的树：至少存在一个节点，与树中其他节点间只有一条边相连至少存在一个节点，与树中其他节点间只有一条边相连。（否则若所有节点都与至少（否则若所有节点都与至少2条边相连，则一定会有回路存在，条边相连，则一定会有回路存在，与树的定义矛盾。）与树的定义矛盾。

39、）将该节点连同与之相连的一条边从树上移将该节点连同与之相连的一条边从树上移走走，得到的图仍是一棵树（只不过，得到的图仍是一棵树（只不过少了一个节点和一条边少了一个节点和一条边）。）。根据根据归纳假设条件归纳假设条件此时满足此时满足V+1=E+2。可知。可知n+1个节点时，个节点时，命题也成立，得证。命题也成立，得证。ch1.47补充：数学归纳法（例补充：数学归纳法（例3）证明（欧拉公式）：任意一张连通平面图的节点数证明（欧拉公式）：任意一张连通平面图的节点数(V)、边数边数(E)和面数和面数(F)的关系可由公式的关系可由公式V+F=E+2表示。表示。n只有只有一个面一个面的图满足的图满足V+1

40、=E+2已证，归纳基础成立。已证，归纳基础成立。n假设有假设有n个面个面的平面图如果有的平面图如果有E条边和条边和V个节点，那么个节点，那么V+n=E+2。n考察有考察有n+1个面个面的图：的图：一定存在某个面一定存在某个面f，使得，使得f与最外面的那个面相邻。因为与最外面的那个面相邻。因为f是面，所是面，所以以f一定由回路围成。那么我们就一定由回路围成。那么我们就去掉去掉f与最外面的那个面之间的与最外面的那个面之间的那条边那条边，这样就，这样就少了一个面和一条边少了一个面和一条边。根据归纳假设条件根据归纳假设条件，此时满足，此时满足V+n=E+2。可知。可知n+1个面时，命题个面时，命题也成立，得证。也成立，得证。证明过程中对其中一个参数（证明过程中对其中一个参数（面数面数F）进行归纳，而归纳）进行归纳，而归纳基础的成立又需要对另一个参数（基础的成立又需要对另一个参数（结点数结点数V）进行归纳。）进行归纳。说明：选择归纳顺序需谨慎，对算法的效率有很大影响。说明：选