| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 559 人关注过本帖
标题:C语言递归算法实现6阶所有幻方(未排除旋转反射等对称情况),求优化程序, ...
只看楼主 加入收藏
li5683li
Rank: 2
等 级:论坛游民
帖 子:12
专家分:13
注 册:2010-4-12
结帖率:50%
收藏
已结贴  问题点数:20 回复次数:3 
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 编辑 ]
搜索更多相关主题的帖子: 算法 旋转 include C语言 
2012-02-22 02:41
zxd675816777
Rank: 7Rank: 7Rank: 7
等 级:黑侠
帖 子:252
专家分:631
注 册:2012-2-3
收藏
得分:14 
哇塞。。。题目大概贴一下咯

数学好难!
2012-02-23 21:29
li5683li
Rank: 2
等 级:论坛游民
帖 子:12
专家分:13
注 册:2010-4-12
收藏
得分:0 
回复 2楼 zxd675816777
6乘6共36个方格,填入1至36这36个数,不许重复,使6横行、6竖行及2对角线的六个数的和分别相等,这是一个数学问题,在数学上叫六阶幻方
2012-02-24 18:57
li5683li
Rank: 2
等 级:论坛游民
帖 子:12
专家分:13
注 册:2010-4-12
收藏
得分:0 
想求出所有解是不可能的,因为有上亿种解。问题是快速地尽可能多的输出符合条件的解,我想这应该需要数据结构及算法的知识,在此求助……
2012-02-24 19:01
快速回复:C语言递归算法实现6阶所有幻方(未排除旋转反射等对称情况),求优化程 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030465 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved