dicorder.cpp

n个元素{1,2,…,n}有n!个不同的排列。将这n!个排列按字典序排列

#include <fstream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <iostream>
#include "time.h"
#include "windows.h"
using namespace std;
int minlast,maxlast;
#ifndef BIG_INT
#define BIG_INT
#include "math.h"
#include <string>
#pragma warning(disable:4035)

typedef unsigned long DWORD;
typedef unsigned int UINT;
typedef unsigned char BYTE;
const DefaultLen = 1;
const MaxLen = 0x0100000;


class CBigInt
{
public:
	//构造及析构函数
	CBigInt();
	CBigInt(DWORD dwValue);
	CBigInt(char* pszVal);
	CBigInt(const CBigInt& x);	
	/*virtual*/ ~CBigInt();
public:
	//以下定义的是运算
	//重载的赋值运算符
	CBigInt& operator = (const CBigInt& x);
	CBigInt& operator = (char* pszVal);
	CBigInt& operator = (DWORD dwValue);

	//重载的加法运算符
	CBigInt& operator += (CBigInt& x);
	CBigInt& operator += (DWORD dwValue);	
	CBigInt  operator + (CBigInt& x);
	CBigInt  operator + (DWORD dwValue);
	CBigInt  operator ++();			//++a
	CBigInt  operator ++(int);		//a++
	
	//重载的减法运算符,因为是无符号数，所以结果为大数减小数得到的差
	CBigInt& operator -= (CBigInt& x);
	CBigInt& operator -= (DWORD dwValue);
	CBigInt operator - (CBigInt& x);
	CBigInt operator - (DWORD dwValue);

	CBigInt&  operator --();			//--a
	CBigInt  operator --(int);		//a--

	//重载的乘法运算符
	CBigInt& operator *= (DWORD dwValue);
	CBigInt& operator *= (CBigInt& x);
	CBigInt  operator * (DWORD dwValue);
	CBigInt  operator * (CBigInt& x);

	//重载的除法运算符
	DWORD operator /= (DWORD dwValue); //返回余数
	CBigInt operator /= (CBigInt& x);//返回余数
	CBigInt operator / (DWORD dwValue); //返回商
	CBigInt operator / (CBigInt& x);//返回商

	CBigInt operator % (CBigInt& x);
	DWORD operator % (DWORD dwValue);

	//重载的比较运算符
	bool operator == (const CBigInt& x);
	bool operator == (DWORD dwValue);
	bool operator != (const CBigInt& x);
	bool operator != (DWORD dwValue);
	bool operator > (const CBigInt& x);
	bool operator > (DWORD dwValue);
	bool operator >= (const CBigInt& x);
	bool operator >= (DWORD dwValue);
	bool operator < (const CBigInt& x);
	bool operator < (DWORD dwValue);
	bool operator <= (CBigInt& x);
	bool operator <= (DWORD dwValue);


	//乘2运算，即 	//  a =  a * 2^dwTimes; 相当于左移一位二进制，低位补0
	CBigInt& Double(DWORD dwTimes = 1);

	//除2运算;　相当于右移一位二进制，高位边补0,低位舍弃
	CBigInt& Half(DWORD dwTimes = 1);
public:
	//以下定义的是常用的操作
	//重新分配内存空间,用于增加数据长度，n为新长度
	void Expand(DWORD n);

	//压缩数据，以节省空间。指去掉高位多余的0。
	void Compress();	

	//转换在十六进制数字符串
	void ToHexStr(std::string& s);
	std::string ToHexStr();
	
	//转换成十进制数字符串
	void ToDecStr(std::string& s);
	std::string ToDecStr();
	unsigned long size(){return (this->ToDecStr()).size();}
protected:
	//辅助函数
	inline DWORD LeastOver(DWORD n) ;//查找一个比n大，且为2^x次方的数

protected:
	DWORD *pValue;		//指向一个DWORD数组，用于存放数值
	DWORD len;			//DWORD数组的长度
	DWORD last;			//数组中的有效长度
};

const My_ErrorNo_OverFlow = 0;
const My_ErrorNo_ZeroByDiv = 1;
class CMyException  
{
public:
	CMyException(char* msg, UINT uErrorNo);
	/*virtual*/ ~CMyException();
	char* m_szMsg;
	UINT  m_uErrorNo;
protected:
	CMyException(){}
};

void MemCpy(DWORD* dst, DWORD* src, DWORD n)
{
	__asm
	{
		mov ecx, n;
		jecxz to_end;	

		//保存方向标志
		pushf;	
		
		mov edi,dst;
		mov esi, src;
		cmp edi, esi;
		jbe to_up;	//dst <= src;
		
		mov eax, ecx;
		shl eax, 2;
		add eax, esi;
		cmp edi, eax;
		jae to_up;	//dst >= src+4n
		
		mov eax, ecx;
		dec eax;
		shl eax, 2;
		add edi, eax;
		add esi, eax;
		std;
		jmp to_mov;
to_up:
		cld;
to_mov:
		rep movsd;
		popf;
to_end:
	}
}

CBigInt::CBigInt()
{
	pValue = new DWORD[len = DefaultLen];
	*pValue = 0;
	last = 1;
}

CBigInt::~CBigInt()
{
	delete [] pValue;
}

CBigInt::CBigInt(const CBigInt &x)
{
	pValue = new DWORD[	len = x.len];
	memset(&pValue[x.last],0,(len-x.last)*4);
	MemCpy(pValue, x.pValue, last = x.last);
}

CBigInt::CBigInt(DWORD dwValue)
{
	pValue = new DWORD[	len = DefaultLen];		
	*pValue = dwValue;
	last = 1;
}

CBigInt::CBigInt(char* pszVal)
{
	len = DefaultLen;
	pValue = new DWORD[len];
	operator = (pszVal);	
}

void CBigInt::Expand(DWORD n)
{
	if (n > MaxLen)
	{
		CMyException* exception = new 
CMyException("超过规定能处理的最大整数", My_ErrorNo_OverFlow);
		throw exception;
	}
	if (n > len)
	{
		DWORD* pTemp = new DWORD [len = n];
		memset(&pTemp[last], 0, (n-last)*4);
        len = n;
		MemCpy(pTemp, pValue, last);
		delete [] pValue;
		pValue = pTemp;
	}
}

CBigInt& CBigInt::operator = (const CBigInt& x)
{
	if (this != &x)
	{
		if (len < x.last)
		{
			Expand(LeastOver(x.last));
		}
		MemCpy(pValue, x.pValue, last = x.last);
	}
	return *this;
}


CBigInt& CBigInt::operator = (DWORD dwValue)
{	
	*pValue = dwValue;
	last = 1;	
	return *this;
}

CBigInt& CBigInt::operator *= (DWORD dwValue)
{	
	if (dwValue == 0)
	{
		*pValue = 0;
		last = 1;	
	}
	else if (dwValue != 1)
	{
		DWORD times;
		__asm
		{
			bsr ebx, dwValue;
			bsf ecx, dwValue;
			cmp ebx, ecx;
			jne M0;				//如果是2的n次方，则使用移位的乘法
			mov times, ebx;
		}
		return Double(times);
		
M0:		
		DWORD dwFull;	
		__asm 
		{
			mov ebx, this;
			mov esi, [ebx]this.pValue;
			mov ecx, [ebx]this.last;
			mov ebx, dwValue;		//乘数
			xor edi, edi;			//作临时存贮器,保存高位
L1:		
			mov eax, [esi];
			mul ebx;
			add eax, edi;
			mov [esi], eax;
			adc edx, 0;
			mov edi, edx;
			add esi, 4;
			loop L1;
			
			cmp edi, 0;
			je L2;
			mov dwFull, edi;
		}
		if (last == len)
		{
			Expand(LeastOver(last+1));			
		}
		pValue[last++] = dwFull;
	}
L2:
	return *this;
}


CBigInt& CBigInt::operator *= (CBigInt& x)
{
	CBigInt a(*this);   
	CBigInt result;	
	a.Expand(LeastOver(x.last + last));
	result.Expand(LeastOver(x.last + last));  
//不用this保存结果是因为考虑到x可能等于*this
	for (DWORD i=0; i<x.last; i++)
	{		
		result.operator += (a * x.pValue[i]);
		a.Double(16);
		a.Double(16);
	}	
	return *this = result;
}

CBigInt CBigInt::operator * (CBigInt& x)  
{
	CBigInt a(*this);
	return a *= x;
}

CBigInt CBigInt::operator * (DWORD dwValue) 
{
	CBigInt a(*this);
	return a *= dwValue;
}

CBigInt& CBigInt::operator += (DWORD dwValue)
{
	__asm
	{		
		mov ebx, this;
		mov edi, [ebx]this.pValue;
		mov ecx, [ebx]this.last;		
		
		mov eax, dwValue;
		add [edi], eax;
		jnc L3;		
		
		mov edx, 1;
		jmp L2;
L1:  		
		add dword ptr[edi][edx*4], 1;
		jnc L3;
		inc edx;
L2:		
		loop L1;
	}
	if (last == len)
	{
		Expand(LeastOver(len+1));			
	}
	pValue[last++] = 1;		
L3:
	return *this;
}

CBigInt& CBigInt::operator += (CBigInt& x)
{	
	Expand(x.len);
	if(last<x.last)
		last=x.last;
	__asm
	{
		mov ebx, this;
		mov edi, [ebx]this.pValue;
		mov edx, x;
		mov esi, [edx]x.pValue;
		mov ecx, [edx]x.last;	
		xor edx, edx;		
		clc;
L1:	
		mov eax, [esi][edx*4];
		adc [edi][edx*4], eax;
		inc edx;
		loop L1;		
		jnc L4;
		
		mov ecx, [ebx]this.last;		//如果this的有效位更长，则加进位
		mov ebx, x;		
		sub ecx, [ebx]x.last;
		jz  L3;		
L2:
		add [edi][edx*4], 1;
		jnc L4;
		inc edx;
		loop L2;		
	}
L3:	
	if (last == len)
	{
		Expand(LeastOver(len+1));			
	}
	pValue[last++] = 1;
L4:	
	return *this;
}

CBigInt CBigInt::operator + (DWORD dwValue) 
{
	CBigInt a(*this);
	return a += dwValue;
}

CBigInt CBigInt::operator + (CBigInt& x)
{
	CBigInt a(*this);
	return a += x;
}

CBigInt& CBigInt::Double(DWORD dwTimes /*= 1*/)
{	
	if (dwTimes % 32 != 0)
	{
		DWORD dwFull = 0;
		__asm 
		{
			mov ebx, this;		
			mov edi, [ebx]this.pValue;
			mov ebx, [ebx]this.last;
			xor eax, eax;
			mov ecx, dwTimes;
L1:
			mov edx, [edi];		
			shld [edi], eax, cl;		
			mov eax, edx;
			add edi, 4;
			dec ebx;
			jnz L1;
			
			neg cl;
			shr edx, cl;
			jz L2;
			mov dwFull, edx;
		}
		if (len == last)
		{
			Expand(LeastOver(last+1));
		}
		pValue[last++] = dwFull;
	}
L2:	
	DWORD dwStep = dwTimes >> 5;  //除以32
	while (dwStep > 0)
	{
		Expand(LeastOver(last+dwStep));
		MemCpy(&pValue[dwStep], pValue, last);
		last += dwStep;
		dwStep--;
	}	
	return *this;
}

void CBigInt::Compress()
{
	DWORD n = LeastOver(last);
	if (n < len)
	{
		DWORD *pTemp = new DWORD [len=n];
		MemCpy(pTemp, pValue, last);
		delete [] pValue;
		pValue = pTemp;
	}
}

CBigInt CBigInt::operator ++(int)         //a++
{
	CBigInt a(*this);
	operator += (1);
	return a;
}

CBigInt  CBigInt::operator ++()			//++a
{
	return operator += (1);
}

inline DWORD CBigInt::LeastOver(DWORD n)
{	
	__asm
	{
		bsr ebx, n;
		bsf ecx, n;
		cmp ebx, ecx;
		je  to_set;
		inc ebx;
to_set:
		xor eax, eax;
		bts eax, ebx;
	}
}

//////////////////////////////////////////////////////////////////////
// CMyException Class
//////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CMyException::CMyException(char* msg, UINT uErrorNo)
{
	m_szMsg = msg;
	m_uErrorNo = uErrorNo;
}

CMyException::~CMyException()
{
	
}

CBigInt& CBigInt::Half(DWORD dwTimes /*= 1*/)
{	
	DWORD dwStep = dwTimes / 32;
	if (dwStep >= last)
	{
		*pValue = 0;
		last = 1;
		return *this;
	}
	else if (dwStep > 0)
	{
		MemCpy(pValue, &pValue[dwStep], last-=dwStep);
	}	
	if (dwTimes % 32 != 0)
	{
		__asm 
		{
			mov ebx, this;		
			mov edi, [ebx]this.pValue;
			mov ebx, [ebx]this.last;			
			dec ebx;
			mov ecx, dwTimes;
			xor edx, edx;
L1: 			
			cmp ebx, edx;
			je  L2;
			mov eax, 4[edi][edx*4];		
			shrd [edi][edx*4], eax, cl;
			inc edx;
			jmp L1;
L2:
			xor eax, eax;
			shrd [edi][edx*4], eax, cl;
		}
		if (last > 1 && pValue[last-1] == 0)
		{     
			last --;				
		}	
	}
	return *this;
}

CBigInt CBigInt::operator /= (CBigInt& x)//返回余数
{
	if (x == 0)		//除数为0
	{
		CMyException* exception = new CMyException("除数为0", 
My_ErrorNo_ZeroByDiv);
		throw exception;		
	}

	if (*this == 0 || x == 1)//被除数为0或除数为1
	{
		return *this;
	}

	if (x.last == 1)	//除数为DWORD时
	{
		return operator /= (x.pValue[0]);
	}

	//商数
	CBigInt r;
	r.Expand(LeastOver(last-x.last+1));
	r.last = last- x.last + 1;
	memset(r.pValue, 0, 4*r.len);

	//减数数组，分别为x*2^i, （i从0到31），暂时为空，如需要再分配
	CBigInt* xx[32];
	xx[0] = new CBigInt(x);
	for (int i=1; i<32; i++)
	{
		xx[i] = NULL;
	}	

	//除数高位第一个1的位置(二进制）
	DWORD bit_x = x.pValue[x.last-1];
	__asm
	{
		bsr eax, bit_x;
		mov bit_x, eax
	}

	int nXX;  //减数在减数数组中的编号
	while (*this >= *xx[0])
	{			
		__asm
		{
			//计算出高DWORD中二进制位1的位置差
			mov ebx, this;
			mov esi, [ebx]this.pValue;
			mov ecx, [ebx]this.last;
			bsr eax, [esi][4*ecx-4];
			sub eax, bit_x;			
			add eax, 32;
			and eax, 0x1f;
			mov nXX, eax;

			//如果减数指针为空，则新分配
			mov eax, type xx;
			mul nXX;
			cmp xx[eax], 0;
			jne to_cmp;
		}
		
		xx[nXX] = new CBigInt(x);
		xx[nXX]->Double(nXX);
		
		__asm
		{
to_cmp:
		//比较
			mov eax, type xx;
			mul nXX;
			mov ebx, xx[eax];						
			mov esi, [ebx]xx.pValue;
			mov ecx, [ebx]xx.last;
			mov eax, ecx;
			dec eax;
			shl eax, 2;
			add esi, eax;

			mov edx, this;
			mov edi, [edx]this.pValue;
			mov eax, [edx]this.last;
			dec eax;
			shl eax, 2;
			add edi, eax;

			
			repe cmpsd;
			jbe to_sub;

			//减数变为前一个
			//如果减数指针为空，则新分配
			add nXX, 31;
			and nXX, 0x1f;
			mov eax, type xx;
			mul nXX;
			cmp xx[eax], 0;
			jne to_sub;
		}
		xx[nXX] = new CBigInt(x);
		xx[nXX]->Double(nXX);
		__asm
		{
to_sub:	
			mov eax, type xx;