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

四阶幻方 v1.1 向2064ms进发

浏览 3944 次
锁定老帖子 主题：四阶幻方 v1.1 向2064ms进发
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • t0uch
  • 等级: 一星会员
  • 性别:
  • 文章: 667
  • 积分: 190
  • 来自: 柳州
   发表时间：2007-08-24  
C++
改进了一下程序，在我的p4 3.2上以2064ms运算完7040个
到此告一段落，880的版本不想写了，麻烦，研究一下五阶的，好像好复杂。371993326789901217467999448150835200000000个组合，呼呼。

开头的两个include 是iostream 和time.h，万恶的代码显示器

cpp 代码
 
  1. #include   
  2. #include   
  3.   
  4. using namespace std;  
  5.   
  6. struct uni  
  7. {  
  8.     int a,b,c,d;  
  9. };  
  10.   
  11. uni can[3000];  
  12. int sum = 0,sum_all = 0;  
  13.   
  14. void get_all_num()  
  15. {  
  16.     for(int i = 1;i <= 16;++i)  
  17.     {  
  18.         for(int j = 1;j <= 16;++j)  
  19.         {  
  20.             for(int k = 1; k <= 16; ++k)  
  21.             {  
  22.                 for(int l = 1;l <= 16;++l)  
  23.                 {                 
  24.                     if(i != j && i != k && i != l && j != k && j != l && k != l)  
  25.                         if(i + j + k + l == 34)  
  26.                         {  
  27.                             can[sum].a = i;  
  28.                             can[sum].b = j;  
  29.                             can[sum].c = k;  
  30.                             can[sum].d = l;  
  31.                             ++sum;  
  32.                         }  
  33.                 }  
  34.             }  
  35.         }  
  36.     }  
  37. }  
  38.   
  39. void p_rint(const int sq[])  
  40. {  
  41.     cout << "i wIll gIvE yOu sOme coLoR 2CC! " << sum_all <
  42.     cout << sq[0] << " " << sq[1] << " " << sq[2] << " " << sq[3] << endl;  
  43.     cout << sq[4] << " " << sq[5] << " " << sq[6] << " " << sq[7] << endl;  
  44.     cout << sq[8] << " " << sq[9] << " " << sq[10] << " " << sq[11] << endl;  
  45.     cout << sq[12] << " " << sq[13] << " " << sq[14] << " " << sq[15] << endl << endl;  
  46. }  
  47.   
  48. bool caca(const int sq[])  
  49. {  
  50.     if(sq[0] + sq[4] + sq[8] + sq[12] !=34)  
  51.         return false;  
  52.     if(sq[2] + sq[6] + sq[10] + sq[14] !=34)  
  53.         return false;  
  54.     return true;  
  55. }  
  56.   
  57. bool detec_2(const int sq[])  
  58. {  
  59.     int km2[17];  
  60.     int i,m;  
  61.     for(i = 0;i <= 16;++i)  
  62.     {  
  63.         km2[i] = 0;  
  64.     }  
  65.       
  66.     for(m = 0;m < 16;++m)  
  67.     {  
  68.         km2[sq[m]]++;  
  69.         if(km2[sq[m]] > 1)  
  70.             return false;  
  71.     }  
  72.       
  73.     return true;  
  74. }  
  75. bool detec_1(const int c1[],const int c2[])  
  76. {  
  77.     int km2[17],i;  
  78.     for(i = 0;i < 16;++i)  
  79.     {  
  80.         km2[i] = 0;  
  81.     }  
  82.       
  83.     km2[c1[0] - 1]++;  
  84.     km2[c1[1] - 1]++;  
  85.     km2[c1[2] - 1]++;  
  86.     km2[c1[3] - 1]++;  
  87.       
  88.     km2[c2[0] - 1]++;  
  89.     km2[c2[1] - 1]++;  
  90.     km2[c2[2] - 1]++;  
  91.     km2[c2[3] - 1]++;  
  92.       
  93.     for(i = 0;i < 16;i++)  
  94.     {  
  95.         if(km2[i] > 1)  
  96.             return false;  
  97.     }  
  98.       
  99.     return true;  
  100. }  
  101.   
  102. void fill_in_line(const int c1[],const int c2[])  
  103. {  
  104.     int sq[16],k,l;  
  105.       
  106.     sq[0] = c1[0];  
  107.     sq[5] = c1[1];  
  108.     sq[10] = c1[2];  
  109.     sq[15] = c1[3];  
  110.       
  111.     sq[3] = c2[0];  
  112.     sq[6] = c2[1];  
  113.     sq[9] = c2[2];  
  114.     sq[12] = c2[3];           
  115.   
  116.     for(k = 1;k <= 16;k++)  
  117.     {  
  118.         sq[4] = k;  
  119.         if(k != c1[0] && k != c1[1] && k != c1[2] && k != c1[3] && k != c2[0] && k != c2[1] && k != c2[2] && k != c2[3])  
  120.         {  
  121.             for(l = 1;l <= 16;++l)  
  122.             {  
  123.                 sq[1] = l;  
  124.                 if(l != sq[4])  
  125.                 {  
  126.                     sq[7] = 34 - sq[4] - sq[5] - sq[6];  
  127.                     sq[11] = 34 - sq[3] - sq[7] - sq[15];  
  128.                     sq[8] = 34 - sq[9] - sq[10] - sq[11];  
  129.                     sq[13] = 34 - sq[1] - sq[5] - sq[9];  
  130.                     sq[14] = 34 - sq[12] - sq[13] - sq[15];  
  131.                     sq[2] = 34 - sq[0] - sq[1] - sq[3];  
  132.   
  133.                     if(sq[7] > 0 && sq[11] > 0 && sq[8] > 0 && sq[13] > 0 && sq[14] > 0 && sq[2] > 0 &&  
  134.                        sq[7] <= 16 && sq[11] <= 16 && sq[8] <= 16 && sq[13] <= 16 && sq[14] <= 16 && sq[2] <= 16)  
  135.                     {  
  136.                             if((sq[0] + sq[1] + sq[4] + sq[5] == sq[10] + sq[11] + sq[14] + sq[15]) &&  
  137.                                 (sq[2] + sq[3] + sq[6] + sq[7] == sq[8] + sq[9] + sq[12] + sq[13]) &&  
  138.                                 caca(sq) && detec_2(sq))  
  139.                             {  
  140.                                 sum_all++;  
  141.                                 p_rint(sq);  
  142.                             }  
  143.                     }  
  144.                 }  
  145.             }  
  146.         }  
  147.     }  
  148.       
  149. }  
  150. void fill_in_eight()  
  151. {  
  152.     int cse1[4],cse2[4];  
  153.       
  154.     for(int i = 0;i < sum;++i)  
  155.     {  
  156.         for(int j = 0;j < sum;++j)  
  157.         {  
  158.             if( i!=j )  
  159.             {  
  160.                 cse1[0] = can[i].a;  
  161.                 cse1[1] = can[i].b;  
  162.                 cse1[2] = can[i].c;  
  163.                 cse1[3] = can[i].d;  
  164.                   
  165.                 cse2[0] = can[j].a;  
  166.                 cse2[1] = can[j].b;  
  167.                 cse2[2] = can[j].c;  
  168.                 cse2[3] = can[j].d;  
  169.                   
  170.                 if(detec_1(cse1,cse2))  
  171.                 {  
  172.                     fill_in_line(cse1,cse2);  
  173.                 }  
  174.             }  
  175.               
  176.         }  
  177.     }  
  178. }  
  179.   
  180. int main()  
  181. {  
  182.     time_t t;  
  183.     t = clock();  
  184.       
  185.     get_all_num();  
  186.     fill_in_eight();  
  187.       
  188.     cout << "time consumed: " << clock() - t << " ms"<< endl;  
  189.     return 0;  
  190. }
返回顶楼
         
  • metaphy
  • 等级: 四星会员
  • 性别:
  • 文章: 1026
  • 积分: 449
  • 来自: 大西洋底
   发表时间：2007-11-01  
大学时候用C写过一次，算法类似。
当时在学校机房的破机器上跑了2分多钟，也是7000多个解。
返回顶楼
          回帖地址
0 请登录后投票
论坛首页 → 编程语言技术版

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