C语言递归算法实现6阶所有幻方（未排除旋转反射等对称情况），求优化程序，提高执行效率
#include <stdio.h> static int flag[37];
static int tmax3[4] = {0,34,35,36};
static int tmin3[4] = {0,1,2,3};
static int tmax2[3] = {0,35,36};
static int tmin2[3] = {0,1,2};
inline void Swap(int& a, int& b)
{// 交换a和b
int temp = a;
a = b;
b = temp;
}
int f_min2(int k)
{//找到36个数中最小的两个
int i, s[3];
if(k<=tmin2[1])
s[0] = k, s[1] = tmin2[1], s[2] = tmin2[2];
else if(k<=tmin2[2])
s[0] = tmin2[1], s[1] = k, s[2] = tmin2[2];
else
s[0] = tmin2[1], s[1] = tmin2[2], s[2] = k;
int j;
for(i=0,j=1;i<3;i++)
{
if(!flag[s[i]])
{
tmin2[j++] = s[i];
if(j==3 && tmin2[2] != tmin2[1])
{
return 1;
}
}
}
for(i=tmin2[2]+1;i<37;i++)
{
if(!flag[i])
{
tmin2[2] = i;
return 1;
}
}
return 0;
}
int f_max2(int k)
{//找到36个数中最大的两个
int i, s[3];
//升序
if(k<=tmax2[1])
s[0] = k, s[1] = tmax2[1], s[2] = tmax2[2];
else if(k<=tmax2[2])
s[0] = tmax2[1], s[1] = k, s[2] = tmax2[2];
else
s[0] = tmax2[1], s[1] = tmax2[2], s[2] = k;
int j;
//由大到小找未用过的数，至少能找到一个（需分析）
for(i=2,j=2;i>0;i--)
{
if(!flag[s[i]])
{
tmax2[j--] = s[i];
//已经找到了两个
if(j==0 && tmax2[2] != tmax2[1])
{
return 1;
}
}
}
//继续找下一个数
for(i=tmax2[1]-1;i>0;i--)
{
if(!flag[i])
{
tmax2[1] = i;
return 1;
}
}
return 0;
}
int f_min3()
{//找到36个数中最小的三个
int i;
tmin3[1] = tmin2[1];
tmin3[2] = tmin2[2];
for(i=tmin2[2]+1; i<37; i++)
{
if(flag[i] == 0)
{
tmin3[3] = i;
return 1;
}
}
return 0;
}
int f_max3()
{//找到36个数中最大的三个
int i;
tmax3[3] = tmax2[3];
tmax3[2] = tmax2[2];
for(i=tmax2[1]-1; i>0; i--)
{
if(flag[i] == 0)
{
tmax3[1] = i;
return 1;
}
}
return 0;
}
int f_sum6(int a1,int a2,int a3,int a4,int a5,int a6)
{//6个数的和为111
if(a1+a2+a3+a4+a5+a6 == 111)
return 0;
else
return 1;
}
int f_3c(int a,int b,int c)
{//三个数的和 + 剩余的数中的三个的最大的和 小于111 或 ...
if(a+b+c+tmax3[3]+tmax3[1]+tmax3[2]<111 || a+b+c+tmin3[1]+tmin3[2]+tmin3[3]>111)
return 1;
else
return 0;
}
int f_4c(int a,int b,int c,int d)
{
if(a+b+c+d+tmax2[1]+tmax2[2]<111 || a+b+c+d+tmin2[1]+tmin2[2]>111)
return 1;
else
return 0;
}
int f_5c(int a,int b,int c,int d,int e)
{
if(a+b+c+d+e<75 || a+b+c+d+e>110)
return 1;
else
return 0;
}
void magic_6_r(int s[], int k, int m,FILE *fid)
{ //生成s [k：m ]的所有排列方式
int i;
int test;
if (k == m && f_sum6(s[3],s[31],s[20],s[13],s[33],s[35])==0 && f_sum6(s[4],s[32],s[14],s[23],s[34],s[36])==0)
{//输出一个排列方式
for (i = 1; i <= 6; i++)
{
fprintf(fid,"%d\t",s[i]);
}
fprintf(fid,"\n");
fprintf(fid,"%d\t%d\t%d\t%d\t%d\t%d\t\n",s[7],s[16],s[31],s[32],s[15],s[30]);
fprintf(fid,"%d\t%d\t%d\t%d\t%d\t%d\t\n",s[8],s[17],s[20],s[14],s[21],s[22]);
fprintf(fid,"%d\t%d\t%d\t%d\t%d\t%d\t\n",s[9],s[18],s[13],s[23],s[24],s[25]);
fprintf(fid,"%d\t%d\t%d\t%d\t%d\t%d\t\n",s[10],s[12],s[33],s[34],s[26],s[29]);
fprintf(fid,"%d\t%d\t%d\t%d\t%d\t%d\t\n",s[11],s[19],s[35],s[36],s[27],s[28]);
fprintf(fid,"\n");
}
else // s[k：m ]有多个排列方式
// 递归地产生这些排列方式
if((k==5) & f_4c(s[1],s[2],s[3],s[4]));
else if((k==6) & f_5c(s[5],s[1],s[2],s[3],s[4]));
else if((k==7) & f_sum6(s[6],s[1],s[2],s[3],s[4],s[5]));
else if((k==9) & f_3c(s[1],s[7],s[8]));
else if((k==10) & f_4c(s[1],s[9],s[7],s[8]));
else if((k==11) & f_5c(s[1],s[10],s[7],s[8],s[9]));
else if((k==12) & f_sum6(s[1],s[11],s[7],s[8],s[9],s[10]));
else if((k==13) & f_3c(s[6],s[11],s[12]));
else if((k==14) & (f_4c(s[11],s[12],s[13],s[6])));
else if((k==15) & f_5c(s[6],s[14],s[12],s[13],s[11]));
else if((k==16) & f_sum6(s[6],s[14],s[12],s[13],s[11],s[15]));
else if((k==17) & f_3c(s[2],s[16],s[12]));
else if((k==18) & f_4c(s[2],s[12],s[16],s[17]));
else if((k==19) & (f_5c(s[2],s[12],s[16],s[17],s[18])));
else if((k==20) & f_sum6(s[2],s[12],s[16],s[17],s[18],s[19]));
else if((k==21) & (f_3c(s[8],s[20],s[17]) || f_3c(s[1],s[16],s[20]) || f_3c(s[3],s[13],s[20]) || f_4c(s[8],s[17],s[14],s[20])));
else if((k==22) & (f_3c(s[5],s[15],s[21]) || f_5c(s[8],s[17],s[20],s[14],s[21])));
else if((k==23) & (f_sum6(s[8],s[17],s[20],s[14],s[21],s[22])));
else if((k==24) & (f_3c(s[4],s[14],s[23]) || f_4c(s[1],s[16],s[20],s[23])||f_4c(s[9],s[18],s[13],s[23])));
else if((k==25) & (f_4c(s[5],s[15],s[21],s[24])||f_5c(s[9],s[18],s[13],s[23],s[24])));
else if((k==26) & f_sum6(s[9],s[18],s[13],s[23],s[24],s[25]));
else if((k==27) & (f_5c(s[1],s[16],s[20],s[23],s[26]) || f_5c(s[5],s[15],s[21],s[24],s[26]) || f_3c(s[10],s[12],s[26])));
else if((k==28) & (f_sum6(s[5],s[15],s[21],s[24],s[26],s[27]) ||f_3c(s[11],s[19],s[27])));
else if((k==29) & (f_4c(s[6],s[22],s[25],s[28]) || f_4c(s[11],s[19],s[28],s[27]) || f_sum6(s[1],s[16],s[20],s[23],s[26],s[28])));
else if((k==30) & (f_4c(s[10],s[12],s[26],s[29]) || f_5c(s[6],s[22],s[25],s[28],s[29])));
else if((k==31) & (f_sum6(s[6],s[22],s[25],s[28],s[30],s[29])|| f_4c(s[7],s[16],s[15],s[30])));
else if((k==32) & (f_4c(s[3],s[31],s[20],s[13]) || f_5c(s[7],s[16],s[31],s[15],s[30])));
else if((k==33) & (f_sum6(s[7],s[16],s[31],s[15],s[30],s[32]) || f_4c(s[4],s[32],s[14],s[23])));
else if((k==34) & (f_5c(s[10],s[12],s[26],s[29],s[33]) || f_5c(s[3],s[31],s[20],s[13],s[33])));
else if((k==35) & f_sum6(s[10],s[12],s[26],s[29],s[33],s[34]));
else
for (i=k; i <= m; i++)
{
{
Swap (s[k], s[i]);
flag[s[k]] = 1;
f_min2(s[i]);
f_max2(s[i]);
f_min3();
f_max3();
magic_6_r(s, k+1, m,fid);
Swap (s[k], s[i]);
flag[s[i]] = 0;
f_min2(s[i]);
f_max2(s[i]);
f_min3();
f_max3();
}
}
}
int main()
{
FILE *fid = fopen("六阶幻方__递归算法.txt","w");
int s[37];
int i;
for(i=0;i<37;i++)
s[i] = i;
magic_6_r(s, 1, 36,fid);
fclose(fid);
return 0;
}
[ 本帖最后由 li5683li 于 2012-2-22 14:33 编辑 ]
