计算卡洛图.cpp

一些c++小程序

#include<iostream.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
const int maxsize=16;
const int size=4;
struct   spoint{
	int  result;
	int  arr[size];//arr[0]为最低位!
};
class  graph{
private:
	spoint point[maxsize];
	int  flag[maxsize],endge[maxsize][maxsize],flagsum[maxsize];
	char  result[maxsize*maxsize];
	int numofvaluepoint,array[maxsize][size/2][size/2][size/2][size/2][maxsize*maxsize],path[maxsize];
public:
	graph(){
		char str[maxsize*size];
		int flagtemp=0,sum=0,temp[size],error=0;
		int i,j,k,s,t,u;
		numofvaluepoint=0;
         for(i=0;i<maxsize;i++)
			 for(j=0;j<size/2;j++)
				 for(k=0;k<size/2;k++)
					 for(s=0;s<size/2;s++)
						 for(t=0;t<size/2;t++)
							 for(u=0;u<maxsize*maxsize;u++)
								 array[i][j][k][s][t][u]=0;
		 for( i=0;i<maxsize;i++)
		 {
		    for(j=0;j<size;j++)
			{
				point[i].arr[j]=-1;
				point[i].result=0;
				temp[j]=-1;
				flag[i]=0;
				flagsum[i]=0;
			}
			for(s=0;s<maxsize;s++)
				endge[i][s]=0;
			path[i]=-1;
		 }
		 cout<<"请输入一个函数变量表达式!正变量用大写表示,反变量用小写!(如有AB的反变量请化成A的反变量乘B的)"<<endl;
		 cin>>str;
		 str[int(strlen(str))+1]=str[int(strlen(str))];
		 str[int(strlen(str))]='+';
		 for(i=0;i<int(strlen(str));i++)
		 {
			 switch(str[i])
			 {
			 case '+':
				 for(j=0;j<size/2;j++)
                    for(k=0;k<size/2;k++)
						for(s=0;s<size/2;s++)
							for(t=0;t<size/2;t++)
							{
								bool te=temp[3]==-1&&temp[2]==-1&&temp[2]==-1&&temp[0]==-1;
								if((j==temp[3]||temp[3]==-1)&&(k==temp[2]||temp[2]==-1)&&(s==temp[1]||temp[1]==-1)&&(t==temp[0]||temp[0]==-1)&&!te)
								{
									int tem=j*8+k*4+s*2+t;
									point[tem].result=1;
									numofvaluepoint++;
									point[tem].arr[3]=j;
									point[tem].arr[2]=k;
									point[tem].arr[1]=s;
									point[tem].arr[0]=t;
								}
							}
							for(j=0;j<size;j++)
								temp[j]=-1;
				 break;
			 case 'A':
				 temp[int('D'-str[i])]=1;
				 break;
			 case 'B':
				 temp[int('D'-str[i])]=1;
				 break;
			 case 'C':
				 temp[int('D'-str[i])]=1;
				 break;
			 case 'D':
				 temp[int('D'-str[i])]=1;
				 break;
             case 'a':
				 temp[int('d'-str[i])]=0;
				 break;
			 case 'b':
				 temp[int('d'-str[i])]=0;
				 break;
			 case 'c':
				 temp[int('d'-str[i])]=0;
				 break;
			 case 'd':
				 temp[int('d'-str[i])]=0;
				 break;
			 default:
				 error++;
				 if(error==1)
				 {
				 cout<<"你的输入有错误!"<<endl;
				 exit(1);
				 }
			 } 
		 }
		 for(i=0;i<maxsize;i++)
			 for(j=0;j<maxsize;j++)
                 if(point[i].result==point[j].result&&point[i].result==1)
				 {
					 if(i!=j)
					 {
					 int t0=!point[i].arr[0]-point[i].arr[0],t1=2*(!point[i].arr[1]-point[i].arr[1]),t2=4*(!point[i].arr[2]-point[i].arr[2]),t3=8*(!point[i].arr[3]-point[i].arr[3]);
					 if(j-i==t0||j-i==t1||j-i==t2||j-i==t3)
					 endge[i][j]=1;
					 }
					 else
						 endge[i][j]=-1;
				 }
				 flag[0]=numofvaluepoint;
				  flag[maxsize-1]=flag[0]/maxsize;
				  int num=0;
				   for(i=0;i<maxsize;i++)
                     if(point[i].result==1)
                        num++;
				   if(num==0)
				   {
					   cout<<'0'<<endl;
					     exit(0);
				   }
				   else
					   if(num==16)
					   {
						   cout<<'1'<<endl;
						   exit(0);
					   }
	}
	void  delonesame(int low,int range )
	{
      int i,j,k,s,t,u,same=0;
	   for(i=low+1;i<maxsize;i++)
		   for(j=0;j<flagsum[i];j++)
		   {
			   same=0;
			   for(k=0;k<size/2;k++)
				   for(s=0;s<size/2;s++)
					   for(t=0;t<size/2;t++)
						   for(u=0;u<size/2;u++)
						   {
                             if(array[low][k][s][t][u][range]==1&&array[i][k][s][t][u][j]==array[low][k][s][t][u][range])
								 same++;
						   }
                      if(same==low+1)
					  {
                           for(int a=0;a<size/2;a++)
							    for(int b=0;b<size/2;b++)
								     for(int c=0;c<size/2;c++)
										 for(int d=0;d<size/2;d++)
											array[low][a][b][c][d][range]=0;
										 break;
										 break;
					  }
		   }

	}
	void  resetflag()
	{
		for(int i=0;i<maxsize;i++)
			flag[i]=0;
	}
	void  search(int des,int src,int k)
	{
		int s;
		if(endge[des][src]==-1)
		{
		int overlap=0;
			for(s=0;s<=k;s++)
				for(int j=s+1;j<=k;j++)
				{
					if(path[s]==path[j]||!(k+1==1||k+1==2||k+1==4||k+1==8||k+1==16))
						overlap=1;
				}
				if(!overlap)
				{
			        for(s=0;s<=k;s++)
						array[k][path[s]/8][(path[s]%8)/4][((path[s]%8)%4)/2][path[s]%2][flagsum[k]]=1;
					         flagsum[k]++;
				}
		}
		else
		{
			s=0;
			while(s<maxsize)
			{
				if(endge[src][s]==1&&flag[s]==0)
				{
					flag[s]=1;
					path[k+1]=s;
					search(des,s,k+1);
					flag[s]=0;
				}
				s++;
			}
		}
	}
	void  depthsearch(int des,int src)
	{
	 path[0]=src;
	 resetflag();
	 search(des,src,0);
	}
	void  ridoverlap()
	{
      int i,j,k,s,t,u,m,arraysum[size];
	  for(i=0;i<maxsize;i++)//去掉重复
		for(u=0;u<flagsum[i];u++)
		  for(j=0;j<size/2;j++)
			for(k=0;k<size/2;k++)
				for(s=0;s<size/2;s++)
					for(t=0;t<size/2;t++)
					{
						for(m=u+1;m<flagsum[i];m++)
						{ 
							int sum=0,a,b,c,d;
							for(a=0;a<size/2;a++)
								for(b=0;b<size/2;b++)
									for(c=0;c<size/2;c++)
										for(d=0;d<size/2;d++)
											if(array[i][a][b][c][d][u]==array[i][a][b][c][d][m])
												sum++;
											if(sum==maxsize)
											{
                                               for(a=0;a<size/2;a++)
							                 	 for(b=0;b<size/2;b++)
								                	for(c=0;c<size/2;c++)
										              for(d=0;d<size/2;d++)
														  array[i][a][b][c][d][m]=0;
											}

						}

					}
            //下面是去掉不合格的
		for(i=0;i<maxsize;i++)
			for(j=0;j<flagsum[i];j++)
			{   
				arraysum[0]=arraysum[1]=arraysum[2]=arraysum[3]=0;
				int tempsum=0;
				for(k=0;k<size/2;k++)
					for(s=0;s<size/2;s++)
						for(t=0;t<size/2;t++)
							for(u=0;u<size/2;u++)
							{
                              if(array[i][k][s][t][u][j]==1)
							  {
								  arraysum[0]+=k;
								  arraysum[1]+=s;
								  arraysum[2]+=t;
								  arraysum[3]+=u;
							  }
							}
							for(int r=0;r<size;r++)
							{
								if(arraysum[r]==0||arraysum[r]==i+1||((arraysum[0]+arraysum[1]+arraysum[2]+arraysum[3]==0)&&i==0))
									tempsum++;
							}
							if(i!=0&&i!=1&&!(i==3&&tempsum==2||i==7&&tempsum==1||i==15&&tempsum==0))
							{
                               for(int a=0;a<size/2;a++)
							      for(int b=0;b<size/2;b++)
								     for(int c=0;c<size/2;c++)
										 for(int d=0;d<size/2;d++)
											array[i][a][b][c][d][j]=0;
							}

			}
			//下面是去掉非必要的最小项
		for(i=0;i<maxsize;i++)
			for(j=0;j<flagsum[i];j++)
			    delonesame(i,j);
			//下面是去掉非质最大蕴涵项
			int  oksum,sums,sumd;
				  for(u=0;u<maxsize;u++)
					  for(m=0;m<flagsum[u];m++)
					  {
						   oksum=0;
					for(i=0;i<size/2;i++)
					   for(j=0;j<size/2;j++)
						   for(k=0;k<size/2;k++)
							   for(s=0;s<size/2;s++)
							   {
								   if(array[u][i][j][k][s][m]==1)
									   array[u][i][j][k][s][m]=2;
							   }
				   for(i=0;i<size/2;i++)
					   for(j=0;j<size/2;j++)
						   for(k=0;k<size/2;k++)
							   for(s=0;s<size/2;s++)
							   { 
                                   sums=0;sumd=0;
                                   if(point[i*8+j*4+k*2+s].result==1)
									   sums=1;
								    else
										sums=0;
                                     for(int p=0;p<maxsize;p++)
										 for(int o=0;o<flagsum[p];o++)
												if(array[p][i][j][k][s][o]==1)
														sumd=1;
															 if(sums==sumd)
																 oksum++;
							   }
							   if(oksum!=maxsize)
							   {
					for(i=0;i<size/2;i++)
					   for(j=0;j<size/2;j++)
						   for(k=0;k<size/2;k++)
							   for(s=0;s<size/2;s++)
							   {
								   if(array[u][i][j][k][s][m]==2)
									   array[u][i][j][k][s][m]=1;
							   }
							   }
					  }
			  
	}
void show()
	{
		int i,j,k,s,t,u,arraysum[size],ge=0;
         for(i=0;i<maxsize;i++)
			for(u=0;u<flagsum[i];u++)
			{
				int tempsum=0;
			 arraysum[0]=arraysum[1]=arraysum[2]=arraysum[3]=0;
				for(k=0;k<size/2;k++)
					for(s=0;s<size/2;s++)
						for(t=0;t<size/2;t++)
							for(j=0;j<size/2;j++)
							{
                              if(array[i][k][s][t][j][u]==1)
							  {  
								  tempsum=1;
								  arraysum[0]+=k;
								  arraysum[1]+=s;
								  arraysum[2]+=t;
								  arraysum[3]+=j;
							  }
							}
							for(int r=0;r<size;r++)
							{
								if(tempsum)
								{
								   if(arraysum[r]==0)
								   {
									result[ge]=char('a'+r);
									ge++;
								   }
								   else
									if(arraysum[r]==i+1)
									{
									result[ge]=char('A'+r);
									ge++;
									}
									if(r==size-1)
									{
										result[ge]='+';
										ge++;
									}
								}
							}
			}
			result[ge-1]='\0';
			for(i=0;i<ge-1;i++)
				if(result[i]!='1')
					cout<<result[i];
				cout<<endl;

	}
};
void main()
{
	graph  king;
	for(int i=0;i<maxsize;i++)
		for(int j=i+1;j<maxsize;j++)
			if(i!=j)
	      king.depthsearch(i,j);
	        king.ridoverlap();
			cout<<"化简后的结果为:"<<endl;
	          king.show();
		        cout<<endl;
				  char t;
				  cin>>t;
}