作者：陈小玉
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
趣学算法试读：
前言
编写背景有一天，一个学生给我留言：“我看到一些资料介绍机器人具有情感，真是不可思议，我对这个特别感兴趣，但我该怎么做呢？”我告诉他：“先看算法。”过了一段时间，这个学生苦恼地说：“算法书上那些公式和大段的程序不能执行，太令人抓狂！我好像懂了一点儿，却又什么都不懂！”我向他推荐了一本简单一点儿的书，他仍然表示不太懂。
问题出在哪里？数据结构？C语言？还是算法表达枯燥、晦涩难懂？
这些问题一点也不意外，你不会想到，有同学拿着C语言书问我：“这么多英文怎么办？for、if这样的单词是不是要记住？”我的天！我从来没考虑过for、if这些是英文，而且是要记的单词！就像拿起筷子吃饭，端起杯子喝水，我从来没考虑我喝的是HO。经过这件事情，2彻底颠覆了我以前的教学理念，终于理解为什么看似简单的问题，那么多人就是看不懂。我们真正需要的是一本算法入门书，一本要简单、简单、再简单的算法入门书。
有学生告诉我：“大多数算法书上的代码都不能运行，或者运行时有各种错误，每每如此都迷茫至崩溃……”我说：“你要理解算法而不是运行代码。”可这个学生告诉我：“你知道吗，我运行代码成功后是多么喜悦和自信！已经远远超越了运行代码的本身。”好吧，相信这本书将会给你满满的喜悦和自信。
本书从算法之美娓娓道来，没有高深的原理，也没有枯燥的公式，通过趣味故事引出算法问题，结合大量的实例及绘图展示，分析算法本质，并给出代码实现的详细过程和运行结果。如果你读这本书，像躺在躺椅上悠闲地读《普罗旺斯的一年》，这就对了！这就是我的初衷。
本书适合那些对算法有强烈兴趣的初学者，以及觉得算法晦涩难懂、无所适从的人，也适合作为计算机相关专业教材。它能帮助你理解经典的算法设计与分析问题，并获得足够多的经验和实践技巧，以便更好地分析和解决问题，为学习更高深的算法奠定基础。
更重要的是——体会算法之美！学习建议
知识在于积累，学习需要耐力。学习就像挖金矿，或许一开始毫无头绪，但转个角度、换换工具，时间久了总会找到一个缝隙。成功就是你比别人多走了一段路，或许恰恰是那么一小步。
第一个建议：多角度，对比学习。
学习算法，可以先阅读一本简单的入门书，然后综合几本书横向多角度看，例如学习动态规划，拿几本算法书，把动态规划这章都找出来，比较学习，多角度对比分析更清晰，或许你会恍然大悟。或许有同学说我哪有那么多钱买那么多书，只要想学习，没有什么可以阻挡你！你可以联系你的老师，每学期上课前，我都会告诉学生，如果你想学习却没钱买书，我可以提供帮助。想一想，你真的没有办法吗？
第二个建议：大视野，不求甚解。
经常有学生为了一个公式推导或几行代码抛锚，甚至停滞数日，然后沉浸在无尽的挫败感中，把自己弄得垂头丧气。公式可以不懂，代码可以不会。你不必投入大量精力试图推导书上的每一个公式，也不必探究语法或技术细节。学算法就是学算法本身，首先是算法思想、解题思路，然后是算法实现。算法思想的背后可能有高深的数学模型、复杂的公式推导，你理解了当然更好，不懂也没关系。算法实现可以用任何语言，所以不必纠结是C、C++、Java、Python……更不必考虑严格的语法规则，除非你要上机调试。建议还是先领会算法，写伪代码，在大脑中调试吧！如果你没有良好的编程经验，一开始就上机或许会更加崩溃。遇到不懂的部分，浏览一下或干脆跳过去，读完了还不明白再翻翻别的书，总有一天，你会发现“蓦然回首，那人却在灯火阑珊处”。
第三个建议：多交流，见贤思齐。
与同学、朋友、老师或其他编程爱好者一起学习和讨论问题，是取得进步最有效的办法之一，也是分享知识和快乐的途径。加入论坛、交流群，会了解其他人在做什么、怎么做。遇到问题请教高手，会感受到醍醐灌顶的喜悦。论坛和群也会分享大量的学习资料和视频，还有不定期的培训讲座和读书交流会。记住，你不是一个人在战斗！
第四个建议：勤实战，越挫越勇。
实践是检验真理的唯一标准。古人云：“学以致用”“师夷长技以制夷”。请不要急切期盼实际应用的例子，更不要看不起小实例。“不积跬步，无以至千里”，大规模的成功商业案例不是我们目前要解决的问题。看清楚并走好脚下的路，比仰望天空更实际。多做一些实战练习，更好地体会算法的本质，在错误中不断成长，越挫越勇，相信你终究会有建树。
第五个建议：看电影，洞察未来。
不管是讲人工智能，还是算法分析，我都会建议同学们去看一看科幻电影，如《人工智能》《记忆裂痕》《绝密飞行》《未来战士》《她》等。奇妙的是，这些科幻的东西正在一步步地被实现，靠的是什么？人工智能。计算机的终极是人工智能，人工智能的核心是算法。未来的战争是科技的战争，先进的科技需要人工智能。我们的国家还有很多技术处于落后状态，未来需要你。“一心两本”学习法：一颗好奇心，两个记录本。
怀着一颗好奇心去学习，才能不断地解决问题，获得满足感，体会算法的美。很多科学大家的秘诀就是永远保持一颗好奇心；一个记录本用来记录学习中的重点难点和随时突发的奇想；一个记录本做日记或周记，记录一天或一周来学了什么，有什么经验教训，需要注意什么，计划下一天或下一周做什么。不停地总结反思过去，计划未来，这样每天都有事做，心中会有满满的正能量。
记住没有人能一蹴而就，付出总有回报。本书特色（1）实例丰富，通俗易懂。从有趣的故事引入算法，从简单到复杂，使读者从实例中体会算法设计思想。实例讲解通俗易懂，让读者获得最大程度的启发，锻炼分析问题和解决问题的能力。（2）完美图解，简单有趣。结合大量完美绘图，对算法进行分解剖析，使复杂难懂的问题变得简单有趣，给读者带来巨大的阅读乐趣，使读者在阅读中不知不觉地学到算法知识，体会算法的本质。（3）深入浅出，透析本质。采用伪代码描述算法，既简洁易懂，又能抓住本质，算法思想描述及注释使代码更加通俗易懂。对算法设计初衷和算法复杂性的分析全面细致，既有逐步得出结论的推导过程，又有直观的绘图展示。（4）实战演练，循序渐进。每一个算法讲解清楚后，进行实战演练，使读者在实战中体会算法，增强自信，从而提高读者独立思考和动手实践的能力。丰富的练习题和思考题用于及时检验读者对所学知识掌的握情况，为读者从小问题出发到逐步解决大型复杂性问题奠定了基础。（5）算法解析，优化拓展。每一个实例都进行了详细的算法解析，分析算法的时间复杂度和空间复杂度，并对其优化拓展进一步讨论，提出了改进算法，并进行伪码讲解和实战演练，最后分析优化算法的复杂度进行对比。使读者在学习算法的基础上更上一个阶梯，对算法优化有更清晰的认识。（6）网络资源，技术支持。网络提供本书所有范例程序的源代码、练习题以及答案解析，这些源代码可以自由修改编译，以符合读者的需要。本书提供源代码执行、调试说明书，对读者存在的问题提供技术支持。建议和反馈
写一本书是一项极其琐碎、繁重的工作，尽管我已经竭力使本书和网络支持接近完美，但仍然可能存在很多漏洞和瑕疵。欢迎读者提供关于本书的反馈意见，有利于我们改进和提高，以帮助更多的读者。如果你对本书有任何评论和建议，或者遇到问题需要帮助，可以加入趣学算法交流QQ群（514626235）进行交流，也可以致信作者邮箱rainchxy@126.com或本书编辑邮箱zhangshuang@ptpress.com.cn，我将不胜感激。致谢
感谢我的家人和朋友在本书编写过程中提供的大力支持！感谢提供宝贵意见的同事们，感谢提供技术支持的同学们！感恩我遇到的众多良师益友！Chapter 1算法之美
1.1 打开算法之门
1.2 妙不可言——算法复杂性
1.3 美不胜收——魔鬼序列
1.4 灵魂之交——马克思手稿中的数学题
1.5 算法学习瓶颈
1.6 你怕什么
如果说数学是皇冠上的一颗明珠，那么算法就是这颗明珠上的光芒，算法让这颗明珠更加熠熠生辉，为科技进步和社会发展照亮了前进的路。数学是美学，算法是艺术。走进算法的人，才能体会它的魅力。
多年来，我有一个梦想，希望每一位提到算法的人，不再立即紧皱眉头，脑海闪现枯燥的公式、冗长的代码；希望每一位阅读和使用算法的人，体会到算法之美，像躺在法国普罗旺斯小镇的长椅上，呷一口红酒，闭上眼睛，体会舌尖上的美味，感受鼻腔中满溢的薰衣草的芳香……1.1 打开算法之门
瑞士著名的科学家N.Wirth教授曾提出：数据结构+算法=程序。
数据结构是程序的骨架，算法是程序的灵魂。
在我们的生活中，算法无处不在。我们每天早上起来，刷牙、洗脸、吃早餐，都在算着时间，以免上班或上课迟到；去超市购物，在资金有限的情况下，考虑先买什么、后买什么，算算是否超额；在家中做饭，用什么食材、调料，做法、步骤，还要品尝一下咸淡，看看是否做熟。所以，不要说你不懂算法，其实你每天都在用！
但是对计算机专业算法，很多人都有困惑：“I can understand, but I can’tuse！”，我能看懂，但不会用！就像参观莫高窟的壁画，看到它、感受它，却无法走进。我们正需要一把打开算法之门的钥匙，就如陶渊明《桃花源记》中的“初极狭，才通人。复行数十步，豁然开朗。”1.2 妙不可言——算法复杂性
我们首先看一道某跨国公司的招聘试题。
写一个算法，求下面序列之和：n−1，1，−1，1，…，(−1)
当你看到这个题目时，你会怎么想？for语句？while循环？
先看算法1-1：//算法1-1 sum=0;for(i=1; i<=n; i++){ sum=sum+(-1)^n;}
这段代码可以实现求和运算，但是为什么不这样算?！
再看算法1-2：//算法1-2if(n%2==0) //判断n是不是偶数，%表示求余数 sum =0;else sum=-1;
有的人看到这个代码后恍然大悟，原来可以这样啊？这不就是数学家高斯使用的算法吗？
一共50对数，每对之和均为101，那么总和为：（1+100）×50=5050
1787年，10岁的高斯用了很短的时间算出了结果，而其他孩子却要算很长时间。
可以看出，算法1-1需要运行n+1次，如果n=100 00，就要运行100 01次，而算法1-2仅仅需要运行1次！是不是有很大差别？高斯的方法我也知道，但遇到类似的题还是……我用的笨办法也是算法吗？
答：是算法。
算法是指对特定问题求解步骤的一种描述。
算法只是对问题求解方法的一种描述，它不依赖于任何一种语言，既可以用自然语言、程序设计语言（C、C++、Java、Python等）描述，也可以用流程图、框图来表示。一般为了更清楚地说明算法的本质，我们去除了计算机语言的语法规则和细节，采用“伪代码”来描述算法。“伪代码”介于自然语言和程序设计语言之间，它更符合人们的表达方式，容易理解，但不是严格的程序设计语言，如果要上机调试，需要转换成标准的计算机程序设计语言才能运行。
算法具有以下特性。（1）有穷性：算法是由若干条指令组成的有穷序列，总是在执行若干次后结束，不可能永不停止。（2）确定性：每条语句有确定的含义，无歧义。（3）可行性：算法在当前环境条件下可以通过有限次运算实现。（4）输入输出：有零个或多个输入，一个或多个输出。算法1-2的确算得挺快的，但如何知道我写的算法好不好呢？“好”算法的标准如下。（1）正确性：正确性是指算法能够满足具体问题的需求，程序运行正常，无语法错误，能够通过典型的软件测试，达到预期的需求。（2）易读性：算法遵循标识符命名规则，简洁易懂，注释语句恰当适量，方便自己和他人阅读，便于后期调试和修改。（3）健壮性：算法对非法数据及操作有较好的反应和处理。例如，在学生信息管理系统中登记学生年龄时，若将21岁误输入为210岁，系统应该提示出错。（4）高效性：高效性是指算法运行效率高，即算法运行所消耗的时间短。算法时间复杂度就是算法运行需要的时间。现代计算机一秒钟能计算数亿次，因此不能用秒来具体计算算法消耗的时间，由于相同配置的计算机进行一次基本运算的时间是一定的，我们可以用算法基本运算的执行次数来衡量算法的效率。因此，将算法基本运算的执行次数作为时间复杂度的衡量标准。（5）低存储性：低存储性是指算法所需要的存储空间低。对于像手机、平板电脑这样的嵌入式设备，算法如果占用空间过大，则无法运行。算法占用的空间大小称为空间复杂度。
除了（1）～（3）中的基本标准外，我们对好的算法的评判标准就是高效率、低存储。（1）～（3）中的标准都好办，但时间复杂度怎么算呢？
时间复杂度：算法运行需要的时间，一般将算法的执行次数作为时间复杂度的度量标准。
看算法1-3，并分析算法的时间复杂度。//算法1-3 sum=0; //运行1次total=0; //运行1次for(i=1; i<=n; i++) //运行n次{ sum=sum+i; //运行n次 for(j=1; j<=n; j++) //运行n*n次 total=total+i*j; //运行n*n次}
把算法的所有语句的运行次数加起来：1+1+n+n+n×n+n×n，可以用一个函数T(n)表达：2T(n)=2n+2n+25105
当n足够大时，例如n=10时，T(n)=2×10+2×10+2，我们可以看到算法运行时间主要取决于第一项，后面的甚至可以忽略不计。
用极限表示为：，C为不等于0的常数
如果用时间复杂度的渐近上界表示，如图1-1所示。
从图1-1中可以看出，当nn时，T(n)Cf (n)，当n足够大时，0T(n)和f (n)近似相等。因此，我们用О(f (n))来表示时间复杂度渐近上界，通常用这种表示法衡量算法时间复杂度。算法1-3的时间复杂度2渐近上界为О(f (n))＝О(n)，用极限表示为：图1-1 渐近时间复杂度上界
还有渐近下界符号Ω(T(n)Cf (n))，如图1-2所示。图1-2 渐近时间复杂度下界
从图1-2可以看出，当nn时，T(n)Cf (n)，当n足够大时，T(n)0和f (n)近似相等，因此，我们用Ω(f (n))来表示时间复杂度渐近下界。
渐近精确界符号Θ(Cf (n)T(n)Cf (n))，如图1-3所示。12
从图1-3中可以看出，当nn时，Cf (n)T(n)Cf (n)，当n足够012大时，T(n)和f (n)近似相等。这种两边逼近的方式，更加精确近似，因此，用Θ (f (n))来表示时间复杂度渐近精确界。图1-3 渐进时间复杂度精确界
我们通常使用时间复杂度渐近上界О(f (n))来表示时间复杂度。
看算法1-4，并分析算法的时间复杂度。//算法1-4i=1; //运行1次while(i<=n) //可假设运行x次{ i=i*2; //可假设运行x次}
观察算法1-4，无法立即确定while 及i=i*2运行了多少次。这时可x23假设运行了x次，每次运算后i值为2，2，2，…，2，当i=n时结x束，即2＝n时结束，则x=logn，那么算法1-4的运算次数为1+2logn，22时间复杂度渐近上界为О(f (n))＝О(logn)。2
在算法分析中，渐近复杂度是对算法运行次数的粗略估计，大致反映问题规模增长趋势，而不必精确计算算法的运行时间。在计算渐近时间复杂度时，可以只考虑对算法运行时间贡献大的语句，而忽略那些运算次数少的语句，循环语句中处在循环内层的语句往往运行次数最多，即为对运行时间贡献最大的语句。例如在算法1-3中，total=total+i*j是对算法贡献最大的语句，只计算该语句的运行次数即可。
注意：不是每个算法都能直接计算运行次数。
例如算法1-5，在a[n]数组中顺序查找x，返回其下标i，如果没找到，则返回−1。//算法1-5 findx(int x) //在a[n]数组中顺序查找x{ for(i=0; i 我们很难计算算法1-5中的程序到底执行了多少次，因为运行次数依赖于x在数组中的位置，如果第一个元素就是x，则执行1次（最好情况）；如果最后一个元素是x，则执行n次（最坏情况）；如果分布概率均等，则平均执行次数为（n+1）/2。 有些算法，如排序、查找、插入等算法，可以分为最好、最坏和平均情况分别求算法渐近复杂度，但我们考查一个算法通常考查最坏的情况，而不是考查最好的情况，最坏情况对衡量算法的好坏具有实际的意义。我明白了，那空间复杂度应该就是算法占了多大存储空间了？ 空间复杂度：算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。 空间复杂度的本意是指算法在运行过程中占用了多少存储空间。算法占用的存储空间包括：（1）输入/输出数据；（2）算法本身；（3）额外需要的辅助空间。 输入/输出数据占用的空间是必需的，算法本身占用的空间可以通过精简算法来缩减，但这个压缩的量是很小的，可以忽略不计。而在运行时使用的辅助变量所占用的空间，即辅助空间是衡量空间复杂度的关键因素。 看算法1-6，将两个数交换，并分析其空间复杂度。//算法1-6 swap(int x,int y) //x与y交换 { int temp; temp=x; //temp为辅助空间 ① x=y; ② y=temp; ③} 两数的交换过程如图1-4所示。图1-4 两数交换过程 图1-4中的步骤标号与算法1-6中的语句标号一一对应，该算法使用了一个辅助空间temp，空间复杂度为О(1)。 注意：递归算法中，每一次递推需要一个栈空间来保存调用记录，因此，空间复杂度需要计算递归栈的辅助空间。 看算法1-7，计算n的阶乘，并分析其空间复杂度。//算法1-7 fac(int n) //计算n的阶乘{ if(n<0) //小于零的数无阶乘值 { printf("n<0,data error!"); return -1; } else if(n= =0 || n= =1) return 1; else return n*fac(n-1); } 阶乘是典型的递归调用问题，递归包括递推和回归。递推是将原问题不断分解成子问题，直到达到结束条件，返回最近子问题的解；然后逆向逐一回归，最终到达递推开始的原问题，返回原问题的解。 思考：试求5的阶乘，程序将怎样计算呢？ 5的阶乘的递推和回归过程如图1-5和图1-6所示。图1-5 5的阶乘递推过程图1-6 5的阶乘回归过程 图1-5和图1-6的递推、回归过程是我们从逻辑思维上推理，用图的方式形象地表达出来的，但计算机内部是怎样处理的呢？计算机使用一种称为“栈”的数据结构，它类似于一个放一摞盘子的容器，每次从顶端放进去一个，拿出来的时候只能从顶端拿一个，不允许从中间插入或抽取，因此称为“后进先出”（last in first out）。 5的阶乘进栈过程如图1-7所示。图1-7 5的阶乘进栈过程 5的阶乘出栈过程如图1-8所示。图1-8 5的阶乘出栈过程 从图1-7和图1-8的进栈、出栈过程中，我们可以很清晰地看到，首先把子问题一步步地压进栈，直到得到返回值，再一步步地出栈，最终得到递归结果。在运算过程中，使用了n个栈空间作为辅助空间，因此阶乘递归算法的空间复杂度为О(n)。在算法1-7中，时间复杂度也为О(n)，因为n的阶乘仅比n−1的阶乘多了一次乘法运算，fac(n)=n*fac(n−1)。如果用T(n)表示fac(n)的时间复杂度，可表示为： T(n)= T(n−1)+1 = T(n−2)+1+1 …… = T(1)+…+1+1 =n1.3 美不胜收——魔鬼序列趣味故事1-1：一棋盘的麦子 有一个古老的传说，有一位国王的女儿不幸落水，水中有很多鳄鱼，国王情急之下下令：“谁能把公主救上来，就把女儿嫁给他。”很多人纷纷退让，一个勇敢的小伙子挺身而出，冒着生命危险把公主救了上来，国王一看是个穷小子，想要反悔，说：“除了女儿，你要什么都可以。”小伙子说：“好吧，我只要一棋盘的麦子。您在第1个格子里放1粒麦子，在第2个格子里放2粒，在第3个格子里放4粒，在第4个格子里放8粒，以此类推，每一格子里的麦子粒数都是前一格的两倍。把这64个格子都放好了就行，我就要这么多。”国王听后哈哈大笑，觉得小伙子的要求很容易满足，满口答应。结果发现，把全国的麦子都拿来，也填不完这64格……国王无奈，只好把女儿嫁给了这个小伙子。 解析 棋盘上的64个格子究竟要放多少粒麦子？ 把每一个放的麦子数加起来，总和为S，则：12363S=1+2+2+2+…+2 ① 我们把式①等号两边都乘以2，等式仍然成立：12363642S=2+2+2+…+2+2 ② 式 ②减去式①，则：64S=2−1 ＝18 446 744 073 709 551 615 据专家统计，每个麦粒的平均重量约41.9毫克，那么这些麦粒的总重量是： 18 446 744 073 709 551 615×41.9＝772 918 576 688 430 212 668.5（毫克） ≈7729（亿吨） 全世界人口按60亿计算，每人可以分得128吨！ 我们称这样的函数为爆炸增量函数，想一想，如果算法时间复杂n度是О(2) 会怎样？随着n的增长，这个算法会不会“爆掉”？经常见到有些算法调试没问题，运行一段也没问题，但关键的时候宕机（shutdown）。例如，在线考试系统，50个人考试没问题，100人考试也没问题，如果全校1万人考试就可能出现宕机。 注意：宕机就是死机，指电脑不能正常工作了，包括一切原因导致的死机。计算机主机出现意外故障而死机，一些服务器（如数据库）死锁，服务器的某些服务停止运行都可以称为宕机。 常见的算法时间复杂度有以下几类。（1）常数阶。 常数阶算法运行的次数是一个常数，如5、20、100。常数阶算法时间复杂度通常用О(1)表示，例如算法1-6，它的运行次数为4，就是常数阶，用О(1)表示。（2）多项式阶。23 很多算法时间复杂度是多项式，通常用О(n)、О(n)、О(n)等表示。例如算法1-3就是多项式阶。（3）指数阶。 指数阶时间复杂度运行效率极差，程序员往往像躲“恶魔”一样nn避开它。常见的有О(2)、О(n！)、О(n)等。使用这样的算法要慎重，例如趣味故事1-1。（4）对数阶。 对数阶时间复杂度运行效率较高，常见的有О(logn)、О(nlogn)等，例如算法1-4。 常见时间复杂度函数曲线如图1-9所示。图1-9 常见函数增量曲线 从图1-9中可以看出，指数阶增量随着x的增加而急剧增加，而对数阶增加缓慢。它们之间的关系为：23nnО(1)< О(logn)< О(n)< О(nlogn) < О(n)< О(n)< О(2) < О(n!)< О(n) 我们在设计算法时要注意算法复杂度增量的问题，尽量避免爆炸级增量。趣味故事1-2：神奇兔子数列 假设第1个月有1对刚诞生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生兔子开始，12个月后会有多少对兔子呢？ 兔子数列即斐波那契数列，它的发明者是意大利数学家列昂纳多•斐波那契（Leonardo Fibonacci，1170—1250）。1202年，他撰写了《算盘全书》（《Liber Abaci》）一书，该书是一部较全面的初等数学著作。书中系统地介绍了印度—阿拉伯数码及其演算法则，介绍了中国的“盈不足术”；引入了负数，并研究了一些简单的一次同余式组。（1）问题分析 我们不妨拿新出生的1对小兔子分析： 第1个月，小兔子①没有繁殖能力，所以还是1对。 第2个月，小兔子①进入成熟期，仍然是1对。 第3个月，兔子①生了1对小兔子②，于是这个月共有2（1+1=2）对兔子。 第4个月，兔子①又生了1对小兔子③。因此共有3（1+2=3）对兔子。 第5个月，兔子①又生了1对小兔子④，而在第3个月出生的兔子②也生下了1对小兔子⑤。共有5（2+3=5）对兔子。 第6个月，兔子①②③各生下了1对小兔子。新生3对兔子加上原有的5对兔子这个月共有8（3+5=8）对兔子。 …… 为了表达得更清楚，我们用图示来分别表示新生兔子、成熟期兔子和生育期兔子，兔子的繁殖过程如图1-10所示。图1-10 兔子繁殖过程 这个数列有十分明显的特点，从第3个月开始，当月的兔子数=上月兔子数+当月新生兔子数，而当月新生的兔子正好是上上月的兔子数。因此，前面相邻两项之和，构成了后一项，即：当月的兔子数=上月兔子数+上上月的兔子数 斐波那契数列如下：1，1，2，3，5，8，13，21，34，… 递归式表达式： 那么我们该怎么设计算法呢？哈哈，这太简单了，用递归算法很快就算出来了！（2）算法设计 首先按照递归表达式设计一个递归算法，见算法1-8。//算法1-8 Fib1(int n) { if(n<1) return -1;if(n==1||n==2) return 1; return Fib1(n-1)+Fib1(n-2);} 写得不错，那么算法设计完成后，我们有3个问题：● 算法是否正确？● 算法复杂度如何？● 能否改进算法？（3）算法验证分析 第一个问题毋庸置疑，因为算法1-8是完全按照递推公式写出来的，所以正确性没有问题。那么算法复杂度呢？假设T(n)表示计算Fib1(n)所需要的基本操作次数，那么：n=1时，T(n)=1；n=2时，T(n)=1；n=3时，T(n)=3；//调用Fib1(2)、Fib1(1)和执行一次加法运算Fib1(2)+Fib1(1) 因此，n>2时要分别调用Fib1(n−1)、Fib1(n−2)和执行一次加法运算，即：n>2时，T(n)= T(n-1)+ T(n-2)+1； 递归表达式和时间复杂度T(n)之间的关系如下： 由此可得：。 那么怎么计算F(n)呢？ 有兴趣的读者可以看本书附录A中通项公式的求解方法，也可以看下文中的简略解释。 斐波那契数列通项为： 当n趋近于无穷时， 由于，这是一个指数阶的算法！ 如果我们今年计算出了F(100)，那么明年才能算出F(101)，多算一个斐波那契数需要一年的时间，爆炸增量函数是算法设计的噩梦！算法1-8的时间复杂度属于爆炸增量函数，这在算法设计时是应当避开的，那么我们能不能改进它呢？（4）算法改进 既然斐波那契数列中的每一项是前两项之和，如果记录前两项的值，只需要一次加法运算就可以得到当前项，时间复杂度会不会更低一些？我们用数组试试看，见算法1-9。//算法1-9 Fib2(int n) { if(n<1) return -1; int *a=new int[n];//定义一个数组 a[1]=1； a[2]=1; for(int i=3;i<=n;i++) a[i]=a[i-1]+a[i-2]; return a[n];} 很明显，算法1-9的时间复杂度为О(n)。算法仍然是按照F(n)的定义，所以正确性没有问题，而时间复杂度却从算法1-8的指数阶降到了多项式阶，这是算法效率的一个巨大突破！ 算法1-9使用了一个辅助数组记录中间结果，空间复杂度也为О(n)，其实我们只需要得到第n个斐波那契数，中间结果只是为了下一次使用，根本不需要记录。因此，我们可以采用迭代法进行算法设计，见算法1-10。//算法1-10 Fib3(int n) { int i,s1,s2; if(n<1) return -1;
试读结束[说明：试读内容隐藏了图片]