说明.txt

常用算法与数据结构原代码

迭代法：
用于求方程或方程组近似根的一种常用算法设计方法。

穷举搜索法：
对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。
例：将A,B,C,D,E,F这6个变量排成三角形，这6个变量分别取[1，6]上的整数，且均不相同。求使三角形三条边上的变量之和相等的全部解。
（即A+B+C=C+D+E=E+F+A。）
解：list.cpp。

递推法：
利用递推关系求问题解的一种方法，即得到问题规模为i-1的解后，由问题的递推性质，能从以求得的规模为1，2，...，i-1的一系列解，构造出问题规模为i的解
例：求出2!,3!,...,n!,设n》2且n《50。
解：factorial.cpp。

递归：
在复杂算法的描述中被经常采用，能采用递归描述的算法中通常有这样的特征：
为求解规模为N的问题，设法将它分解为一些规模较小的问题，并且这些规模较小的问题也能采用同样的分解和综合方法。特别的，当规模N=1时，能直接得到解。
例1：找出从自然数1,2,...,n中任取r个数的所有组合。
解：Combo.cpp。

例2：背包问题。有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，是选中物品的总重量不超过指定的限制重量，但选中物品的价值之和为最大。
解：bag.cpp。

例3：汉诺塔问题：hanoi.cpp

回溯法：
例1：在任意给定的字符表上，生成一个由该字符表上的字符组成，含n个字符的序列，但要求生成的序列中是没有两个相邻子序列是相同的。
解：string.cpp。

例2：求和等于n的所有不增的正整数和式分解式。
解：递归：dissolve1.cpp，
    非递归：dissolve2.cpp。

例3：求出在一个n*n的棋盘上，放置n个不能互相捕捉的国际象棋皇后的所有布局解：非递归：queen.cpp，
    递归：requeen.cpp。

例4：函数divisor()设有四个参数：正整数n,m,正整数数表d和正整数dn。其作用     是将n分解成不多于m个数字的数字和。其中数字选自数表d,数表d共有dn个     数字。
解：divisor.cpp。

例5：列举从整数1到n中任取r个整数的所有组合。设求得组合中的各数分别存储     于数组C的C0,C1,C2,...Cn-1中，并假定C0<C1<C2<...<Cn-1,
     则有性质Ci《n-r+i+1(0《i<r)。
解：enumall.cpp。

贪婪法：
例1：装箱问题，设有编号为0,1,...,n-1的n种商品，体积分别为v0,v1,...,vn-1
将这n种物品装到容量都为V的若干箱子里。约定这n种商品的体积均不超过V,要求使装尽这n种物品的箱子数要少。
解：box.cpp。

例2：马的遍历问题。在8*8方格的棋盘上，从任意指定的方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路经。
解：chess.cpp。

分治法：
例1：为参加网球比赛的选手安排比赛日程。设有n(=2k)位选手参加网球循环赛，循环赛共进行n-1天，每位选手每天赛一场，不轮空。
解：calendar.cpp。

动态规划法：
例1：两位水平相当的棋手A和B比试，谁先赢n盘就获胜。在A再赢i盘获胜,B再赢j盘获胜的条件下，求A胜的概率。
解：awin.cpp。

例2：求最长公共字符子序列。
解：计算两个序列最长公共子序列的长度：get_len();
    构造最长公共子序列：build_s()。