算法描述

尝试使用C/C++ 使用描述（实现）一些算法，希望在此交流互相学习。
若你发现其中存在问题，可以随时联系本人。
e-mail：[email protected]

欢迎交流，谢谢！

####### 19.
/**
** 源文件： project_euler.h project_euler.cpp
** 功能说明：
	projecteuler题目的解决方案，详细题目参加https://projecteuler.net/ 网站。
	
	===
*/

####### 18.
/**
** 源文件： test_special_sort.cpp
** 功能说明：
	引用自：http://groups.google.com/group/pongba/t/54146dfb71a67827
	特殊排序题目：
	姓名集合names，名次集合ranks，按照名次顺序输出她们的名字，要求O(N)时间。解法如下：
	
	解法一，不改变原来集合顺序，O(N)时间， O(N)空间。
	描述： ranks数组下标相当于姓名索引，新空间ranks2以名次顺序记录着姓名索引。ranks2数值下标为名次，其值为姓名索引值。
		for (i = 0; i < N; ++i)
			ranks2[ranks[i]] = i;
		for (i = 0; i < N; ++i)
			print(names[ranks2[i]]);
		
	解法二，在位重新排序，改变原来集合顺序，O(N)时间， O(1)空间。
	描述：每一次swap {names, ranks} 确定一个的位置，最多总共N次swap能全部定位。
		for (i = 0; i < N; ++i)
			while (i != ranks[i])
				swap(names[i], names[ranks[i]]);
				swap(ranks[i], ranks[ranks[i]]);
		for (i = 0; i < N; ++i)
			print(names[i]);
	===
*/
	
####### 17.
/**
** 源文件： huffman_use_cace.cpp
** 功能介绍：
	来自Google groups论坛讨论，转：http://groups.google.com/group/pongba/t/bf95272e7543d0aa
	把一块长度为L的木棒切成N块，每段的大小必须为a1,a2,…,an，每一次切木棒的代价为当前木棒的长度，
	完成切割任务的最小代价？
	Input
	首先输入T，有T个测试用例
	每个测试用例输入两行
	第一行整数L和N。接下来一行是N个数表示每一段的木棒长度。
	Output
	求完成任务的最小代价
	Sample Input
	2
	10 4
	1 2 3 4
	306 8
	120 37 42 42 32 2 7 24
	Sample Output
	19
	785
	
	反过来想每次合并是两段长度之和。于是就变成了Huffman问题了。
	解释一下样例一，10分割为4和6，代价为10，6分割为3和3，代价为6，3分割为1和2，代价为3。
	总代价为10+6+3，即Huffman树中非叶节点的 权值和。
*/

####### 16.

/**
** 源文件： huffman_code.cpp. huffman_code.h
** 功能说明：
** 测试程序，霍夫曼编码的简单应用及其演示。如程序运行霍夫曼自动编码功能效果如下：
请输入你要进行编码的字符串：abbcccddddeeeeeffffff
          字符  权值  编码      编码长度
           a      1   1110      4
           b      2   1111      4
           c      3    110      3
           d      4     00      2
           e      5     01      2
           f      6     10      2
** wiki介绍：http://zh.wikipedia.org/zh/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
** 具体实现，详见源码与注释说明。

** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 15.
/**
** 源文件： evaluate_ expr.cpp
** 功能说明：
** 测试程序，表达式求值解法，栈数据结构经典应用，需要预先定义运算符op的优先级。
	1. 中缀表达式到后缀表达式的转换；
	2. 后缀表达式求值。
转：

中缀表达式到后缀表达式的转换
　　要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。
  优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。 如果所有操作符优先级一样，
  那么求值顺序就取决于它们的结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。
  转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号：
	1. 初始化一个空堆栈，将结果字符串变量置空。
	2. 从左到右读入中缀表达式，每次一个字符。
	3. 如果字符是操作数，将它添加到结果字符串。
	4. 如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis）、优先级较低的操作符或者同一优先级的右结合符号。
	把这个操作符压入（push）堆栈。
	5. 如果字符是个开括号，把它压入堆栈。
	6. 如果字符是个闭括号（closing parenthesis），在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。
	7. 如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。

后缀表达式求值
对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中，不需要括号，而且操作符的优先级也不再起作用了。
您可以用如下算法对后缀表达式求值：
	1. 初始化一个空堆栈
	2. 从左到右读入后缀表达式
	3. 如果字符是一个操作数，把它压入堆栈。
	4. 如果字符是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入堆栈。如果您不能够弹出两个操作数，后缀表达式的语法就不正确。
	5. 到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空。


** 作者：junkun huang
** 创建日期：2008-09 前 /
*/

####### 14.
/**
** 源文件： queen_problem.cpp, queen_problem.h
** 功能说明：
** N皇后问题的解法。应用回溯法求解问题的所有解法。
回溯法百科
回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，
发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，
而满足回溯条件的某个状态的点称为“回溯点”。

A. solve_problem程序结构说明：
	1.	先将第一个皇后Q1固定在第一列第一行的位置pos[1][1]。
	2.	跳至下一列，寻找合理位置摆放皇后，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
	2.1	若找到合理位置，则记录“回溯点”于栈容器，继续寻找下一列摆放下一皇后的合理位置，
	直至最后一列为止，这时就找到了一组满足条件的皇后排列，然后进行步骤2.2。
	2.2	若找不到合理位置，则从栈容器出栈“回溯点”，再寻找下一合理位置，再进行步骤2。
	直至回溯到第一列的位置，然后开始步骤3。
	3.	继续将Q1固定在下一位置pos[x+1][1]，继续开始步骤2，循环直至Q1固定在pos[n+1][1]。

B. solve_problem2程序结构区别于solve_problem，依次将第一列元素pos[x][1] （x >= n ）作为栈底，进行类似A的递归操作。

** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 13.
/**
** 源文件： find_a_fake_coin.cpp
** 功能说明：
** 测试程序，假币问题：有若干金币【3-1000】，存有一假币，且不知假币较轻或较重，用一天枰找出其中的假币且知其轻重，
	要求比较次数越少越好。
** 以下程序以分治法，递归的形式求解包括，二分法，三分法和四分法。程序逻辑有一定相似性，但效率不一。整体上效率：
** 三分法 >= 四分法 >= 二分法
** 具体实现，详见源码与注释说明。

** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 12.
/**
** 源文件： find_a_fake_coin_form_12.cpp
** 功能说明：
** 测试程序，假币问题：12枚金币中存有一假币，且不知假币较轻或较重，给一天枰限称3次找出其中的假币并知其轻重。
    程序罗列出所有不同的解法，共2*12种。

** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 11.
/**
** 源文件： josephus_problem.cpp
** 功能说明：
** 测试程序，模拟约瑟夫问题的演示。以下采用两种数据结构实现：
	1. 数组；2. 循环链表。
	整体上，循环链表要优于数组，但数组的实现可能较易于理解与编码。

** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 10.
/**
** 源文件： gauss_elimination.cpp
** 功能说明：
** 测试程序，用高斯消去法求解方程组，详见《算法分析与设计》6.2高斯消去法。
** 用到方程组的初等变换：
	1. 交换方程组中两个方程的位置；
	2. 把一个方程替换为它的非零倍；
	3. 把一个方程替换为它和另一个方程倍数之间的和或差。
** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 9.
/**
** 源文件： knapsack _test.cpp
** 功能说明：
** 测试程序，背包问题与记忆功能。算法详细介绍详见《算法分析与设计》8.4背包问题与记忆功能。
** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 8.
/**
** 源文件： horner_rule.cpp
** 功能说明：
** 测试程序，霍纳法则用于计算多项式值的一种古老的算法，但却十分优雅和高效。
** 霍纳法则还有一些有用的副产品，例如有多项式P(x)，在计算P(a)的值过程产生的中间数字，
	可组织作为P(X)除以X-a商与余数。详见《算法分析与设计》6.5.1霍纳法则。
** 关于霍纳法则，详见http://baike.baidu.com/view/3060869.htm
** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 7.
/**
** 源文件： binomial_coefficient.cpp
** 功能说明：
** 测试程序，计算二项式系数，一个动态规划解法应用的典型例子，简单易理解。
** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 6.
/**
** 源文件： greatest_common_divisor.cpp
** 功能说明：
** 测试程序，计算两个数的最小公约数，不同解法：
	a. 欧几里得算法 gcd1.
	b. 计算gcd(m, n)的连续整数检测算法gcd2.
	c. 中学里的计算方法gcd3, 相对最复杂的办法,但是有效的.
		1 找到m的所有质数prime1；
		2 找到n的所有质数prime2；
		3 从prime1和prime2中找出所有的公因数com_prime。
		注意：如果p是其中一个公因数，而且在prime1和prime2中分别出现Pm，Pn次
		那么应该将p重复min{Pm, Pn}次；
		4 将com_prime的所有质因数相乘，结果即m, n最大公约数。
		（gcd3解法O_o 够折腾的求解过程吧。）

** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 5.
/**
** 源文件： convex_hull.h, convex_hull.cpp
** 功能：凸包问题的解决方案, 蛮力法与分治法.
** 蛮力法使用到几何知识:
 P1，P2{(x1, y1), (x2, y2)} => ax + by = c
 => {a = y2-y1, b = x1 - x2, c = x1y2 - y1x2}
 使用公式ax + by = c可判断点P3(x3, y3)落在{(x1, y1), (x2, y2)}哪边.
蛮力解法步骤：
1. 循环遍历所有的点，找出所有像P1，P2的点，需满足条件：
 其他所有的点均分布在直线P1P2同一边，借助以上几何知识。
2. 找出了所有这样的点，那么就完成凸包问题。

蛮力解决方案时间复杂度O(n^3).

** 分治法使用到几何知识:
 {(x1, y1), (x2, y2), (x3, y3)} P1, P2, P3.面积S(P1P2P3)为以下行列式绝对值的一半，
 |x1 y1 1|
 |x2 y2 1| = x1y2 + x3y1 + x2y3 - x3y2 - x2y1 - x1y3
 |x3 y3 1|
 P3位于直线P1P2的左侧时，该表达式为正值。
 P3位于直线P1P2的右侧时，该表达式为负值。
 该绝对值越大，即P3就与直线P1P2距离越大。
分治解法步骤：
1. 按照X轴（或Y轴）排序点集合S0，得到最小大值P1，Pn，并划分上包，下包不同点集合。
2. 以上包为例，根据以上几何知识，找出上包顶点Pmax即距离P1Pn最远的点，找不到即结束。
3. 继续以P1Pmax和PmaxPn构造上包，递归下去直至找不到上包顶点。得到点集合S1.
4. 下包操作同。得到点集合S2.
5. 合并集合S1, S2, 得到S3即凸包结果.

分治法解决方案时间复杂度O(n^2).
btw 详细的算法可以参见<算法分析与设计> 3.蛮力法3.3.2凸包问题 & 4.分治法4.6.2凸包问题.
** 算法实现详见以上源文件代码.
** 凸包问题描述:
	定理:任意包含n>2个点（不共线）的集合S的凸包是以S中的某些点为顶点的凸多边形。
	凸包问题是为一个n个点的集合构造凸包的问题。
	极点：对于任何一集合中的点为端点的线段来说，它们不是这种线段的中点。
** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 4.
/**
** 源文件： min_spanning_tree.cpp
** 功能说明：
** 测试程序，最小生成树问题CMST解决方案Prim算法与Kruskal算法。
** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 3.
/**
** 源文件： nearest_neighbor_search.cpp
** 功能说明：
** 测试程序，最近点对问题解决方案，蛮力法与分治法。详见以下代码。
** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 2.
/**
** 源文件： shortest_path.cpp
** 功能说明：
** 测试程序，最短路径问题解决方案，Floyd算法与Dijkstra算法。详见以下代码。
** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

####### 1.
/**
** 源文件： random_list_node.h, random_list_node_test.cpp
** 功能：拷贝“随机链表”，即节点带有一个指针可能指向链表随机另一个节点的链表。
** 一般的简单蛮力算法，可完成该功能，但时间复杂度为 O(n*m)。而以下算法较高效，相比时间复杂度为O(m).
** 具体操作，需要遍历源链表三遍。包括拷贝链表+复制随机指针+回复源链表NEXT指针。
** 作者：junkun huang
** 日期：2011-06-10 /
*/

####### 0.
/**
** 源文件： hanoi_tower_test.cpp
** 功能说明：
** 测试程序，汉若塔的计算（搬运次数）与演示搬运过程。
** 作者：junkun huang
** 创建日期：2008-11 前 /
*/

** 作者：junkun huang  e-mail：[email protected] **