随机算法

``````a a a a b
a a a a b
...
a a a a b
c c c c d``````

``````#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>

using namespace std;

bool IsSquare( int a)
{
int k = (int)sqrt(a);
if( k*k == a )  return 1;
return 0;
}

int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)){
int a,b,c,d;
while( 2 > 1 ) {
a = rand()%100 + 1;
b = rand()%100 + 1;
c = rand()%100 + 1;
d = rand()%100 + 1;
int s1 = (m-1)*a*a + b*b;
int s2 = (n-1)*a*a + c*c;
int s3 = (m-1)*c*c + d*d;
int s4 = (n-1)*b*b + d*d;
if( IsSquare( s1 ) && IsSquare( s2 ) &&
IsSquare( s3 ) && IsSquare( s4 ) )
{
break;
}
}

for(int i=0;i<n-1;i++){
for(int j=0;j<m-1;j++) printf("%d ",a);
printf("%d\n",b);
}
for(int j=0;j<m-1;j++) printf("%d ",c);
printf("%d\n",d);
}
return 0;
}``````

模拟退火算法

``````#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const double eps=1e-7,INF=1e99;  // T: 初始温度  delta：下降速率
const double T=10,delta=0.88;    //一般地，T=100, delta=0.98
const int N=5e2+10;

struct point{
double x,y;
}p[N],s;

double dis(point a,point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double solve(int n){
s=p[0];
double t=T;
double r=INF;
while(t>eps){
int k=0;
double d=0;
for(int i=0;i<n;i++){
double f=dis(s,p[i]);
if(f>d){
d=f;
k=i;
}
}
s.x+=(p[k].x-s.x)/d*t;
s.y+=(p[k].y-s.y)/d*t;
r=min(r,d);
t*=delta;
}
return r;
}

int main()
{
int n;
while(~scanf("%d",&n)&&n){
for(int i=0;i<n;i++){
scanf("%lf %lf",&p[i].x,&p[i].y);
}
double r=solve(n);
printf("%.2lf %.2lf %.2lf\n",s.x,s.y,r);
}
return 0;
}``````

0 0 vote
Article Rating
Subscribe
Notify of