论坛首页 → 编程语言技术论坛 →

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

浏览 4578 次
锁定老帖子 主题：880版本四阶幻方，我的机器上跑用了34ms
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • t0uch
  • 等级: 一星会员
  • 性别:
  • 文章: 667
  • 积分: 190
  • 来自: 柳州
   发表时间：2007-10-10  
C++

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

  1. #include < iostream >   
  2. #include < time.h >   
  3.   
  4. using namespace std;   
  5.   
  6. struct uni   
  7. {   
  8.     int a, b, c, d;   
  9. };   
  10.   
  11. uni can[1032];   
  12. const unsigned long punk = 1UL << 2;   
  13. int sum = 0, sum_all = 0;   
  14.   
  15. bool test_4num( int a, int b, int c, int d )   
  16. {   
  17.     int i;   
  18.   
  19.     for ( i = 0;i <= sum;++i )   
  20.     {   
  21.         if ( can[i].a == d &&   
  22.                 can[i].b == c &&   
  23.                 can[i].c == b &&   
  24.                 can[i].d == a )   
  25.             return false;   
  26.     }   
  27.   
  28.     return true;   
  29. }   
  30.   
  31. void get_all_num()   
  32. {   
  33.     for ( int i = 1;i <= 16;++i )   
  34.     {   
  35.         for ( int j = 1;j <= 16;++j )   
  36.         {   
  37.             for ( int k = 1; k <= 16; ++k )   
  38.             {   
  39.                 for ( int l = 1;l <= 16;++l )   
  40.                 {   
  41.                     if ( i != j && i != k && i != l && j != k && j != l && k != l && i + j + k + l == 34 && test_4num( i, j, k, l ) )   
  42.                     {   
  43.                         can[sum].a = i;   
  44.                         can[sum].b = j;   
  45.                         can[sum].c = k;   
  46.                         can[sum].d = l;   
  47.   
  48.                         ++sum;   
  49.                     }   
  50.                 }   
  51.             }   
  52.         }   
  53.     }   
  54.   
  55.     //cout << sum << endl;   
  56. }   
  57.   
  58. void p_rint( const int sq[] )   
  59. {   
  60.     cout << "i wIll gIvE yOu sOme coLoR 2CC! " << sum_all << endl;   
  61.     cout << sq[0] << " " << sq[1] << " " << sq[2] << " " << sq[3] << endl;   
  62.     cout << sq[4] << " " << sq[5] << " " << sq[6] << " " << sq[7] << endl;   
  63.     cout << sq[8] << " " << sq[9] << " " << sq[10] << " " << sq[11] << endl;   
  64.     cout << sq[12] << " " << sq[13] << " " << sq[14] << " " << sq[15] << endl << endl;   
  65. }   
  66.   
  67. __inline bool fill_in_line( const int c1[], const int c2[] )   
  68. {   
  69.     int sq[16], k, l;   
  70.     unsigned long a, b, c, d;   
  71.   
  72.     sq[0] = c1[0];   
  73.     sq[5] = c1[1];   
  74.     sq[10] = c1[2];   
  75.     sq[15] = c1[3];   
  76.   
  77.     a = punk | ( 1UL << ( sq[0] * 2 ) ) | ( 1UL << ( sq[5] * 2 ) ) | ( 1UL << ( sq[10] * 2 ) ) | ( 1UL << ( sq[15] * 2 ) );   
  78.   
  79.     sq[3] = c2[0];   
  80.     sq[6] = c2[1];   
  81.     sq[9] = c2[2];   
  82.     sq[12] = c2[3];   
  83.   
  84.     b = punk | ( 1UL << ( sq[3] * 2 ) ) | ( 1UL << ( sq[6] * 2 ) ) | ( 1UL << ( sq[9] * 2 ) ) | ( 1UL << ( sq[12] * 2 ) );   
  85.   
  86.     if ( ( a & b ) == punk )   
  87.     {   
  88.         for ( k = 1;k <= 16;++k )   
  89.         {   
  90.             sq[4] = k;   
  91.             sq[7] = 34 - sq[4] - sq[5] - sq[6];   
  92.             sq[11] = 34 - sq[3] - sq[7] - sq[15];   
  93.             sq[8] = 34 - sq[9] - sq[10] - sq[11];   
  94.   
  95.             if ( sq[7] > 0 && sq[7] <= 16 && sq[11] > 0 && sq[11] <= 16 && sq[8] > 0 && sq[8] <= 16 &&   
  96.                     sq[4] != sq[7] && sq[4] != sq[11] && sq[4] != sq[8] &&   
  97.                     sq[7] != sq[11] && sq[7] != sq[8] && sq[11] != sq[8] )   
  98.             {   
  99.                 c = punk | ( 1UL << ( sq[4] * 2 ) ) | ( 1UL << ( sq[7] * 2 ) ) | ( 1UL << ( sq[11] * 2 ) ) | ( 1UL << ( sq[8] * 2 ) );   
  100.   
  101.                 if ( ( b & c ) == punk && ( a & c ) == punk )   
  102.                 {   
  103.                     for ( l = 1;l <= 16;++l )   
  104.                     {   
  105.                         sq[1] = l;   
  106.                         sq[13] = 34 - sq[1] - sq[5] - sq[9];   
  107.                         sq[14] = 34 - sq[12] - sq[13] - sq[15];   
  108.                         sq[2] = 34 - sq[0] - sq[1] - sq[3];   
  109.   
  110.                         if ( sq[13] > 0 && sq[13] <= 16 && sq[14] > 0 && sq[14] <= 16 && sq[2] > 0 && sq[2] <= 16 &&   
  111.                                 sq[1] != sq[13] && sq[1] != sq[14] && sq[1] != sq[2] &&   
  112.                                 sq[13] != sq[14] && sq[13] != sq[2] && sq[14] != sq[2] )   
  113.                         {   
  114.                             d = punk | ( 1UL << ( sq[1] * 2 ) ) | ( 1UL << ( sq[13] * 2 ) ) | ( 1UL << ( sq[14] * 2 ) ) | ( 1UL << ( sq[2] * 2 ) );   
  115.   
  116.                             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 )   
  117.                             {   
  118.                                 sum_all++;   
  119.                                 //p_rint(sq);   
  120.                             }   
  121.                         }   
  122.                     }   
  123.                 }   
  124.             }   
  125.         }   
  126.     }   
  127.   
  128.     return true;   
  129. }   
  130.   
  131. void fill_in_eight()   
  132. {   
  133.     int cse1[4], cse2[4], i, j;   
  134.     unsigned long m, n;   
  135.   
  136.     for ( i = 0;i < sum;i++ )   
  137.     {   
  138.         for ( j = i + 1;j < sum;j++ )   
  139.         {   
  140.             m = punk | ( 1UL << ( can[i].a * 2 ) ) | ( 1UL << ( can[i].b * 2 ) ) | ( 1UL << ( can[i].c * 2 ) ) | ( 1UL << ( can[i].d * 2 ) );   
  141.             n = punk | ( 1UL << ( can[j].a * 2 ) ) | ( 1UL << ( can[j].b * 2 ) ) | ( 1UL << ( can[j].c * 2 ) ) | ( 1UL << ( can[j].d * 2 ) );   
  142.   
  143.             if ( ( m & n ) == punk )   
  144.             {   
  145.                 cse1[0] = can[i].a;   
  146.                 cse1[1] = can[i].b;   
  147.                 cse1[2] = can[i].c;   
  148.                 cse1[3] = can[i].d;   
  149.   
  150.                 cse2[0] = can[j].a;   
  151.                 cse2[1] = can[j].b;   
  152.                 cse2[2] = can[j].c;   
  153.                 cse2[3] = can[j].d;   
  154.   
  155.                 fill_in_line( cse1, cse2 );   
  156.             }   
  157.         }   
  158.     }   
  159. }   
  160.   
  161. int main()   
  162. {   
  163.     time_t t;   
  164.     get_all_num();   
  165.   
  166.     
  167.     t = clock();   
  168.   
  169.     fill_in_eight();   
  170.   
  171.     cout << "time consumed: " << clock() - t << " ms" << endl;   
  172.        
  173.     cout << sum_all << endl;   
  174.     return 0;   
  175. }   

 
返回顶楼
         
  • stephen
  • 等级: 二星会员
  • 性别:
  • 文章: 56
  • 积分: 216
   发表时间：2007-10-10  
不如说明一下你的这个程序在同类程序中算是好的还是坏的？如果是好的，好在什么方面？你这样放代码出来，估计没什么人有兴趣看，除了准备抄作业的之外，:)
返回顶楼
          回帖地址
0 请登录后投票
  • Sing
  • 等级: 初级会员
  • 性别:
  • 文章: 31
  • 积分: 90
  • 来自: 北京
   发表时间：2008-02-20  
我的机器上大约需要200ms左右,改进的效率还是比较高的
返回顶楼
          回帖地址
0 请登录后投票
论坛首页 → 编程语言技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics