repcomb1.cpp

穷举法进行三八二十四的计算。列举所有可能的表达式进行计算筛选。

// CombRepElem.cpp: implementation of the CCombRepElem class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "repcomb1.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

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

CRepComb::CRepComb()
{
m_nm=m_nn=m_nLength=0;
m_pCouple=NULL;
m_pScope=NULL;
m_pSel=NULL;
}

CRepComb::~CRepComb()
{
  if(m_nLength>0)
  {
  delete[] m_pScope;
  delete[] m_pCouple;
  delete[] m_pSel;
  delete[] m_pLastPos;
  m_nn=0;
  m_nLength=0;
  m_nm=0;
  }
}
//功能：对排列器进行初始设置
//numDiffElem表示不同元素的个数
//a数组表示各元素的重复次数
void CRepComb::initiate(int *a, int numDiffElem,int m)
{
  if(a==NULL||numDiffElem<1) return;
  int count=0;
  int x=numDiffElem;
  while(--x>=0)	 
	if(a[x]<=0) return;
	else count+=a[x];
  if(m>count) return;
  m_nDiffElem=numDiffElem;
  if(m_nLength<count)
  {
	  //重新分配存储单元
     if(m_nLength>0)
	 {
        delete[] m_pScope;
		delete[] m_pCouple;
		delete[] m_pSel;
		delete[] m_pLastPos;
		m_nn=0;
		m_nLength=0;
		m_nm=0;
	 }
	 m_nLength=count;
	 m_pScope=new int[m_nLength];
	 m_pCouple=new CCouple[m_nLength];
	 m_pSel=new int[m_nLength];
	 m_pLastPos=new int[m_nLength];
	 m_nn=m_nLength;
	 m_nm=m;
  }
  else m_nn=count;
  int nIndex;
  int tip,y=0;
  m_pLastPos[0]=a[0]-1;
  for(nIndex=1;nIndex<numDiffElem;nIndex++)
	  m_pLastPos[nIndex]=m_pLastPos[nIndex-1]+a[nIndex];
  for(tip=0,nIndex=0;nIndex<m_nn;nIndex++)
  {
	  m_pScope[nIndex]=-1;
	  if(y<a[tip])
	  {
	    m_pCouple[nIndex].x=tip;
		m_pCouple[nIndex].y=y++;
	  }
	  else
	  {
		  ++tip;
		  y=0;
          m_pCouple[nIndex].x=tip;
		  m_pCouple[nIndex].y=y++;
	  }
  }
  m_pCouple[m_nn].x=numDiffElem;
  m_pCouple[m_nn].y=-1;
  next(true);
}

bool CRepComb::next(bool bInitiate)
{
  bool bFound=true,bTryAgain;
  int nIndex;
  //nIndex==-3表示对排列进行初始化
  if(bInitiate)
  {
	  for(nIndex=0;nIndex<m_nm;nIndex++)
		m_pSel[nIndex]=-3;
	  nIndex=0;
  }
  else nIndex=m_nm-1;
  /////////////////////////////////
  do
  {
    ResetMark(nIndex,m_pSel[nIndex]); //m_pScope[m_pSel[nIndex]]=false;
    m_pSel[nIndex]=NextElem(m_pSel[nIndex]); //m_pSel[nIndex]++;
    while(nIndex>=0&&!IsSelectable(nIndex,m_pSel[nIndex]))/*m_pScope[m_pSel[nIndex]]*/
	{
	    if(m_pSel[nIndex]>=m_nn) 
		{
	      nIndex--;
		  if(nIndex>=0)
		  {
		    ResetMark(nIndex,m_pSel[nIndex]); //m_pScope[m_pSel[nIndex]]=false;
		    m_pSel[nIndex]=NextElem(m_pSel[nIndex]);  //m_pSel[nIndex]++;
		  }
		}
	    else m_pSel[nIndex]++;   //m_pSel[nIndex]++;
	}
   if(nIndex<0) return false;
   SetMark(nIndex,m_pSel[nIndex]);   //m_pScope[m_pSel[nIndex]]=true;
   nIndex++;
   bTryAgain=false;
   while(nIndex<=m_nm-1&&!bTryAgain)
   {
	  m_pSel[nIndex]=0;
	  while(m_pSel[nIndex]<m_nn&&!IsSelectable(nIndex,m_pSel[nIndex]))  //m_pScope[m_pSel[nIndex]])
		  m_pSel[nIndex]++;  //m_pSel[nIndex]++;
	  if(m_pSel[nIndex]<m_nn)
	  {
	      SetMark(nIndex,m_pSel[nIndex]);//m_pScope[m_pSel[nIndex]]=true;
	      nIndex++;
		  bFound=true;
	  }
	  else
	  {
		  nIndex--;
		  bFound=false;
		  bTryAgain=true;
	  }	
   }
  }while(!bFound);
  return true;
}

void CRepComb::get(int a[])
{
  for(int i=0;i<m_nm;i++)
	  a[i]=m_pCouple[m_pSel[i]].x;
}
//m_pScope[n]==-1表示可以选择该元素
//m_pScope[n]==-2表示禁止选择该元素
//m_pScope[n]>=0表示该元素放在排列中所处的位置
void CRepComb::SetMark(int nIndex,int n)
{
 int x;
 if(n<0||n>m_nn-1||nIndex<0||nIndex>m_nm-1) return;
 x=m_pCouple[n].x;
 m_pScope[n]=nIndex;
 n--;
 while(n>=0&&m_pScope[n]==-1&&m_pCouple[n].x==x)
 {
	 m_pScope[n]=-2;
	 n--;
 }
}

void CRepComb::ResetMark(int nIndex,int n)
{
	int x;
	if(n<0||n>m_nn-1||nIndex<0||nIndex>m_nm-1) return;
	x=m_pCouple[n].x;
	m_pScope[n]=-1;
	while(n>=0&&m_pScope[n]==-2&&m_pCouple[n].x==x)
	{
		m_pScope[n]=-1;
		n--;
	}
}

bool CRepComb::IsSelectable(int nIndex, int n)
{
  	if(n<0||n>m_nn-1||nIndex<0||nIndex>m_nm-1) false;
	if(m_pScope[n]==-1) return true;
	else return false;
}

int CRepComb::NextElem(int n)
{
  if(n<0&&n!=-3||n>m_nn-1) return m_nn;
  if(n==-3) return 0;
  int x,nIndex;
  x=m_pCouple[n].x;
  nIndex=m_pLastPos[x]+1;
  while(nIndex<m_nn&&m_pScope[nIndex]!=-1)
	  nIndex++;
  return nIndex;
}