详情
本书介绍了算法和数据结构的基础知识，包括基础算法思想、简单数据结构、复杂数据结构、排序和查找算法等内容；下篇用4章的篇幅介绍了用数据结构解决实际问题的相关程序，包括解决数学问题、数据结构问题、算法经典问题等内容以及信息学奥赛部分试题的程序，最后一章介绍了与算法和数据结构相关的常见面试题。
书名：算法学习与应用从入门到精通
ISBN：978-7-115-41885-2
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
• 著 张玲玲
责任编辑 张 涛
• 人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
• 读者服务热线：(010)81055410
反盗版热线：(010)81055315
算法是程序的灵魂，只有掌握了算法，才能轻松地驾驭程序开发。算法能够告诉开发者在面对一个项目功能时用什么思路去实现，有了这个思路后，编程工作只需遵循这个思路去实现即可。本书循序渐进、由浅入深地详细讲解了算法实现的核心技术，并通过具体实例的实现过程演练了各个知识点的具体使用流程。
全书共20章，其中，第1章讲解了算法为什么是程序的灵魂；第2～8章分别讲解了常用的算法，如线性表、队列和栈，树，图，查找算法，内部排序算法，外部排序算法等知识，这些内容都是算法技术核心的语法知识；第9～15章分别讲解了经典的数据结构问题、解决数学问题、解决趣味问题、解决图像问题、算法的经典问题、解决奥赛问题、常见算法应用实践等高级编程技术，这些内容是算法技术的重点和难点；第16～20章分别通过5个综合实例的实现过程，介绍了算法在综合开发项目中的使用流程和发挥的作用。全书内容以“技术解惑”和“实践应用”贯穿全书，引领读者全面掌握算法的核心技术。
本书不但适合算法研究和学习的初学者，也适合有一定算法基础的读者，还可以作为大中专院校相关专业师生的学习用书和培训学校的教材。
从你开始学习编程的那一刻起，就注定了以后所要走的路：从编程学习者开始，依次经历实习生、程序员、软件工程师、架构师、CTO等职位的磨砺；当你站在职位顶峰的位置蓦然回首，会发现自己的成功并不是偶然，在程序员的成长之路上会有不断修改代码、寻找并解决Bug、不停测试程序和修改项目的经历；不可否认的是，只要你在自己的开发生涯中稳扎稳打，并且善于总结和学习，最终将会得到可喜的收获。
对于一名想从事程序开发的初学者来说，究竟如何学习才能提高自己的开发技术呢？其一的答案就是买一本合适的程序开发书籍进行学习。但是，市面上许多面向初学者的编程书籍中，大多数篇幅都是基础知识讲解，多偏向于理论；读者读了以后面对实战项目时还是无从下手，如何实现从理论平滑过渡到项目实战，是初学者迫切需要的书籍，为此，作者特意编写了本书。
本书用一本书的容量讲解了入门类、范例类和项目实战类3类图书的内容，并且对实战知识不是点到为止地讲解，而是深入地探讨。用纸质书＋光盘资料（视频和源程序）＋网络答疑的方式，实现了入门＋范例演练＋项目实战的完美呈现，帮助读者从入门平滑过渡到适应项目实战的角色。
1．以“入门到精通”的写作方法构建内容，让读者入门容易
为了使读者能够完全看懂本书的内容，本书遵循“入门到精通”基础类图书的写法，循序渐进地讲解了算法的基本知识。
2．破解语言难点，“技术解惑”贯穿全书，绕过学习中的陷阱
本书不是编程语言知识点的罗列式讲解，为了帮助读者学懂基本知识点，每章都会有“技术解惑”板块，让读者知其然又知其所以然，也就是看得明白，学得通。
3．全书共计320个实例，具有与“实例大全”类图书同数量级的范例
书中一共有320个实例，其中包含了5个综合实例。通过这些实例的练习，读者有更多的实践演练机会，实现了对知识点的横向切入和纵向比较，并且可以从不同的角度展现一个知识点的用法，真正达到举一反三的效果。
4．视频讲解，降低学习难度
书中每一章节均提供声、图并茂的语音教学视频，这些视频能够引导初学者快速入门，增强学习的信心，从而快速理解所学知识。
5．贴心提示和注意事项提醒
本书根据需要在各章安排了很多“注意”“说明”和“技巧”等小板块，让读者可以在学习过程中更轻松地理解相关知识点及概念，更快地掌握个别技术的应用技巧。
6．源程序＋视频＋PPT丰富的学习资料，让学习更轻松
因为本书的内容非常多，不可能用一本书的篇幅囊括“基础+范例+项目案例”的内容，所以需要配套DVD光盘来辅助实现。在本书的光盘中不但有全书的源代码，而且还精心制作了实例讲解视频。本书配套的PPT资料可以在网站下载（www.toppr.net）。
7．QQ群+网站论坛实现教学互动，形成互帮互学的朋友圈
本书作者为了方便给读者答疑，特提供了网站论坛、QQ群等技术支持，并且随时在线与读者互动。让大家在互学互帮中形成一个良好的学习编程的氛围。
本书的学习论坛是：www.toppr.net。
本书的QQ群是：347459801。
本书循序渐进、由浅入深地详细讲解了算法应用技术，并通过具体实例的实现过程演练了各个知识点的具体应用。全书共20章，讲解了常用的算法思想，线性表、队列和栈，树，图，查找算法，内部排序算法，外部排序算法等知识，这些内容都是算法技术最核心的语法知识；另外，还讲解了经典的数据结构问题，解决数学问题，解决趣味问题，解决图像问题，算法的经典问题，解决奥赛问题，常见算法应用实践高级编程技术的基本知识等算法技术的重点和难点。最后通过5个综合实例的实现过程，介绍了算法在综合开发项目中的使用流程和发挥的作用。全书以“技术讲解”→“范例演练”→“技术解惑”贯穿全书，引领读者全面掌握算法的应用。
初学编程的自学者 算法爱好者
大中专院校的教师和学生 相关培训机构的教师和学员
毕业设计的学生 初、中级程序开发人员
软件测试人员 参加实习的初级程序员
在职程序员
本书在编写过程中，十分感谢我的家人给予的巨大支持。本人水平毕竟有限，书中存在纰漏之处在所难免，诚请读者提出意见或建议，以便修订并使之更臻完善。编辑联系邮箱：zhangtao@ptpress.com.cn。
最后感谢读者购买本书，希望本书能成为读者编程路上的领航者，祝读者阅读快乐！
作者
实例2-1：使用枚举法解决“百钱买百鸡”问题
实例2-2：使用枚举法解决“填写运算符”问题
实例2-3：使用顺推法解决“斐波那契数列”问题
实例2-4：使用逆推法解决“银行存款”问题
实例2-5：使用递归算法解决“汉诺塔”问题
实例2-6：使用递归算法解决“阶乘”问题
实例2-7：解决“大数相乘”问题
实例2-8：使用分治算法解决“欧洲冠军杯比赛日程安排”问题
实例2-9： 使用贪心算法解决“装箱”问题
实例2-10：使用贪心算法解决“找零方案”问题
实例2-11：使用试探算法解决“八皇后”问题
实例2-12：解决“体彩29选7彩票组合”问题
实例2-13：解决“求平方根”问题
实例2-14：使用模拟算法解决“猜数字游戏”问题
实例2-15：使用模拟算法解决“掷骰子游戏”问题
实例3-1：演示顺序表操作函数的用法
实例3-2：讲解操作顺序表的方法
实例3-3：演示前面定义的链表操作函数的用法
实例3-4：进一步讲解操作链表的方法
实例3-5：演示一个完整的顺序队列的操作过程
实例3-6：演示一个完整的循环队列的操作过程
实例3-7：实现一个排号程序
实例3-8：编写对栈的各种操作函数
实例3-9：测试栈操作函数
实例4-1：测试二叉树操作函数
实例4-2：C++的二叉树操作
实例4-3：编码实现各种线索二叉树的操作
实例4-4：在控制台中测试线索二叉树的操作
实例4-5：编码实现各种霍夫曼树的操作
实例4-6：在控制台中测试霍夫曼树的操作
实例5-1：创建一个邻接矩阵
实例5-2：在控制台中测试霍夫曼树的操作
实例5-3：实现图的遍历操作
实例5-4：实现图的遍历操作
实例5-5：创建一个最小生成树
实例5-6：调用最小生成树函数实现操作
实例5-7：创建最短路径算法函数
实例5-8：调用最短路径算法实现测试
实例6-1：实现顺序查找算法
实例6-2：改进的顺序查找算法
实例6-3：使用折半查找算法查找数据
实例6-4：使用折半查找算法查找10个已 排好序的数
实例6-5：创建的二叉树，并将数据插入到节点中
实例6-6：在创建的二叉树中删除一个节点
实例6-7：使用索引查找法查找出指定的关键字
实例6-8：实现索引查找并插入一个新关键字
实例7-1：编写直接插入排序算法
实例7-2：使用插入排序算法对数据进行排序处理
实例7-3：使用希尔排序算法对数据进行排序处理
实例7-4：使用希尔排序处理数组
实例7-5：用冒泡排序算法实现对数据的排序处理
实例7-6：演示快速排序算法的用法
实例7-7：用直接选择排序算法实现对数据的排序处理
实例7-8：用堆排序算法实现对数据的排序处理
实例7-9：用归并算法实现对数据的排序处理
实例7-10：使用归并排序算法求逆序对
实例9-1：解决约瑟夫环问题
实例9-2：使用数组方法实现大整数运算
实例9-3：使用链表方法实现大整数运算
实例9-4：通过编程的方式，实现计算机进制的转换处理
实例9-5：用编程方式将中序表达式转换为后序表达式
实例10-1：计算两个正整数的最大公约数和最小公倍数
实例10-2：哥德巴赫猜想的证明
实例10-3：编写程序，求出1～10000的完全数
实例10-4： 编写程序求出指定范围内的亲密数
实例10-5：编写可以计算自守数的程序
实例10-6：实现用高斯消元法解方程组
实例10-7：二分法解非线性方程
实例10-8：用牛顿迭代法解非线性方程
实例10-9：实现矩阵运算
实例10-10：实现n×n整数方阵的转置（n小于10）
实例10-11：编程实现一元多项式的加法运算
实例10-12：编程实现一元多项式的减法运算
实例11-1：歌星大奖赛
实例11-2：编程解决“借书方案”的问题
实例11-3：编程解决“三天打鱼两天晒网”的问题
实例11-4：编程解决“捕鱼和分鱼”的问题
实例11-5：编程解决“出售金鱼”的问题
实例11-6：编程解决“平分七筐鱼”的问题
实例11-7：编程解决“绳子长度和井深”的问题
实例11-8：编程实现“鸡兔同笼”的问题
实例11-9：用递归法解决“汉诺塔”问题
实例11-10：用非递归法解决“汉诺塔”问题
实例11-11：使用循环查找法解决“马踏棋盘”问题
实例11-12：使用递归法解决“马踏棋盘”问题
实例11-13：使用栈方法解决“马踏棋盘”问题
实例11-14：使用编程方法解决“三色球”问题
实例11-15：使用编程方法解决“新郎和新娘”问题
实例11-16：使用编程方法解决“计算年龄”问题
实例12-1：使用递归法解决“八皇后”问题
实例12-2：使用循环法解决“八皇后”问题
实例12-3：使用编程方法解决“生命游戏”问题
实例12-4：使用编程方法解决“黑白棋”问题
实例12-5：使用编程方法解决“骑士迷宫”问题
实例12-6：找出迷宫问题中的所有路径
实例13-1：编程解决“存钱利息最大化”问题
实例13-2：使用动态规划法解决“背包”问题
实例13-3：使用递归法解决“背包”问题
实例13-4：编程解决“农夫过河”问题
实例13-5：编程解决“三色旗”问题
实例13-6：编程解决“取石子”游戏
实例13-7：编程解决“停车场管理”问题
实例13-8：编程解决“约瑟夫生者死者游戏”问题
实例14-1：编程解决“孪生素数”问题
实例14-2：编程解决“百钱买百鸡”
实例14-3：编程解决马克思手稿中的数学题
实例14-4：编程解决“正整数分解质因数”问题
实例14-5：编程解决“水仙花”问题
实例14-6：求1000以内的所有素数
实例14-7：求1000以内的回文素数
实例15-1：编程实现Ping命令
实例15-2：编程实现24点游戏
实例15-3：C语言编程实现洗牌
实例15-4：C语言编程实现21点游戏
实例15-5：C语言编程实现2048游戏
实例15-6：C语言编程实现引用计数算法
实例15-7：C语言编程实现猫捉老鼠游戏
综合实例01：俄罗斯方块游戏
综合实例02：学生成绩管理系统
综合实例03：绘图板系统
综合实例04：UDP传输系统
综合实例05：推箱子游戏
算法是程序的灵魂，只有掌握了算法，才能轻松地驾驭程序开发。软件开发工作不是按部就班的，而是选择一种最合理的算法去实现项目功能。算法能够引导开发者在面对一个项目功能时用什么思路去实现，有了这个思路后，编程工作只需遵循这个思路去实现即可。在本章将详细讲解计算机算法的基础知识，为读者步入后面的学习打下基础。
知识点讲解：光盘:视频讲解\第1章\算法的基础.avi
自然界中的很多事物并不是独立存在的，而是和许多其他事物有着千丝万缕的联系。就拿算法和编程来说，两者之间就有着必然的联系。在编程界有一个不成文的原则，要想学好编程就必须学好算法。要想获悉这一说法的原因，先看下面对两者的定义。
（1）算法：是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对符合一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。
（2）编程：是让计算机为解决某个问题而使用某种程序设计语言编写程序代码，并最终得到结果的过程。为了使计算机能够理解人的意图，人类就必须将需要解决的问题的思路、方法和手段通过计算机能够理解的形式“告诉”计算机，使计算机能够根据人的指令一步一步去工作，完成某种特定的任务。编程的目的是实现人和计算机之间的交流，整个交流过程就是编程。
在上述对编程的定义中，核心内容是思路、方法和手段等，这都需要用算法来实现。由此可见，编程的核心是算法，只要算法确定了，后面的编程工作只是实现算法的一个形式而已。
在1950年，Algorithm（算法）一词经常同欧几里德算法联系在一起。这个算法就是在欧几里德的《几何原本》中所阐述的求两个数的最大公约数的过程，即辗转相除法。从此以后，Algorithm这一叫法一直沿用至今。
随着时间的推移，算法这门科学得到了长足的发展，算法应该具有如下5个重要的特征。
① 有穷性：保证执行有限步骤之后结束。
② 确切性：每一步骤都有确切的定义。
③ 输入：每个算法有零个或多个输入，以刻画运算对象的初始情况，所谓零个输入是指算法本身舍弃了初始条件。
④ 输出：每个算法有一个或多个输出，显示对输入数据加工后的结果，没有输出的算法是毫无意义的。
⑤ 可行性：原则上算法能够精确地运行，进行有限次运算后即可完成一种运算。
为了理解什么是算法，先看一道有趣的智力题。
“烧水泡茶”有如下5道工序：①烧开水、②洗茶壶、③洗茶杯、④拿茶叶、⑤泡茶。
烧开水、洗茶壶、洗茶杯、拿茶叶是泡茶的前提。其中，烧开水需要15分钟，洗茶壶需要2分钟，洗茶杯需要1分钟，拿茶叶需要1分钟，泡茶需要1分钟。
下面是两种“烧水泡茶”的方法。
第一步：烧水。
第二步：水烧开后，洗刷茶具，拿茶叶。
第三步：沏茶。
第一步：烧水。
第二步：烧水过程中，洗刷茶具，拿茶叶。
第三步：水烧开后沏茶。
问题：比较这两个方法有何不同，并分析哪个方法更优。
上述两个方法都能最终实现“烧水泡茶”的功能，每种方法的3个步骤就是一种“算法”。算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。
知识点讲解：光盘:视频讲解\第1章\计算机中的算法.avi
众所周知，做任何事情都需要一定的步骤。计算机虽然功能强大，能够帮助人们解决很多问题，但是计算机在解决问题时，也需要遵循一定的步骤。在编写程序实现某个项目功能时，也需要遵循一定的算法。在本节的内容中，将一起探寻算法在计算机中的地位，探索算法在计算机中的基本应用知识。
计算机中的算法可分为如下两大类。
① 数值运算算法：求解数值。
② 非数值运算算法：事务管理领域。
假设有一个下面的运算：1×2×3×4×5，为了计算上述运算结果，最普通的做法是按照如下步骤进行计算。
第1步：先计算1乘以2，得到结果2。
第2步：将步骤1得到的乘积2乘以3，计算得到结果6。
第3步：将6再乘以4，计算得24。
第4步：将24再乘以5，计算得120。
最终计算结果是120，上述第1步到第4步的计算过程就是一个算法。如果想用编程的方式来解决上述运算，通常会使用如下算法来实现。
第1步：假设定义t=1。
第2步：使i=2。
第3步：使t×i，乘积仍然放在变量t中，可表示为t×i→t。
第4步：使i的值+1，即i+1→i。
第5步：如果i
5，返回重新执行步骤3以及其后的步骤4和步骤5；否则，算法结束。
由此可见，上述算法方式就是数学中的“n!”公式。既然有了公式，在具体编程的时候，只需使用这个公式就可以解决上述运算的问题。
再看下面的一个数学应用问题。
假设有80个学生，要求打印输出成绩在60分以上的学生。
在此用n来表示学生学号，ni表示第i个学生学号；cheng表示学生成绩，chengi表示第i个学生成绩。根据题目要求，可以写出如下算法。
第1步：1→i。
第2步：如果chengi
60，则打印输出ni和chengi，否则不打印输出。
第3步：i+1→i。
第4步：如果i80，返回步骤2，否则，结束。
由此可见，算法在计算机中的地位十分重要。所以在面对一个项目应用时，一定不要立即编写程序，而是要仔细思考解决这个问题的算法是什么。想出算法之后，然后以这个算法为指导思想来编程。
相信广大读者经过了解和学习1.2.1节的内容，已基本了解了算法在计算机编程中的重要作用，在程序开发中，算法已经成为衡量一名程序员水平高低的参照物。水平高的程序员都会看重数据结构和算法的作用，水平越高，就越能理解算法的重要性。算法不仅仅是运算工具，它更是程序的灵魂。在现实项目开发过程中，很多实际问题需要精心设计的算法才能有效解决。
算法是计算机处理信息的基础，因为计算机程序本质上是一个算法，告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。通常，当算法在处理信息时，数据会从输入设备读取，写入输出设备，也可能保存起来供以后使用。
著名计算机科学家沃思提出了下面的公式。
数据结构+算法=程序实际上，一个程序应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言来表示。因此，可以用下面的公式表示。
程序=算法+数据结构+程序设计方法+语言和环境上述公式中的4个方面是一种程序设计语言所应具备的知识。在这4个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。其中，算法是用来解决“做什么”和“怎么做”的问题。实际上程序中的操作语句就是算法的体现，所以说，不了解算法就谈不上程序设计。数据是操作对象，对操作的描述即是操作步骤，操作的目的是对数据进行加工处理以得到期望的结果。举个通俗点的例子，厨师做菜肴，需要有菜谱。菜谱上一般应包括：①配料（数据）、②操作步骤（算法）。这样，面对同样的原料可以加工出不同风味的菜肴。
知识点讲解：光盘:视频讲解\第1章\在计算机中表示算法的方法.avi
在1.2.1节中演示的算法都是通过语言描述来体现的。其实除了语言描述之外，还可以通过其他方法来描述算法。在接下来的内容中，将简单介绍几种表示算法的方法。
流程图的描述格式如图1-1所示。
图1-1 流程图标识说明
再次回到1.2.1节中的问题。
假设有80个学生，要求打印输出成绩在60分以上的学生。
针对上述问题，可以使用图1-2所示的算法流程图来表示。
图1-2 算法流程图
在日常流程设计应用中，通常使用如下3种流程图结构。
① 顺序结构。顺序结构如图1-3所示，其中A和B两个框是顺序执行的，即在执行完A以后再执行B的操作。顺序结构是一种基本结构。
图1-3 顺序结构
② 选择结构。选择结构也称为分支结构，如图1-4所示。此结构中必含一个判断框，根据给定的条件是否成立来选择是执行A框还是B框。无论条件是否成立，只能执行A框或B框之一，也就是说A、B两框只有一个，也必须有一个被执行。若两框中有一框为空，程序仍然按两个分支的方向运行。
图1-4 选择结构
③ 循环结构。循环结构分为两种，一种是当型循环，一种是直到型循环。当型循环是先判断条件P是否成立，成立才执行A操作，如图1-5（a）所示。而直到型循环是先执行A操作再判断条件P是否成立，成立再执行A操作，如图1-5（b）所示。
图1-5 循环结构
上述3种基本结构有如下4个特点，这4个特点对于理解算法很有帮助。
① 只有一个入口。
② 只有一个出口。
③ 结构内的每一部分都有机会被执行到。
④ 结构内不存在“死循环”。
在1973年，美国学者提出了N-S流程图的概念，通过它可以表示计算机的算法。N-S流程图由一些特定意义的图形、流程线及简要的文字说明构成，能够比较清晰明确地表示程序的运行过程。人们在使用传统流程图的过程中，发现流程线不一定是必需的，所以设计了一种新的流程图，这种新的方式可以把整个程序写在一个大框图内，这个大框图由若干个小的基本框图构成，这种新的流程图简称N-S图。
遵循N-S流程图的特点，N-S流程图的顺序结构图1-6所示，选择结构如图1-7所示，循环结构如图1-8所示。
图1-6 顺序结构
图1-7 选择结构
图1-8 循环结构
因为算法可以解决计算机中的编程问题，是计算机程序的灵魂，所以，可以使用计算机语言来表示算法。当用计算机语言表示算法时，必须严格遵循所用语言的语法规则。再次回到1.2.1节中的问题：1×2×3×4×5，如果用C语言编程来解决这问题，可以通过如下代码实现。
main(){
int i,t;//定义两个变量
t=1;
i=2;//t初始值为1，i初始值为2
while(i<=5){
t=t*i;
i=i+1;
}
printf("%d",t);
}上述代码是根据1.2.1节中的语言描述算法编写的，因为是用C语言编写的，所以，需要严格遵循C语言的语法。例如在上述代码中，主函数main()、变量和printf()输出信息都遵循了C语言的语法规则。
在一些培训班的广告中到处充斥着“一个月打造高级程序员”的口号，书店里也随处可见书名打着“入门捷径”旗号的书。有过学习经验和工作经验的人们往往深有体会，这些宣传不能全信，学习编程之路需要付出辛苦的汗水，需要付出相当多的时间和精力。结合笔者的学习经验，现总结出如下3条经验和大家一起分享。
（1）学得要深入，基础要扎实
基础的作用不必多说，基础的重要性在大学课堂上老师曾经讲过了很多次，在此重点说明“深入”。职场不是学校，企业要求你能高效地完成项目功能，但是现实中的项目种类繁多，需要从根本上掌握算法技术的精髓，入门水平不会被开发公司所接受，他们需要的是高手。
（2）恒心、演练、举一反三
学习编程的过程是枯燥的，要将学习算法作为自己的乐趣，只有做到持之以恒才能掌握到编程的精髓。另外，编程最注重实践，最害怕闭门造车。每一个语法，每一个知识点，都要反复用实例来演练，这样才能加深对知识的理解。并且要做到举一反三，只有这样才能对知识有深入的理解。
（3）语言之争的时代更要学会坚持
当今新技术、新思想、新名词层出不穷，令人眼花缭乱。希望大家不要盲目追求各种新的技术，建议大家做一名立场坚定的程序员，人们都说C语言已经老掉牙了，但是现实是，C语言永远是我们学习高级语言的基础，永远是内核和嵌入式开发的首选语言。所以只要认定自己的选择，就要坚持下去。
算法思想有很多，业界公认的常用算法思想有8种，分别是枚举、递推、递归、分治、贪心、试探法、动态迭代和模拟。当然8种只是一个大概的划分，是一个“仁者见仁、智者见智”的问题。在本章将详细讲解这8种算法思想的基本知识，希望读者理解并掌握这8种算法思想的基本用法和核心知识，为学习本书后面的知识打下基础。
知识点讲解：光盘:视频讲解\第2章\枚举算法思想.avi
枚举算法思想的最大特点是，在面对任何问题时它会去尝试每一种解决方法。在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这个结论是可靠的，这种归纳方法叫作枚举法。
枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。在C语言中，枚举算法一般使用while循环实现。使用枚举算法解题的基本思路如下。
① 确定枚举对象、枚举范围和判定条件。
② 逐一列举可能的解，验证每个解是否是问题的解。
枚举算法一般按照如下3个步骤进行。
① 题解的可能范围，不能遗漏任何一个真正解，也要避免有重复。
② 判断是否是真正解的方法。
③ 使可能解的范围降至最小，以便提高解决问题的效率。
枚举算法的主要流程如图2-1所示。
图2-1 枚举算法流程图
为了说明枚举算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解枚举算法思想在编程中的基本应用。
源码路径 光盘\daima\2\xiaoji.c
问题描述：我国古代数学家在《算经》中有一道题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”意为：公鸡每只5元，母鸡每只3元，小鸡3只1元。用100元钱买100只鸡，问公鸡、母鸡、小鸡各多少？
算法分析：根据问题的描述，可以使用枚举法解决这个问题。以3种鸡的个数为枚举对象（分别设为mj、gj和xj），以3种鸡的总数（mj+gj+xj=100）和买鸡用去的钱的总数(xj/3+mj×3+gj×5=100)作为判定条件，穷举各种鸡的个数。
具体实现：根据上述问题描述，用枚举算法解决实例2-1的问题。根据“百钱买百鸡”的枚举算法分析，编写实现文件xiaoji.c，具体实现代码如下所示。
#include <stdio.h>
int main()
{
int x,y,z;//定义3个变量，分别表示公鸡、母鸡和小鸡个数
for(x=0;x<=20;x++)
{
for(y=0;y<=33;y++)
{
z=100-x-y;
if (z%3==0 &&x*5+y*3+z/3==100)//3种鸡一共100只
printf("公鸡：%d,母鸡：%d,小鸡：%d\n",x,y,z);
}
}
getch();
return 0;
}执行后的效果如图2-2所示。
图2-2 “百钱买百鸡”问题执行效果
一个实例不能说明枚举算法思想的基本用法，在下面的实例中将详细解使用枚举法解决“填写运算符”的问题。
源码路径 光盘\daima\2\yunsuan.c
问题描述：在下面的算式中，添加“+”“−”“×”“÷”4个运算符，使这个等式成立。
5 5 5 5 5 = 5
算法分析：上述算式由5个数字构成，一共需要填入4个运算符。根据题目要求，知道每两个数字之间的运算符只能有4种选择，分别是“+”“−”“×”“÷”。在具体编程时，可以通过循环来填入各种运算符，然后再判断算式是否成立。并且保证当填入除号时，其右侧的数不能是0，并且“×”“÷”运算符的优先级高于“+”“−”。
具体实现：根据上述“填写运算符”的枚举算法分析，编写实现文件yunsuan.c，具体实现代码如下所示。
#include <stdio.h>
int main()
{
int j,i[5]; //循环变量，数组i用来表示4个运算符
int sign; //累加运算时的符号
int result; //保存运算式的结果值
int count=0; //计数器，统计符合条件的方案
int num[6]; //保存操作数
float left,right; //保存中间结果
char oper[5]={' ','+','-','*','/'}; //运算符
printf("输入5个数，之间用空格隔开：");
for(j=1;j<=5;j++)
scanf("%d",&num[j]);
printf("输入结果：");
scanf("%d",&result);
for(i[1]=1;i[1]<=4;i[1]++) //循环4种运算符，1表示+，2表示-,3表示*，4表示/
{
if((i[1]<4) || (num[2]!=0)) //运算符若是/,则第二个运算数不能为0
{
for(i[2]=1;i[2]<=4;i[2]++)
{
if((i[2]<4) || (num[3]!=0))
{
for(i[3]=1;i[3]<=4;i[3]++)
{
if((i[3]<4) || num[4]!=0)
{
for(i[4]=1;i[4]<=4;i[4]++)
{
if((i[4]<4) || (num[5]!=0))
{
left=0;
right=num[1];
sign=1;
//使用case语句，将四种运算符填到对应的空格位置，并进行运算
for(j=1;j<=4;j++)
{
switch(oper[i[j]])
{
case '+':
left=left+sign*right;
sign=1;
right=num[j+1];
break;
case '-':
left=left+sign*right;
sign=-1;
right=num[j+1];
break;//通过f=-1实现减法
case '*':
right=right*num[j+1];
break;//实现乘法
case '/':
right=right/num[j+1];//实现除法
break;
}
}
//开始判断，如果运算式的结果和输入的结果相同，则表示找到一种算法，并输出这个解
if(left+sign*right==result)
{
count++;
printf("%3d：",count);
for(j=1;j<=4;j++)
printf("%d%c",num[j],oper[i[j]]);
printf("%d=%d\n",num[5],result);
}
}
}
}
}
}
}
}
}
if(count==0)
printf("没有符合要求的方法！\n");
getch();
return 0;
}在上述代码中，定义了left和right两个变量，left用于保存上一步的运算结果，right用于保存下一步的运算结果。因为“×”和“÷”的优先级高于“+”和“−”，所以计算时先计算“×”和“÷”，再计算“+”和“−”。执行后的效果如图2-3所示。
图2-3 “填写运算符”问题执行效果
知识点讲解：光盘:视频讲解\第2章\递推算法思想.avi
与枚举算法思想相比，递推算法能够通过已知的某个条件，利用特定的关系得出中间推论，然后逐步递推，直到得到结果为止。由此可见，递推算法要比枚举算法聪明，它不会尝试每种可能的方案。
递推算法可以不断利用已有的信息推导出新的东西，在日常应用中有如下两种递推 算法。
① 顺推法：从已知条件出发，逐步推算出要解决问题的方法。例如斐波那契数列就可以通过顺推法不断递推算出新的数据。
② 逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。
为了说明递推算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解递推算法思想在编程过程中的基本应用。
源码路径 光盘\daima\2\shuntui.c
问题描述：斐波那契数列因数学家列昂纳多•斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？
算法分析：以新出生的一对小兔子进行如下分析。
① 第一个月小兔子没有繁殖能力，所以还是一对。
② 2个月后，一对小兔子生下了一对新的小兔子，所以共有两对兔子。
③ 3个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是3对。
……
依次类推可以列出关系表，如表2-1所示。
表2-1 月数与兔子对数关系表
| 月数： | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | … |
| 对数： | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | … |
表中数字1，1，2，3，5，8……构成了一个数列，这个数列有个十分明显的特点：前面相邻两项之和，构成了后一项。这个特点的证明：每月的大兔子数为上月的兔子数，每月的小兔子数为上月的大兔子数，某月兔子的对数等于其前面紧邻两个月的和。
由此可以得出具体算法如下所示：
设置初始值为F0=1，第1个月兔子的总数是F1=1。
第2个月的兔子总数是F2= F0+F1。
第2个月的兔子总数是F3= F1+F2。
第3个月的兔子总数是F4= F2+F3。
………
第n个月的兔子总数是Fn= Fn-2+Fn-1。
具体实现：根据上述问题描述，根据“斐波那契数列”的顺推算法分析，编写实现文件shuntui.c，具体实现代码如下所示。
#include <stdio.h>
#define NUM 13
int main()
{
int i;
long fib[NUM] = {1,1}; //定义一个拥有13个元素的数组，用于保存兔子的初始数据和每月的总数
//顺推每个月的总数
for(i=2;i<NUM;i++)
{
fib[i] = fib[i-1]+fib[i-2];
}
//循环输出每个月的总数
for(i=0;i<NUM;i++)
{
printf("第%d月兔子总数:%d\n", i, fib[i]);
}
getch();
return 0;
}执行后的效果如图2-4所示。
图2-4 “斐波那契数列”问题执行效果
一个实例不能说明递推算法思想的基本用法，接下来开始使用逆推算法解决“银行存款”问题。
源码路径 光盘\daima\2\nitui.c
问题描述：母亲为儿子小Sun 4年的大学生活准备了一笔存款，方式是整存零取，规定小Sun每月月底取下一个月的生活费。现在假设银行的年利息为1.71%，请编写程序，计算母亲最少需要存入多钱？
算法分析：可以采用逆推法分析存钱和取钱的过程，因为按照月为周期取钱，所以需要将4年分为48个月，并分别对每个月进行计算。
如果在第48月后Sun大学毕业时连本带息要取1000元，则要先求出第47个月时银行存款的钱数：
第47月月末存款=1000/(1+0.0171/12)；
第46月月末存款=(第47月月末存款+1000)/(1+0.0171/12)；
第45月月末存款=(第46月月末存款+1000)/(1+0.0171/12)；
第44月月末存款=(第45月月末存款+1000)/(1+0.0171/12)；
……
第2月月末存款=(第3月月末存款+1000)/(1+0.0171/12)；
第1月月末存款=(第2月月末存款+1000)/(1+0.0171/12)。
具体实现：编写实现文件nitui.c，具体实现代码如下所示。
#include <stdio.h>
#define FETCH 1000
#define RATE 0.0171
int main()
{
double corpus[49];
int i;
corpus[48]=(double)FETCH;
for(i=47;i>0;i--)
{
corpus[i]=(corpus[i+1]+FETCH)/(1+RATE/12);
}
for(i=48;i>0;i--)
{
printf("%d月月末本利共计:%.2f\n",i,corpus[i]);
}
getch();
return 0;
}执行后的效果如图2-5所示。
图2-5 “银行存款”问题执行效果
知识点讲解：光盘:视频讲解\第2章\递归算法思想.avi
因为递归算法思想往往用函数的形式来体现，所以递归算法需要预先编写功能函数。这些函数是独立的功能，能够实现解决某个问题的具体功能，当需要时直接调用这个函数即可。在本节的内容中，将详细讲解递归算法思想的基本知识。
在计算机编程应用中，递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。递归算法有如下3个特点。
① 递归过程一般通过函数或子过程来实现。
② 递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。
③ 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。
在使用递归算法时，读者应该注意如下4点。
① 递归是在过程或函数中调用自身的过程。
② 在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。
③ 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。
④ 在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。
为了说明递归算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解递归算法思想在编程中的基本应用。
源码路径 光盘\daima\2\hannuo.c
问题描述：寺院里有3根柱子，第一根有64个盘子，从上往下盘子越来越大。方丈要求小和尚A1把这64个盘子全部移动到第3根柱子上。在移动的时候，始终只能小盘子压着大盘子，而且每次只能移动一个。
方丈发布命令后，小和尚A1就马上开始了工作，下面看他的工作过程。
（1）聪明的小和尚A1在移动时，觉得很难，另外他也非常懒惰，所以找来A2来帮他。他觉得要是A2能把前63个盘子先移动到第二根柱子上，自己再把最后一个盘子直接移动到第三根柱子，再让A2把刚才的前63个盘子从第二根柱子上移动到第三根柱子上，整个任务就完成了。所以他找了另一个小和尚A2，然后下了如下命令：
① 把前63个盘子移动到第二根柱子上；
② 把第64个盘子移动到第三根柱子上后；
③ 把前63个盘子移动到第三根柱子上；
（2）小和尚A2接到任务后也觉得很难，所以他也和A1想的一样：要是有一个人能把前62个盘子先移动到第三根柱子上，再把最后一个盘子直接移动到第二根柱子，再让那个人把刚才的前62个盘子从第三根柱子上移动到第三根柱子上，任务就算完成了。所以他也找了另外一个小和尚A3，然后下了如下命令：
① 把前62个盘子移动到第三根柱子上；
② 自己把第63个盘子移动到第二根柱子上后；
③ 把前62个盘子移动到第二根柱子上；
（3）小和尚A3接了任务，又把移动前61个盘子的任务“依葫芦画瓢”的交给了小和尚A4，这样一直递推下去，直到把任务交给了第64个小和尚A64为止。
（4）此时此刻，任务马上就要完成了，唯一的工作就是A63和A64的工作了。
小和尚A64移动第1个盘子，把它移开，然后小和尚A63移动给他分配的第2个盘子。
小和尚A64再把第1个盘子移动到第2个盘子上。到这里A64的任务完成，A63完成了A62交给他的任务的第一步。
算法分析：从上面小和尚的工作过程可以看出，只有A64的任务完成后，A63的任务才能完成，只有小和尚A2～小和尚A64的任务完成后，小和尚A1剩余的任务才能完成。只有小和尚A1剩余的任务完成，才能完成方丈吩咐给他的任务。由此可见，整个过程是一个典型的递归问题。接下来我们以有3个盘子来分析。
第1个小和尚命令：
① 第2个小和尚先把第一根柱子前2个盘子移动到第二根柱子，借助第三根柱子；
② 第1个小和尚自己把第一根柱子最后的盘子移动到第三根柱子；
③ 第2个小和尚你把前2个盘子从第二根柱子移动到第三根柱子。
非常显然，第②步很容易实现。
其中第一步，第2个小和尚有2个盘子，他就命令：
① 第3个小和尚把第一根柱子第1个盘子移动到第三根柱子（借助第二柱子）；
② 第2个小和尚自己把第一根柱子第2个盘子移动到第二根柱子上；
③ 第3个小和尚把第1个盘子从第三根柱子移动到第二根柱子。
同样，第②步很容易实现，但第3个小和尚只需要移动1个盘子，所以他也不用再下派任务了（注意：这就是停止递归的条件，也叫边界值）。
第③步可以分解为，第2个小和尚还是有2个盘子，于是命令：
① 第3个小和尚把第二根柱子上的第1个盘子移动到第一根柱子；
② 第2个小和尚把第2个盘子从第二根柱子移动到第三根柱子；
③ 第3个小和尚你把第一根柱子上的盘子移动到第三根柱子。
分析组合起来就是：1→3，1→2，3→2，借助第三根柱子移动到第二根柱子；1→3是自私人留给自己的活；2→1，2→3，1→3是借助别人帮忙，第一根柱子移动到第三根柱子一共需要七步来完成。
如果是4个盘子，则第一个小和尚的命令中第①步和第③步各有3个盘子，所以各需要7步，共14步，再加上第1个小和尚的第①步，所以4个盘子总共需要移动7+1+7=15步；同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=63步……由此可以知道，移动n个盘子需要（2n−1）步。
假设用hannuo（n,a,b,c）表示把第一根柱子上的n个盘子借助第2根柱子移动到第3根柱子。由此可以得出如下结论。
第①步的操作是hannuo(n-1,1,3,2)，第③步的操作是hannuo(n-1,2,1,3)。
具体实现：根据上述算法分析，编写实现文件hannuo.c，具体代码如下所示。
move(int n,int x,int y,int z)//移动函数，根据递归算法编写
{
if (n==1)
printf("%c-->%c\n",x,z);
else
{
move(n-1,x,z,y);
printf("%c-->%c\n",x,z);
{
getchar();}
move(n-1,y,x,z);
}
}
main()
{
int h;
printf("输入盘子个数: ");//提示输入盘子个数
scanf("%d",&h);
printf("移动%2d个盘子的步骤如下:\n",h);
move(h,'a','b','c');//调用前面定义的函数开始移动，依次输出一定步骤
system("pause");
}执行后先输入移动盘子的个数，按下【Enter】键后将会显示具体步骤。执行效果如图2-6所示。
图2-6 “汉诺塔”问题执行效果
为了说明递归算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解使用递归算法思想解决阶乘问题的方法。
源码路径 光盘\daima\2\yunsuan.c
问题描述：阶乘（factorial）是基斯顿·卡曼（Christian Kramp）于1808年发明的一种运算符号。自然数由1～n的n个数连乘积叫作n的阶乘，记作n!。
例如所要求的数是4，则阶乘式是1×2×3×4，得到的积是24，即24就是4的阶乘。
例如所要求的数是6，则阶乘式是1×2×3×…×6，得到的积是720，即720就是6的阶乘。
例如所要求的数是n，则阶乘式是1×2×3×…×n，设得到的积是x，x就是n的阶乘。
在下面列出了0～10的阶乘。
0!=1
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
算法分析：假如计算6的阶乘，则计算过程如图2-7所示。
图2-7 计算6的阶乘的过程
具体实现：根据上述算法分析，使用递归法编写文件jiecheng.c，具体代码如下所示。
#include <stdio.h>
int fact(int n);
int main()
{
int i;
printf("输入要计算阶乘的一个整数：");
scanf("%d",&i);
printf("%d的阶乘结果为：%d\n",i,fact(i));
getch();
return 0;
}
int fact(int n)
{
if(n<=1)
return 1;
else
return n*fact(n-1);
}执行后如果输入“6”并按下【Enter】键，则会输出6的阶乘是720，执行效果如图2-8所示。
图2-8 计算6的阶乘的执行效果
知识点讲解：光盘:视频讲解\第2章\分治算法思想.avi
在本节将要讲解的分治算法也采取了各个击破的方法，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。只要求出子问题的解，就可得到原问题的解。
在编程过程中，经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题。在求解这类问题时，可以采用各个击破的方法。具体做法是：先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治算法的基本思想。
使用分治算法解题的一般步骤如下。
① 分解，将要解决的问题划分成若干个规模较小的同类问题。
② 求解，当子问题划分得足够小时，用较简单的方法解决。
③ 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。
为了说明分治算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解分治算法思想在编程中的基本应用。
源码路径 光盘\daima\2\fenzhi.c
问题描述：所谓大数相乘，是指计算两个大数的积。
算法分析：假如计算123×456的结果，则分治算法的基本过程如下所示。
第一次拆分为：12和45，具体说明如下所示。
设char *a = "123"，*b = "456"，对a实现t = strlen(a)，t/2得12(0，1位置)余3(2位置)为3和6。
同理，对另一部分b也按照上述方法拆分，即拆分为456。
使用递归求解：12×45，求得12×45的结果左移两位补0右边，因为实际上是120×450；12×6（同上左移一位其实是120×6）；3×45（同上左移一位其实是3×450）；3×6（解的结果不移动）。
第二次拆分：12和45，具体说明如下所示。
1和4：交叉相乘并将结果相加，1×4左移两位为400，1×5左移一位为50，2×4左移一位为80，2×5不移为10。
2和5：相加得400+50+80+10=540。
另外几个不需要拆分得72、135、18，所以：54000+720+1350+18=56088。
由此可见，整个解法的难点是对分治的理解，以及结果的调整和对结果的合并。
具体实现：根据上述分治算法思想，编写实例文件fenzhi.c，具体实现代码如下所示。
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
char *result = '\0';
int pr = 1;
void getFill(char *a,char *b,int ia,int ja,int ib,int jb,int tbool,int move){
int r,m,n,s,j,t;
char *stack;
m = a[ia] - 48;
if( tbool ){// 直接将结果数组的标志位填入,这里用了堆栈思想
r = (jb - ib > ja - ia) ? (jb - ib) : (ja - ia);
stack = (char *)malloc(r + 4);
for(r = j = 0,s = jb; s >= ib; r ++,s --){
n = b[s] - 48;
stack[r] = (m * n + j) % 10;
j = (m * n + j) / 10;
}
if( j ){
stack[r] = j;
r ++;
}
for(r --; r >= 0; r --,pr ++)
result[pr] = stack[r];
free(stack);
for(move = move + pr; pr < move; pr ++)
result[pr] = '\0';
}
else{ //与结果的某几位相加,这里不改变标志位pr的值
r = pr - move - 1;
for(s = jb,j = 0; s >= ib; r --,s --){
n = b[s] - 48;
t = m * n + j + result[r];
result[r] = t % 10;
j = t / 10;
}
for( ; j ; r -- ){
t = j + result[r];
result[r] = t % 10;
j = t / 10;
}
}
}
int get(char *a,char *b,int ia,int ja,int ib,int jb,int t,int move){
int m,n,s,j;
if(ia == ja){
getFill(a,b,ia,ja,ib,jb,t,move);
return 1;
}
else if(ib == jb){
getFill(b,a,ib,jb,ia,ja,t,move);
return 1;
}
else{
m = (ja + ia) / 2;
n = (jb + ib) / 2;
s = ja - m;
j = jb - n;
get(a,b,ia,m,ib,n,t,s + j + move);
get(a,b,ia,m,n + 1,jb,0,s + move);
get(a,b,m + 1,ja,ib,n,0,j + move);
get(a,b,m + 1,ja,n + 1,jb,0,0 + move);
}
return 0;
}
int main(){
char *a,*b;
int n,flag;
a = (char *)malloc(1000);
b = (char *)malloc(1000);
printf("The program will computer a*b\n");
printf("Enter a b:");
scanf("%s %s",a,b);
result = (char *)malloc(strlen(a) + strlen(b) + 2);
flag = pr = 1;
result[0] = '\0';
if(a[0] == '-' && b[0] == '-')
get(a,b,1,strlen(a)-1,1,strlen(b)-1,1,0);
if(a[0] == '-' && b[0] != '-'){
flag = 0;
get(a,b,1,strlen(a)-1,0,strlen(b)-1,1,0);
}
if(a[0] != '-' && b[0] == '-'){
flag = 0;
get(a,b,0,strlen(a)-1,1,strlen(b)-1,1,0);
}
if(a[0] != '-' && b[0] != '-')
get(a,b,0,strlen(a)-1,0,strlen(b)-1,1,0);
if(!flag)
printf("-");
if( result[0] )
printf("%d",result[0]);
for(n = 1; n < pr ; n ++)
printf("%d",result[n]);
printf("\n");
free(a);
free(b);
free(result);
system("pause");
return 0;
}执行后先分别输入两个大数，例如123和456，按下【Enter】键后将输出这两个数相乘的积。执行效果如图2-9所示。
图2-9 “大数相乘”问题的执行效果
源码路径 光盘\daima\2\ouguan.c
问题描述：一年一度的欧洲冠军杯马上就要打响，在初赛阶段采用循环制，设共有n队参加，初赛共进行n−1天，每队要和其他各队进行一场比赛，然后按照最后积分选拔进入决赛的球队。要求每队每天只能进行一场比赛，并且不能轮空。请按照上述需求安排比赛日程，决定每天各队的对手。
算法分析：根据分治算法思路，将所有参赛队伍分为两半，则n队的比赛日程表可以通过n/2个队的比赛日程来决定。然后继续按照上述一分为二的方法对参赛队进行划分，直到只剩余最后2队时为止。
假设n队的编号为1，2，3，…，n，比赛日程表制作为一个二维表格，每行表示每队所对阵队的编号。例如8支球队7天比赛的日程表如表2-2所示。
表2-2 8队比赛日程表
| 编号 |
第1天 |
第2天 |
第3天 |
第4天 |
第5天 |
第6天 |
第7天 |
|---|---|---|---|---|---|---|---|
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
| 2 |
1 |
4 |
3 |
6 |
5 |
8 |
7 |
| 3 |
4 |
1 |
2 |
7 |
8 |
5 |
6 |
| 4 |
3 |
2 |
1 |
8 |
7 |
6 |
5 |
| 5 |
6 |
7 |
8 |
1 |
2 |
3 |
4 |
| 6 |
5 |
8 |
7 |
2 |
1 |
4 |
3 |
| 7 |
8 |
5 |
6 |
3 |
4 |
1 |
2 |
| 8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
根据表2-2的分析，可以将复杂的问题分治而解，即分解为多个简单的问题。例如有4队的比赛日程如表2-3所示。
表2-3 4队比赛日程表
| 编号 |
第1天 |
第2天 |
第3天 |
|---|---|---|---|
| 1 |
2 |
3 |
4 |
| 2 |
1 |
4 |
3 |
| 3 |
4 |
1 |
2 |
| 4 |
3 |
2 |
1 |
具体实现：根据上述分治算法思想，编写实例文件ouguan.c，具体实现代码如下所示。
#include <stdio.h>
#define MAXN 64
int a[MAXN+1][MAXN+1]={0};
void gamecal(int k,int n)//处理编号k开始的n个球队的日程
{
int i,j;
if(n==2)
{
a[k][1]=k; //参赛球队编号
a[k][2]=k+1; //对阵球队编号
a[k+1][1]=k+1; //参赛球队编号
a[k+1][2]=k; //对阵球队编号
}else{
gamecal(k,n/2);
gamecal(k+n/2,n/2);
for(i=k;i<k+n/2;i++) //填充右上角
{
for(j=n/2+1;j<=n;j++)
{
a[i][j]=a[i+n/2][j-n/2];
}
}
for(i=k+n/2;i<k+n;i++) //填充左下角
{
for(j=n/2+1;j<=n;j++)
{
a[i][j]=a[i-n/2][j-n/2];
}
}
}
}
int main()
{
int m,i,j;
printf("参赛球队数：");
scanf("%d",&m);
j=2;
for(i=2;i<8;i++)
{
j=j*2;
if(j==m) break;
}
if(i>=8)
{
printf("参赛球队数必须为2的整数次幂，并且不超过64！\n");
getch();
return 0;
}
gamecal(1,m);
printf("\n编号 ");
for(i=2;i<=m;i++)
printf("%2d天 ",i-1);
printf("\n");
for(i=1;i<=m;i++)
{
for(j=1;j<=m;j++)
printf("%4d ",a[i][j]);
printf("\n");
}
getch();
return 0;
}执行后先输入参赛球队数目，输入完成并按下【Enter】键会显示具体的比赛日程，执行效果如图2-10所示。
图2-10 比赛日程安排的执行效果
知识点讲解：光盘:视频讲解\第2章\贪心算法思想.avi
本节所要讲解的贪心算法也被称为贪婪算法，它在求解问题时总想用在当前看来是最好方法来实现。这种算法思想不从整体最优上考虑问题，仅仅是在某种意义上的局部最优求解。虽然贪心算法并不能得到所有问题的整体最优解，但是面对范围相当广泛的许多问题时，能产生整体最优解或者是整体最优解的近似解。由此可见，贪心算法只是追求某个范围内的最优，可以称之为“温柔的贪婪”。
贪心算法从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出一个近似解。由贪心算法的特点和思路可看出，贪心算法存在以下3个问题。
① 不能保证最后的解是最优的。
② 不能用来求最大或最小解问题。
③ 只能求满足某些约束条件的可行解的范围。
贪心算法的基本思路如下。
① 建立数学模型来描述问题。
② 把求解的问题分成若干个子问题。
③ 对每一子问题求解，得到子问题的局部最优解。
④ 把子问题的局部最优解合并成原来解问题的一个解。
实现该算法的基本过程如下。
（1）从问题的某一初始解出发。
（2）while能向给定总目标前进一步。
（3）求出可行解的一个解元素。
（4）由所有解元素组合成问题的一个可行解。
为了说明贪心算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解贪心算法思想在编程中的基本应用。
源码路径 光盘\daima\2\zhuangxiang.c
问题描述：假设有编号分别为0, 1,…, n−1的n种物品，体积分别为V0, V1,…, Vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V，即对于0i＜n，有0＜ViV。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求用尽量少的箱子装下这n种物品。
算法分析：如果将n种物品的集合分解为n个或小于n个物品的所有子集，使用最优解法就可以找到。但是所有可能的划分的总数会显得太大。对于适当大的n，如果要找出所有可能的划分，会需要花费很多时间。此时可以使用贪心算法这种近似算法来解决装箱问题。如果每只箱子所装物品用链表来表示，链表的首节点指针保存在一个结构中，该结构能够记录剩余的空间量和该箱子所装物品链表的首指针，并使用全部箱子的信息构成 链表。
具体实现：根据上述算法思想，编写实例文件zhuangxiang.c，具体实现代码如下所示。
#include <stdio.h>
#include <stdlib.h>
#define N 6
#define V 100
typedef struct box
{
int no;
int size;
struct box* next;
}BOX;
void init_list(BOX** H)
{
*H = (BOX*)malloc(sizeof(BOX));
(*H)->no = 0;
(*H)->size = 0;
(*H)->next = NULL;
}
BOX* find_p(BOX* H, int volume, int v)
{
BOX* p = H->next;
while(p!=NULL)
{
if(p->size+volume <= v)
break;
p = p->next;
}
return p;
}
void add_list_tail(BOX* H, BOX* p)
{
BOX* tmp = H->next;
BOX* q = H;
while(tmp!=NULL)
{
q = tmp;
tmp = tmp->next;
}
q->next = p;
}
void print_list(BOX* H)
{
BOX* p = H->next;
while(p!=NULL)
{
printf("%d:%d\n", p->no, p->size);
p = p->next;
}
}
int add_box(int volume[], int v)
{
int count = 0;
int i;
BOX* H = NULL;
init_list(&H);
for(i=0;i<N;i++)
{
BOX* p = find_p(H, volume[i], v);
if(p==NULL)
{
count++;
p = (BOX*)malloc(sizeof(BOX));
p->no = count;
p->size = volume[i];
p->next = NULL;
add_list_tail(H, p);
}
else
{
p->size += volume[i];
}
}
print_list(H);
return count;
}
int main(int argc, char *argv[])
{
int ret;
int volumes[] = {60, 45, 35, 20, 20, 20};
ret = add_box(volumes, V);
printf("%d\n", ret);
system("PAUSE");
return 0;
}执行后的效果如图2-11所示。
图2-11 “装箱”问题执行效果
为了说明贪心算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解解决“找零方案”问题的方法。
源码路径 光盘\daima\2\ling.c
问题描述：要求编写一段程序实现统一银座超市的找零方案，只需要输入需要补给顾客的金额，然后通过程序可以计算出该金额可以由哪些面额的人民币组成。
算法分析：人民币有100、50、10、5、2、1、0.5、0.2、0.1等多种面额（单位为元）。在找零钱时，可以有多种方案，例如需补零钱68.90元，至少可有以下3个方案。
① 1张50、1张10、1张5、3张1、1张0.5、4张0.1。
② 2张20、2张10、1张5、3张1、1张0.5、4张0.1。
③ 6张10、1张5、3张1、1张0.5、4张0.1。
具体实现：根据上述算法思想分析，编写实例文件ling.c，具体实现代码如下所示。
#include <stdio.h>
#define MAXN 9
int parvalue[MAXN]={10000,5000,2000,1000,500,100,50,10};
int num[MAXN]={0};
int exchange(int n)
{
int i,j;
for(i=0;i<MAXN;i++)
if(n>parvalue[i]) break; //找到比n小的最大面额
while(n>0 && i<MAXN)
{
if(n>=parvalue[i])
{
n-=parvalue[i];
num[i]++;
}else if(n<10 && n>=5)
{
num[MAXN-1]++;
break;
}else i++;
}
return 0;
}
int main()
{
int i;
float m;
printf ("输入需要找零金额: " );
scanf("%f",&m);
exchange((int)100*m);
printf("\n%.2f元零钱的组成：\n",m);
for(i=0;i<MAXN;i++)
if(num[i]>0)
printf("%6.2f：%d张\n",(float)parvalue[i]/100.0,num[i]);
getch();
return 0;
}执行后先输入需要找零的金额，例如68.2，按下【Enter】键后会输出找零方案，执行如图2-12所示。
图2-12 “找零方案”问题执行效果
知识点讲解：光盘:视频讲解\第2章\试探法算法思想.avi
试探法也叫回溯法，试探法的处事方式比较委婉，它先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一进行枚举和检验。当发现当前候选解不可能是正确的解时，就选择下一个候选解。如果当前候选解除了不满足问题规模要求外能够满足所有其他要求时，则继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，并继续试探的过程称为向前试探。
使用试探算法解题的基本步骤如下所示。
① 针对所给问题，定义问题的解空间。
② 确定易于搜索的解空间结构。
③ 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
试探法为了求得问题的正确解，会先委婉地试探某一种可能的情况。在进行试探的过程中，一旦发现原来选择的假设情况是不正确的，立即会自觉地退回一步重新选择，然后继续向前试探，如此这般反复进行，直至得到解或证明无解时才死心。
假设存在一个可以用试探法求解的问题P，该问题表达为：对于已知的由n元组（y1，y2，…，yn）组成的一个状态空间E={（y1，y2，…，yn）∣yi∈Si，i=1，2，…，n}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中，Si是分量yi的定义域，且|Si|有限，i=1，2，…，n。E中满足D的全部约束条件的任一n元组为问题P的一个解。
解问题P的最简单方法是使用枚举法，即对E中的所有n元组逐一检测其是否满足D的全部约束，如果满足，则为问题P的一个解。但是这种方法的计算量非常大。
对于现实中的许多问题，所给定的约束集D具有完备性，即i元组（y1，y2，…，yi）满足D中仅涉及y1，y2，…，yj的所有约束，这意味着j（j<i）元组（y1，y2，…，yj）一定也满足D中仅涉及y1，y2，…，yj的所有约束，i=1，2，…，n。换句话说，只要存在0jn−1，使得（y 1，y 2，…，yj）违反D中仅涉及y1，y2，…，yj的约束之一，则以（y1，y2，…，yj）为前缀的任何n元组（y1，y2，…，yj，yj+1，…，yn）一定也违反D中仅涉及y 1，y 2，…，yi的一个约束，ni>;j。因此，对于约束集D具有完备性的问题P，一旦检测断定某个j元组（y1，y2，…，yj）违反D中仅涉及y1，y2，…，yj的一个约束，就可以肯定，以（y1，y2，…，yj）为前缀的任何n元组（y1，y2，…，yj，yj+1，…，yn）都不会是问题P的解，因而就不必去搜索它们、检测它们。试探法是针对这类问题而推出的，比枚举算法的效率更高。
为了说明试探算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解试探算法思想在编程中的基本应用。
源码路径 光盘\daima\2\hui.c
问题描述：“八皇后”问题是一个古老而著名的问题，是试探法的典型例题。该问题由19世纪数学家高斯1850年手工解决：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
算法分析：首先将这个问题简化，设为4×4的棋盘，会知道有2种摆法，每行摆在列2、4、1、3或3、1、4、2上。
输入：无
输出：若干种可行方案，每种方案用空行隔开，如下是一种方案。
第1行第2列
第2行第4列
第3行第2列
第4行第3列
试探算法将每行的可行位置入栈（就是放入一个数组a[5]，这里用的是a[1]～a[4]），不行就退栈换列重试，直到找到一套方案输出。再接着从第一行换列重试其他方案。
具体实现：根据上述问题描述，使用试探算法加以解决。根据“八皇后”的试探算法分析，编写实现文件hui.c，具体实现代码如下所示。
#include <stdio.h>
#define N 8
int solution[N], j, k, count, sols;
int place(int row, int col)
{
for (j = 0; j <row; j++)
{
if (row - j == solution[row] - solution[j] || row + solution[row] == j + solution[j] || solution[j] == solution[row])
return 0;
}
return 1;
}
void backtrack(int row)
{
count++;
if (N == row)
{
sols++;
for (k = 0; k <N; k++)
printf("%d\t", solution[k]);
printf("\n\n");
}
else
{
int i;
for (i = 0; i <N; i++)
{
solution[row] = i;
if (place(row, i))
backtrack(row + 1);
}
}
}
void queens()
{
backtrack(0);
}
int main(void)
{
queens();
printf("总共方案: %d\n", sols);
getch();
return 0;
}执行后会输出所有的解决方案，执行效果如图2-13所示。
图2-13 “八皇后”问题执行效果
为了说明试探算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解解决“体彩29选7彩票组合”问题的方法。
源码路径 光盘\daima\2\caipiao.c
问题描述：假设有一种29选7的彩票，每注由7个1～29的数字组成，且这7个数字不能相同，编写程序生成所有的号码组合。
算法分析：采用试探法可以逐步解出所有可能的组合，首先分析按照如下顺序生成彩票号码。
29 28 27 26 25 24 23
29 28 27 26 25 24 22
29 28 27 26 25 24 21
……
29 28 27 26 25 24 1
29 28 27 26 25 23 22
……
从上述排列顺序可以看出，在生成组合时首先变化最后一位，当最后一位为1时将试探计算倒数第二位，并且使该位值减1，到最后再变化最后一位。通过上述递归调用，就可以实现29选7的彩票组合。
具体实现：根据“彩票组合”的试探算法分析编写实现文件caipiao.c，具体实现代码如下所示。
#include <stdio.h>
#define MAXN 7 //设置每一注彩票的位数
#define NUM 29 //设置组成彩票的数字
int num[NUM];
int lottery[MAXN];
void combine(int n, int m)
{
int i,j;
for(i=n;i>=m;i--)
{
lottery[m-1]=num[i-1]; //保存一位数字
if (m>1)
combine(i-1,m-1);
else //若m=1，输出一注号码
{
for(j=MAXN-1;j>=0;j--)
printf("%3d",lottery[j]);
getch();
printf("\n");
}
}
}
int main()
{
int i,j;
for(i=0;i<NUM;i++) //设置彩票各位数字
num[i]=i+1;
for(i=0;i<MAXN;i++)
lottery[i]=0;
combine(NUM,MAXN);
getch();
return 0;
}执行后的效果如图2-14所示。
图2-14 “体彩29选7彩票组合”问题执行效果
知识点讲解：光盘:视频讲解\第2章\迭代算法.avi
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，在解决问题时总是重复利用一种方法。与迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法，功能都比较类似。
迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。
在使用迭代算法解决问题时，需要做好如下3个方面的工作。
（1）确定迭代变量
在可以使用迭代算法解决的问题中，至少存在一个迭代变量，即直接或间接地不断由旧值递推出新值的变量。
（2）建立迭代关系式
迭代关系式是指如何从变量的前一个值推出其下一个值的公式或关系。通常可以使用递推或倒推的方法来建立迭代关系式，迭代关系式的建立是解决迭代问题的关键。
（3）对迭代过程进行控制
在编写迭代程序时，必须确定在什么时候结束迭代过程，不能让迭代过程无休止地重复执行下去。通常可分为如下两种情况来控制迭代过程：
① 所需的迭代次数是个确定的值，可以计算出来，可以构建一个固定次数的循环来实现对迭代过程的控制；
② 所需的迭代次数无法确定，需要进一步分析出用来结束迭代过程的条件。
为了说明迭代算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解迭代算法思想在编程中的基本应用。
源码路径 光盘\daima\2\diedai.c
问题描述：在屏幕中输入一个数字，使用编程方式求出其平方根是多少。
算法分析：求平方根的迭代公式是：x1=1/2*(x0+a/x0)。
① 设置一个初值x0作为a的平方根值，在程序中取a/2作为a的初值；利用迭代公式求出一个x1。此值与真正的a的平方根值相比往往会有很大的误差。
② 把新求得的x1代入x0，用这个新的x0再去求出一个新的x1。
③ 利用迭代公式再求出一个新的x1的值，即用新的x0求出一个新的平方根值x1，此值将更加趋近于真正的平方根值。
④ 比较前后两次求得的平方根值x0和x1，如果它们的差值小于指定的值，即达到要求的精度，则认为x1就是a的平方根值，去执行步骤⑤；否则执行步骤②，即循环进行迭代。
⑤ 输出结果。
迭代法常用于求方程或方程组的近似根，假设设方程为f(x)=0，用某种数学方法导出等价的形式x=g(x)，然后按以下步骤执行：
① 选一个方程的近似根，赋给变量x0；
② 将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0；
③ 当x0与x1的差的绝对值还大于指定的精度要求时，重复步骤②的计算。
如果方程有根，并且用上述方法计算出来了近似的根序列，则按照上述方法求得的x0就被认为是方程的根。
具体实现：根据上述算法思想，编写实例文件diedai.c，具体实现代码如下所示。
#include<stdio.h>
#include<math.h>
void main()
{
double a,x0,x1;
printf("Input a:\n");
scanf("%lf",&a);
if(a<0)
printf("Error!\n");
else
{
x0=a/2;
x1=(x0+a/x0)/2;
do
{
x0=x1;
x1=(x0+a/x0)/2;
}while(fabs(x0-x1)>=1e-6);
}
printf("Result:\n");
printf("sqrt(%g)=%g\n",a,x1);
getch();
return 0;
}执行后先输入要计算平方根的数值，假如输入2，按下【Enter】键后会输出2的平方根结果。执行效果如图2-15所示。
图2-15 “求平方根”问题执行效果
使用迭代法求根时应注意以下两种可能发生的情况。
① 如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制。
② 方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败。
知识点讲解：光盘:视频讲解\第2章\模拟算法思想.avi
模拟是对真实事物或者过程的虚拟。在编程时为了实现某个功能，可以用语言来模拟那个功能，模拟成功也就相应地表示编程成功。
模拟算法是一种基本的算法思想，可用于考查程序员的基本编程能力，其解决方法就是根据题目给出的规则对题目要求的相关过程进行编程模拟。在解决模拟类问题时，需要注意字符串处理、特殊情况处理和对题目意思的理解。在C语言中，通常使用函数srand()和rand()来生成随机数。其中，函数srand()用于初始化随机数发生器，然后使用函数rand()来生成随机数。如果要使用上述两个函数，则需要在源程序头部包含time.h文件。在程序设计过程中，可使用随机函数来模拟自然界中发生的不可预测情况。在解题时，需要仔细分析题目给出的规则，要尽可能地做到全面考虑所有可能出现的情况，这是解模拟类问题的关键点之一。
为了说明模拟算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解模拟算法思想在编程中的基本应用。
源码路径 光盘\daima\2\shuzi.c
问题描述：用计算机随机生成一个1～100的数字，然后由用户来猜这个数，根据用户猜测的次数分别给出不同的提示。
算法分析：使用模拟算法进行如下分析。
① 通过rand()随机生成一个1～100的数字。
② 通过循环让用户逐个输入要猜测的整数，并将输入的数据与随机数字进行比较。
③ 将比较的结果输出。
具体实现：根据上述问题描述，及“猜数字游戏”的模拟算法分析，编写实现文件shuzi.c，具体实现代码如下所示。
#include <time.h>
#include <stdio.h>
int main()
{
int n,m,i=0;
srand(time(NULL));
n=rand() % 100 + 1;
do{
printf("输入你猜的数字:");
scanf("%d",&m);
i++;
if (m>n)
printf("错误!太大了!\n");
else if (m<n)
printf("错误!数太小了!\n");
}while(m!=n);
printf("回答正确!\n");
printf("共猜测了%d次。\n",i);
if(i<=5)
printf("你太聪明了，这么快就猜出来了！");
else if(i>5)
printf("还需改进方法，以便更快猜出来！");
getch();
return 0;
}执行后的效果如图2-16所示。
图2-16 “猜数字游戏”问题执行效果
为了说明模拟算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解解决“掷骰子游戏”问题的方法。
源码路径 光盘\daima\2\guzi.c
问题描述：由用户输入骰子数量和参赛人数，然后由计算机随机生成每一粒骰子的数量，再累加得到每一个选手的总点数。
算法分析：使用模拟算法进行分析。
① 定义一个随机函数play()，根据骰子数量随机生成骰子的点数。
② 设置一个死循环，可以重复操作。
③ 处理每个选手，调用函数play()模拟掷骰子游戏的场景。
具体实现：根据“掷骰子游戏”的模拟算法分析编写实现文件guzi.c，具体实现代码如下所示。
#include <stdio.h>
#include <time.h>
void play(int n)
{
int i,m=0,t=0;
for(i=0;i<n;i++)
{
t=rand()%6+1;
m+=t;
printf("\t第%d粒:%d;\n",i+1,t);
}
printf("\t总点数为:%d\n",m);
}
int main(void)
{
int c;//参赛人数
int n;//骰子数量
int i,m;
do{
srand(time(NULL));
printf("设置骰子数量(输入0退出):");
scanf("%d",&n);
if(n==0) break;//至少一个骰子
printf("\n输入本轮参赛人数(输入0退出):");
scanf("%d",&c);
if(c==0) break;
for(i=0;i<c;i++)
{
printf("\n第%d位选手掷出的骰子为：\n",i+1);
play(n);
}
printf("\n");
}while(1);
return 0;
}执行后的效果如图2-17所示。
图2-17 “掷骰子游戏”问题执行效果
算法是否优劣有如下5个标准。
① 确定性。算法的每一种运算必须有确定的意义，该种运算应执行何种动作应无二义性，目的明确。
② 可行性。要求算法中待实现的运算都是可行的，即至少在原理上能由人用纸和笔在有限的时间内完成。
③ 输入。一个算法有零个或多个输入，在算法运算开始之前给出算法所需数据的初值，这些输入来自特定的对象集合。
④ 输出。输出是算法运算的结果，一个算法会产生一个或多个输出，输出同输入具有某种特定关系。
⑤ 有穷性。一个算法总是在执行了有穷步的运算后终止，即该算法是有终点的。
通常有如下两种衡量算法效率的方法：
① 事后统计法。该方法的缺点是必须在计算机上实际运行程序，容易被其他因素掩盖算法本质。
② 事前分析估算法。该方法的优点是可以预先比较各种算法，以便均衡利弊而从中选优。
与算法执行时间相关的因素如下：
① 算法所用“策略”；
② 算法所解问题的“规模”；
③ 编程所用“语言”；
④ “编译”的质量；
⑤ 执行算法的计算机的“速度”。
在上述因素中，后3条受计算机硬件和软件的制约，因为是“估算”，所以只需考虑前两条即可。
事后统计容易陷入盲目境地，例如，当程序执行很长时间仍未结束时，不易判别是程序错了还是确实需要那么长的时间。
一个算法的“运行工作量”通常是随问题规模的增长而增长，所以应该用“增长趋势”来作为比较不同算法的优劣的准则。假如，随着问题规模n的增长，算法执行时间的增长率与f(n)的增长率相同，则可记作：T(n) = O(f(n))，称T(n)为算法的（渐近）时间复杂度。
究竟如何估算算法的时间复杂度呢？任何一个算法都是由一个“控制结构”和若干“原操作”组成的，所以可以将一个算法的执行时间看作：所有原操作的执行时间之和∑（原操作(i)的执行次数×原操作(i)的执行时间）。
算法的执行时间与所有原操作的执行次数之和成正比。对于所研究的问题来说，从算法中选取一种基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法时间复杂度的依据。以这种衡量效率的办法所得出的不是时间量，而是一种增长趋势的量度。它与软硬件环境无关，只暴露算法本身执行效率的优劣。下面通过3段代码介绍时间复杂度的估算方法。
代码1：两个n×n的矩阵相乘。其中矩阵的“阶”n为问题的规模。
算法如下：
void Mult_matrix( int c[][], int a[][], int b[][]，int n)
{
// a、b和c均为n阶方阵，且c是a和b的乘积
for (i=1; i<=n; ++i)
for (j=1; j<=n; ++j) {
c[i,j] = 0;
for (k=1; k<=n; ++k)
c[i,j] += a[i,k]*b[k,j];
}
}// Mult_matrix算法的时间复杂度为O(n3)。
代码2：对n个整数的序列进行选择排序。其中序列的“长度”n为问题的规模。
算法如下：
void select_sort(int a[], int n)
{
// 将a中整数序列重新排列成自小至大有序的整数序列。
for ( i = 0; i< n-1; ++i ) {
j = i;
for ( k = i+1; k < n; ++k )
if (a[k] < a[j] ) j = k;
if ( j != i ) { w = a[j]; a[j] = a[i]; a[i] = w;}
} // select_sort算法的时间复杂度为O(n2)。
代码3：对n个整数的序列进行起泡排序。其中序列的“长度”n为问题的规模。
算法如下：
void bubble_sort(int a[], int n)
{
// 将a中整数序列重新排列成自小至大有序的整数序列。
for (i=n-1, change=TRUE; i>1 && change; --i) {
change = FALSE;
for (j=0; j<i; ++j)
if (a[j] > a[j+1])
{ w = a[j]; a[j]= a[j+1]; a[j+1]= w; change = TRUE }
}
} // bubble_sort算法的时间复杂度为O(n2)。
从上述3个例子可见，算法时间复杂度取决于最深循环内包含基本操作的语句的重复执行次数，称语句重复执行的次数为语句的“频度”。
也许很多读者觉得枚举（enumeration）有点“笨”，所以很多人称之为“暴力算法（brute force enumeration）”；但是枚举却又总是人们面对算法问题时的第一反应。
在任何情况下，需要选准最合适的对象，无论是枚举还是其他算法思想，这都是最关键的。选准（枚举）对象的根本原因在于优化，具体表现为减少求解步骤，缩小求解的解空间，或者是使程序更具有可读性和易于编写。有时候选好了枚举对象，确定了枚举思想解决问题，问题就迎刃而解了。有时候对题目无从下手，只得使用枚举思想解题时，需要考虑的往往是从众多枚举对象中选择最适合的对象，这往往需要辨别的智慧。
在运用枚举思想时需要面对的问题如表2-4所示。
表2-4 运用枚举思想时需要面对的问题
| 特点及要求 |
可能出现的问题 |
|---|---|
| 选取考察对象 |
选取的考察对象不恰当 |
| 逐个考察所有可能的情况 |
没有“逐个”考察，不恰当地遗漏了一些情况； |
| 选取判断标准 |
判断标准“不正确”，导致结果错误； |
用枚举法解题的最大缺点是运算量比较大，解题效率不高。如果枚举范围太大（一般以不超过200万次为限），因为效率低的问题会在时间上难以承受。但枚举算法的思路简单，无论是程序编写和还是调试都很方便。所以如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以有更多的时间去解答其他难题。
递推和递归虽然只有一个字的差异，但是两者之间还是不同的。递推像是多米诺骨牌，根据前面几个得到后面的；递归是大事化小，比如“汉诺塔”（Hanoi）问题就是典型的递归。如果一个问题既可以用递归算法求解，也可以用递推算法求解，此时往往选择用递推算法，因为递推的效率比递归高。
分治法所能解决的问题一般具有以下4个特征。
① 当问题的规模缩小到一定的程度就可以容易地解决问题。此特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般随着问题规模的增加而增加。
② 问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。此特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用。
③ 利用该问题分解出的子问题的解可以合并为该问题的解；此特征最为关键，能否利用分治法完全取决于问题是否具有特征③，如果具备了特征①和特征②，而不具备特征③，则可以考虑用贪婪法或动态迭代法。
④ 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。此特征涉及分治法的效率问题，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态迭代法较好。
分治策略的思想起源于对问题解的特性所做出的观察和判断，即：原问题可以被划分成k个子问题，然后用一种方法将这些子问题的解合并，合并的结果就是原问题的解。既然知道解可以以某种方式构造出来，就没有必要（使用枚举回溯）进行大批量的搜索了。枚举、回溯、分支限界利用了计算机工作的第一个特点——高速，不怕数据量大；分治算法思想利用了计算机工作的第二个特点——重复。
还是看“装箱”问题，说明贪婪算法并不是解决问题的最优方案。该算法依次将物品放到它第一个能放进去的箱子中，该算法虽不能保证找到最优解，但还是能找到非常好的解。设n件物品的体积按从大到小排序，即有V0V1…Vn−1。如不满足上述要求，只要先对这n件物品按它们的体积从大到小排序，然后按排序结果对物品重新编号即可。下面介绍就是一个典型的贪心算法的问题。
先取体积最大的
{ 输入箱子的容积；
输入物品种数n；
按体积从大到小顺序，输入各物品的体积；
预置已用箱子链为空；
预置已用箱子计数器box_count为0；
for (i=0;i<n;i++)
{ 从已用的第一只箱子开始顺序寻找能放入物品i的箱子j；
if（已用箱子都不能再放物品i）
{ 另用一个箱子，并将物品i放入该箱子；
box_count++；
}
else
将物品i放入箱子j；
}
}通过上述算法，能够求出需要的箱子数box_count，并能求出各箱子所装物品。
再看下面的例子。
设有6种物品，它们的体积分别为60、45、35、20、20和20单位体积，箱子的容积为100个单位体积。按上述算法计算，需三只箱子，各箱子所装物品分别为：第一只箱子装物品1、3；第二只箱子装物品2、4、5；第三只箱子装物品6。而最优解为两只箱子，分别装物品1、4、5和2、3、6。
上述例子说明，贪心算法不一定能找到最优解。
下面是回溯的3个要素。
① 解空间：是要解决问题的范围，不知道范围的搜索是不可能找到结果的。
② 约束条件：包括隐形的和显性的，题目中的要求以及题目描述隐含的约束条件，是搜索有解的保证。
③ 状态树：是构造深搜过程的依据，整个搜索以此树展开。
适合解决没有要求求最优解的问题，如果采用，一定要注意跳出条件及搜索完成的标志，否则会陷入泥潭不可自拔。
下面是影响算法效率的因素。
递归是自顶向下逐步拓展需求，最后自下向顶运算，即由f(n)拓展到f(1)，再由f(1)逐步算回f(n)。迭代是直接自下向顶运算，由f(1)算到f(n)。递归是在函数内调用本身，迭代是循环求值，建议熟悉其他算法的读者不推荐使用递归算法。
虽然递归算法的效率低一点，但是随着现在计算机性能的提升，且递归便于理解，可读性强，所以建议对其他算法不熟悉的初学者使用递归算法来解决问题。
