📄 roman.cpp
字号:
#include <stdio.h>
#include <string.h>
#include <stddef.h>
#define Max_V_Num 500
#define Max_E_Num 4000
int test=0;
main()
{
int i,j,l,v[Max_V_Num],sm[Max_V_Num],k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12,k13,k14,k15,k16,k17,k18,k19,k20,k21,k22,k23,k24,k25,k26,k27,k28,k29,k30,k31,k32,k33,k34,k35,k36,k37,k38,k39,k40,
state[Max_V_Num][4],adjv[Max_V_Num][4],result[Max_V_Num],segnum,n,mod,k,segrn,p,q,tm[Max_V_Num];
double re[Max_V_Num],rn,totalrn,check;
char ma[10];
k=2;
sprintf(ma,"pn%d",k);
printf("ma=%s\n",ma);
for(n=25;n<=100;n++)
{
q=-1;
sm[0]=0;
for(i=1;i<=2*n;i++)
{
sm[i]=0;
re[i]=1;
}
if(k==2)
{
mod=7;
segrn=8;
segnum=n/mod;
if(n%mod==0)rn=segnum*segrn;
else if(n%mod==1) rn=segnum*segrn+2;
else if(n%mod==2) rn=segnum*segrn+3;
else if(n%mod==3) rn=segnum*segrn+4;
else if(n%mod==4) rn=segnum*segrn+5;
else if(n%mod==5) rn=segnum*segrn+6;
else if(n%mod==6) rn=segnum*segrn+7;
rn+=1;
}//if(k==2)
if(k==3)
{
mod=4;
segrn=4;
segnum=n/mod;
if(n%mod==0)rn=segnum*segrn+1;
else if(n%mod==1) rn=segnum*segrn+5;
else if(n%mod==2) rn=segnum*segrn+5;
else if(n%mod==3) rn=segnum*segrn+5;
}
else
rn=2*n;
//构造pn2存储方法
for(i=1;i<=2*n;i++)
{
if(i%2==1)
{
adjv[i][0]=i;
j=i-2;
if(j<=0)j+=2*n;
adjv[i][1]=j;
adjv[i][2]=i+1;
j=i+2;
if(j>2*n)j-=2*n;
adjv[i][3]=j;
}//if(i%2==1)
else
{
adjv[i][0]=i;
j=i-2*k;
if(j<=0)j+=2*n;
adjv[i][1]=j;
adjv[i][2]=i-1;
j=i+2*k;
if(j>2*n)j-=2*n;
adjv[i][3]=j;
}//else
}//for(i=1;i<=2*n;i++)
v[0]=1;
tm[1]=1;
for(j=0;j<4;j++)
{
p=adjv[1][j];
state[1][j]=sm[p];
if(sm[p])
{
re[p]+=0.5;
}
else
{
re[p]-=0.5;
sm[p]=1;
}
}//for(j=0;j<4;j++)
l=1;
j=v[l-1];
j++;
totalrn=0;
for(i=1;i<=2*n;i++)
{
totalrn=totalrn+re[i];
}//for(i=1;i<=2*n;i++)
if(totalrn<rn)
{
rn=totalrn;
q=l-1;
for(i=0;i<=q;i++)
result[i]=v[i];
}
//开始运算
do{
if(j<=2*n)
{
if(j%2==1)
{
k1=j;
k2=j-2;if(k2<=0)k2+=2*n;
k3=j+1;
/* k4=j+1;
k5=j-2;if(k5<=0)k5+=2*n;
k6=j+1;
k1=j-4;if(k1<=0) k1+=2*n;
k2=j-2;if(k2<=0) k2+=2*n;
k3=j-2;if(k3<=0) k3+=2*n;
k4=j-1;if(k4<=0) k4+=2*n;
k5=j-2;if(k5<=0) k5+=2*n;
k6=j-6;if(k6<=0) k6+=2*n;
k7=j-4;if(k7<=0) k7+=2*n;
k8=j-6;if(k8<=0) k8+=2*n;
k9=j-2;if(k9<=0) k9+=2*n;
k10=j-3;if(k10<=0) k10+=2*n;
k11=j-3;if(k11<=0) k11+=2*n;
k12=j-4;if(k12<=0) k12+=2*n;
k13=j-2;if(k13<=0) k13+=2*n;
k14=j-1-2*k;if(k14<=0) k14+=2*n;
k15=j-1;if(k15<=0) k15+=2*n;
k16=j-1-2*k;if(k16<=0) k16+=2*n;
k17=0;
k18=0;
k19=0;
k20=0;
k21=0;
k22=0;
k23=0;
k24=0;
k25=0;
k26=0;
k27=0;
k28=0;
k29=0;
k30=0;*/
}//if(j%2==1)
else
{
k1=j-2*k;if(k1<=0) k1+=2*n;
k2=j;
k3=j-1;if(k3<=0) k3+=2*n;;
/* k4=j-1;if(k4<=0) k4+=2*n;
k5=j;
k6=j-1;if(k6<=0) k6+=2*n;
k1=j-1;if(k1<=0) k1+=2*n;
k2=j-3;if(k2<=0) k2+=2*n;
k3=j-2*k;if(k3<=0) k3+=2*n;
k4=j-1;if(k4<=0) k4+=2*n;
k5=j-2*k;if(k5<=0) k5+=2*n;
k6=j-2*k-1;if(k6<=0) k6+=2*n;
k7=j-2*k;if(k7<=0) k7+=2*n;
k8=j-4*k;if(k8<=0) k8+=2*n;
k9=j-2*k;if(k9<=0) k9+=2*n;
k10=j-6*k;if(k10<=0) k10+=2*n;
k11=j-4*k;if(k11<=0) k11+=2*n;
k12=j-6*k;if(k12<=0) k12+=2*n;
k13=j-2*k;if(k13<=0) k13+=2*n;
k14=j-4*k-1;if(k14<=0) k14+=2*n;
k15=j-4*k;if(k15<=0) k15+=2*n;
k16=j-4*k-1;if(k16<=0) k16+=2*n;
k17=j-2*k;if(k17<=0) k17+=2*n;
k18=j-2*k-3;if(k18<=0) k18+=2*n;
k19=j-2*k-1;if(k19<=0) k19+=2*n;
k20=j-2*k-3;if(k20<=0) k20+=2*n;
k21=j-1;if(k21<=0) k21+=2*n;
k22=j-2;if(k22<=0) k22+=2*n;
k23=j-2;if(k23<=0) k23+=2*n;
k24=j-3;if(k24<=0) k24+=2*n;
k25=j-1;if(k25<=0) k25+=2*n;
k26=j-5;if(k26<=0) k26+=2*n;
k27=j-3;if(k27<=0) k27+=2*n;
k28=j-5;if(k28<=0) k28+=2*n;
k29=j-1;if(k29<=0) k29+=2*n;
k30=j-4*k;if(k30<=0) k30+=2*n;*/
}//if(j%2==1)
// printf("result=%d\t",!((sm[k1]&&sm[k2])||(sm[k3]&&sm[k4])||(sm[k5]&&sm[k6])));
// printf("j=%d,k1=%d,k2=%d,k3=%d,k4=%d,k5=%d,k6=%d,sm[k1]=%d,sm[k2]=%d,sm[k3]=%d,sm[k4]=%d,sm[k5]=%d,sm[k6]=%d,",j,k1,k2,k3,k4,k5,k6,sm[k1],sm[k2],sm[k3],sm[k4],sm[k5],sm[k6]);
// if(!((tm[k1]&&tm[k2])||(tm[k3]&&tm[k4])||(tm[k5]&&tm[k6])||(tm[k7]&&tm[k8])||(tm[k9]&&tm[k10])||(tm[k11]&&tm[k12])||(tm[k13]&&tm[k14])||(tm[k15]&&tm[k16])||(tm[k17]&&tm[k18])||(tm[k19]&&tm[k20])||(tm[k21]&&tm[k22])||(tm[k23]&&tm[k24])||(tm[k25]&&tm[k26])||(tm[k27]&&tm[k28])||(tm[k29]&&tm[k30])))
if( (sm[k1]+sm[k2]+sm[k3])<2 )
{
// tm[j]=1;
for(i=0;i<4;i++)
{
p=adjv[j][i];
state[j][i]=sm[p];
if(sm[p])
{
re[p]+=0.5;
}
else
{
re[p]-=0.5;
sm[p]=1;
}
}//for(j=0;j<4;j++)
v[l++]=j;
//计算罗马数
totalrn=0;
check=0;
for(i=1;i<=2*n;i++)
{
totalrn+=re[i];
if(sm[i])
check+=re[i];
else
check+=0.5;
}//for(i=1;i<=2*n;i++)
if(totalrn<rn)
{
rn=totalrn;
q=l-1;
for(i=0;i<=q;i++)
result[i]=v[i];
}
if(check>=rn)
{
j=v[--l];
for(i=0;i<4;i++)
{
p=adjv[j][i];
sm[p]=state[j][i];
if(sm[p])
{
re[p]-=0.5;
}
else
{
re[p]+=0.5;
}
}//for(j=0;j<4;j++)
// tm[j]=0;
}
// printf("true\n\n");
}//if(!((sm[k1]&&sm[k2])||(sm[k3]&&sm[k4])||(sm[k5]&&sm[k6])))//||(sm[k7]&&sm[k8])||(sm[k9]&&sm[k10])||(sm[k11]&&sm[k12])||(sm[k13]&&sm[k14])||(sm[k15]&&sm[k16])||(sm[k17]&&sm[k18])||(sm[k19]&&sm[k20])||(sm[k21]&&sm[k22])||(sm[k23]&&sm[k24])||(sm[k25]&&sm[k26])||(sm[k27]&&sm[k28])||(sm[k29]&&sm[k30])))
// else
// {
// printf("false\n\n");
// }
j++;
}//if(j<=2*n)
else
{
j=v[--l];
for(i=0;i<4;i++)
{
p=adjv[j][i];
sm[p]=state[j][i];
if(sm[p])
{
re[p]-=0.5;
}
else
{
re[p]+=0.5;
}
}//for(j=0;j<4;j++)
// tm[j]=0;
j++;
}//if(j<=2*n) else
}while(l>0);
printf("n=%d\trm=%f\n",n,rn);
for(i=0;i<=q;i++)
{
printf("%d\t",result[i]);
}
printf("\n");
}//for(n=2*k+1;n<100;n++)
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -