js24dot.h

计算24点源程序

// 作者：周星星

#include "Rational.h"
#include <string>
using namespace std;

bool Js24dot(CRational* pR,size_t Count,string& pStr);
bool Js24dot_cb(CRational* pR,size_t Count,size_t m,size_t n,CRational nv,string& Str);

const INTYPE JG = 24;
const INTYPE_MAXLENGTH=12;

bool Js24dot(CRational* pR,size_t Count,string& pStr)
{
	if(Count==0) return false;
	if(Count==1) return pR[0]==JG;

	return Js24dot_cb(pR,Count+1,0,Count,pR[0],pStr);
}

bool Js24dot_cb(CRational* pR,size_t Count,size_t m,size_t n,CRational nv,string& Str)
{
	if(Count==2) return nv==24;

	CRational* pNR=new CRational[Count-1];
	for(size_t k=0,l=0;k<Count;++k)
	{
		if(k==n) continue;
		pNR[l++]=pR[k];
	}
	pNR[m<n?m:m-1]=nv;

	char CurOperator;
	for(size_t i=0,j=0;i<Count-1;++i)
	{
		for(j=0;j<Count-1;++j)
		{
			if(i==j) continue;

			if(i<j)
			{
				if(Js24dot_cb(pNR,Count-1,i,j,pNR[i]+pNR[j],Str)) { CurOperator='+'; goto success; }
				if(Js24dot_cb(pNR,Count-1,i,j,pNR[i]*pNR[j],Str)) { CurOperator='*'; goto success; }
			}
			if(Js24dot_cb(pNR,Count-1,i,j,pNR[i]-pNR[j],Str)) { CurOperator='-'; goto success; }
			if(pNR[j]!=0)
			{
				if(Js24dot_cb(pNR,Count-1,i,j,pNR[i]/pNR[j],Str)) { CurOperator='/'; goto success; }
			}
		}
	}
	delete pNR;
	return false;

success:
	char stmp[INTYPE_MAXLENGTH];
	string strtmp;
	strtmp+="< ";
	strtmp+=_ltoa(pNR[i].GetNumerator(),stmp,10);
	if(pNR[i].GetDemoninator()!=1)
	{
		strtmp+='/';
		strtmp+=_ltoa(pNR[i].GetDemoninator(),stmp,10);
	}
	strtmp+=' ';
	strtmp+=CurOperator;
	strtmp+=' ';
	strtmp+=_ltoa(pNR[j].GetNumerator(),stmp,10);
	if(pNR[j].GetDemoninator()!=1)
	{
		strtmp+='/';
		strtmp+=_ltoa(pNR[j].GetDemoninator(),stmp,10);
	}
	strtmp+=" >";
	Str=strtmp+Str;
	delete pNR;
	return true;
}