#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

void main()
{
	int i,j,k,a,b,c;//計數器
	int n0;//初始pool size
	float recom, mutate;//初始化雜交率，變異率
	int reco[40];//雜交緩存
	int seq[][40];
	int select[][40];
	float fit[];//每個序列的適配值
	float sigmafit,;//適配值之和
	float selecton;//輪盤賭上的小球，選擇子
	int sat;//滿足全部條件的解的個數
	//設置初始pool個體數目//
	cout<<"Input the size of initial pool: ";
	cin>>n0;
	cout<<"Input the recombination rate: ";
	cin>>recom;
	cout<<"Input the mutation rate: ";
	cin>>mutate;

	//設置所有初始解//
	srand((unsigned)time(NULL));
	for(i=0; i<n0; i++)
	{
		for(j=0;j<40;j++)
		{
			seq[i][j]=rand()%2;
		}
	}
	/******************************************開始計算*************************************************/
loop:
	//step1.計算所有解的適配值//
	for(i=0;i<n0;i++)
	{
		k=(1-(1-seq[i][0])*(1-seq[i][1])*(1-seq[i][2]))+(1-seq[i][0]*seq[i][1]*(1-seq[i][2]))+(1-(1-seq[i][0])*seq[i][1]*(1-seq[i][2]))+(1-seq[i][0]*(1-seq[i][1])*(1-seq[i][2]))+(1-(1-seq[i][0])*(1-seq[i][1])*seq[i][2])+(1-(1-seq[i][0])*seq[i][1]*seq[i][2])+(1-seq[i][0]*(1-seq[i][1])*seq[i][2])
			for(j=3;j<40;j++)
			{
				k++=1-seq[i][j-2]*seq[i][j-1]*(1-seq[i][j]);
			}
			fit[i]=k;
	}
	//
	//計算歸一化適配值,并令每個適配值疊加前一項
	
	sigmafit=0;
	for(i=0;i<n0;i++)
	{
		sigmafit+=fit[i];
	}

	fit[0]=fit[0]/sigmafit;

	for(i=1;i<n0;i++)
	{
		fit[i]=fit[i]/sigmafit+fit[i-1];
	}

	//根據適配值的大小進行選擇，被選擇的概率和適配值大小成正比
	for(k=0;k<n0;k++)
	{
		selecton=rand()/32767;
		for(i=0;i<n0;k++)
		{
			if(selecton<=fit[i])
			{
				for(j=0;j<40;j++)
				{
					select[k][j]=seq[i][j];
				}
			}
		}
		
	}
	//將選擇產物進行判斷，若滿足全部條件的解超過1000條，則停止計算，否則雜交變異
	sat=0;
    for(i=0;i<n0;i++)
	{
		k=(1-(1-seq[i][0])*(1-seq[i][1])*(1-seq[i][2]))+(1-seq[i][0]*seq[i][1]*(1-seq[i][2]))+(1-(1-seq[i][0])*seq[i][1]*(1-seq[i][2]))+(1-seq[i][0]*(1-seq[i][1])*(1-seq[i][2]))+(1-(1-seq[i][0])*(1-seq[i][1])*seq[i][2])+(1-(1-seq[i][0])*seq[i][1]*seq[i][2])+(1-seq[i][0]*(1-seq[i][1])*seq[i][2])
			for(j=3;j<40;j++)
			{
				k++=1-seq[i][j-2]*seq[i][j-1]*(1-seq[i][j]);
			}
			fit[i]=k;
			if(fit[i]=46)
			{
				sat++;
			}
	}
	if(sat<1000)//判斷是否有足夠的滿足所有條件的解：沒有，進行雜交變異
	{
		for(k=0;k<recom*n0;k++)
		{
			a=rand()/32767*n0;
			b=rand()/32767*n0;
			c=rand()/32767*40;
			for(j=c;j<40;j++)
			{
				reco[j]=select[b][j];
				select[b][j]=select[a][j];
				select[a][j]=reco[j];
			}
		}//雜交完成
		
		for(k=0;k<mutate*n0;k++)
		{
			a=rand()/32767*n0;
			b=rand()/40;
			select[a][b]=1-select[a][b];
		}//變異完成

		goto loop;
	}
}