/*    Copyright (C) 2010  zerob13 <zerob13@gmail.com> */
#include <iostream>
#include<time.h>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
using namespace std;
#define MAXNUM 1023;//种群范围
#define NUMLEN 10//种群编码长度
#define	STNUM 200//种群个体数目
#define PC 0.007//变异率
#define AGE 100//迭代种群代数
double Fsun;//储存所有值的和
void itoa(int a,int ans[])//输入整数a，和数组ans，然后，a的二进制会存放在ans里。（当然你也可以直接用系统自带的itoa)
{
	int i,j;
	int co=0;
	while(a!=1&&a){
		ans[co++]=a%2;
		a/=2;
	}
	if(a)
	{
		ans[co++]=1;
	}
	for(i=0,j=NUMLEN-1;i<j;j--,i++)
	{
		ans[i]^=ans[j];
		ans[j]^=ans[i];
		ans[i]^=ans[j];
	}
}
 
int atoi2(int ans[])//输入二进制数组返回整数值 如数组ans[]={0,0,0,0,0,1,0,1}，就会返回5
{
	int an=0,i;
	for(i=0;i<NUMLEN;i++)
	{
		an+=ans[i]*(1<<(NUMLEN-1-i));
	}
	return an;
}
 
void getrand(int ra[])//获取1~MAXNUM的随机初始种群 放在你输入的数组ra[]中
{
 
	srand(time(NULL));
	for(int i=0;i<STNUM;i++)
	{
		ra[i]=1+rand()%MAXNUM;
	}		
}
 
void getP(double P[])//获取0~1随机数 放在你输入的数组P[]中，作为选择概率用
{
	srand(time(NULL));
	for(int i=0;i<STNUM;i++)
	{
		P[i]=double(rand()%10000)/10000.0;
	}
 
 
}
 
int getValue(int va)//获取适应度
{
	return va*va;
}
 
double getchoseP(int va)//获取选择概率
{
	return (double)va/Fsun;
}
 
void creatAP(double P[],double AP[])//获取积累概率
{
	int i,j;
	for(i=0;i<STNUM;i++)
	{
		AP[i]=0.0;
		for(j=0;j<=i;j++)
		{
			AP[i]+=P[j];
		}
	}
	return ;
}
 
int getPcNum()//获取变异位数
{
	return (int)(PC*NUMLEN*STNUM);
}
 
void Exchange(int ans[STNUM][NUMLEN])//交叉运算
{
	int i,j,k,c;
	k=getPcNum();
	for(i=0;i<STNUM-1;i+=2)
	{
		for(j=NUMLEN-5;j<NUMLEN;j++)
		{
			ans[i][j]^=ans[i+1][j];
			ans[i+1][j]^=ans[i][j];
			ans[i][j]^=ans[i+1][j];
		}
 
 
	}
	while(k--){		
		c=rand()%(NUMLEN*STNUM);
		ans[c/NUMLEN][c%STNUM]^=1;
 
	}
 
 
	return ;
}
 
int main (int argc, char * const argv[]) {
 
	int ans[STNUM][NUMLEN];
	int ra[STNUM];
	int rb[STNUM];
	int i,j;
	double P[STNUM];
	double AP[STNUM];
	double Cp[STNUM];
	int maxx,maxn;
	int flag=0;
	memset(ans,0,sizeof(ans));
	for(Fsun=0,i=1;i<512;i++)
	{
		Fsun+=getValue(i);
	}
	maxx=0;
	maxn=0;
	getrand(ra);
	for(i=0;i<STNUM;i++){
 
		if(maxx<getValue(ra[i]))
		{
			maxx=getValue(ra[i]);
			maxn=ra[i];
		}
 
	}
 
	while(flag<AGE)
	{
		flag++;
		for(i=0;i<STNUM;i++)
		{
			Cp[i]=getchoseP(getValue(ra[i]));
		}
		creatAP(Cp,AP);
		getP(P);
		for(i=0;i<STNUM;i++)
		{
			for(j=0;j<STNUM;j++)
			{
				if(j==0)
				{
					if(P[i]<=AP[j])
					{
						rb[i]=ra[j];
						break;
					}
				}else {
					if(P[i]<=AP[j]&&P[i]>AP[j-1]){
 
							rb[i]=ra[j];
							break;
						}
				}
 
			}
			itoa(rb[i],ans[i]);
		}
 
		Exchange(ans);
		for(i=0;i<STNUM;i++)
		{
			ra[i]=atoi2(ans[i]);
 
			if(getValue(ra[i])>maxx)
			{
				flag=0;
				maxn=ra[i];
				maxx=getValue(ra[i]);
			}
		}
	}
	printf("%d\n",maxn);
 
    return 0;
}