880版本四阶幻方，我的机器上跑用了34ms

闲来无事，改进改进，多说无益，贴代码，看帖要回帖啊各位

#include < iostream >
#include < time.h >

using namespace std;

struct uni
{
    int a, b, c, d;
};

uni can[1032];
const unsigned long punk = 1UL << 2;
int sum = 0, sum_all = 0;

bool test_4num( int a, int b, int c, int d )
{
    int i;

    for ( i = 0;i <= sum;++i )
    {
        if ( can[i].a == d &&
                can[i].b == c &&
                can[i].c == b &&
                can[i].d == a )
            return false;
    }

    return true;
}

void get_all_num()
{
    for ( int i = 1;i <= 16;++i )
    {
        for ( int j = 1;j <= 16;++j )
        {
            for ( int k = 1; k <= 16; ++k )
            {
                for ( int l = 1;l <= 16;++l )
                {
                    if ( i != j && i != k && i != l && j != k && j != l && k != l && i + j + k + l == 34 && test_4num( i, j, k, l ) )
                    {
                        can[sum].a = i;
                        can[sum].b = j;
                        can[sum].c = k;
                        can[sum].d = l;

                        ++sum;
                    }
                }
            }
        }
    }

    //cout << sum << endl;
}

void p_rint( const int sq[] )
{
    cout << "i wIll gIvE yOu sOme coLoR 2CC! " << sum_all << endl;
    cout << sq[0] << " " << sq[1] << " " << sq[2] << " " << sq[3] << endl;
    cout << sq[4] << " " << sq[5] << " " << sq[6] << " " << sq[7] << endl;
    cout << sq[8] << " " << sq[9] << " " << sq[10] << " " << sq[11] << endl;
    cout << sq[12] << " " << sq[13] << " " << sq[14] << " " << sq[15] << endl << endl;
}

__inline bool fill_in_line( const int c1[], const int c2[] )
{
    int sq[16], k, l;
    unsigned long a, b, c, d;

    sq[0] = c1[0];
    sq[5] = c1[1];
    sq[10] = c1[2];
    sq[15] = c1[3];

    a = punk | ( 1UL << ( sq[0] * 2 ) ) | ( 1UL << ( sq[5] * 2 ) ) | ( 1UL << ( sq[10] * 2 ) ) | ( 1UL << ( sq[15] * 2 ) );

    sq[3] = c2[0];
    sq[6] = c2[1];
    sq[9] = c2[2];
    sq[12] = c2[3];

    b = punk | ( 1UL << ( sq[3] * 2 ) ) | ( 1UL << ( sq[6] * 2 ) ) | ( 1UL << ( sq[9] * 2 ) ) | ( 1UL << ( sq[12] * 2 ) );

    if ( ( a & b ) == punk )
    {
        for ( k = 1;k <= 16;++k )
        {
            sq[4] = k;
            sq[7] = 34 - sq[4] - sq[5] - sq[6];
            sq[11] = 34 - sq[3] - sq[7] - sq[15];
            sq[8] = 34 - sq[9] - sq[10] - sq[11];

            if ( sq[7] > 0 && sq[7] <= 16 && sq[11] > 0 && sq[11] <= 16 && sq[8] > 0 && sq[8] <= 16 &&
                    sq[4] != sq[7] && sq[4] != sq[11] && sq[4] != sq[8] &&
                    sq[7] != sq[11] && sq[7] != sq[8] && sq[11] != sq[8] )
            {
                c = punk | ( 1UL << ( sq[4] * 2 ) ) | ( 1UL << ( sq[7] * 2 ) ) | ( 1UL << ( sq[11] * 2 ) ) | ( 1UL << ( sq[8] * 2 ) );

                if ( ( b & c ) == punk && ( a & c ) == punk )
                {
                    for ( l = 1;l <= 16;++l )
                    {
                        sq[1] = l;
                        sq[13] = 34 - sq[1] - sq[5] - sq[9];
                        sq[14] = 34 - sq[12] - sq[13] - sq[15];
                        sq[2] = 34 - sq[0] - sq[1] - sq[3];

                        if ( sq[13] > 0 && sq[13] <= 16 && sq[14] > 0 && sq[14] <= 16 && sq[2] > 0 && sq[2] <= 16 &&
                                sq[1] != sq[13] && sq[1] != sq[14] && sq[1] != sq[2] &&
                                sq[13] != sq[14] && sq[13] != sq[2] && sq[14] != sq[2] )
                        {
                            d = punk | ( 1UL << ( sq[1] * 2 ) ) | ( 1UL << ( sq[13] * 2 ) ) | ( 1UL << ( sq[14] * 2 ) ) | ( 1UL << ( sq[2] * 2 ) );

                            if ( ( a & d ) == punk && ( b & d ) == punk && ( c & d ) == punk && sq[0] + sq[4] + sq[8] + sq[12] == 34 && sq[2] + sq[6] + sq[10] + sq[14] == 34 )
                            {
                                sum_all++;
                                //p_rint(sq);
                            }
                        }
                    }
                }
            }
        }
    }

    return true;
}

void fill_in_eight()
{
    int cse1[4], cse2[4], i, j;
    unsigned long m, n;

    for ( i = 0;i < sum;i++ )
    {
        for ( j = i + 1;j < sum;j++ )
        {
            m = punk | ( 1UL << ( can[i].a * 2 ) ) | ( 1UL << ( can[i].b * 2 ) ) | ( 1UL << ( can[i].c * 2 ) ) | ( 1UL << ( can[i].d * 2 ) );
            n = punk | ( 1UL << ( can[j].a * 2 ) ) | ( 1UL << ( can[j].b * 2 ) ) | ( 1UL << ( can[j].c * 2 ) ) | ( 1UL << ( can[j].d * 2 ) );

            if ( ( m & n ) == punk )
            {
                cse1[0] = can[i].a;
                cse1[1] = can[i].b;
                cse1[2] = can[i].c;
                cse1[3] = can[i].d;

                cse2[0] = can[j].a;
                cse2[1] = can[j].b;
                cse2[2] = can[j].c;
                cse2[3] = can[j].d;

                fill_in_line( cse1, cse2 );
            }
        }
    }
}

int main()
{
    time_t t;
    get_all_num();


    t = clock();

    fill_in_eight();

    cout << "time consumed: " << clock() - t << " ms" << endl;

    cout << sum_all << endl;
    return 0;
}

 

评论

2 楼 Sing 2008-02-20  

我的机器上大约需要200ms左右,改进的效率还是比较高的

1 楼 stephen 2007-10-10  

不如说明一下你的这个程序在同类程序中算是好的还是坏的？如果是好的，好在什么方面？你这样放代码出来，估计没什么人有兴趣看，除了准备抄作业的之外，:)