lifegame_cpp.cpp

用程序模拟生命演化游戏

///////////////////////////////////////////////////////////////
//				生命游戏C++版								 //
// 								 //
// 											 //
///////////////////////////////////////////////////////////////


#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
enum condition{dead,alive};

//个体的定义，包括生死情况和周围的生存人数 
struct individual
{
	condition con;
	int SurvivorsAround;
};

//环境的定义，包含无参，单参和双参的重载构造函数（参数表示长宽），复制构造函数，析构函数，
//修改函数Modify(),后处理函数postprocessor(),主要用来计算下一代的SurvivorsAround.
struct environment
{
	individual** p;int m,n,pred;//pred为已经处理了的round数，在后面search()有用
	void Modify(int r,int s,condition t)
	{
		p[r][s].con=t;
	}
	void postprocessor()
	{
	for(int i=1;i<m+1;i++)
		for(int j=1;j<n+1;j++)
			p[i][j].SurvivorsAround=p[i-1][j-1].con+p[i-1][j].con+p[i-1][j+1].con
			+p[i][j-1].con				   +p[i][j+1].con 
			+p[i+1][j-1].con+p[i+1][j].con+p[i+1][j+1].con;
	}
	environment(int r)
	{
	m=r;
	n=r;
	p=new (individual*[m+2]);
	for(int i=0;i<m+2;i++)
		p[i]=new individual[n+2];
	for(i=0;i<m+2;i++)//初始化，全部为死
		for(int j=0;j<n+2;j++)
		{
			
			p[i][j].con=dead;	
		}
		postprocessor();
		pred=1;
	}
	environment(int r,int s)
	{
	m=r;
	n=s;
	p=new (individual*[m+2]);
	for(int i=0;i<m+2;i++)
		p[i]=new individual[n+2];
	for(i=0;i<m+2;i++)
		for(int j=0;j<n+2;j++)
		{
			
			p[i][j].con=dead;	
		}
		postprocessor();
		pred=1;
	}
	
	environment(environment& a)
	{
	m=a.m;
	n=a.n;
	p=new (individual*[m+2]);
	for(int i=0;i<m+2;i++)
		p[i]=new individual[n+2];
	for(i=0;i<m+2;i++)
		for(int j=0;j<n+2;j++)
		{
			
			p[i][j].con=a.p[i][j].con;	
		}

	postprocessor();
	pred=a.pred;
	}
	
	environment()
	{}
};

///////////////////////////////////////////////////////
//         生命衍化过程的演示程序部分				 //
//            第98行到第213行
///////////////////////////////////////////////////////

//构造人工环境，人工输入环境中每个个体的情况。
environment CreateArtificialEnvironment(int m,int n)
{
	environment a;
	int k=0;
	a.m=m;
	a.n=n;
	a.p=new (individual*[m+2]);
	for(int i=0;i<m+2;i++)
		a.p[i]=new individual[n+2];
	cout<<"请以矩阵形式输入"<<m*n<<"个个体的初始情况，1代表生存，0代表死亡";
	for(i=1;i<m+1;i++)
		for(int j=1;j<n+1;j++)
		{
			cin>>k;
			a.p[i][j].con=(enum condition)k;	
		}
		for(i=0;i<m+2;i++)
		{
			a.p[i][0].con=dead;
			a.p[i][n+1].con=dead;
		}
		for(int j=0;j<m+2;j++)
		{
			a.p[0][j].con=dead;
			a.p[m+1][j].con=dead;
		}
		a.postprocessor();
		return a;
}


//计算环境中的某一个体下一代的生存情况
condition surviveordie(const environment&a,int i,int j)
{
	int q=a.p[i][j].SurvivorsAround;
	if(a.p[i][j].con==alive)
	{
		if(q>=4||q<=1)
			return dead;
		else
			return alive;
	}
	else if(q==3)
		return alive;
	else
		return dead;
} 



//计算出下一代的情况，并把原环境改变
void next(environment&a)//注意，这用的是引用
{
	condition**s;
	s=new condition*[a.m];
	for(int i=0;i<a.m;i++)
		s[i]=new condition[a.n];
	for(i=0;i<a.m;i++)
		for(int j=0;j<a.n;j++)
			s[i][j]=surviveordie(a,i+1,j+1);
		for(i=0;i<a.m;i++)
			for(int j=0;j<a.n;j++)
				a.p[i+1][j+1].con=s[i][j];
			a.postprocessor();
}



//环境的打印函数
void print(environment&a)
{
	for(int i=0;i<a.m;i++)//?
	{
		for(int j=0;j<a.n;j++)
		{
			if(a.p[i+1][j+1].con==alive)
				cout<<"* ";
			else
				cout<<"  ";
		}
		cout<<endl;
	}
}


//生成随机环境
environment CreateRandomEnvironment(int m,int n)
{
	environment a;
	int k=0;
	a.m=m;
	a.n=n;
	a.p=new (individual*[m+2]);
	for(int i=0;i<m+2;i++)
		a.p[i]=new individual[n+2];

for(i=1;i<m+1;i++)
		for(int j=1;j<n+1;j++)
		{
		
			a.p[i][j].con=(enum condition)(rand()%2);	
		}
		for(i=0;i<m+2;i++)
		{
			a.p[i][0].con=dead;
			a.p[i][n+1].con=dead;
		}
		for(int j=0;j<m+2;j++)
		{
			a.p[0][j].con=dead;
			a.p[m+1][j].con=dead;
		}
		a.postprocessor();
		return a;
}



//////////////////////////////////////////////////////////////////////
//						     导读									//
//			下面属于计算给定地图的最大稳定容纳量部分。				//
//				分为广度优先和深度优先两种方法。					//
//				 广度优先从第225行到第333行							//
//				 深度优先从第336行到第460行							//
//////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////
//              这里开始为广度优先搜索					  //
////////////////////////////////////////////////////////////

typedef environment DataType;
#include"queue.h"

//由于用到广度搜索，需要一个队列，队列的元素为环境类型
PLinkQueue Map=createEmptyQueue_link();

//判断某节点的状态在进程中是否稳定
int IsSafe(const environment&a ,int m,int n)
{
	return(surviveordie(a,m,n)==a.p[m][n].con);//下一代的情况是否跟原来一样
}

//round是指从左上角开始数到round的一个 “_|”形的区域。
//这个函数的作用在于按照num的二进制码来设置这一区域的状况
//也就是num的二进制码的每一位'0''1'对应每一点的死与生
environment set(environment a,int round,int num)
{
int x=1;int i=1;
for(i=1;i<=round;i++)
{
	a.p[round][i].con=condition((x&num)!=0);
	x*=2;
}
for(i=round-1;i>=1;i--)
{
	a.p[i][round].con=condition((x&num)!=0);
	x*=2;
}
a.postprocessor();
return a;
}


//计算整个环境最后总存活个数
int countsurvivals(const environment&a)
{
int i,j,c=0;
for(i=1;i<=a.m;i++)
	for(j=1;j<=a.n;j++)
		if(a.p[i][j].con==alive)
			c++;
return c;
}


//小小指数函数，求m的n次方
int exp(int m,int n)
{
if(n==0)
return 1;
return m*exp(m,n-1);
}


//判断环境中round对应的'_|'形区域是否稳定
int CircleSafe(const environment &a,int round)
{

int i=1;
for(i=1;i<=round;i++)
{
	if(!IsSafe(a,round,i))
	return 0;
}
for(i=round-1;i>=1;i--)
{
	if(!IsSafe(a,i,round))
	return 0;
}
return 1;
}



//总的BSearch()，计算n*n的环境的最大稳定存活量,从左上角向右下角蔓延
int BSearch(int n)
{
if(n==1) return 0;
environment a(n),b(n);
int count;
enQueue_link(Map,set(a,1,0));
enQueue_link(Map,set(a,1,1));//把最左上角的点的两种情况入队
while(!isEmptyQueue_link(Map))
{
a=frontQueue_link(Map);//不断处理队首元素
deQueue_link(Map);
	for(int i=0;i<exp(2,2*a.pred+1);i++)  //2*a.pred+1为第pred圈的节点个数
		{
			b=set(a,a.pred+1,i);//把a.pred对应的那个'_|'区域的各种情况检查，行得通的入队
			if(CircleSafe(b,a.pred))
			{
				b.pred=a.pred+1;
				if(b.pred==n)//这条路已经走到尽头，把这种方法能存活的最大人数计入count
				{
					if(CircleSafe(b,b.pred)&&count<countsurvivals(b))
						count=countsurvivals(b);
					continue;
				}
				enQueue_link(Map,b);
			}

		}
}
return count;
}


////////////////////////////////////////////////////
//              这里开始为深度优先搜索			  //					
////////////////////////////////////////////////////

struct Mark//环境状况的标志字。注意，为了不引起混淆和以后使用方便，这里弃用数组第0号元素与最后一号元素。
{
	Mark(int i)
	{
		mark=new int[i+2];
		for(int j=0;j<=i+1;j++)//注意这里mark[0]与mark[i+1]是不使用的，他们为CircleSafe()凑形式而已
			mark[j]=0;//初始化时全为0
		n=i;//方阵边长的大小
	}
	void SetMark(int i,int m)//将标志字的第i位设成m。
	{
		mark[i]=m;
	}
	void ClearMark(int i)//将第i位之后的各位清零,不包括i
	{
	for(int j=i+1;j<=n;j++)
		mark[j]=0;
	}
	void PrintMark()
	{
		for(int i=1;i<=n;i++)
			cout<<mark[i]<<'\t';
		cout<<endl;
	}
	int* mark;//标志字数组
	int n;
};

int IsSafe(const Mark&a,int i,int j)//(1<=i<=n;1<=j<=n)重载IsSafe()函数，用标志字判断第i列第j位是否稳定
{
	int k,l;//i=1的情况在Mark(int)里清零时保证满足，j=n的情况以二进制的取与方式保证满足。
	//k为周围人的生存个数，l为自身生存情况
	
	if(j==1)//只有j=1须特殊讨论，这时它周围u只有五个单位
		k=(a.mark[i-1]&1)+((a.mark[i-1]&2)/2)+((a.mark[i]&2)/2)+(a.mark[i+1]&1)+((a.mark[i+1]&2)/2);
	
	else//一般情况下周围有8个单位
		k=((a.mark[i-1]&exp(2,j-2))/exp(2,j-2))+((a.mark[i-1]&exp(2,j-1))/exp(2,j-1))+((a.mark[i-1]&exp(2,j))/exp(2,j))
			+((a.mark[i]&exp(2,j-2))/exp(2,j-2))+((a.mark[i]&exp(2,j))/exp(2,j))
			+((a.mark[i+1]&exp(2,j-2))/exp(2,j-2))+((a.mark[i+1]&exp(2,j-1))/exp(2,j-1))+((a.mark[i+1]&exp(2,j))/exp(2,j));
	l=(a.mark[i]&exp(2,j-1))/exp(2,j-1);
	if(k>3&&l==0||k<=2&&l==0||k>=2&&k<=3&&l!=0)//本来死的还是死，本来活的还是活，注意这里2的双重性
		return 1;
	return 0;
	
}

int CollumSafe(Mark&a,int i)//判断第i列是否全体稳定
{
	for(int j=1;j<=a.n;j++)
	{
		if(!IsSafe(a,i,j))
			return 0;
	}
	return 1;
}

int countsurvivals(Mark&a)//从标志数中数出环境的存活量//待优化
{
	int num=0;
	for(int i=1;i<=a.n;i++)
	{
		for(int j=0;j<a.n;j++)//注意这里j的限
			if(a.mark[i]&exp(2,j))
				num++;
	}
	return num;

}

int DSearch(int n)//深度优先，先根遍历n叉树
{
Mark a(n);
int i=1,max=0;//
while(i!=0)//此循环跳出条件是全树遍历完
{
	do
	{
		while(!CollumSafe(a,i))//第i列不稳定，调整到第i列稳定为止
		{
			if(a.mark[i+1]==exp(2,n)-1)//下层的所有情况已经遍历，问题在上层
			{
				while(a.mark[i]==exp(2,n)-1)//这一层也已经遍历，往再上一层找,跳出时第i层未遍历完或i=0
				{
					i--;
				}
				if(i==0)//已经遍历完
					return max;
				a.mark[i]++;//看下一种情况
				a.ClearMark(i);//i后各位清零，下一种情况的开始
				if(i!=1)
					i--;
				continue;//找下一条可能的路径
			}
			else a.mark[i+1]++;//看下一条
		}
		i++;//稳定，往下走
	}while(i!=n);//跳出条件:i已经遍历到底，即全环境除最后一行安全，产生出准可行路径
	
	//因为i已经遍历到底而跳出，作最后判断
	if(CollumSafe(a,n))
	{
	int p=countsurvivals(a);
	if(max<p)
	max=p;
	}
	//以下为i的复位
		while(a.mark[i]==exp(2,n)-1)//这一层又已经遍历，往上一层找
			i--;
		if(i==0)
			return max;
	a.mark[i]++;
	a.ClearMark(i);
	int q=countsurvivals(a);
	if(i==1)
		continue;
	i--;//这里两次i--有问题
}
return max;

}

//////////////
//主函数部分//
//////////////
void main()
{
	cout<<"生命游戏\n\n游戏规则：\n我们将生命演化放到平面上的正交网格点上。\n a)每个格点有8个邻点；\n b)如一个格点上有生命，但它的邻点上只有一个有生命或没有生命，那么它的下一代因为孤独而失去生命；\n c)如一个格点上有生命，但它的邻点上有四个或多于四个有生命，那么它的下一代因为拥挤而失去生命；\n d)如一个格点上有生命，且它的邻点上有两个或三个有生命，那么它的下一代有生命；\n e)如一个格点上没有生命，但它的邻点上正好有三个有生命，那么它的下一代变成有生命；\n f)所有的生死在同一时间发生。\n\n";
	cout<<"请输入你想创建的二维环境的长和宽:";
	int m,n,i=2;
	char c;
	environment a;
	cin>>m>>n;
	cout<<"请问你想要随机地图还是人工地图？(\'r\' for random,\'a\'for artificial)";
	cin>>c;
	if(c=='r')
	a=CreateRandomEnvironment(m,n);
	else
	a=CreateArtificialEnvironment(m,n);
	print(a);
	cout<<"下一代是:"<<endl;
	do
	{
		next(a);
		print(a);
		cout<<"要打印下一代(第"<<i<<"代)吗?('y' or 'n')"<<endl;
		cin>>c;
		i++;
	}while(c=='y');
	cout<<"打印结束!"<<endl;
	cout<<"以下是最大稳定存活问题部分"<<endl;
	cout<<"请选择你要选用的方法，广度优先(1~5)-press'1',深度优先(1~6)-press'2'"<<endl;
	int s,t;
	cin>>t;
	cout<<"请输入要检索的方阵的阶数："<<endl;
	cin>>s;
	cout<<s<<"阶矩阵最大稳定人数:  ";
	if(t==1)
		cout<<BSearch(s)<<endl;
	else
		cout<<DSearch(s)<<endl;
}