程序设计算法与实践

第1章程序设计算法概述

1.1算法实现过程

1.2算法的特征及评价标准

1.3算法分析

1.4算法实践

第2章基础算法

2.1枚举法

2.1.1 生理周期(Biorhythms/1006）

2.1.2 立方体（Blocks/2363）

2.1.3 完美立方(Perfect Cubes/1543)

2.1.4千年虫病毒（Y2KAccounting Bug/2586）

2.1.5 保险箱(Safecracker/1248)

2.1.6 装盒问题(Packets/1017)

2.2递归法

2.2.1 递归函数(Function Run Fun/1579)

2.2.2 还原二叉树（Tree Recovery/2255)

2.2.3 分形(Fractal/2083)

2.2.4放苹果（1664）

2.2.5 排列问题（Orders/1731）

2.3分治法

2.3.1 谁在中间（Whos in the Middle/2388）

2.3.2排序问题（Ultra-QuickSort/2299）

2.3.3 好斗的牛(Aggressive cows/2456)

2.3.4 分馅饼（Pie/3122）

2.3.5 木杆的膨胀（Expanding Rods/1905）

2.3,6 星形还是树形(A Star not a Tree?/2420)

第3章基础数据结构

3.1堆栈

3.1.1 网站导航（Web Navigation/1028）

3.1.2 糟糕的一天（Bad Hair Day/3250）

3.1.3 铁轨问题(Rails/1363）

3.1.4 可怕的集合（Terrible Sets/2082）

3.1.5 数字密码（Code/1780）

3.2队列…

3.2.1 纸牌戏法（Card Trick/3032)

3.2.2 纸牌发牌（Card Stacking/3629）

3.2.3 打印队列（Printer Queue/3125)

3.2.4 成组队列（Team Queue/2259）

3.2.5 滑动窗口(Sliding Window/2823)

3.3 堆…

3.3.1 修理栅栏（Fence Repair/3253)

3.3.2数据流管理系统（Argus/2051）

3.3.3 黑盒问题（Black Box/1442）

3.3.4 序列问题（Sequence/2442）

3.3.5 财务补助(Moo University-Financial Aid/2010)

第4章动态规划

4.1 基础动态规划问题

4.1.1 数学三角形（The Triangle/1163/3176）

4.1.2括号序列(Brackets/2955)

4.1.3 乘法问题（Multiplication Puzzle/1651）

4.1.4 接苹果(Apple Catching/2385）

4.1.5 海明数(Hamming Problem/2545)

4.2子序列问题

4.2.1 最长有序子序列(Longest Ordered Subsequence/2533)

4.2.2 加工木棍（Wooden Sticks/1065）

4.2.3 士兵列队（Alignment/1836）

4.2.4 求最大和（Maximum sum/2479）

4.2.5 求最大矩阵和（To the Max/1050）

4.3最长公共子串问题

4.3.1 公共子序列（Common Subsequence/1458）

4.3.2 回文串（Palindrome/1159）

……

9.1.3 取木条（Pick-up sticks/2653）

9.1.4 交点(Intersection/1410）

9.1.5 相交线(Intersecting Line/1269）

多边形

9.2.1 求面积（Area/1654）

9.2.2 抬石头(Lifting the Stone/1385)

9.2.3围牧场（Cows/3348）

9.2.4 选美比赛（Beauty Contest/2187）

9.3综合问题

9.3.1 景观线（Line of Sight/2074）

9.3.2 亚特兰蒂斯（Atlantis/1151）

9.3.3突袭（Raid/3714）

9.3.4 风水(Feng Shui/3384)

参考文献

第1章

程序设计算法概述

算法是指为了求解问题而给出的指令序列，可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，输入给定的某个值或值的集合，通过计算输出指定的值或值的集合。在计算机科学中，算法通过程序来实现。程序在设计过程中，通过算法实现对问题的求解。

程序设计算法的核心是在求解问题的过程中，在有限的存储空间内运行有限的时间而得到正确的结果。同时，程序也可以作为算法的一种描述，但程序通常还需要考虑很多与方法和分析无关的细节问题，这是因为编写程序时会受计算机系统环境的限制。通常，程序的编写不可能优于算法的设计。

1.1算法实现过程

使用计算机进行程序设计算法实现的过程，需要在计算机中建立一个解决问题的模型。在这个模型中，计算机内部的数据表示需要被处理的实际对象，包括其内在的性质和关系、处理这些数据的程序、模拟对象领域中的求解过程。通过解释计算机程序的运行结果，得到实际问题的解。下面给出用程序设计算法实现的一般步骤。

1.问题分析

问题分析阶段的任务是了解题目提供的已知信息和所要解决的问题是什么，完整地理解和描述问题是解决问题的关键。要做到这一点，必须注意以下问题：在未经加工的原始表达中，是否明白所用的术语的准确定义?题目提供了哪些已知信息？还可以得到哪些潜在的信息?题目中做了哪些假定？题目要求得到什么结果?等等。针对每个具体问题，必须认真审查问题的有关描述，深入分析，以加深对问题的准确理解。

2.数学模型的建立

使用计算机解决实际问题时，必须建立合适的数学模型。因为在现实问题面前，计算机是无能为力的。对一个实际问题建立数学模型，可以考虑两个基本问题：最适合此问题的数学模型是什么?是否有已经解决的类似问题可以借鉴?

建立数学模型是最关键且较困难的一步，涉及4个世界和三级抽象。4个世界分别是现实世界（客观世界）、信息世界（概念世界）、数据世界、计算机世界。三级抽象分别是现实世界到信息世界的抽象（建立信息模型或概念模型)：信息世界到数据世界的抽象（将信息数据转换为数据模型）)：数据世界到计算机世界的抽象(在计算机中建立存储模型）。

3.算法设计

算法设计是指设计求解某一特定出形间题的一系列步骤，并且这些步骤是可以通过计算机的基本操作来实现的。算法设计要同时结合数据结构的设计，简单来说，数据结构的设计就是选取存储方式，因为不同的数据结构的设计导致算法的差异很大。算法的设计与模型的选择是密切相关的，但同一模型仍然可以有不同的算法，而且它们的有效性可能有相当大的差距。

算法设计方法也称算法设计技术，或算法设计策略，是设计算法的一般性方法，可用于解决不同计算领域的多种问题。虽然设计算法，尤其是设计出好的算法是一件非常困难的工作，但是设计算法也不是没有方法可循，人们经过几十年来的工作，总结和积累了许多行之有效的方法，了解和掌提这些方法会给我们解决问题提供一些思路。本书讨论的算法设计方法已经被证明是对算法设计非常实用的通用技术，这些算法设计方法构成了一组强有力的工具，可用于大量实际问题的求解。

4.算法表示

对于复杂的问题，确定算法后可以选择一种算法描述方法来准确表示算法。算法的描述方式有很多，如传统流程图、盒图、问题分析图（problem analysis diagram.PAD）、伪码和高级语言等。其中，高级语言是最理想的描述算法的方法，因此，本书选择C++语言来表示算法。

5.算法分析

算法分析的目的，首先是对算法的某些特定输入，估算该算法所需的内存空间和运

行时间：其次是建立衡量算法优劣的标准，用以比较同一类问题的不同算法。一般来说，一个好的算法首先应该比同类算法的时间效率高；算法的时间效率用时间复杂度来度量。

6.算法实现

算法实现是指编码，也就是平常所说的编写程序，即将算法设计“转译”成某种计算机语言的表述形式，才能够在计算机上执行。编码的目的是，使用选定的程序设计语言，把算法描述翻译成使用该语言编写的源程序（或源代码）。源程序应该正确可靠、简明清晰，而且具有较高的效率。

在把算法转换为程序的过程中，虽然现代编译器提供了代码优化功能，但是，仍然需要一些技巧，如在循环之外计算循环中的不变式、合并公共子表达式等。……

本书介绍了程序设计算法的基础知识，通过算法问题实践，讲解了程序设计常用的算法，包括题目描述、题目分析，并给出了参考代码。本书的内容一方面作为基础语言(C、C++)的后续内容以及数据结构课程的巩固和提高，另一方面，为软件工程、应用程序开发、网络信息技术、大数据和人工智能等提供算法知识基础。