作者：张玲玲
出版社：人民邮电出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
算法学习与应用从入门到精通试读：
前言
从你开始学习编程的那一刻起，就注定了以后所要走的路：从编程学习者开始，依次经历实习生、程序员、软件工程师、架构师、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章算法是程序的灵魂
算法是程序的灵魂，只有掌握了算法，才能轻松地驾驭程序开发。软件开发工作不是按部就班的，而是选择一种最合理的算法去实现项目功能。算法能够引导开发者在面对一个项目功能时用什么思路去实现，有了这个思路后，编程工作只需遵循这个思路去实现即可。在本章将详细讲解计算机算法的基础知识，为读者步入后面的学习打下基础。1.1 算法的基础知识点讲解：光盘:视频讲解\第1章\算法的基础.avi
自然界中的很多事物并不是独立存在的，而是和许多其他事物有着千丝万缕的联系。就拿算法和编程来说，两者之间就有着必然的联系。在编程界有一个不成文的原则，要想学好编程就必须学好算法。要想获悉这一说法的原因，先看下面对两者的定义。（1）算法：是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对符合一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。（2）编程：是让计算机为解决某个问题而使用某种程序设计语言编写程序代码，并最终得到结果的过程。为了使计算机能够理解人的意图，人类就必须将需要解决的问题的思路、方法和手段通过计算机能够理解的形式“告诉”计算机，使计算机能够根据人的指令一步一步去工作，完成某种特定的任务。编程的目的是实现人和计算机之间的交流，整个交流过程就是编程。
在上述对编程的定义中，核心内容是思路、方法和手段等，这都需要用算法来实现。由此可见，编程的核心是算法，只要算法确定了，后面的编程工作只是实现算法的一个形式而已。1.1.1 算法的特征
在1950年，Algorithm（算法）一词经常同欧几里德算法联系在一起。这个算法就是在欧几里德的《几何原本》中所阐述的求两个数的最大公约数的过程，即辗转相除法。从此以后，Algorithm这一叫法一直沿用至今。
随着时间的推移，算法这门科学得到了长足的发展，算法应该具有如下5个重要的特征。
① 有穷性：保证执行有限步骤之后结束。
② 确切性：每一步骤都有确切的定义。
③ 输入：每个算法有零个或多个输入，以刻画运算对象的初始情况，所谓零个输入是指算法本身舍弃了初始条件。
④ 输出：每个算法有一个或多个输出，显示对输入数据加工后的结果，没有输出的算法是毫无意义的。
⑤ 可行性：原则上算法能够精确地运行，进行有限次运算后即可完成一种运算。1.1.2 何为算法
为了理解什么是算法，先看一道有趣的智力题。“烧水泡茶”有如下5道工序：①烧开水、②洗茶壶、③洗茶杯、④拿茶叶、⑤泡茶。
烧开水、洗茶壶、洗茶杯、拿茶叶是泡茶的前提。其中，烧开水需要15分钟，洗茶壶需要2分钟，洗茶杯需要1分钟，拿茶叶需要1分钟，泡茶需要1分钟。
下面是两种“烧水泡茶”的方法。1．方法1
第一步：烧水。
第二步：水烧开后，洗刷茶具，拿茶叶。
第三步：沏茶。2．方法2
第一步：烧水。
第二步：烧水过程中，洗刷茶具，拿茶叶。
第三步：水烧开后沏茶。
问题：比较这两个方法有何不同，并分析哪个方法更优。
上述两个方法都能最终实现“烧水泡茶”的功能，每种方法的3个步骤就是一种“算法”。算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。1.2 计算机中的算法知识点讲解：光盘:视频讲解\第1章\计算机中的算法.avi
众所周知，做任何事情都需要一定的步骤。计算机虽然功能强大，能够帮助人们解决很多问题，但是计算机在解决问题时，也需要遵循一定的步骤。在编写程序实现某个项目功能时，也需要遵循一定的算法。在本节的内容中，将一起探寻算法在计算机中的地位，探索算法在计算机中的基本应用知识。1.2.1 认识计算机中的算法
计算机中的算法可分为如下两大类。
① 数值运算算法：求解数值。
② 非数值运算算法：事务管理领域。
假设有一个下面的运算：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步：如果i5，返回重新执行步骤3以及其后的步骤4和步骤5；否则，算法结束。
由此可见，上述算法方式就是数学中的“n!”公式。既然有了公式，在具体编程的时候，只需使用这个公式就可以解决上述运算的问题。
再看下面的一个数学应用问题。
假设有80个学生，要求打印输出成绩在60分以上的学生。
在此用n来表示学生学号，n表示第i个学生学号；cheng表示学生i成绩，cheng表示第i个学生成绩。根据题目要求，可以写出如下算法。i
第1步：1→i。
第2步：如果cheng60，则打印输出n和cheng，否则不打印输iii出。
第3步：i+1→i。
第4步：如果i80，返回步骤2，否则，结束。
由此可见，算法在计算机中的地位十分重要。所以在面对一个项目应用时，一定不要立即编写程序，而是要仔细思考解决这个问题的算法是什么。想出算法之后，然后以这个算法为指导思想来编程。1.2.2 为什么说算法是程序的灵魂
相信广大读者经过了解和学习1.2.1节的内容，已基本了解了算法在计算机编程中的重要作用，在程序开发中，算法已经成为衡量一名程序员水平高低的参照物。水平高的程序员都会看重数据结构和算法的作用，水平越高，就越能理解算法的重要性。算法不仅仅是运算工具，它更是程序的灵魂。在现实项目开发过程中，很多实际问题需要精心设计的算法才能有效解决。
算法是计算机处理信息的基础，因为计算机程序本质上是一个算法，告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。通常，当算法在处理信息时，数据会从输入设备读取，写入输出设备，也可能保存起来供以后使用。
著名计算机科学家沃思提出了下面的公式。数据结构+算法=程序
实际上，一个程序应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言来表示。因此，可以用下面的公式表示。程序=算法+数据结构+程序设计方法+语言和环境
上述公式中的4个方面是一种程序设计语言所应具备的知识。在这4个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。其中，算法是用来解决“做什么”和“怎么做”的问题。实际上程序中的操作语句就是算法的体现，所以说，不了解算法就谈不上程序设计。数据是操作对象，对操作的描述即是操作步骤，操作的目的是对数据进行加工处理以得到期望的结果。举个通俗点的例子，厨师做菜肴，需要有菜谱。菜谱上一般应包括：①配料（数据）、②操作步骤（算法）。这样，面对同样的原料可以加工出不同风味的菜肴。1.3 在计算机中表示算法的方法知识点讲解：光盘:视频讲解\第1章\在计算机中表示算法的方法.avi
在1.2.1节中演示的算法都是通过语言描述来体现的。其实除了语言描述之外，还可以通过其他方法来描述算法。在接下来的内容中，将简单介绍几种表示算法的方法。1.3.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个特点对于理解算法很有帮助。
① 只有一个入口。
② 只有一个出口。
③ 结构内的每一部分都有机会被执行到。
④ 结构内不存在“死循环”。1.3.2 用N-S流程图来表示算法
在1973年，美国学者提出了N-S流程图的概念，通过它可以表示计算机的算法。N-S流程图由一些特定意义的图形、流程线及简要的文字说明构成，能够比较清晰明确地表示程序的运行过程。人们在使用传统流程图的过程中，发现流程线不一定是必需的，所以设计了一种新的流程图，这种新的方式可以把整个程序写在一个大框图内，这个大框图由若干个小的基本框图构成，这种新的流程图简称N-S图。
遵循N-S流程图的特点，N-S流程图的顺序结构图1-6所示，选择结构如图1-7所示，循环结构如图1-8所示。图1-6 顺序结构图1-7 选择结构图1-8 循环结构1.3.3 用计算机语言表示算法
因为算法可以解决计算机中的编程问题，是计算机程序的灵魂，所以，可以使用计算机语言来表示算法。当用计算机语言表示算法时，必须严格遵循所用语言的语法规则。再次回到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语言的语法规则。1.4 技术解惑
在一些培训班的广告中到处充斥着“一个月打造高级程序员”的口号，书店里也随处可见书名打着“入门捷径”旗号的书。有过学习经验和工作经验的人们往往深有体会，这些宣传不能全信，学习编程之路需要付出辛苦的汗水，需要付出相当多的时间和精力。结合笔者的学习经验，现总结出如下3条经验和大家一起分享。（1）学得要深入，基础要扎实
基础的作用不必多说，基础的重要性在大学课堂上老师曾经讲过了很多次，在此重点说明“深入”。职场不是学校，企业要求你能高效地完成项目功能，但是现实中的项目种类繁多，需要从根本上掌握算法技术的精髓，入门水平不会被开发公司所接受，他们需要的是高手。（2）恒心、演练、举一反三
学习编程的过程是枯燥的，要将学习算法作为自己的乐趣，只有做到持之以恒才能掌握到编程的精髓。另外，编程最注重实践，最害怕闭门造车。每一个语法，每一个知识点，都要反复用实例来演练，这样才能加深对知识的理解。并且要做到举一反三，只有这样才能对知识有深入的理解。（3）语言之争的时代更要学会坚持
当今新技术、新思想、新名词层出不穷，令人眼花缭乱。希望大家不要盲目追求各种新的技术，建议大家做一名立场坚定的程序员，人们都说C语言已经老掉牙了，但是现实是，C语言永远是我们学习高级语言的基础，永远是内核和嵌入式开发的首选语言。所以只要认定自己的选择，就要坚持下去。第2章常用的算法思想
算法思想有很多，业界公认的常用算法思想有8种，分别是枚举、递推、递归、分治、贪心、试探法、动态迭代和模拟。当然8种只是一个大概的划分，是一个“仁者见仁、智者见智”的问题。在本章将详细讲解这8种算法思想的基本知识，希望读者理解并掌握这8种算法思想的基本用法和核心知识，为学习本书后面的知识打下基础。2.1 枚举算法思想知识点讲解：光盘:视频讲解\第2章\枚举算法思想.avi
枚举算法思想的最大特点是，在面对任何问题时它会去尝试每一种解决方法。在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这个结论是可靠的，这种归纳方法叫作枚举法。2.1.1 枚举算法基础
枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。在C语言中，枚举算法一般使用while循环实现。使用枚举算法解题的基本思路如下。
① 确定枚举对象、枚举范围和判定条件。
② 逐一列举可能的解，验证每个解是否是问题的解。
枚举算法一般按照如下3个步骤进行。
① 题解的可能范围，不能遗漏任何一个真正解，也要避免有重复。
② 判断是否是真正解的方法。
③ 使可能解的范围降至最小，以便提高解决问题的效率。
枚举算法的主要流程如图2-1所示。图2-1 枚举算法流程图2.1.2 实战演练——百钱买百鸡
为了说明枚举算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解枚举算法思想在编程中的基本应用。实例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
执行后的效果如图2-2所示。图2-2 “百钱买百鸡”问题执行效果2.1.3 实战演练——解决“填写运算符”问题
一个实例不能说明枚举算法思想的基本用法，在下面的实例中将详细解使用枚举法解决“填写运算符”的问题。实例2-2 使用枚举法解决“填写运算符”问题
源码路径 光盘\daima\2\yunsuan.c
问题描述：在下面的算式中，添加“+”“−”“×”“÷”4个运算符，使这个等式成立。
5 5 5 5 5 = 5
算法分析：上述算式由5个数字构成，一共需要填入4个运算符。根据题目要求，知道每两个数字之间的运算符只能有4种选择，分别是“+”“−”“×”“÷”。在具体编程时，可以通过循环来填入各种运算符，然后再判断算式是否成立。并且保证当填入除号时，其右侧的数不能是0，并且“×”“÷”运算符的优先级高于“+”“−”。
具体实现：根据上述“填写运算符”的枚举算法分析，编写实现文件yunsuan.c，具体实现代码如下所示。#include
在上述代码中，定义了left和right两个变量，left用于保存上一步的运算结果，right用于保存下一步的运算结果。因为“×”和“÷”的优先级高于“+”和“−”，所以计算时先计算“×”和“÷”，再计算“+”和“−”。执行后的效果如图2-3所示。图2-3 “填写运算符”问题执行效果2.2 递推算法思想知识点讲解：光盘:视频讲解\第2章\递推算法思想.avi
与枚举算法思想相比，递推算法能够通过已知的某个条件，利用特定的关系得出中间推论，然后逐步递推，直到得到结果为止。由此可见，递推算法要比枚举算法聪明，它不会尝试每种可能的方案。2.2.1 递推算法基础
递推算法可以不断利用已有的信息推导出新的东西，在日常应用中有如下两种递推 算法。
① 顺推法：从已知条件出发，逐步推算出要解决问题的方法。例如斐波那契数列就可以通过顺推法不断递推算出新的数据。
② 逆推法：从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。2.2.2 实践演练——解决“斐波那契数列”问题
为了说明递推算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解递推算法思想在编程过程中的基本应用。实例2-3 使用顺推法解决“斐波那契数列”问题
源码路径 光盘\daima\2\shuntui.c
问题描述：斐波那契数列因数学家列昂纳多•斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？
算法分析：以新出生的一对小兔子进行如下分析。
① 第一个月小兔子没有繁殖能力，所以还是一对。
② 2个月后，一对小兔子生下了一对新的小兔子，所以共有两对兔子。
③ 3个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是3对。
……
依次类推可以列出关系表，如表2-1所示。
表2-1 月数与兔子对数关系表月数：12345678…对数：1123581321…
表中数字1，1，2，3，5，8……构成了一个数列，这个数列有个十分明显的特点：前面相邻两项之和，构成了后一项。这个特点的证明：每月的大兔子数为上月的兔子数，每月的小兔子数为上月的大兔子数，某月兔子的对数等于其前面紧邻两个月的和。
由此可以得出具体算法如下所示：
设置初始值为F=1，第1个月兔子的总数是F=1。01
第2个月的兔子总数是F= F+F。201
第2个月的兔子总数是F= F+F。312
第3个月的兔子总数是F= F+F。423
………
第n个月的兔子总数是F= F-2+F-1。nnn
具体实现：根据上述问题描述，根据“斐波那契数列”的顺推算法分析，编写实现文件shuntui.c，具体实现代码如下所示。#include 执行后的效果如图2-4所示。图2-4 “斐波那契数列”问题执行效果2.2.3 实践演练——解决“银行存款”问题 一个实例不能说明递推算法思想的基本用法，接下来开始使用逆推算法解决“银行存款”问题。实例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 执行后的效果如图2-5所示。图2-5 “银行存款”问题执行效果2.3 递归算法思想知识点讲解：光盘:视频讲解\第2章\递归算法思想.avi 因为递归算法思想往往用函数的形式来体现，所以递归算法需要预先编写功能函数。这些函数是独立的功能，能够实现解决某个问题的具体功能，当需要时直接调用这个函数即可。在本节的内容中，将详细讲解递归算法思想的基本知识。2.3.1 递归算法基础 在计算机编程应用中，递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。递归算法有如下3个特点。 ① 递归过程一般通过函数或子过程来实现。 ② 递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。 ③ 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。 在使用递归算法时，读者应该注意如下4点。 ① 递归是在过程或函数中调用自身的过程。 ② 在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。 ③ 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。 ④ 在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。2.3.2 实践演练——解决“汉诺塔”问题 为了说明递归算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解递归算法思想在编程中的基本应用。实例2-5 使用递归算法解决“汉诺塔”问题 源码路径 光盘\daima\2\hannuo.c 问题描述：寺院里有3根柱子，第一根有64个盘子，从上往下盘子越来越大。方丈要求小和尚A把这64个盘子全部移动到第3根柱子1上。在移动的时候，始终只能小盘子压着大盘子，而且每次只能移动一个。 方丈发布命令后，小和尚A就马上开始了工作，下面看他的工1作过程。（1）聪明的小和尚A在移动时，觉得很难，另外他也非常懒1惰，所以找来A来帮他。他觉得要是A能把前63个盘子先移动到第22二根柱子上，自己再把最后一个盘子直接移动到第三根柱子，再让A把刚才的前63个盘子从第二根柱子上移动到第三根柱子上，整个2任务就完成了。所以他找了另一个小和尚A，然后下了如下命令：2 ① 把前63个盘子移动到第二根柱子上； ② 把第64个盘子移动到第三根柱子上后； ③ 把前63个盘子移动到第三根柱子上；（2）小和尚A接到任务后也觉得很难，所以他也和A想的一21样：要是有一个人能把前62个盘子先移动到第三根柱子上，再把最后一个盘子直接移动到第二根柱子，再让那个人把刚才的前62个盘子从第三根柱子上移动到第三根柱子上，任务就算完成了。所以他也找了另外一个小和尚A，然后下了如下命令：3 ① 把前62个盘子移动到第三根柱子上； ② 自己把第63个盘子移动到第二根柱子上后； ③ 把前62个盘子移动到第二根柱子上；（3）小和尚A接了任务，又把移动前61个盘子的任务“依葫芦3画瓢”的交给了小和尚A，这样一直递推下去，直到把任务交给了4第64个小和尚A为止。64（4）此时此刻，任务马上就要完成了，唯一的工作就是A和63A64的工作了。 小和尚A移动第1个盘子，把它移开，然后小和尚A移动给他6463分配的第2个盘子。 小和尚A再把第1个盘子移动到第2个盘子上。到这里A的任务6464完成，A完成了A交给他的任务的第一步。6362 算法分析：从上面小和尚的工作过程可以看出，只有A的任务64完成后，A的任务才能完成，只有小和尚A～小和尚A的任务完成63264后，小和尚A剩余的任务才能完成。只有小和尚A剩余的任务完11成，才能完成方丈吩咐给他的任务。由此可见，整个过程是一个典型的递归问题。接下来我们以有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 “汉诺塔”问题执行效果2.3.3 实践演练——解决“阶乘”问题 为了说明递归算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解使用递归算法思想解决阶乘问题的方法。实例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 执行后如果输入“6”并按下【Enter】键，则会输出6的阶乘是720，执行效果如图2-8所示。图2-8 计算6的阶乘的执行效果2.4 分治算法思想知识点讲解：光盘:视频讲解\第2章\分治算法思想.avi 在本节将要讲解的分治算法也采取了各个击破的方法，将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。只要求出子问题的解，就可得到原问题的解。2.4.1 分治算法基础 在编程过程中，经常遇到处理数据相当多、求解过程比较复杂、直接求解法会比较耗时的问题。在求解这类问题时，可以采用各个击破的方法。具体做法是：先把这个问题分解成几个较小的子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个大问题的解。如果这些子问题还是比较大，还可以继续再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治算法的基本思想。 使用分治算法解题的一般步骤如下。 ① 分解，将要解决的问题划分成若干个规模较小的同类问题。 ② 求解，当子问题划分得足够小时，用较简单的方法解决。 ③ 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。2.4.2 实践演练——解决“大数相乘”问题 为了说明分治算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解分治算法思想在编程中的基本应用。实例2-7 解决“大数相乘”问题 源码路径 光盘\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 执行后先分别输入两个大数，例如123和456，按下【Enter】键后将输出这两个数相乘的积。执行效果如图2-9所示。图2-9 “大数相乘”问题的执行效果
试读结束[说明：试读内容隐藏了图片]