-
三十六軍官問題
鎖定
三十六軍官問題解決
三十六軍官問題提出後，很長一段時間沒有得到解決，直到20世紀初才被證明這樣的方隊是排不起來的。儘管很容易將三十六軍官問題中的軍團數和軍階數推廣到一般的n的情況，而相應的滿足條件的方隊被稱為n階歐拉方。歐拉曾猜測：對任何非負整數t，n=4t+2階歐拉方都不存在。t=1時，這就是三十六軍官問題，而t=2時，n=10，數學家們構造出了10階歐拉方，這説明歐拉猜想不對。但到1960年，數學家們徹底解決了這個問題，證明了n=4t+2(t≥2)階歐拉方都是存在的。
三十六軍官問題應用
除了上面的定義外需要注意的是每個組合不能重複，如2階方正會出現類似如下情況：
(1,1) (2,1)
(2,2) (1,2)
由於出現類似(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 5
typedef 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);
}
}
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：16次歷史版本
- 最近更新： qinxianzhi小溪