cubes.cpp

给定12根长度相同的彩色小木棒的颜色,设计一个算法,计算用这12根长度彩色小木棒可搭出多少个不同的小立方体.

//12种颜色的编号假设为：1，2，3，4，5，6，7，8，9，10，11，12

#include <stdio.h>
#include <fstream.h>
#include <string.h>
#include <stdlib.h>

//计算正方体选择构成的置换群

char rotate[3][12];
char swaps[3][12]={
	{0,1,2,3,4,5,6,7,8,9,10,11},
	{3,1,9,11,0,5,8,4,2,6,10,7},
	{0,2,10,8,1,6,9,5,3,7,11,4}};
char (*states)[12];
int alloc_states;
int num_states;   //正方体选择构成的置换群中元素数目
void init_rotate()
{
   int i,j;
   for(i=0;i<3;i++)
   {
	   for(j=0;j<3;j++)
	   {
		   int i1=swaps[i][j*4];
           int i2=swaps[i][j*4+1];
           int i3=swaps[i][j*4+2];
           int i4=swaps[i][j*4+3];
           rotate[i][i1]=i2;
           rotate[i][i2]=i3;
           rotate[i][i3]=i4;
           rotate[i][i4]=i1;
		}
	}
}

void gen(int start,int end)
{
	int i;
	char n[12];
    for(i=start;i<end;i++)
	{
		int j,k;
        for(j=0;j<3;j++)
		{
			for(k=0;k<12;k++)
            n[k]=states[i][rotate[j][k]];
            for(k=0;k<num_states;k++)
            if(memcmp(n,states[k],12)==0)break;
            if(k==num_states)
			{
				if(alloc_states==num_states)
				{
					states=(char (*)[12])realloc(states, 2*alloc_states*sizeof(states[0]));
                    alloc_states*=2;
				}
			memcpy(states[num_states++],n,12);
			}
		}
	}
}

void search_states()
{
	int i,start,end;
    for(i=0;i<12;i++)states[0][i]=i;
    num_states++;
    start=0,end=num_states;
    do
	{
		gen(start,end);
		if(num_states==end)break;
        start=end,end=num_states;
	}while(1);
}

/*
void output(){
int i;
printf("Total %d states\n",num_states);
for(i=0;i<num_states;i++){
int k;
char used[12];
memset(used,0,sizeof(used));
for(k=0;k<12;k++){
if(!used[k]){
int start=k,j;
printf("(%c",k+'A');
used[k]=1;
for(j=states[i][start];j!=start;j=states[i][j]){
used[j]=1;
printf("%c",j+'A');
}
printf(")");
}
}
printf("\n");
}
}
*/

//计算n的阶乘
int fac(int n)  
{
  int s=1;
  for(int i=n;i>0;i--)
  {
	  if(s<=s*i) 
		  s=s*i;
	  else
	  {
		  cout<<"over int area."<<endl;
		  return 0;
	  }
  }
return s;
}

void main()
{
	ifstream input("input.txt");
	ofstream output("output.txt");
	int a[12]={0};
	int b[12]={0};
	double K=1,M=1,N=1,L=1,s=0;
	int J=0,db=0,ds=0,d3=0,d4=0;
	init_rotate();
    alloc_states=64;
    states=(char (*)[12])malloc(alloc_states*sizeof(states[0]));
    search_states();
	for(int i=0;i<12;i++) //输入是12种颜色，每种颜色分别有b[0],b[2],...,b[11]条边
	{
		input>>a[i];
		switch(a[i])      //12种颜色的编号假设为：1，2，3，4，5，6，7，8，9，10，11，12
		{
			case 1: b[0]++;break;
			case 2: b[1]++;break;
            case 3: b[2]++;break;
			case 4: b[3]++;break;
			case 5: b[4]++;break;
			case 6: b[5]++;break;		
			case 7: b[6]++;break;
			case 8: b[7]++;break;
			case 9: b[8]++;break;
			case 10: b[9]++;break;		
			case 11: b[10]++;break;
			case 12: b[11]++;break;
		}
	 
	}
	for(int j=0;j<12;j++)
	{
		if(b[j]!=0)
		{
			J++;
			M*=fac(b[j]/2);
            N*=fac(b[j]/3);
			L*=fac(b[j]/4);
			K*=fac(b[j]);
			if(b[j]%2==0) 
				db++;      //判断偶数
			else
				ds++;      //判断奇数
			if(b[j]%3==0) d3++; //判断多少个能被3整除
			if(b[j]%4==0) d4++; //判断多少个能被3整除
		}
	}
	s=fac(12)/K;
	if(db==J) s+=9*fac(6)/M;  //b[0],b[2],...,b[11]都是偶数
	if(ds==2) s+=12*fac(5)/M; //b[0],b[2],...,b[11]中正好有两个奇数
	if(d3==J) s+=8*fac(4)/N;  //b[0],b[2],...,b[11]都是3的倍数
	if(d4==J) s+=6*fac(3)/L;  //b[0],b[2],...,b[11]都是4的倍数
	s=s/num_states;
    output<<s;
}