m1.cpp

来自「给定整数n」· C++ 代码 · 共 90 行

#include <stdio.h>

//给定整数n，产生所有[2n]上的匹配（matching）
//将其视为一个所有块大小均为2的集合分拆
//输出格式为 a1 a2 - b1 b2 - c1 c2 - ...
//满足a1<a2, b1<b2, ...
//且 a1 < b1 < c1 <...
//时间大约30s


//算法思想如下：
//将集合中的元素以数组a[i]来表示
//初始分拆为1234...，依次产生新的分拆
//直至找不到p使得a[2p]<a[2p+2]

//产生新的分拆方法为：
//1. 找到a[2p]<a[2p+2]
//2. 将a[2p]和它后面比它大的最小元素x互换
//3. 将a[2p]后面的元素顺序排列

//在2中有两种情况，一种是x为某个a[2q]，另一种是x为奇数位。
//注意到a[2q]递减而a[2q+1]递增，
//我们可以首先从前往后检查a[2q]，
//然后再从后往前检查a[2q+1]

//在进行排序的时候，注意到a[2p]和x交换不影响顺序，
//我们可以直接将a[2p]之后的元素交错排列即可，
//即其顺序为a[2p+1]<a[2p+3]<...<a[2n-1]<a[2n]<a[2n-2]<...<a[2p+2]

void main()
{

	int i,p,q,n,tmp;
	long int tnum;

	int a[21],b[21];
	
	n=3;

	for (i=1;i<=2*n;i++) a[i]=i;
	tnum=0;

	while (n>0) 
	{	
		
		//输出匹配
		tnum++;
		for (i=1;i<n;i++)
			printf("%d%d-",a[2*i-1],a[2*i]);
		printf("%d%d\n",a[2*n-1],a[2*n]);
		
		//查找下一个匹配
		p=n-1;
		while ((p>0) && (a[2*p]>a[2*p+2])) p--;  //查找第一个顺序的偶数位。
		
		if (p==0) 
			break;
		else
		{
			q=p+1; tmp=a[2*p];
			while ((q<n) && (a[2*q+2]>tmp)) q++;  //查找最后一个比a[2*p]大的偶数位——2q
			if (q<n)
			{
				a[2*p]=a[2*q]; a[2*q]=tmp; //交换a[2p]和a[2q]
			}
			else
			{
				while (a[2*q-1]>tmp) q--;  //查找第一个比a[2*p]大的奇数位——2q+1
				if (q==n) 
				{
					a[2*p]=a[2*n]; a[2*n]=tmp; //如果没有找到，2n就是比a[2p]大的最近的一个。
				}
				else
				{
					a[2*p]=a[2*q+1]; a[2*q+1]=tmp; //交换a[2p]和a[2q+1]
				}
			}

			//重排a[2p]之后的数字
			for (i=p+1;i<=n;i++) 
			{
				b[i-p]=a[2*i-1]; b[n-2*p+i]=a[2*(n+p+1-i)];
			}
			for (i=2*p+1;i<=2*n;i++) a[i]=b[i-2*p];

		}
	} 
	printf("%d\n",tnum);
}