Chris

快速排序的基本思想是在待排序数据中选取一个pivot数据，将剩余数据按照与pivot的比较结果分割成两份，小的放在pivot左边，大的放在pivot右边（假设是升序排序），这样pivot已经在正确的位置上了。然后对pivot的左右待排数据继续递归调用上述过程。到待排数据长度<=1的时候递归返回，当所有递归都返回，就完成了整个数据的排序。

如何分割是快速排序的关键所在。这里提三种不同的分割方式。

所谓分割就是要对所有数据的位置进行重新安排，使得所有比pivot小的数据位于pivot左侧，所有比pivot大的数据位于pivot右侧。

第一种策略采用空位vacancy的概念。用low和high标记未检测区域的边界，起初将E[low]作为pivot保存在本地变量中，这样E[low]成为一个空位，用vacancy标记。为了找到一个元素放在这个空位里（应该是小于pivot的），而且为了尽可能远地移动它（通过一次比较而将元素移动尽可能远的距离可能争取到更高的排序效率），我们从high开始向左查找第一个大于pivot的数，找到后将它移动到vacancy里，这样该处留下了一个空位标记为highVac，同时更新high=highVac，因为右侧的数据都已经检查过了，都比pivot大，在接下来的过程中不需要在移动。接下来从low处开始向右查找第一个比pivot大的元素（同样，为了将它放在刚空出来的highVac中，而且希望移动尽可能远的距离），找到后将其移动到highVac中，将新空出来的空位用lowVac标记，并且更新low=lowVac。至此，我们完成了一次迭代，更新了low和high，使得未被检测的区域变窄了，而且low左侧的数据都比pivot小，high右侧的数据都比pivot大，low处为一个空位，这和迭代开始的条件是一致的，因此迭代可以进行下去。直到某一次查找大于或小于pivot元素的过程中一直到对面的空位都没有找到，则说明所有元素的位置都已经被安排好，这时候再把保存在本地变量中的pivot放到空位里，就完成了分割。

第二种策略与第一种类似，也是从两侧向中间推进，但是没有使用空位的概念，而是采用交换的方法。将pivot放在E[low]处，从E[low+1]和E[high]分别开始向中间查找第一个大于pivot的和第一个小于pivot的数据，找到后将两者进行交换，然后继续向中间推进，直到两个方向的查找相遇。然后交换E[low]和最后一个小于pivot的数据，就完成了分割。

第三种策略是单向的策略，基本思想是时刻更新标记小于pivot的最后一个数据位置m初始为low-1。在按照下标i遍历的过程中，如果E[i]>pivot那么一切正常，m不需要更新，E[i]在m之右；如果E[i]<pivot，那么说明m需要增一，然后需要将E[i]与E[m]交换，这样就维持了m标记最后一个比pivot小的数据这样一个不变式。最后遍历完成之后将E[m]与位于队头的pivot进行交换，即完成了分割。

在CSDN算法版看到的题目，据说是MS的笔试题。

题目是这样的：

一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。

NASH说了个想法，很直观，用O(logN)找到原序列的起点，再用O(logN)找到要找的点（做一些下标控制）。应该可以，我没有实现，BAD说这叫化未知问题为已知问题，嗯，不错。

我自己写了另一个解法，单纯的二分查找，只不过判断该左转还是右转的时候需要谨慎一些，把所有情况都考虑到自然就没有问题了。

在此序列不断二分的过程中，由于原序列是一个递减序列经过旋转得到的，将它从任何位置分开，都会得到两个序列，其中一个是递减序列，另一个可以通过一个递减序列通过旋转得到。这样在不断地二分查找时，我们处理的序列子片段要么就是一个旋转后递减序列，要么就是一个纯递减序列，而无论是前者还是后者，在继续分成两个片段时，至少有一个纯递减序列（可能两个都是，如果之前的序列片段就是纯递减序列的话）。这样我们可以保证能找到一个片段是纯递减序列（if(data[i]>=data[j])），然后判断我们要找的数是否在这个片段中（这是很直观的，if(data[i]< =num&&num<=data[j])），如果在则继续在此片段中查找，否则说明在另一个序列中，则递归在其中查找。

代码如下：
Continue reading »

由于求最小哈密顿回路的问题是NP问题，随着递归的进行，时间复杂度为阶乘级（如不加标记则为指数级），故最优解法能解决的问题范围是非常有限的。前面写过的那篇解决N=16个节点的图大概需要十几秒钟。

这里给出一种近似解法，是老杨上课时候给出的。后来上网搜文献搜到了这个想法的相关paper，发现作者就是老杨，据说是他第一个提出的。

想法倒是很朴素，采用分片，将一个大图分成若干个小图，每个小图单独求最小哈密顿回路，然后将各个回路连上，这样得到的基本上不会是最优解，但是能解决问题的规模大大提高了，算是一个比较好的近似解法思路吧。

原来那篇的数据结构是邻接矩阵，这里就不能用邻接矩阵了，而只能用坐标来描述图上的点，边之间的权重直接取两点之间的距离，直接默认为完全图。

代码有两个小问题没有解决，一是没有剪枝，二是有一处内存泄露。弄得头大，暂时不搞了。

解N=40是瞬间的事，当然了相当于解N=10嘛，不剪枝也挺快的。N=50大概需要17分钟，慢的不行。

Continue reading »

第二次上课的作业之一是实现所有会的排序算法（之二是实现查找欧拉回路的算法），用了总计大概两天的时间写好了这九个排序算法。没有一个算法是一次通过的，都经过了调试，甚至冒泡，而且后来才发现我第一次写的冒泡程序竟然是错误的，囧。
这还是第一次把这些算法全部亲手实现，收获还是很大的，真的加深了理解。期待通过这门课有效地提高自己的编程能力。
废话不说，上代码。
以下算法，没给出参数的默认排序范围为data[]的第0位到第N位。有些采用分治思想的算法需要范围参数，如快排和归并。
为了优化，在递归过程中如果待排序长度较短则使用插入排序代替递归，因此插入排序函数有一个带参数版本为此所用。桶排序需要一个算法实现桶内排序，这里选择了快排，因此快排有一个带三个参数的重载版本。
另外堆排序的实现用了一个类加一个外部函数。
genData函数用于生成随机数据；
check函数用于检查数据是否有序；
exchange函数用于交换两个数据；
show函数用于打印；
digit函数返回数据的某一位（用于基数排序）；
Continue reading »

老杨留的作业，折腾几个小时加上参考别人的终于写出来了，还是很弱啊。

效率貌似还可以，强化了分支定界的条件之后计算N=20的情况只需要十几秒。

好好体会一下~

 
#include <cstdlib>
#include <iostream>
#include <stdlib.h>
#include <time.h>
 
using namespace std;
 
#define N 15
 
int curLightestWeight = 1000000;
int curDepth = 0;
int curWeight = 0;
int depth;
int curCircle[N],bestCircle[N];
bool used[N];
int p[N][N];
 
void update();
void show();
 
void genGraphic(int maxWeight)
{
	for(int i = 0;i < N;i++)
	{
		for(int j = 0;j < N;j++)
		{
			if(i == j)
				p[i][j] = 0;
			else
				p[i][j] = rand()%maxWeight + 1;
		}
	}
	for(int i = 0;i < N;i++)
	{
		for(int j = 0;j < N;j++)
		{
			cout<<p[i][j]<<"   "; 		 
		} 		 
		cout<<endl;
	}
}
 
void MHC_recursion(int curVertex)
{
	curCircle[curDepth] = curVertex;
 
	curDepth++;
	used[curVertex] = true;
 
	if(curWeight + (depth - curDepth) >= curLightestWeight)
	{
		curDepth--;
		used[curVertex] = false;
		return;
	}		
	else if(curDepth == depth)
	{
		int thisWeight = p[curVertex][0];
		curWeight += thisWeight;
		if(curWeight < curLightestWeight)
		{
			curLightestWeight = curWeight;
			update();
		}
		curDepth--;
		used[curVertex] = false;
		curWeight -= thisWeight;
		return;
	} 
	else
	{
		for(int i = 0;i < N;i++)
		{
			if(i == curVertex || used[i] == true)
				continue;
			int thisWeight = p[curVertex][i];
			curWeight += thisWeight;
			MHC_recursion(i);
			curWeight -= thisWeight; 		
		}  
	}
	used[curVertex] = false;
	curDepth--;
	return;
}
 
void update()
{
	for(int i = 0;i < N;i++)
		bestCircle[i] = curCircle[i];
}
 
void show()
{
	for(int i = 0;i < N;i++)
		cout<<bestCircle[i]<<"-->";
	cout<<bestCircle[0]<<endl;
	cout<<"The weight of the circle is "<<curLightestWeight<<"."<<endl; 
}
 
void init()
{
	curDepth = 0;
	curWeight = 0;
	curLightestWeight = 1000000;
	depth = N;
}
 
int main(int argc, char *argv[])
{
	genGraphic(9);
	init();
	MHC_recursion(0);
	show();
	system("PAUSE");
	return EXIT_SUCCESS;
}

这三个算法每本算法书都要讲到，这次看《算法之道》又复习了一遍，觉得有些新的领悟，写个模板记录一下。

Kruskal和Prim算法解决的问题都是最小生成树问题，即对于一个图G<V,E>，找到它的最小生成树T<V,E’>，其中E’包含于E，使得所有V都连通。Dijkstra算法解决的是单源多点最短路径问题，即对于一个图G<V,E>和一个起点S，为图中的其它所有节点找到距离S最近的路径。

所说的图都是加权图，如果是均权图或者权重为一的图，则不存在最小生成树这一概念，因为任意一棵生成树的大小都是一致的。所谓的单源多点最短路径也可以用BFS进行解答。

这三个算法的本质都是贪心，三个问题都具有贪婪选择性质使得使用贪心算法可以得到最优解。

先来看Kruskal算法。先描述算法再证明最优性。

建立两个边集，初始时Q为所有边的集合，A为空集，算法终结时A为所求的最小生成树。每次删掉Q中权重最小的边并对其进行考察，如果它加入A中不会形成环路，则将其加入A，当A中边数打到|V|-1时，求解完毕。

Q=E
A=NULL
while(n<|V|-1)
      e=min(Q)
      Q=Q-e
      if(e加入A中不会构成回路)
            A=A AND e

容易知道一棵最小生成树所包含边的条数为|V|-1。所以求解一棵最小生成树的过程就是选择|V|-1条边的过程。问题的开始相当于所有的节点都是分离的，而问题的结尾要求所有的节点连通。每一条边的加入必须要使图的连通度加一（否则构成环路，则产生冗余的可删除的边）。将问题抽象为：对于一个森林和一些潜在的边，要求加入一条权重最小边使得森林的连通度加一，即森林中树的个数减少一。这样问题就具备了贪婪选择性质：每次应该选择不构成回路的权重最小的边，并且次贪婪选择只引出一个子问题。另外该问题又具备最优子结构，最优解一定包含子问题的最优解，否则可以用子问题的最优解替换当前子问题的解从而得到整个问题的更优解而导出矛盾。因此用贪心策略的Kruskal算法解决最小生成树问题是正确的。

再看Prim算法。Kruskal算法以边的权值作为贪心考虑，每次加入一条能起到作用的权重最小的边，从而得到最优解，是一种很直观的思路。另一种思路，将问题初始阶段看做所有节点都独立，然后构建一个连通的集合，每次按照贪婪的策略向该集合内加入一个点，最终使得所有点都在集合内，便完成了最小生成树的构建。那么应该给每个点赋一个什么样的值来进行贪婪选择呢？应该赋予每个点距离现有集合的距离（与集合里距离最短的点之间的距离）。

伪代码如下：

Q=V
A=NULL
while(|A|<|V|-1)
      v=Q中到A中距离最小的点
      A=A AND v
      由于v的加入，更新Q中剩余点到A的距离

Prim算法在求解的过程中一直维持中途解是一棵树，而Kruskal的中途解则是一个森林。将问题抽象为给定一棵树和一组散节点，通过将散节点中的一个加入树中从而使得树的节点数增一，要求增加的权重最小。这样问题就具有了最优子结构和贪婪选择性质。每步求解后的子问题的最优解一定包含在整个问题的最优解当中，同样也是反证法可以证明；每次的贪婪选择都只会留下一个子问题。这样就证明了Prim算法的正确性。

Dijkstra算法和Prim算法如出一辙。也是每次向一棵树（或者说子图）按照贪心的策略加入一个节点，加入后对会被新加入节点所影响的未加入节点信息进行更新，再重复上述过程直到所有节点都加入为止。区别在于贪心所考虑的指标不同。最小生成树要求的是连通，因此应该将与已构建的部分生成树中的任意节点的距离中最小的一条距离作为贪心考虑，而单源多点最短路径考虑的是所有节点与一个特定原点的距离，因此在进行贪婪选择的时候也应该选择所有未加入的点中与该原点之间距离最短的节点，加入后要更新的信息也是这个，更新方法是考察原有距离和经由刚加入的节点到达原点的距离哪个更小。

伪代码如下：

Q=V
A=NULL
while(|A|<|V|-1)
      v=Q中到s距离最小的点
      A=A AND v
      由于v的加入，更新Q中剩余点到A的距离
      for each x in Q
            dist[x]=min(dist[x],dist[v]+e(u,v))

《算法之道》提到，问题的基本求解理念有三种——分治与递归、动态规划、贪心。

分治与递归所能处理的问题最多，对问题的性质没有要求（不过可能会出现很复杂的分治情况），所需要求解的子问题数最多，而且如果子问题有重复，则每一次都要重复求解；

动态规划叫做Dynamic Programming，这里的Programming的意思不是编程而是查表，动态规划不如翻译成动态查表更容易理解些，规划这个词太空了。动态规划的思想就是发现在分治递归求解中有很多子问题都被求解了多次从而造成了复杂度的上升，如果只求解一次然后存储起来再备后来查表，就可以解决这个问题。所以将递归的自顶向下改为自底向上就得到了动态规划的思路，如果仍然使用自顶向下的思路但是每次求解一个子问题的时候查看是否已经求解过（自然也需要将子问题的解存储起来）则得到了“存储化递归”的解法，复杂度与动态规划只有常数差别。

动态规划要处理的问题要求问题具有最优子结构（即最优解包含子问题的最优解），是一种自底向上的求解思路，与递归正好相反，每次求解到一个阶段时，该阶段求解所依赖的子问题已经完全求解完毕，因此每一步的求解都是在直到全部所需信息的情况下进行的，因此可以得到全局最优解。

贪心算法如果想要得到最优解，需要对问题性质有更严格的要求，除了要有最优子结构外，还要求问题具有贪婪选择性质。具体来说就是：贪心是一种策略，即每一步都要选择当前看来最好的，做完此选择后便将问题化为一个（仅仅一个）子问题，这是一个顺序的求解过程，每一步都是单独考虑，只考虑局部最优，因为并没有完成对之后子问题的求解，所以贪心算法不能完成对整个解空间的搜索，因此通常不能得到最优解。除非问题具有贪婪选择性质。所谓贪婪选择性质就是问题经过一次贪婪选择后只能形成一个子问题，这样求解空间实际上就是一个线性的空间，贪心算法可以得到最优解。

也许有些问题初看起来并不具备该性质而需要一定的转化，这方面一个经典的例子是教室排课问题：给出N门课的开始时间和结束时间，如何排课才能让尽可能多的课在一个教室里面上？贪心策略是每次选择可以选择的课（即开始时间晚于当前已排课程中结束最晚的课的结束时间）里结束时间最早的课。

1.任取黑白混杂的棋子21个,排成3行7列,证明无论怎样排列,都可以找到一个小长方形矩阵，使四个角上的棋子的颜色相同。

三行七列，每一列至少有两个颜色相同，六种情况：12同白，12同黑，13同白，13同黑，23同白，23同黑。六种情况、七列，必然有至少两列情况相同，故得到解，鸽笼原理，记得小时候书上管这叫抽屉原理来着。

2.从2n个连续整数中任取n+1个，证明：这n+1个数中必有两个互质。

按顺序两两分组，分成n组，每组中的k,k+1必互质，再次利用鸽笼原理，必有一组中的两个数同时被选中，两数互质，证毕。

3.8*8的棋盘，可以用32个多米诺骨牌（1*2的矩形）恰好覆盖。若去掉左上角和右下角的格子，证明用31块骨牌不能覆盖余下的棋盘。

将棋盘的行用i=1…8标记，列用j=1…8标记，则棋盘上的格子可按i+j是奇数还是偶数分成两类，各32个，且相间出现，即每个第一类格子的四周都是第二类格子，每个第二类格子的四周都是第一类格子。左上角和右下角的格子是同类格子，因此去掉后两类格子分别剩下30个和32个，而一个骨牌只能覆盖一块1*2区域，且该区域内必有两类格子各一个，故不能用31个骨牌将余下的棋盘恰好覆盖。

4.“门票问题”——2n个人排队购票入场，其中n个人手拿50元钞票，n个人手拿100元钞票，门票价格为50元，售票处没有任何零钱，问有多少种排队方式能顺利让2n个人都购票入场？n个0和n个1共2n个数进行排列，要求从头遍历到任何位置时0的个数都不小于1个个数，问有多少种排列方式？

答案为卡特兰数C(2n,n)-C(2n,n-1)=C(2n,n)/(n+1)，证明如下：不考虑是否符合题目要求，n个0和n个1的排列方式为C(2n,n)，再考虑不符合条件的排列方式有多少，减去即可。考虑每种不符合条件的排列，必存在一个奇数位置2m+1，在该处之前出现了m+1个1和m个0，该位置之后的2(n-m)-1个数中出现n-m个0和n-m-1个1，将后面这部分的0和1互换（0变成1，1变成0），这样每个不符合条件的序列都对应一个由n+1个1和n-1个0组成的2n长的序列；反过来，任何一个由n+1个1和n-1个0组成的2n长的序列，都能找到一个奇数位置2m+1使得从头至此有m+1个1和m个0，将后面的部分0和1互换，这样每个由n+1个1和n-1个0组成的2n长序列都对应一个不符合条件的序列。因此证明了不符合条件的序列个数为C(2n,n-1)，故符合条件的序列个数为C(2n,n)-C(2n,n-1) = C(2n,n)/(n+1)。

5.“方程的解”问题——已知一个方程x1+x2+…+xn=P，其中x1>=a1,x2>=a2,…xn>=an，并且(a1+a2+…+an)<=P。问共有多少组解？

首先很容易分析出，问题等同于找到x1+x2+…+xn=P’，其中P’=P-(a1+a2+…+an)，x1>=0,x2>=0,…xn>=0。

这个问题有个异常强大的思路：写一个由P’个1和n-1个0组成的序列，令xi等于第i-1个0和第i个0之间1的个数，且x0等于第一个0之前1的个数，xn等于第n-1个0后面的1个个数，这样每个P’个1和n-1个0组成的序列和每个方程的解就是一一对应的了。所以解的组数是C(P’+n-1,n-1)。强大吧？

Description

Input

Output

Sample Input

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

Sample Output

15

Source

#include <iostream>
 
using namespace std;
 
int numbers[105][105],dp[105],n,temp[105];
 
int main()
{
	cin>>n;
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= n;j++)
			cin>>numbers[i][j];
	int Max = 0;
	for (int i = 1;i <= n;i++)	//start from line i
	{
		memset(temp,0,sizeof(temp));
		for (int j = i;j <= n;j++)	//end at line j
		{
			for (int k = 1;k <= n;k++)
			{
				temp[k] += numbers[j][k];
 
				if (temp[k] + dp[k-1] > 0)
					dp[k] = temp[k] + dp[k-1];
				else
					dp[k] = 0;
 
				if (Max < dp[k])
					Max = dp[k];
			}
		}
	}
	cout<<Max<<endl;
}

Description

‘Oh no, they’ve done it again’, cries the chief designer at the Waferland chip factory. Once more the routing designers have screwed up completely, making the signals on the chip connecting the ports of two functional blocks cross each other all over the place. At this late stage of the process, it is too expensive to redo the routing. Instead, the engineers have to bridge the signals, using the third dimension, so that no two signals cross. However, bridging is a complicated operation, and thus it is desirable to bridge as few signals as possible. The call for a computer program that finds the maximum number of signals which may be connected on the silicon surface without crossing each other, is imminent. Bearing in mind that there may be thousands of signal ports at the boundary of a functional block, the problem asks quite a lot of the programmer. Are you up to the task?

A typical situation is schematically depicted in figure 1. The ports of the two functional blocks are numbered from 1 to p, from top to bottom. The signal mapping is described by a permutation of the numbers 1 to p in the form of a list of p unique numbers in the range 1 to p, in which the i:th number specifies which port on the right side should be connected to the i:th port on the left side.Two signals cross if and only if the straight lines connecting the two ports of each pair do.

Input

Output

Continue reading »