1、Algorithm
Gossip: 4N 魔方陣
說明
與 奇數(shù)魔術(shù)方陣 相同，在於求各行、各列與各對角線的和相等，而這次方陣的維度是4的倍數(shù)。
解法
先來看看4X4方陣的解法：
簡單的說，就是一個從左上由1依序開始填，但遇對角線不填，另一個由左上由16開始填，但只填在對角線，再將兩個合起來就是解答了；如果N大於2，則以
4X4為單位畫對角線：
至於對角線的位置該如何判斷，有兩個公式，有興趣的可以畫圖印證看看，如下所示：
if(i%4==j%4||(i%4+j%4==3)//zai duijiao xian
shang
實作
#include <stdio.h>
#include <stdlib.h>
#define N 8
int main(void) {
int i, j;
int square[N+1][N+1] = {0};
for(j = 1; j <= N; j++) {
for(i = 1; i <= N; i++){
if(j % 4 == i % 4 || (j % 4 + i % 4) == 1)
square[i][j] = (N+1-i) * N -j + 1;
else
square[i][j] = (i - 1) * N + j;
}
}
for(i = 1; i <= N; i++) {
for(j = 1; j <= N; j++)
printf("- ", square[i][j]);
printf("\n");
}
return 0;
}
說明
方陣的維度整體來看是偶數(shù)，但是其實是一個奇數(shù)乘以一個偶數(shù)，例如6X6，其中6=2X3，我們也稱這種方陣與單偶數(shù)方陣。
解法
如果您會解奇數(shù)魔術(shù)方陣，要解這種方陣也就不難理解，首先我們令n=2(2m+1)，並將整個方陣看作是數(shù)個奇數(shù)方陣的組合，如下所示：
首先依序?qū)、B、C、D四個位置，依奇數(shù)方陣的規(guī)則填入數(shù)字，填完之後，方陣中各行的和就相同了，但列與對角線則否，此時必須在A-D與C-
B之間，作一些對應(yīng)的調(diào)換，規(guī)則如下：
- 將A中每一列(中間列除外)的頭m個元素，與D中對應(yīng)位置的元素調(diào)換。
- 將A的中央列、中央那一格向左取m格，並與D中對應(yīng)位置對調(diào)
- 將C中每一列的倒數(shù)m-1個元素，與B中對應(yīng)的元素對調(diào)
舉個實例來說，如何填6X6方陣，我們首先將之分解為奇數(shù)方陣，並填入數(shù)字，如下所示：
接下來進行互換的動作，互換的元素以不同顏色標示，如下：
由於m-1的數(shù)為0，所以在這個例子中，C-B部份並不用進行對調(diào)。
實作
#include <stdio.h>
#include <stdlib.h>
#define N 6
#define SWAP(x,y) {int t; t = x; x = y; y = t;}
void magic_o(int [][N], int);
void exchange(int [][N], int);
int main(void) {
int square[N][N] = {0};
int i, j;
magic_o(square, N/2);
exchange(square, N);
for(i = 0; i < N; i++) {
for(j = 0; j < N; j++)
printf("- ", square[i][j]);
printf("\n");
}
return 0;
}
void magic_o(int square[][N], int n) {
int count, row, column;
row = 0;
column = n / 2;
for(count = 1; count <= n*n; count++) {
square[row][column] = count; // 填A(yù)
square[row+n][column+n] = count + n*n; // 填B
square[row][column+n] = count + 2*n*n; // 填C
square[row+n][column] = count + 3*n*n; // 填D
if(count % n == 0)
row++;
else {
row = (row == 0) ? n - 1 : row - 1 ;
column = (column == n-1) ? 0 : column + 1;
}
}
}
void exchange(int x[][N], int n) {
int i, j;
int m = n / 4;
int m1 = m - 1;
for(i = 0; i < n/2; i++) {
if(i != m) {
for(j = 0; j < m; j++) // 處理規(guī)則 1
SWAP(x[i][j], x[n/2+i][j]);
for(j = 0; j < m1; j++) // 處理規(guī)則 2
SWAP(x[i][n-1-j], x[n/2+i][n-1-j]);
}
else { // 處理規(guī)則 3
for(j = 1; j <= m; j++)
SWAP(x[m][j], x[n/2+m][j]);
for(j = 0; j < m1; j++)
SWAP(x[m][n-1-j], x[n/2+m][n-1-j]);
}
}
}
說明
將1到n(為奇數(shù))的數(shù)字排列在nxn的方陣上，且各行、各列與各對角線的和必須相同，如下所示：
解法
填魔術(shù)方陣的方法以奇數(shù)最為簡單，第一個數(shù)字放在第一行第一列的正中央，然後向右(左)上填，如果右(左)上已有數(shù)字，則向下填，如下圖所示：
一般程式語言的陣列索引多由0開始，為了計算方便，我們利用索引1到n的部份，而在計算是向右(左)上或向下時，我們可以將索引值除以n值，如果得到餘數(shù)為1就向下，否則就往右(左)上，原理很簡單，看看是不是已經(jīng)在同一列上繞一圈就對了。
幻方問題分為奇幻方和偶幻方。奇幻方和偶幻方方陣的布陣規(guī)律不同，而偶幻方又分為 是4的倍數(shù)（如4，8，12，16，20等）和不是4的倍數(shù)（如6，10，14，18等）兩種。
現(xiàn)在就幻方的三種情形的布陣規(guī)律分別加以介紹。
1、奇幻方
N=2*M+1（M=1，2，3，……）的布陣規(guī)律
a、把1放在N*N方陣中的第一行中間一列，即放在位置為（1，（N+1）/2）；
b、后一個數(shù)存放的行數(shù)比前一個數(shù)存放的行數(shù)減1，若這個行數(shù)為0，則取行數(shù)為N；
c、后一個數(shù)存放的列數(shù)比前一個數(shù)存放的列數(shù)加1，若這個列數(shù)為N+1，則取列數(shù)為1；
d、如果前一個數(shù)是N的倍數(shù)，則后一個數(shù)存放的列數(shù)不變，而行數(shù)加1。
2、偶幻方N=4*（M=1，2，3，……）的布陣規(guī)律
先將1至N*N由小到大的順序，從第一行開是依序填入N*N的方陣中，然后將N*N的方陣以4
行4列劃分為若干個4*4的小方陣，再將所有4*4小方陣的兩個對角線上的數(shù)字劃掉，之后
將所有被劃掉的數(shù)字重新由大到小的進行排列，然后再將這些數(shù)字按排列順序由N*N方陣
的第一行開始，放入被劃掉的格子中去。則此時的偶幻方也就布好陣了。
//先看一個4階偶數(shù)陣
//先把1->n*n，按順序填入，遇到對角線的不填。
//再把n*n->1，在剩下的空中按順序填入
//再看4N階的排法
//把矩陣分成N個4階的矩陣，各個矩陣按4階排列
#include<stdio.h>
#define N 8
void main()
{
int f[20][20];
int i,j,k;
k=1;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
{
if(i%4==j%4||(i%4+j%4==3))
{
f[i][j]=N*N-k+1;
k++;
}
else
{
f[i][j]=k++;
}
}
int s;
for(i=0;i<N;i++)
{
s=0;
for(j=0;j<N;j++)
{
printf("%d ",f[i][j]);
s=s+f[i][j];
}
printf("%d\n",s);
}
}
3、偶幻方N=2*（2*M+1）（M=1，2，3，……）的布陣規(guī)律
先將N*N的方陣劃分為2*2的四個小方陣，設(shè)為A，B，C，D，則這四部分都正好是奇行奇
列的方陣，設(shè)每個小方陣為U*U，其中U=N/2。然后將1至U*U按奇幻方的的方式填入小方
陣A中，同理填入U*U+1至U*U*2到B中，填入U*U*2+1至U*U*3到C中，填入U*U*3+1至U*U*4
到D中。然后按下列方法交換：
a、將A和D的第一列對應(yīng)位置的元素（出各自的中間一行外）進行交換；
b、將A和D的中間一列的中間一行的元素進行交換；
c、如果（U+1）/2>2，則將A和D中左邊的第二列開始到第（U-1）/2列為止，對應(yīng)行的數(shù)字全部進行交換，同時將B和C右邊第一列起連續(xù)（U-1）/2-1列對英航的數(shù)字也全部進行交換。
|
