三階幻方c語言演算法

Ⅰ 幻方的構造原理

在《射鵰英雄傳》中郭黃二人被裘千仞追到黑龍潭，躲進瑛姑的小屋。瑛姑出了一道題：數字1~9填到三行三列的表格中，要求每行、每列、及兩條對角線上的和都相等。這道題難倒了瑛姑十幾年，被黃蓉一下子就答出來了。 492357816這就是一個最簡單的3階平面幻方。因為幻方的智力性和趣味性，很多游戲和玩具都與幻方有關，如捉放曹、我們平時玩的六面體，也成為學習編程時的常見問題。
幻方又稱縱橫圖、九宮圖，最早記錄於中國古代的洛書。夏禹治水時，河南洛陽附近的大河裡浮出了一隻烏龜，背上有一個很奇怪的圖形，古人認為是一種祥瑞，預示著洪水將被夏禹王徹底制服。後人稱之為洛書或河圖，又叫河洛圖。
南宋數學家楊輝，在他著的《續古摘奇演算法》里介紹了這種方法：只要將九個自然數按照從小到大的遞增次序斜排，然後把上、下兩數對調，左、右兩數也對調；最後再把中部四數各向外面挺出，幻方就出現了。（摘自《趣味數學辭典》）
最簡單的幻方就是平面幻方，還有立體幻方、高次幻方等。對於立體幻方、高次幻方世界上很多數學家仍在研究，只討論平面幻方。
對平面幻方的構造，分為三種情況：N為奇數、N為4的倍數、N為其它偶數(4n+2的形式）
1、 N 為奇數時，最簡單：
⑴ 將1放在第一行中間一列；
⑵ 從2開始直到n×n止各數依次按下列規則存放：
按 45°方向行走，如向右上
每一個數存放的行比前一個數的行數減1，列數加1
⑶ 如果行列范圍超出矩陣范圍，則回繞。
例如1在第1行，則2應放在最下一行，列數同樣加1;
⑷ 如果按上面規則確定的位置上已有數，或上一個數是第1行第n列時，
則把下一個數放在上一個數的下面。
2、 N為4的倍數時
採用對稱元素交換法。
首先把數1到n×n按從上至下，從左到右順序填入矩陣
然後將方陣的所有4×4子方陣中的兩對角線上位置的數關於方陣中心作對
稱交換，即a(i,j）與a(n+1-i,n+1-j）交換，所有其它位置上的數不變。
（或者將對角線不變，其它位置對稱交換也可）
**以上方法只適合於n=4時**
3、 N 為其它偶數時
當n為非4倍數的偶數（即4n+2形）時：首先把大方陣分解為4個奇數(2m+1階）子方陣。
按上述奇數階幻方給分解的4個子方陣對應賦值
由小到大依次為上左子陣（i），下右子（i+v），上右子陣（i+2v)，下左子陣（i+3v），
即4個子方陣對應元素相差v，其中v=n*n/4
四個子矩陣由小到大排列方式為 ① ③
④ ②
然後作相應的元素交換：a(i,j）與a(i+u,j）在同一列做對應交換（j<t或j>n-t+2),
a(t-1,0）與a(t+u-1,0）；a(t-1,t-1)與a(t+u-1,t-1)兩對元素交換
其中u=n/2，t=(n+2)/4 上述交換使行列及對角線上元素之和相等。
C語言實現 #includestdio.h#includemath.hinta[256][256];intsum;intcheck();voidins(intn);voidmain(){inti,j,n,k,t,p,x;scanf(%d,&n);sum=(n*n+1)*n/2;if(n%2==1)//奇數幻方ins(n);if(n%4==2){//單偶數幻方k=n/2;ins(k);for(i=0;i<k;i++)for(j=0;j<k;j++){a[i][j+k]=a[i][j]+2*k*k;a[i+k][j]=a[i][j]+3*k*k;a[i+k][j+k]=a[i][j]+k*k;}t=(n-2)/4;for(i=0;i<k;i++)for(j=0;j<k;j++){if((j<t)&&(i<t)){p=a[i][j];a[i][j]=a[i+k][j];a[i+k][j]=p;}if((j<t)&&(i>k-t-1)){p=a[i][j];a[i][j]=a[i+k][j];a[i+k][j]=p;}if((i>=t&&i<=k-t-1)&&(j>=t&&j<t*2)){p=a[i][j];a[i][j]=a[i+k][j];a[i+k][j]=p;}if(j>1&&j<=t){p=a[i][j+k];a[i][j+k]=a[i+k][j+k];a[i+k][j+k]=p;}}}if(n%4==0){//雙偶數幻方x=1;for(i=0;i<n;i++)for(j=0;j<n;j++)a[i][j]=x++;for(i=0;i<n;i++)for(j=0;j<n;j++){if(i%4==0&&abs(i-j)%4==0)for(k=0;k<4;k++)a[i+k][j+k]=n*n-a[i+k][j+k]+1;elseif(i%4==3&&(i+j)%4==3)for(k=0;k<4;k++)a[i-k][j+k]=n*n-a[i-k][j+k]+1;}}if(check(n)==1){for(i=0;i<n;i++){for(j=0;j<n;j++)printf(%5d,a[i][j]);printf( );}}}intcheck(intn){//檢驗是否是幻方inti,j,sum1=0,sum2;for(i=0;i<n;i++){for(j=0;j<n;j++)sum1+=a[i][j];if(sum1!=sum)return0;sum1=0;}for(i=0;i<n;i++){for(j=0;j<n;j++)sum1+=a[i][j];if(sum1!=sum)return0;sum1=0;}for(sum1=0,sum2=0,i=0,j=0;i<n;i++,j++){sum1+=a[i][j];sum2+=a[i][n-j-1];}if(sum1!=sum)return0;if(sum2!=sum)return0;elsereturn1;}voidins(intn){//單偶數幻方的輸入intx,y,m;x=0;y=n/2;for(m=1;m<=n*n;m++){a[x][y]=m;if(m%n!=0){x--;y++;if(x<0)x=x+n;if(y==n)y=n-y;}else{x++;if(x==n)x=x-n;}}}//c++語言實現//（1）求奇數幻方#include<iostream.h>#include<iomanip.h>intmain(){intn,x,y,tot=0,i,j,a[100][100]={0};cout<<請輸入一個奇數<<endl;cin>>n;a[i=n/2][j=0]=++tot;i--;j--;while(tot<=n*n){i<0?i=n-1:i=i;j<0?j=n-1:j=j;if(a[i][j]){i=x;j=y+1;}a[i][j]=++tot;x=i;y=j;i--;j--;}for(i=0;i<n;i++){for(j=0;j<n;j++)cout<<setw(3)<<a[i][j];cout<<endl;}return0;}//（2）求單偶幻方#include<iostream.h>#include<iomanip.h>intmain(){intn,i=0,j=0,a[100][100],tot=0;cout<<請輸入4的倍數<<endl;cin>>n;for(i=0;i<n;i++)for(j=0;j<n;j++){a[i][j]=++tot;}for(i=0;i<n;i++){for(j=0;j<n;j++){if(i%4==j%4||i%4+j%4==3)a[i][j]=n*n+1-a[i][j];}}for(i=0;i<n;i++){for(j=0;j<n;j++){cout<<setw(4)<<a[i][j];}cout<<endl;}return0;}奇階幻方
當n為奇數時，我們稱幻方為奇階幻方。可以用Merzirac法與loubere法實現，根據我的研究，發現用國際象棋之馬步也可構造出更為神奇的奇幻方，故命名為horse法。
偶階幻方
當n為偶數時，我們稱幻方為偶階幻方。當n可以被4整除時，我們稱該偶階幻方為雙偶幻方；當n不可被4整除時，我們稱該偶階幻方為單偶幻方。可用了Hire法、Strachey以及YinMagic將其實現，Strachey為單偶模型，我對雙偶(4m階）進行了重新修改，製作了另一個可行的數學模型，稱之為Spring。YinMagic是我於2002年設計的模型，他可以生成任意的偶階幻方。
在填幻方前我們做如下約定：如填定數字超出幻方格範圍，則把幻方看成是可以無限伸展的圖形，如下圖：
Merzirac法生成奇階幻方
在第一行居中的方格內放1，依次向右上方填入2、3、4…，如果右上方已有數字，則向下移一格繼續填寫。如下圖用Merziral法生成的5階幻方： 17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9 loubere法生成奇階幻方
在居中的方格向上一格內放1，依次向右上方填入2、3、4…，如果右上方已有數字，則向上移二格繼續填寫。如下圖用Louberel法生成的5階幻方： 23 6 19 2 15 10 18 1 14 22 17 5 13 21 9 4 12 25 8 16 11 24 7 20 3 Hire法生成偶階幻方
將n階幻方看作一個矩陣，記為A，其中的第i行j列的數字記為a(i,j）。在A內兩對角線上填寫1、2、3、……、n，各行再填寫1、2、3、……、n，使各行各列數字之和為n*(n+1)/2。填寫方法為：第1行從n到1填寫，從第2行到第n/2行按從1到進行填寫（第2行第1列填n，第2行第n列填1)，從第n/2+1到第n行按n到1進行填寫，對角線的方格內數字不變。如下所示為6階填寫方法：
1 5 4 3 2 6
6 2 3 4 5 1
1 2 3 4 5 6
6 5 3 4 2 1
6 2 4 3 5 1
1 5 4 3 2 6
如下所示為8階填寫方法（轉置以後）：
1 8 1 1 8 8 8 1
7 2 2 2 7 7 2 7
6 3 3 3 6 3 6 6
5 4 4 4 4 5 5 5
4 5 5 5 5 4 4 4
3 6 6 6 3 6 3 3
2 7 7 7 2 2 7 2
8 1 8 8 1 1 1 8
將A上所有數字分別按如下演算法計算，得到B，其中b(i,j)=n×（a(i,j）－1)。則AT+B為目標幻方
（AT為A的轉置矩陣）。如下圖用Hire法生成的8階幻方：
1 63 6 5 60 59 58 8
56 10 11 12 53 54 15 49
41 18 19 20 45 22 47 48
33 26 27 28 29 38 39 40
32 39 38 36 37 27 26 25
24 47 43 45 20 46 18 17
16 50 54 53 12 11 55 9
57 7 62 61 4 3 2 64
⑴.Strachey法生成單偶幻方
將n階單偶幻方表示為4m+2階幻方。將其等分為四分，成為如下圖所示A、B、C、D四個2m+1階奇數幻方。
A C
D B
A用1至2m+1填寫成(2m+1)2階幻方；B用(2m+1)2+1至2*(2m+1)2填寫成2m+1階幻方；C用2*(2m+1)2+1至3*(2m+1)2填寫成2m+1階幻方；D用3*(2m+1)2+1至4*(2m+1)2填寫成2m+1階幻方；在A中間一行取m個小格，其中1格為該行居中1小格，另外m-1個小格任意，其他行左側邊緣取m列，將其與D相應方格內交換；B與C接近右側m-1列相互交換。如下圖用Strachey法生成的6階幻方：
35 1 6 26 19 24
3 32 7 21 23 25
31 9 2 22 27 20
8 28 33 17 10 15
30 5 34 12 14 16
4 36 29 13 18 11
⑵Spring法生成以偶幻方
將n階雙偶幻方表示為4m階幻方。將n階幻方看作一個矩陣，記為A，其中的第i行j列方格內的數字記為a(i,j）。
先令a(i,j)=(i-1)*n+j，即第一行從左到可分別填寫1、2、3、……、n；即第二行從左到可分別填寫n+1、n+2、n+3、……、2n；…………之後進行對角交換。對角交換有兩種方法：
方法一；將左上區域i+j為偶數的與幻方內以中心點為對稱點的右下角對角數字進行交換；將右上區域i+j為奇數的與幻方內以中心點為對稱點的左下角對角數字進行交換。（保證不同時為奇或偶即可。）
方法二；將幻方等分成m*m個4階幻方，將各4階幻方中對角線上的方格內數字與n階幻方內以中心點為對稱點的對角數字進行交換。
如下圖用Spring法生成的4階幻方：
16 2 3 13
5 11 10 8
9 7 6 12
4 14 15 1
YinMagic構造偶階幻方
先構造n-2幻方，之後將其中的數字全部加上2n-2，放於n階幻方中間，再用該方法將邊緣數字填寫完畢。該方法適用於n>4的所有幻方，我於2002年12月31日構造的數學模型。YinMagic法可生成6階以上的偶幻方。如下圖用YinMagic法生成的6階幻方：
10 1 34 33 5 28
29 23 22 11 18 8
30 12 17 24 21 7
2 26 19 14 15 35
31 13 16 25 20 6
9 36 3 4 32 27
魔鬼幻方
如將幻方看成是無限伸展的圖形，則任何一個相鄰的n*n方格內的數字都可以組成一個幻方。則稱該幻方為魔鬼幻方。
用我研究的Horse法構造的幻方是魔鬼幻方。如下的幻方更是魔鬼幻方，因為對於任意四個在兩行兩列上的數字，他們的和都是34。此幻方可用YinMagic方法生成。
15 10 3 6
4 5 16 9
14 11 2 7
1 8 13 12
羅伯法：
1居上行正中央，依次斜填右上方，上出框往下填，
右出框左邊放，排重便在下格填，右上排重一個樣。

Ⅱ 幻方怎麼填，有計算方法嗎

幻方演算法（Magic Square）學習筆記

一、幻方按照階數可分成了三類，即奇數階幻方、雙偶階幻方、單偶階幻方。

二、奇數階幻方（勞伯法）

奇數階幻方最經典的填法是羅伯法。填寫的方法是：

把1（或最小的數）放在第一行正中；按以下規律排列剩下的(n×n－1)個數：

1、每一個數放在前一個數的右上一格；

2、如果這個數所要放的格已經超出了頂行那麼就把它放在底行，仍然要放在右一列；

3、如果這個數所要放的格已經超出了最右列那麼就把它放在最左列，仍然要放在上一行；

4、如果這個數所要放的格已經超出了頂行且超出了最右列，那麼就把它放在底行且最左列；

5、如果這個數所要放的格已經有數填入，那麼就把它放在前一個數的下一行同一列的格內。

三、雙偶數階幻方（海爾法）

所謂雙偶階幻方就是當n可以被4整除時的偶階幻方，即4K階幻方。在說解法之前我們先說明一個「互補數」定義：就是在n階幻方中，如果兩個數的和等於幻方中最大的數與1的和（即n×n＋1），我們稱它們為一對互補數。

如在三階幻方中，每一對和為10的數，是一對互補數 ；在四階幻方中，每一對和為17的數，是一對互補數。

雙偶數階幻方最經典的填法是海爾法。填寫的方法是：

以8階幻方為例：

1、先把數字按順序填。然後，按4×4把它分割成4塊。

2、每個小方陣對角線上的數字（如左上角小方陣部分），換成和它互補的數。

四、單偶數階幻方（斯特拉茲法）

所謂單偶階幻方就是當n不可以被4整除時的偶階幻方，即4K+2階幻方。如(n=6，10，14……)的幻方。

單偶數階幻方最經典的填法是斯特拉茲法。填寫的方法是：

以10階幻方為例。這時，k=2。

1、把魔方陣分為A，B，C，D四個象限，這樣每一個象限肯定是奇數階。用羅伯法，依次在A象限，D象限，B象限，C象限按奇數階幻方的填法填數。

2、在A象限的中間行、中間格開始，按自左向右的方向，標出k格。A象限的其它行則標出最左邊的k格。將這些格，和C象限相對位置上的數互換位置。

3、在B象限所有行的中間格，自右向左，標出k－1格。(註：6階幻方由於k－1=0，所以不用再作B、D象限的數據交換)，將這些格，和D象限相對位置上的數互換位置。

(2)三階幻方c語言演算法擴展閱讀：

種類

完全幻方

完全幻方指一個幻方行、列、主對角線及泛對角線各數之和均相等 。

乘幻方

乘幻方指一個幻方行列、對角線各數乘積相等。

高次幻方

n階幻方是由前n^2（n的2次方）個自然數組成的一個n階方陣，其各行、各列及兩條對角線所含的n個數的和相等。

高次幻方是指，當組成幻方各數替換為其2，3,...,k次冪時，仍滿足幻方條件者，稱此幻方為k次幻方。

反幻方

反幻方的定義：在一個由若干個排列整齊的數組成的正方形中，圖中任意一橫行、一縱行及對角線的幾個數之和不相等，具有這種性質的圖表，稱為「反幻方」。

反幻方與正幻方最大的不同點是幻和不同，正幻方所有幻和都相同，而反幻方所有幻和都不同。所謂幻和就是幻方的任意行、列及對角線幾個數之和。如下圖3階反幻方的比較。

參考資料來源：網路-幻方