N阶幻方入门算法及图解

2019-11-06 07:05:39

字体：大中小

来源：转载

供稿：网友

幻方（Magic Square）1是一种将数字安排在正方形格子中，使每行、列和对角线上的数字和都相等的方法。幻方有3种不同解法，分别对应于奇数阶， 4*m阶，以及4*m+2阶。注：部分代码来源网络2

奇数阶幻方解法

英姑对黄蓉说：“你算法自然精我百倍，可是我问你：将一至九这九个数字排成三列，不论纵横斜角，每三个字相加都是十五，如何排列？” 黄蓉当下低声诵道：“九宫之意，法以灵龟，二四为肩，六八为足，左三右七，戴九履一，五居中央。”边说边画，在沙上画了一个九宫之图。 ——金庸《射雕英雄传》第二十九回黑沼隐女黄蓉给出的结果为： 4 9 2 3 5 7 8 1 6 更通用的解法如下： 1、把1填在第一行中央位置； 2、从2开始，每个数填在上一个数的左上角位置，越界则取模。 3、若左上角有数，则改填在上一个数的正下方。上文中“左上角，正下方”可以改为其他对称情况，如黄蓉用的“右下角，正上方”。代码如下：

void Magic_Odd(vector<vector<int> > &a){ int n = a.size(); int count = 2; int x = 0, y = n / 2; a[x][y] = 1; while (count <= n*n) { // get the new position int x2 = (x - 1 + n) % n; int y2 = (y - 1 + n) % n; if (a[x2][y2]) { x2 = (x + 1 + n) % n;// position is not valid, get next row. y2 = y; } x = x2; y = y2; a[x2][y2] = count++; }}

4*m阶幻方解法

黄蓉笑道：“不但九宫，即使四四图，五五图，以至百子图，亦不足为奇。“就说四四图罢，以十六字依次作四行排列，先以四角对换，一换十六，四换十三，后以内四角对换，六换十一，七换十。这般横直上下斜角相加，皆是三十四。 ——金庸《射雕英雄传》第二十九回黑沼隐女通用的做法如下： 1、从数字1开始从小到大，即从左到右，从上到下进行填充； 2、将魔方中间n/2列的元素上、下进行翻转； 3、将魔方中间n/2行的元素左、右进行翻转。这里写图片描述

void Magic_4m(vector<vector<int> > &a){ int n = a.size(); int count = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) a[i][j] = count++; } // swap for (int j = n/2 - 1; j < n/2 - 1 + n/2; ++j) { for (int i = 0; i < n/2; i++) swap(a[i][j], a[n - 1 - i][j]); // mid 2 col } for (int j = n / 2 - 1; j < n / 2 - 1 + n / 2; ++j) { for (int i = 0; i < n / 2; i++) swap(a[j][i], a[j][n - 1 - i]); // mid 2 row }}

4*m+2阶幻方解法

这个就比较麻烦点了。需要将矩阵分块后一一解决。 1、将魔方分成A、B、C、D四个k阶方阵，如下图这四个方阵都为奇方阵，依次将A、D、B、C填充为奇魔方。 A B C D 2、交换A、C魔方元素：对魔方的中间行，交换从中间列向右的m列各对应元素；对其他行，交换从左向右m列各对应元素。 3、交换B、D魔方元素：交换从中间列向左m – 1列各对应元素。这里写图片描述

void Magic_4m_2(vector<vector<int> > &a){ int n = a.size(); int i, k, temp; int col, row;// col 列，row 行 //初始化 k = n / 2; col = (k - 1) / 2; row = 0; a[row][col] = 1; //生成奇魔方A for (i = 2; i <= k*k; i++) { if ((i - 1) % k == 0)//前一个数是3的倍数 row++; else { // if row = 0, then row = n-1, or row = row - 1 row--; row = (row + k) % k; // if col = n, then col = 0, or col = col + 1 col++; col %= k; } a[row][col] = i; } //根据A生成B、C、D魔方 for (row = 0; row < k; row++) { for (col = 0; col < k; col++) { a[row + k][col + k] = a[row][col] + k*k; a[row][col + k] = a[row][col] + 2 * k*k; a[row + k][col] = a[row][col] + 3 * k*k; } } // Swap A and C for (row = 0; row < k; row++) { if (row == k / 2)//中间行，交换从中间列向右的m列，n = 2*(2m+1) { for (col = k / 2; col < k - 1; col++) swap(a[row][col], a[row + k][col]); } else//其他行，交换从左向右m列,n = 2*(2m+1) { for (col = 0; col < k / 2; col++) swap(a[row][col], a[row + k][col]); } } // Swap B and D for (row = 0; row < k; row++)//交换中间列向左m-1列，n = 2*(2m+1) { for (i = 0; i < (k - 1) / 2 - 1; i++) swap(a[row][k + k / 2 - i], a[row + k][k + k / 2 - i] ); }}

参考文献：

http://www.cnblogs.com/furzoom/p/furzoom-magic-square.html ↩百度百科:幻方 ↩

上一篇：CSS_选择器01

下一篇：1001: [BeiJing2006]狼抓兔子