當前位置:編程學習大全網 - 編程語言 - 三十六軍官問題的應用

三十六軍官問題的應用

這種方陣在近代組合數學中稱為正交拉丁方,它在工農業生產和科學實驗方面有廣泛的應用。現已經證明,除了2階和6階以外,其它各階3,4,5,7,8,……各階正交拉丁方都是作得出來的。

除了上面的定義外需要註意的是每個組合不能重復,如2階方正會出現類似如下情況:

(1,1) (2,2)

(2,2) (1,1)

由於出現類似(1,1)的重復,問題中36個軍官不可能同時站在不同位置,故不滿足需求,所以2階方正不存在。根據計算機編程能很容易求得3,4,5階的方正,由於組合眾多,現舉例如下:

3階:

(1,1) (2,2) (3,3)

(2,3) (3,1) (1,2)

(3,2) (1,3) (2,1)

4階:

(2,1) (4,4) (3,2) (1,3)

(4,2) (2,3) (1,1) (3,4)

(3,3) (1,2) (2,4) (4,1)

(1,4) (3,1) (4,3) (2,2)

5階:

(1,1) (2,2) (3,5) (4,3) (5,4)

(4,5) (1,3) (5,2) (3,4) (2,1)

(2,4) (5,5) (4,1) (1,2) (3,3)

(5,3) (3,1) (1,4) (2,5) (4,2)

(3,2) (4,4) (2,3) (5,1) (1,5)

c++ 代碼如下: #include?<iostream>#define?ARMY_SIZE?5typedef?struct?snode?{ int?x; int?y;}node;void?set_value(int?x,?int?y);bool?can_set(int?x,?int?y,?int?i,?int?j);void?set_next(int?x,?int?y);?node?nodes[ARMY_SIZE][ARMY_SIZE];int?main(void){ memset(nodes,?0,?sizeof(nodes)); set_value(0,?0); std::cout?<<?end...?<<?std::endl;? std::cin.get();? return?0;?}void?set_value(int?x,?int?y){ for?(int?i?=?1;?i?<?ARMY_SIZE?+?1;?++i)?{ for?(int?j?=?1;?j?<?ARMY_SIZE?+?1;?++j)?{ if?(can_set(x,?y,?i,?j))?{ nodes[x][y].x?=?i; nodes[x][y].y?=?j; set_next(x,?y); nodes[x][y].x?=?0; nodes[x][y].y?=?0; } } }}bool?can_set(int?x,?int?y,?int?i,?int?j){ for?(int?_x?=?0;?_x?<?x;?++_x)?{ if?(nodes[_x][y].x?==?i?||?nodes[_x][y].y?==?j) return?false; } for?(int?_z?=?0;?_z?<?x;?++_z)?{ for?(int?_i?=?0;?_i?<?ARMY_SIZE;?++_i)?{ if?(nodes[_z][_i].x?==?i?&&?nodes[_z][_i].y?==?j)?{ return?false; } } } for?(int?_y?=?0;?_y?<?y;?++_y)?{ if?(nodes[x][_y].x?==?i?||?nodes[x][_y].y?==?j) return?false; } return?true;?}void?set_next(int?x,?int?y){ if?(y?+?1?==?ARMY_SIZE)?{ if?(x?+?1?==?ARMY_SIZE)?{ for?(int?i?=?0;?i?<?ARMY_SIZE;?++i)?{ for?(int?j?=?0;?j?<?ARMY_SIZE;?++j)?{ std::cout?<<?(?<<?nodes[i][j].x?<<?,?<<?nodes[i][j].y?<<?)?; } std::cout?<<?std::endl; } std::cout?<<?*************************************?<<?std::endl; }?else?{ set_value(x?+?1,?0); } }?else?{ set_value(x,?y?+?1); }}

  • 上一篇:大型的 PHP應用 通常使用什麽應用做 消息隊列 的
  • 下一篇:在國內,妳去過哪些感受很棒,但還沒紅的冷門景點?
  • copyright 2024編程學習大全網