igdd (3,1)^11.cpp

组合数学中求IGDD的程序。详细看程序吧。由于功能限制

// igdd (3,1)^11.cpp

#include<fstream>
#include<iostream>
#include<iomanip>
#include<vector>
#include<map>
#include<cstdlib>
#include<ctime>
using namespace std;

const int VALUE=33;
const int BLOCK_NUMBER=20;
const int BLOCK_LENGTH=3;
const int GUI_NUMBER=20;

int block[BLOCK_NUMBER][BLOCK_LENGTH];
int guiid[VALUE][VALUE];
int gui[GUI_NUMBER];
int shu[VALUE];

int a[10]={14,17,20,23,26,29,32,2,5,8};
int b[10]={25,28,31,1,4,7,10,13,16,19};
int c[20]={14,17,20,23,26,29,32,2,5,8,25,28,31,1,4,7,10,13,16,19};

struct ABC
{
	int a[10];
	int b[10];
}ab;

void init()
{
	int id;
	int i, j, k;

	for(i=0; i<VALUE-1; i++)
	{
		for(j=i+1; j<VALUE; j++)
		{
			if((j-i)%11==0 || i%3==0 || j%3==0)
				guiid[i][j]=-2;
			else
				guiid[i][j]=-1;
		}
	}

	id=0;
	for(i=0; i<VALUE-1; i++)
	{
		for(j=i+1; j<VALUE; j++)
		{
			if(guiid[i][j]==-1)
			{
				for(k=0; k<VALUE; k+=3)
				{
					int x=(i+k)%33;
					int y=(j+k)%33;
					guiid[x][y]=guiid[y][x]=id;
				}
				id++;
			}
		}
	}

	for(i=0; i<id; i++)
		gui[i]=0;

	for(i=0; i<VALUE; i++)
		shu[i]=0;


	// 输出各个轨道
	ofstream cout("轨道.txt");
	cout<<"共有 "<<id<<" 个轨道.\n\n";
	for(k=0; k<id; k++)
	{
		vector<int> x, y;
		for(i=0; i<VALUE-1; i++)
		{
			for(j=i+1; j<VALUE; j++)
			{
				if(guiid[i][j]==k)
				{
					x.push_back(i);
					y.push_back(j);
				}
			}
		}
		cout<<"第 "<<k+1<<" 个轨道:\n";
		for(i=0; i<x.size(); i++)
			cout<<setw(2)<<x[i]<<' ';
		cout<<endl;
		for(i=0; i<y.size(); i++)
			cout<<setw(2)<<y[i]<<' ';
		cout<<endl;
		cout<<endl;
	}
}

int ok()
{
	int i;

	for(i=0; i<VALUE; i++)
	{
		if(shu[i]!=3)
			return 0;
	}
	for(i=0; i<GUI_NUMBER; i++)
	{
		if(gui[i]!=3)
			return 0;
	}

	return 1;
}

void solve()
{
	int i, j, k;

	srand(time(0));

	int ii=rand()%BLOCK_NUMBER;
	int jj=rand()%BLOCK_LENGTH;

	for(i=0; i<BLOCK_NUMBER; i++)
	{
		for(j=0; j<BLOCK_LENGTH; j++)
		{
			block[i][j]=-1;
		}
	}

	for(i=0; i<10; i++)
	{
		for(j=0; j<3; j++)
		{
			while(1)
			{
				ii=rand()%BLOCK_NUMBER;
				jj=rand()%BLOCK_LENGTH;
				if(block[ii][jj]==-1)
				{
					for(k=0; k<3; k++)
					{
						if(k!=jj && block[ii][k]!=-1)
						{
							if(block[ii][k]==a[i] && block[ii][k]==b[i])
								break;
						}
					}
					if(k==3)
					{
						block[ii][jj]=a[i];
						break;
					}
				}
			}
		}
	}

	for(i=0; i<10; i++)
	{
		for(j=0; j<3; j++)
		{
			while(1)
			{
				ii=rand()%BLOCK_NUMBER;
				jj=rand()%BLOCK_LENGTH;
				if(block[ii][jj]==-1)
				{
					for(k=0; k<3; k++)
					{
						if(k!=jj && block[ii][k]!=-1)
						{
							if(block[ii][k]==b[i] && block[ii][k]==a[i])
								break;
						}
					}
					if(k==3)
					{
						block[ii][jj]=b[i];
						break;
					}
				}
			}
		}
	}

	ofstream cout("Block 搜索.txt");
	cout<<"初始 Block\n";
	for(i=0; i<BLOCK_NUMBER; i++)
	{
		cout<<setw(2)<<i<<": ";
		for(j=0; j<BLOCK_LENGTH; j++)
		{
			cout<<setw(2)<<block[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<endl;


	for(i=0; i<10; i++)
	{
		ab.a[i]=a[i];
		ab.b[i]=b[i];
	}

	while(!ok())
	{
		//cout<<"随机交换 ";
		for(i=0; i<2; i++)
		{
			int i1=rand()%BLOCK_NUMBER;
			int j1=rand()%BLOCK_LENGTH;
			int i2=rand()%BLOCK_NUMBER;
			int j2=rand()%BLOCK_LENGTH;

			if(block[i1][j1]==block[i2][j2])
				continue;

			for(j=1; j<3; j++)
			{
				if(block[i1][j]==block[i2][j2])
					break;
				if(block[i2][j]==block[i1][j1])
					break;
			}
			if(j<3)
				continue;
			
			int val1=0, val2=0;
			for(k=0; k<10; k++)
			{
				if(block[i2][j2]==ab.a[k])
				{
					val1=ab.b[k];
					break;
				}
				if(block[i2][j2]==ab.b[k])
				{
					val1=ab.a[k];
					break;
				}
			}
			for(k=0; k<10; k++)
			{
				if(block[i1][j1]==ab.a[k])
				{
					val2=ab.b[k];
					break;
				}
				if(block[i1][j1]==ab.b[k])
				{
					val2=ab.a[k];
					break;
				}
			}
			for(j=0; j<3; j++)
			{
				if(j!=j1 && block[i1][j]==val1)
					break;
				if(j!=j2 && block[i2][j]==val2)
					break;
			}
			if(j<3)
				continue;

			//cout<<"("<<i1<<" , "<<j1<<") 和 ("<<i2<<" , "<<j2<<") ";

			int tmp=block[i1][j1];
			block[i1][j1]=block[i2][j2];
			block[i2][j2]=tmp;
		}
		/*
		cout<<"后的Block:\n";
		for(i=0; i<BLOCK_NUMBER; i++)
		{
			cout<<setw(2)<<i<<": ";
			for(j=0; j<BLOCK_LENGTH; j++)
			{
				cout<<setw(2)<<block[i][j]<<' ';
			}
			cout<<endl;
		}
		cout<<endl;
		*/
	}

	cout<<"符合 Block\n";
	for(i=0; i<BLOCK_NUMBER; i++)
	{
		cout<<setw(2)<<i<<": ";
		for(j=0; j<BLOCK_LENGTH; j++)
		{
			cout<<setw(2)<<block[i][j]<<' ';
		}
		cout<<endl;
	}
	cout<<endl;
}

int main()
{
	init();
	solve();

	return 0;
}