?? lifegame_cpp.cpp
字號:
///////////////////////////////////////////////////////////////
// 生命游戲C++版 //
// //
// //
///////////////////////////////////////////////////////////////
#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<malloc.h>
enum condition{dead,alive};
//個體的定義，包括生死情況和周圍的生存人數(shù)
struct individual
{
condition con;
int SurvivorsAround;
};
//環(huán)境的定義，包含無參，單參和雙參的重載構造函數(shù)（參數(shù)表示長寬），復制構造函數(shù)，析構函數(shù)，
//修改函數(shù)Modify(),后處理函數(shù)postprocessor(),主要用來計算下一代的SurvivorsAround.
struct environment
{
individual** p;int m,n,pred;//pred為已經處理了的round數(shù)，在后面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行
///////////////////////////////////////////////////////
//構造人工環(huán)境，人工輸入環(huán)境中每個個體的情況。
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;
}
//計算環(huán)境中的某一個體下一代的生存情況
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;
}
//計算出下一代的情況，并把原環(huán)境改變
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();
}
//環(huán)境的打印函數(shù)
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;
}
}
//生成隨機環(huán)境
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;
}
//////////////////////////////////////////////////////////////////////
// 導讀 //
// 下面屬于計算給定地圖的最大穩(wěn)定容納量部分。 //
// 分為廣度優(yōu)先和深度優(yōu)先兩種方法。 //
// 廣度優(yōu)先從第225行到第333行 //
// 深度優(yōu)先從第336行到第460行 //
//////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
// 這里開始為廣度優(yōu)先搜索 //
////////////////////////////////////////////////////////////
typedef environment DataType;
#include"queue.h"
//由于用到廣度搜索，需要一個隊列，隊列的元素為環(huán)境類型
PLinkQueue Map=createEmptyQueue_link();
//判斷某節(jié)點的狀態(tài)在進程中是否穩(wěn)定
int IsSafe(const environment&a ,int m,int n)
{
return(surviveordie(a,m,n)==a.p[m][n].con);//下一代的情況是否跟原來一樣
}
//round是指從左上角開始數(shù)到round的一個 “_|”形的區(qū)域。
//這個函數(shù)的作用在于按照num的二進制碼來設置這一區(qū)域的狀況
//也就是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;
}
//計算整個環(huán)境最后總存活個數(shù)
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;
}
//小小指數(shù)函數(shù)，求m的n次方
int exp(int m,int n)
{
if(n==0)
return 1;
return m*exp(m,n-1);
}
//判斷環(huán)境中round對應的'_|'形區(qū)域是否穩(wěn)定
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的環(huán)境的最大穩(wě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圈的節(jié)點個數(shù)
{
b=set(a,a.pred+1,i);//把a.pred對應的那個'_|'區(qū)域的各種情況檢查，行得通的入隊
if(CircleSafe(b,a.pred))
{
b.pred=a.pred+1;
if(b.pred==n)//這條路已經走到盡頭，把這種方法能存活的最大人數(shù)計入count
{
if(CircleSafe(b,b.pred)&&count<countsurvivals(b))
count=countsurvivals(b);
continue;
}
enQueue_link(Map,b);
}
}
}
return count;
}
////////////////////////////////////////////////////
// 這里開始為深度優(yōu)先搜索 //
////////////////////////////////////////////////////
struct Mark//環(huán)境狀況的標志字。注意，為了不引起混淆和以后使用方便，這里棄用數(shù)組第0號元素與最后一號元素。
{
Mark(int i)
{
mark=new int[i+2];
for(int j=0;j<=i+1;j++)//注意這里mark[0]與mark[i+1]是不使用的，他們?yōu)镃ircleSafe()湊形式而已
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;//標志字數(shù)組
int n;
};
int IsSafe(const Mark&a,int i,int j)//(1<=i<=n;1<=j<=n)重載IsSafe()函數(shù)，用標志字判斷第i列第j位是否穩(wěn)定
{
int k,l;//i=1的情況在Mark(int)里清零時保證滿足，j=n的情況以二進制的取與方式保證滿足。
//k為周圍人的生存?zhèn)€數(shù)，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列是否全體穩(wěn)定
{
for(int j=1;j<=a.n;j++)
{
if(!IsSafe(a,i,j))
return 0;
}
return 1;
}
int countsurvivals(Mark&a)//從標志數(shù)中數(shù)出環(huán)境的存活量//待優(yōu)化
{
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)//深度優(yōu)先，先根遍歷n叉樹
{
Mark a(n);
int i=1,max=0;//
while(i!=0)//此循環(huán)跳出條件是全樹遍歷完
{
do
{
while(!CollumSafe(a,i))//第i列不穩(wěn)定，調整到第i列穩(wěn)定為止
{
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++;//穩(wěn)定，往下走
}while(i!=n);//跳出條件:i已經遍歷到底，即全環(huán)境除最后一行安全，產生出準可行路徑
//因為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;
}
//////////////
//主函數(shù)部分//
//////////////
void main()
{
cout<<"生命游戲\n\n游戲規(guī)則：\n我們將生命演化放到平面上的正交網(wǎng)格點上。\n a)每個格點有8個鄰點；\n b)如一個格點上有生命，但它的鄰點上只有一個有生命或沒有生命，那么它的下一代因為孤獨而失去生命；\n c)如一個格點上有生命，但它的鄰點上有四個或多于四個有生命，那么它的下一代因為擁擠而失去生命；\n d)如一個格點上有生命，且它的鄰點上有兩個或三個有生命，那么它的下一代有生命；\n e)如一個格點上沒有生命，但它的鄰點上正好有三個有生命，那么它的下一代變成有生命；\n f)所有的生死在同一時間發(fā)生。\n\n";
cout<<"請輸入你想創(chuàng)建的二維環(huán)境的長和寬:";
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<<"以下是最大穩(wěn)定存活問題部分"<<endl;
cout<<"請選擇你要選用的方法，廣度優(yōu)先(1~5)-press'1',深度優(yōu)先(1~6)-press'2'"<<endl;
int s,t;
cin>>t;
cout<<"請輸入要檢索的方陣的階數(shù)："<<endl;
cin>>s;
cout<<s<<"階矩陣最大穩(wěn)定人數(shù): ";
if(t==1)
cout<<BSearch(s)<<endl;
else
cout<<DSearch(s)<<endl;
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -