1、算法与复杂性算法与复杂性刘杰南华大学计算机学院软件工程系课程简介课程简介1 1课程学时课程学时 总学时：总学时：4848学时（理论）学时（理论）2 2课程主要内容课程主要内容p 介绍算法的概念及算法分析的基础知识；介绍算法的概念及算法分析的基础知识；p 介绍一些经典算法介绍一些经典算法*蛮力法蛮力法 分治法分治法 贪心法贪心法 动态规划动态规划 回溯法回溯法 分支限界法分支限界法 NP完全问题完全问题 *算法赏析算法赏析3 3考核方法考查考核方法考查 课堂表现、考勤、实验（占课堂表现、考勤、实验（占6060）期末考查（小组答辩，占期末考查（小组答辩，占4040）4 4本课程主要参考书本课程主要
2、参考书11王晓东编著，王晓东编著，计算机算法设计与分析计算机算法设计与分析(第第4版版)，电子工业出，电子工业出版社，版社，2012201222屈婉玲等，算法设计与分析，清华大学出版社，屈婉玲等，算法设计与分析，清华大学出版社，20112011刘汝佳刘汝佳“白皮书白皮书”、“黑宝书黑宝书”5 5网上学习（百度网上学习（百度&CSDN&CSDN）作业提交作业提交l算法设计实现类的作业算法设计实现类的作业l网址：网址：http:/:9988/（南华（南华OJ）l登陆账号：学号登陆账号：学号（如：（如：20134330101）l密码：学号后面的密码：学号后面的6位数字位数字（以上面账号为例，则密码（
3、以上面账号为例，则密码为为330101）注意：注意：已注册过的同学提交本课程作业请用新账号和口令。已注册过的同学提交本课程作业请用新账号和口令。l课程课程PPT和参考资料、其他作业（报告）和参考资料、其他作业（报告）lhttp:/61.187.179.69:9988/sc8/（南华大学数字化教学（南华大学数字化教学中心）中心）l计算机：计算机：WSTD-6758 软件软件2班：班：UFSM-0601l软件软件3班：班：KQEQ-5247 物联网：物联网：PPKL-3080l船本软件：船本软件：PWAH-5676 船本计算机：船本计算机：VPKW-5550从经典的从经典的IBM面试题说起面试题说
4、起l村子中有村子中有50个人，每人有一条狗。在这个人，每人有一条狗。在这50条狗中有病狗条狗中有病狗（这种病不会传染）。于是人们就要找出病狗。（这种病不会传染）。于是人们就要找出病狗。l每个人可以观察其他的每个人可以观察其他的49条狗，以判断它们是否生病（如条狗，以判断它们是否生病（如果有病一定能看出来），只是自己的狗不能看。观察后得果有病一定能看出来），只是自己的狗不能看。观察后得到的结果不得交流，也不能通知病狗的主人。主人一旦推到的结果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪毙自己的狗（发现后必须在一算出自己家的是病狗就要枪毙自己的狗（发现后必须在一天内枪毙），而
5、且每个人只有权利枪毙自己的狗，没有权天内枪毙），而且每个人只有权利枪毙自己的狗，没有权利打死其他人的狗。利打死其他人的狗。l第一天大家全看完了，但枪没有响，第二天仍没有枪响。第一天大家全看完了，但枪没有响，第二天仍没有枪响。到了第三天传来一阵枪声，问村里共有几条病狗，如何推到了第三天传来一阵枪声，问村里共有几条病狗，如何推算得出？算得出？Brainstorml腾讯面试题：腾讯面试题：给你给你10分钟时间，根据上排给出十个数，在分钟时间，根据上排给出十个数，在其下排填出对应的十个数，要求下排每个数都是先前上排其下排填出对应的十个数，要求下排每个数都是先前上排那十个数在下排出现的次数。那十个数在下
6、排出现的次数。上排的十个数如下：上排的十个数如下：【0，1，2，3，4，5，6，7，8，9】l阿里巴巴面试题：阿里巴巴面试题：澳大利亚的父母喜欢女孩，如果生出来澳大利亚的父母喜欢女孩，如果生出来的第一个女孩，就不再生了，如果是男孩就继续生，直到的第一个女孩，就不再生了，如果是男孩就继续生，直到生到第一个女孩为止，问若干年后，男女的比例是多少？生到第一个女孩为止，问若干年后，男女的比例是多少？l淘宝校园笔试题：淘宝校园笔试题：N个鸡蛋放到个鸡蛋放到M个篮子中，篮子不能为空，个篮子中，篮子不能为空，要满足：对任意不大于要满足：对任意不大于N的数量，能用若干个篮子中鸡蛋的数量，能用若干个篮子中鸡蛋的
7、和表示。对输入整数的和表示。对输入整数N和和M，输出所有可能的鸡蛋的放法。，输出所有可能的鸡蛋的放法。l百度移动开发笔试题：百度移动开发笔试题：三色球排序的问题，相同的球放到三色球排序的问题，相同的球放到一起，让你按顺序输出红白蓝三种颜色的球，可以用一起，让你按顺序输出红白蓝三种颜色的球，可以用012来表示，要求只能扫描一次数组。来表示，要求只能扫描一次数组。为什么学习算法为什么学习算法？关于用计算机解决问题关于用计算机解决问题计算机的能力计算机的能力每秒每秒5000次次每秒数千亿次每秒数千亿次继电器继电器真空管真空管晶体管晶体管集成电路集成电路大规模集成电路大规模集成电路超大规模集成电路超大
8、规模集成电路元器件元器件“单兵作战单兵作战”计算机网络计算机网络单机的串行单机的串行分布计算分布计算结构结构算法算法运算速度运算速度世界最快的超级计算机（世界最快的超级计算机（2014）10.神秘计算机神秘计算机这是美国政府运营的一台神秘的、基于无限带宽技这是美国政府运营的一台神秘的、基于无限带宽技术的术的Cray CS-Storm机器，具体位置不详。它是唯一新入选榜单者，也机器，具体位置不详。它是唯一新入选榜单者，也是最节能的超级计算机，每瓦特电可每秒进行是最节能的超级计算机，每瓦特电可每秒进行2386.42百万次浮点运算。百万次浮点运算。最高速度：每秒最高速度：每秒3.57千万亿次浮点运算
9、，总核心数：千万亿次浮点运算，总核心数：7.28万个万个 9.Vulcan（美国）（美国）Vulcan是跻身最新榜单的美国能源部四大超级计算是跻身最新榜单的美国能源部四大超级计算机性能最弱的一台，它目前应用于能源部的高性能运算创新中心。最高机性能最弱的一台，它目前应用于能源部的高性能运算创新中心。最高速度：每秒速度：每秒4.29千万亿次浮点运算，总核心数：千万亿次浮点运算，总核心数：39.3216万个万个8.JUQUEEN（德国）（德国）JUQUEEN是前十榜单的是前十榜单的“常客常客”，2012年年中年年中以来未曾落选过。它运营于德国北莱茵以来未曾落选过。它运营于德国北莱茵-威斯特伐利亚的威
10、斯特伐利亚的Jlich研究中心。研究中心。相比欧洲上榜的另一台超级计算机，它的性能较弱。最高速度：每秒相比欧洲上榜的另一台超级计算机，它的性能较弱。最高速度：每秒5千万亿次浮点运算，总核心数：千万亿次浮点运算，总核心数：45.8752万个万个7.Stampede（美国）（美国）该来自德州大学的超级计算机是此榜单上的唯一该来自德州大学的超级计算机是此榜单上的唯一一台戴尔产品，它也是全球最强大的学术用超级计算机。最高速度：每一台戴尔产品，它也是全球最强大的学术用超级计算机。最高速度：每秒秒5.17千万亿次浮点运算，总核心数：千万亿次浮点运算，总核心数：46.2462万个万个6.Piz Daint（
11、瑞士）（瑞士）Piz Daint是欧洲性能最强大的一台超级计算机，是欧洲性能最强大的一台超级计算机，它运营于位于卢加诺的瑞士国家计算中心，以该中心它运营于位于卢加诺的瑞士国家计算中心，以该中心80英里以外的阿尔英里以外的阿尔卑斯山命名。最高速度：每秒卑斯山命名。最高速度：每秒6.27千万亿次浮点运算，总核心数：千万亿次浮点运算，总核心数：11.5984万个万个5.Mira（美国）（美国）Mira是前十榜单的另一位常客，效力于美国阿贡国家是前十榜单的另一位常客，效力于美国阿贡国家实验室。这是它第六次上榜，同时也是连续第四次位居第五位。最高速实验室。这是它第六次上榜，同时也是连续第四次位居第五位。
12、最高速度：每秒度：每秒8.59千万亿次浮点运算，总核心数：千万亿次浮点运算，总核心数：78.6432万个万个4.K Computer（日本）（日本）富士通富士通K Computer登上前十榜单的次数比登上前十榜单的次数比Mira还要多，达到还要多，达到10次。次。2011年年6月首次上榜它便是全球最快速的超级月首次上榜它便是全球最快速的超级计算机。跟计算机。跟Mira一样，它也是连续一样，它也是连续4次入选。最高速度：每秒次入选。最高速度：每秒10.5千万千万亿次浮点运算，总核心数：亿次浮点运算，总核心数：70.5024万个万个3.Sequoia（美国）（美国）Sequoia在跻身前在跻身前5
13、00强榜单的时间比富士通强榜单的时间比富士通K Computer仅晚仅晚6个月，第二次上榜便荣登首位。它运行于美国能源部位个月，第二次上榜便荣登首位。它运行于美国能源部位于加州的劳伦斯利弗莫尔国家实验室。最高速度：每秒于加州的劳伦斯利弗莫尔国家实验室。最高速度：每秒17.2千万亿次浮千万亿次浮点运算，总核心数：点运算，总核心数：157.2864万个万个2.Titan（美国）（美国）该美国超级计算机也是能源部的机器，它运行于位于该美国超级计算机也是能源部的机器，它运行于位于田纳西州的橡树岭国家实验室。在最近的田纳西州的橡树岭国家实验室。在最近的4次评比中，它都位居第二位。次评比中，它都位居第二位
14、。最高速度：每秒最高速度：每秒17.6千万亿次浮点运算，总核心数：千万亿次浮点运算，总核心数：56.064万个万个1.天河二号（中国）天河二号（中国）运行于位于广州的超级计算中心。最高速度：每秒运行于位于广州的超级计算中心。最高速度：每秒33.9千万亿次浮点运算，总核心数千万亿次浮点运算，总核心数312万个。万个。计算机什么都能做计算机什么都能做?天河二号：天河二号：3200032000颗主颗主CPUCPU，4800048000个协处理器个协处理器，300300多万个计算核心多万个计算核心，峰值计算速度达到每秒，峰值计算速度达到每秒5.495.49亿亿次，而持续计算时的速度每秒可达亿亿次，而持
15、续计算时的速度每秒可达3.393.39亿亿次。亿亿次。假设每人每秒钟进行一次运算，假设每人每秒钟进行一次运算，“天河二号天河二号”运算一小时，相当于运算一小时，相当于1313亿人同时用计算器算亿人同时用计算器算上上10001000年。年。除了助力除了助力探月工程探月工程、载人航天载人航天等政府科研项目外，等政府科研项目外，天河二号目前已经逐渐应用于民用领域，比如天河二号目前已经逐渐应用于民用领域，比如石石油勘探油勘探、汽车飞机的设计制造汽车飞机的设计制造、基因测序基因测序等。等。天河二号能做什么？天河二号能做什么？比如拿最简单例子，比如拿最简单例子，2626个英文字母全排列，个英文字母全排列，
16、它的排列数为：它的排列数为：2626！4 410102626以每年以每年365365天计算，共有天计算，共有 3653652424360036003.15363.153610107 7秒秒以每秒能完成以每秒能完成10109 9个排列的超高速电子计算机来个排列的超高速电子计算机来做这项工作，需要做这项工作，需要 4 410102626/(3.1536/(3.153610101616)1.2)1.210101010年年即使计算机运行速度随着技术的提高，恐怕也还即使计算机运行速度随着技术的提高，恐怕也还是不可能实现的。因计算机的速度再提高也有它是不可能实现的。因计算机的速度再提高也有它的极限。的极限
17、。用计算机解决问题的关键用计算机解决问题的关键算法算法一个熟悉的公式（一个熟悉的公式（Nicklaus Wirth）：）：程序程序=算法十数据结构算法十数据结构l算法是计算机科学的基础，更是程序的基石，算法是计算机科学的基础，更是程序的基石，只有具有良好的算法基础才能成为训练有素只有具有良好的算法基础才能成为训练有素的软件人才。的软件人才。l对于计算机专业的学生来说，学习算法的理对于计算机专业的学生来说，学习算法的理由是非常充分的。因为你必须知道来自不同由是非常充分的。因为你必须知道来自不同计算领域的重要算法，你也必须学会设计新计算领域的重要算法，你也必须学会设计新的算法、确认其正确性并分析其
18、效率。的算法、确认其正确性并分析其效率。1 1、学习算法的必要性、学习算法的必要性2 2、研究算法的重要性、研究算法的重要性2.1 2.1 问题能解决吗问题能解决吗 假设某一负责人交给你一个很难的任务，几假设某一负责人交给你一个很难的任务，几天后询问你问题解决了没有。可能会发生如下天后询问你问题解决了没有。可能会发生如下图这样的情况：图这样的情况：问：问：“交给你的问题，解决方案设计出来了吗？交给你的问题，解决方案设计出来了吗？”答：答：“我找不到一个有效的算法来解决它，没能完我找不到一个有效的算法来解决它，没能完成任务。成任务。”问：问：“交给你的问题，解决方案设计出来了吗？交给你的问题，解
19、决方案设计出来了吗？”答：答：“我找不到一个有效的算法来解决它，因为我找不到一个有效的算法来解决它，因为 这样的算法是不存在的。这样的算法是不存在的。”(不过，要证明一个问题不存在有效算法，往往跟不过，要证明一个问题不存在有效算法，往往跟寻找有效算法一样难。寻找有效算法一样难。)问：问：“交给你的问题，解决方案设计出来了吗？交给你的问题，解决方案设计出来了吗？”答：答：“我找不到一个有效的算法来解决它，但不是我找不到一个有效的算法来解决它，但不是 我不行，因为所有这些名人也都找不到解决它我不行，因为所有这些名人也都找不到解决它 的有效算法。的有效算法。”如果是你的话，你愿意是哪种结果？如果是你
20、的话，你愿意是哪种结果？伟大的智者伟大的智者Donald E.Knuth（美）高德纳（美）高德纳 计算机程计算机程序设计艺术序设计艺术的作者；的作者；谦逊的长者谦逊的长者Edsger Wybe（荷兰）（荷兰）Dijkstra算法（最短算法（最短路径算法）发明者；路径算法）发明者；运筹学大师运筹学大师George Dantzing（俄国）在运筹学建树极（俄国）在运筹学建树极高，获得了包括高，获得了包括“冯诺伊曼理论奖冯诺伊曼理论奖”在内的诸多奖项。；在内的诸多奖项。；推动时代前进的人推动时代前进的人James Cooley（美）（美）FFT（快速傅利（快速傅利叶变换）算法发明者，该算法主要用语数
21、字信号处理技术；叶变换）算法发明者，该算法主要用语数字信号处理技术；FORTRAN之父之父John Backus（美）（美）FORTRAN之父，之父，又提出规范编程语言语法的又提出规范编程语言语法的Backus-Naur Form(BNF)；影响计算机算法世界的十位大师影响计算机算法世界的十位大师实践探索先锋实践探索先锋 Jon Bentley（美）（美）Programming Pearls（中文名（中文名编程珠玑编程珠玑）作者，精于软件工程；）作者，精于软件工程；Pascal之父之父Nicklaus Wirth（瑞士）（瑞士）PASCAL之父，提出了之父，提出了“算法算法+数据结构数据结构=
22、程序程序”，他是创办，他是创办Borland公司的公司的Philie kahn的的老师；老师；算法的讲解者算法的讲解者Robort Sedgewick（美）算法讲解者；（美）算法讲解者；计算机领域的爵士计算机领域的爵士 Tony Hoare（英）快速排序算法（英）快速排序算法（Quick Sort）发明者，年加入微软创办了剑桥研究院；）发明者，年加入微软创办了剑桥研究院；首席算法官首席算法官 Udi Manber（美）（美）Google副总裁，首席算法官。副总裁，首席算法官。影响计算机算法世界的十位大师影响计算机算法世界的十位大师来自圣经的十大算法来自圣经的十大算法No10:Huffman c
23、oding（霍夫曼编码）（霍夫曼编码）No9:Binary Search（二分查找）（二分查找）No8:Miller-Rabin算法（基于概率的素数测试算法）算法（基于概率的素数测试算法）No7:Depth First Search、Breadth First Search（深度、广（深度、广 度优先搜索）度优先搜索）No6:Gentrys Fully Homomorphic Encryption Scheme （绅士完全同态加密机制）算法（绅士完全同态加密机制）算法No5:Floyd-Warshall all-pairs最短路径算法最短路径算法No4:Quicksort（快速排序）（快速排序
24、）No3:BFPRT 算法（第算法（第k大元素平均复杂度为大元素平均复杂度为O（N）的算法，）的算法，俗称俗称中位数之中位数算法中位数之中位数算法）No2:Knuth-Morris-Pratt字符串匹配算法字符串匹配算法No1:Union-find（并查集）（并查集）源自源自CSDN博客，博主博客，博主v_JULY_v为什么要学算法？为什么要学算法？l如果不如果不学学，你可能用一，你可能用一个个很花很花钱钱（Time,Space）的的Algorithm去解去解决问题决问题lLife-time Job:l永远永远知道解某一知道解某一问题问题最佳的最佳的Algorithm是是什么什么l方法：方法：
25、对于对于自己的自己的领域随时领域随时要查要查paper，update最佳的最佳的algorithms或至少知道可以或至少知道可以问问谁谁。为什么要学算法？为什么要学算法？l2.如果不如果不学学，你可能去，你可能去对对NP-Complete的的问题问题去找去找efficient的解的解lLife-time Job:l去知道去知道哪些问题哪些问题是是NP-Complete的的Real ApplicationAverage Performance好的好的找找Approximating的解的解作为即将从事计算机专业的人士作为即将从事计算机专业的人士l实践上实践上l必须了解计算领域中不同问题的一系列标准
26、必须了解计算领域中不同问题的一系列标准算法。算法。l具备设计新算法和分析其效率的能力。具备设计新算法和分析其效率的能力。l理论上理论上l算法研究是计算机科学的基石。算法研究是计算机科学的基石。l培养分析问题的能力！培养分析问题的能力！2.2 2.2 问题解决的好吗？问题解决的好吗？设计出解决问题的算法后，要知道算法的设计出解决问题的算法后，要知道算法的优劣好坏，是好算法则不必对其怀疑而再浪费优劣好坏，是好算法则不必对其怀疑而再浪费时间进行研究。不是好算法则应再进行研究改时间进行研究。不是好算法则应再进行研究改进。而如何知道算法的优劣好坏，需要学习分进。而如何知道算法的优劣好坏，需要学习分析算法
27、的方法。析算法的方法。要设计出好算法，需要学习算法设计的常要设计出好算法，需要学习算法设计的常用方法。用方法。一些有趣的问题一些有趣的问题(1)巡回推销员问题巡回推销员问题:设有设有n个城市，已知任意两城个城市，已知任意两城市间之距离，现有一推销员想从某一城市出发巡市间之距离，现有一推销员想从某一城市出发巡回经过每一城市（且每城市只经过一次），最后回经过每一城市（且每城市只经过一次），最后又回到出发点，问如何找一条最短路径。又回到出发点，问如何找一条最短路径。设距离矩阵如下：设距离矩阵如下：0186572641805673556556041772734103964557390D试一试求出最短路
28、径。试一试求出最短路径。（2)2)皇后问题皇后问题:这是高斯这是高斯18501850年提出的一个年提出的一个著名问题：著名问题：国际象棋中的国际象棋中的“皇后皇后”在横向、在横向、直向、和斜向都能走步和吃子，问在直向、和斜向都能走步和吃子，问在n nn n 格格的棋盘上如何能摆上的棋盘上如何能摆上n n个皇后而使她们都不能个皇后而使她们都不能互相吃。互相吃。当当n n很大时，问题很难。很大时，问题很难。对于对于n=8,n=8,现已知此问题共有现已知此问题共有9292种解，但只种解，但只有有1212种是独立的，其余的都可以由这种是独立的，其余的都可以由这1212种利种利用对称性或旋转而得到。用对
29、称性或旋转而得到。设设n=4n=4，试一试。，试一试。(3(3）设天平有一些设天平有一些2525克的砝码，一些克的砝码，一些1010克的砝码，克的砝码，一些一些5 5克的砝码和一些克的砝码和一些1 1克的砝码。现要称克的砝码。现要称6363克的物克的物体，问至少需要用几个砝码。体，问至少需要用几个砝码。(4(4）背包问题背包问题1 1：有一旅行者要从：有一旅行者要从n n种物品中选取种物品中选取不超过不超过b b公斤重的行李随身携带，要求总价值最大。公斤重的行李随身携带，要求总价值最大。例：设背包的容量为例：设背包的容量为5050千克。物品千克。物品1 1重重1010千克，价千克，价值值606
30、0元；物品元；物品2 2重重2020千克，价值千克，价值100100元；物品元；物品3 3重重3030千克，价值千克，价值120120元。求总价值最大。元。求总价值最大。（5 5）背包问题背包问题2 2：设有：设有n=8n=8个体积分别为个体积分别为5454，4545，4343，2929，2323，2121，1414，1 1的物体和一个容积为的物体和一个容积为C=110C=110的背包，问选择哪几个物体装入背包可以使其装的的背包，问选择哪几个物体装入背包可以使其装的最满。最满。（6 6）装箱问题：设有体积分别为装箱问题：设有体积分别为v v1 1,v,v2 2,v,vn n的的n n种物品种物
31、品u u1 1,u,u2 2,u,un n装到容量为装到容量为L L的箱子里。的箱子里。不同的装箱方案所需的箱子数目可能不同，不同的装箱方案所需的箱子数目可能不同，问如何装箱能装完这问如何装箱能装完这n n种物品且使用的箱子数种物品且使用的箱子数目最少。目最少。（7 7）平面图的四色猜想问题：一个平面图平面图的四色猜想问题：一个平面图是否用四种颜色就可使相邻的区域颜色都不是否用四种颜色就可使相邻的区域颜色都不相同？相同？数据挖掘领域十大经典算法数据挖掘领域十大经典算法lC4.5：机器学习算法中的一个分类决策树算法，是：机器学习算法中的一个分类决策树算法，是决策树核心算法决策树核心算法ID3的改
32、进算法。的改进算法。lk-means算法算法：是一个聚类算法，把：是一个聚类算法，把n的对象根据的对象根据他们的属性分为他们的属性分为k个分割个分割(k n)Swap(m,n);return RGcd(m,n);欧几里德迭代算法欧几里德迭代算法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;Gcd的连续整数检测算法的连续整数检测算法int Gcd(int m,int n)if(m=0)return n;if(n=0)return m;i
33、nt t=mn?n:m;while(m%t|n%t)t-;return t;l中学的解题思路：l（1）找到m的所有质因数l（2）找到n的所有质因数l（3）找到（1），（2）中的公因数l（4）求公因数的积，该乘积为m、n的最大公约数1.2 问题求解方法问题求解方法1.2.1 问题和问题求解问题和问题求解问题求解（问题求解（problem solving）是寻找一种方法来实）是寻找一种方法来实现目标。现目标。问题求解过程问题求解过程（problem solving process）通过使）通过使用问题领域知识来理解和定义问题，选择和使用适当用问题领域知识来理解和定义问题，选择和使用适当的问题求解策
34、略、技术和工具，将一个问题描述转换的问题求解策略、技术和工具，将一个问题描述转换成问题解的过程。成问题解的过程。计算机求解问题的关键之一是寻找一种计算机求解问题的关键之一是寻找一种问题求解策略问题求解策略（problem solving strategy），得到求解问题的算），得到求解问题的算法，从而得到问题的解。法，从而得到问题的解。1.2.2 问题求解过程问题求解过程 理解问题理解问题（understand the problem）设计方案设计方案（design a plan）实现方案实现方案（carry out the plan）回顾复查回顾复查（look back）1.2.3 系统生命
35、周期系统生命周期l 一个计算机程序的开发过程就是使用计算机求解问一个计算机程序的开发过程就是使用计算机求解问题的过程。题的过程。软件工程软件工程（software engineering）将）将软件开发和维护过程分成若干阶段，称为软件开发和维护过程分成若干阶段，称为系统生命系统生命周期周期（system life cycle）或）或软件生命周期。软件生命周期。l软件生命周期软件生命周期划分为划分为:l分析（分析（analysis）l设计（设计（design）l编码（编码（coding or programming）l测试（测试（testing）l维护（维护（maintenance）等等5个阶段
36、。前个阶段。前4个阶段属于开发期，最后一个阶个阶段属于开发期，最后一个阶段处于运行期。段处于运行期。1.3 算法设计与分析算法设计与分析1.3.1 算法问题求解过程算法问题求解过程l 算法分类算法分类一个一个精确算法精确算法（exact algorithm）总能保证求得问题）总能保证求得问题的解。的解。一个一个启发式算法启发式算法（heuristic algorithm）通过使用某种规则、）通过使用某种规则、简化或智能猜测来减少问题求解简化或智能猜测来减少问题求解时间。时间。证明正确性证明正确性分析算法分析算法设计程序设计程序理解问题理解问题精确解或近似解精确解或近似解选择数据结构选择数据结构
37、算法设计策略算法设计策略设计算法设计算法 对于最优化问题，一个算法如果致力于寻找近对于最优化问题，一个算法如果致力于寻找近似解而不是最优解，被称为似解而不是最优解，被称为（approximation algorithm）。）。如果在算法中需做出某些随机选择，则称为如果在算法中需做出某些随机选择，则称为（randomized algorithm）。）。1.3.2 如何设计算法如何设计算法l 使用计算机的问题求解策略主要指使用计算机的问题求解策略主要指算法设计策略算法设计策略（algorithm design strategy）。）。l掌握一些基本的算法设计策略，判断问题是否符合某掌握一些基本的算
38、法设计策略，判断问题是否符合某种策略处理的问题特性。种策略处理的问题特性。1.3.3 如何表示算法如何表示算法l 算法描述方法算法描述方法l自然语言自然语言 l流程图流程图 l伪代码伪代码 l程序设计语言程序设计语言 l教材使用教材使用 C/C+语言描述算法语言描述算法 1.3.4 如何确认算法如何确认算法确认一个算法是否正确的活动称为确认一个算法是否正确的活动称为算法确认算法确认（algorithm validation）。）。使用数学方法证明算法的正确性，称为使用数学方法证明算法的正确性，称为算法证明算法证明（algorithm proof）。）。程序测试程序测试（program test
39、ing）是指对程序模块或程）是指对程序模块或程序总体，输入事先准备好的样本数据（称为序总体，输入事先准备好的样本数据（称为测试用例测试用例，test case），检查该程序的输出，来发现程序存在），检查该程序的输出，来发现程序存在的错误及判定程序是否满足其设计要求的一项积极活的错误及判定程序是否满足其设计要求的一项积极活动动。1.3.5 如何分析算法如何分析算法算法分析算法分析（algorithm analysis）活动是指对算）活动是指对算法的执行时间和所需空间的估算。法的执行时间和所需空间的估算。当然在算法写成程序后，便可使用样本数据，实当然在算法写成程序后，便可使用样本数据，实际测量一个
40、程序所消耗的时间和空间，这称为程际测量一个程序所消耗的时间和空间，这称为程序的序的性能测量性能测量（performance measurement）。）。*1.4 递归和归纳递归和归纳1.4.1 递归递归l 递归定义递归定义递归（递归（recursive）定义）定义是一种直接或间接引用自是一种直接或间接引用自身的定义方法。身的定义方法。一个合法的递归定义包括两部分：一个合法的递归定义包括两部分：基础情况基础情况（base case）和）和递归部分递归部分。例例1-1 斐波那契数列斐波那契数列 斐波那契数列斐波那契数列1102110 nFFF,FFnnn当一个算法采用递归方式定义时便成为当一个算
41、法采用递归方式定义时便成为。一个递归算法是指直接或间接调用自身的。一个递归算法是指直接或间接调用自身的算法。算法。求求Fn long Fib(long n)if(n=1)return n;else return Fib(n-2)+Fib(n-1);可以用所谓的可以用所谓的递归树递归树（recursive tree）来描述）来描述程序程序1-4的函数的函数Fib执行时的调用关系。执行时的调用关系。N！？！？l 递归数据结构递归数据结构使用递归方式定义的数据结构称为使用递归方式定义的数据结构称为递归数据结构递归数据结构（recursive data structure）。）。1.4.2 递归算法示
42、例递归算法示例l 例例1-2 逆序输出正整数的各位数逆序输出正整数的各位数【程序程序1-5】void PrintDigit(unsigned int n)cout=10)PrintDigit(n/10);/以逆序输出前以逆序输出前k-1位数位数 l例例1-3 汉诺塔问题（汉诺塔问题（tower of Hanoi）假定有三个塔座：假定有三个塔座：X，Y，Z，在塔座，在塔座X上有上有n个直个直径大小各不相同，按圆盘大小从小到大编号为径大小各不相同，按圆盘大小从小到大编号为1，2，n的圆盘。现要求将的圆盘。现要求将X塔座上塔座上n个圆盘移个圆盘移到塔座到塔座Y上，并仍按同样顺序叠排。上，并仍按同样顺
43、序叠排。圆盘移动时必须遵循下列规则：圆盘移动时必须遵循下列规则：（1）每次只能移动一个圆盘；）每次只能移动一个圆盘；（2）圆盘可以加到塔座）圆盘可以加到塔座X，Y，Z中任意一个上；中任意一个上；（3）任何时刻都不能将一个较大的圆盘放在较小）任何时刻都不能将一个较大的圆盘放在较小的圆盘之上。的圆盘之上。汉诺塔问题汉诺塔问题enum tower A=X,B=Y,C=Z;void Move(int n,tower x,tower y)/将第将第n个圆盘从塔座个圆盘从塔座x移到塔座移到塔座y的顶部的顶部cout The disk n is moved from char(x)to top of tow
44、er char(y)endl;void Hanoi(int n,tower x,tower y,tower z)/将将x上部的上部的n个圆盘移到个圆盘移到y上，顺序不变。上，顺序不变。if(n)Hanoi(n-1,x,z,y);Move(n,x,y);Hanoi(n-1,z,y,x);1.4.3 归纳证明归纳证明l定理定理1-1 对于对于n0，程序，程序1-5是正确的。是正确的。证明：证明：（归纳法证明）（归纳法证明）当当n是是1位数时，程序显然是正确的。位数时，程序显然是正确的。假定函数假定函数PrintDigit对所有位数小于对所有位数小于k（k1）的正整）的正整数都能正确运行，当数都能正
45、确运行，当n的位数为的位数为k位时，此时有位时，此时有n10，算法必定先执行语句算法必定先执行语句cout 10)PrintDigit(n/10);。由于由于 n/10 是是n的前的前k-1位数字形成的数，归纳法假位数字形成的数，归纳法假设函数调用设函数调用PrintDigit(n/10)能够将它正确地（并能够将它正确地（并在有限步内）按数字的逆序输出，那么，现在先在有限步内）按数字的逆序输出，那么，现在先执行语句输出个位数字（执行语句输出个位数字（n%10），然后由于按逆），然后由于按逆序输出前序输出前k-1位数字的做法是能够正确按逆序输出位数字的做法是能够正确按逆序输出全部全部k位数字的，所以程序位数字的，所以程序1-5是正确的。是正确的。
