奇數階幻方構造方法的原理是什麼?
在小學奧數里就遇到過構造幻方的題目,記得當時有口訣:『一居上行正中央,依次填在右上方……』好像有些奧數書里把這個方法稱為『拓撲法』,但沒有說原理。
後來就忘了這事,剛剛突然想起來,查了一下,好像叫Siamese method,但是wiki上也沒有寫原理。回想起『拓撲法』這個名字,感覺好像這個方法是把平面當成環面來構造幻方的。但具體還是沒有搞清楚,也不知道為什麼只適用於奇數階幻方。謝謝!
謝 @匡世珉 小朋友邀,我終於來填這個答案了(? ??_??)?
- &<壹&>
①
小時候玩幻方的時候沒有去記這些口訣,每次我都會說我不喜歡記口訣,其實真正原因估計是懶,懶著懶著好像記性也變差了。(?′?`?)老師帶你們回顧一下奇數階幻方口訣的口訣——一居上行正中央,依次斜填切莫忘;上出框時向下放,右出框時向左放;排重便在下格填,右上排重一個樣。這是由法國人羅伯(do la loubere)總結出來的,所以都叫他羅(蘿)伯(卜)法。(哈哈哈哈)先解釋一下這個口訣的意思:
下面給出一個用這個方法構造的五階幻方一居上行正中央:數字 1 放在首行最中間的格子中;
依次斜填切莫忘:向右上角斜行,依次填入數字;上出框時向下放:如果右上方向出了上邊界,就以出框後的虛擬方格位置為基準,將數字豎直降落至底行對應的格子中;右出框時向左放:同上,向右出了邊界,就以出框後的虛擬方格位置為基準,將數字平移至最左列對應的格子中;排重便在下格填:如果數字右上的格子已被其它數字佔領,就將 填寫在下面的格子中;右上排重一個樣:如果朝右上角出界,和上面重複的情況做同樣處理。
但是這個方法,我只能回答到這裡了,它的構造原理我暫時還不能很好的回答。
以前有看過幻方構造的出入相補原理法,可以解決2k+1,4k,4k+2階的幻方構造,但是和羅伯法不一樣,有興趣的可以了解。②那我再來給大家講講另一種方法,這會是一種更為有趣的方法。這是我國古代數學家楊輝給出的一種巧妙的排法:九子斜排,上下對易,左右相更,四維挺進。舉個例子:9個數斜著排,上下的兩個數1,9,左右的兩個數3,7互相換一下,四個角上的2,4,6,8就移到那四個角上去,這樣就填好了一個三階幻方了.③或許你會覺得這樣子不是很漂亮,那就改進一下吧,斜排好九個數字後,就將上、下、左、右的四個數字向對方的方向(下、上、右、左)移動三格。那麼這樣就漂亮啦!這種方法就是巴舍法(平移補空法)啦~【討論來了,biubiu~(覺得啰嗦的可以直接跳到最後看"魔力輪胎"~)那麼再來由另一種方法來藉助坐標格點來代替格子,繼續討論三階幻方構造的巴舍法到底是為什麼可以這樣做的。個人覺得羅伯法簡單易懂,只要會數數就夠了,但是對於階數比較大的幻方寫起來會比較累,但是楊輝法和巴舍法對於解決階數比較大的幻方會相對簡單一些誒。
如上圖中的左圖。
我們做第一步——九子斜排。在點(0,2)處標記1,在點(1,1)處標記2,在點(2,0)處標記3,這是第一段;
在點(-1,1),(0,0),(1,-1)處分別標記4,5,6,這是第二段;
在點(-2,0),(-1,-1),(0,-2)處分別標記7,8,9,這是第二段;
那接下來第二步——畫正方形。以點(-1,1),(1,1),(1,-1),(-1,-1)為頂點做一個正方形,我們發現1,9,3,7四個數在這個正方形外。最後一步,吧位於正方形外的四個數,都向正方形內平移三個單位,就得到了三階幻方(上圖中的右圖)。
為了討論的方便,我們對於上述的三段,分別有如下記法:第一段:,其中,,也即:;第二段:,其中,,也即:;第三段:,其中,,也即:.這樣,就建立好了一個函數列
你也會發現這個函數列取決於兩個等差數列:其中公差;其中公差;可以進行驗算,發現三橫行,三縱列,以及兩條對角線的和,當然他們都等於15:,這裡給出主對角線和副對角線的驗算:主對角線:副對角線:對於三橫行和三縱行的算式都和副對角線一樣,可以歸結為,數列各項的和就是幻和。……
舉個例子:繼續利用我們在三階幻方中構造的函數來看,,就是對於每個點的橫坐標加上常數,而這個是一個等差數列,首項為1,公差為.好了,對於任意的奇數階方陣,我們就有如下的構造方法:
①將排成一個斜的方陣;②以為中心做一個方陣(格);③將位於這個方陣(格)外的所有元素都向方陣內平移格。好了這樣就填好了一個奇數階的幻方!= ̄ω ̄=
- &<貳&>
說了這麼多,我終於要說我覺得好玩的東西了,不過跟奇數階幻方不一樣,我要講的是四階幻方。但是我覺得和題主提到的拓撲法,有一丟丟關係。
這是我以前在科學美國人趣味數學集錦之二 (豆瓣)里看到的,小時候看到這個覺得好好玩!因為三階幻方在中國被稱為洛書,它在很長的一段歷史時期中被當做咒符。由於幻方達到四階後,複雜度相對三階要大了好多,在不計旋轉和鏡射的情況下,四階幻方就有880種,其中還有一種有趣的幻方叫對稱幻方,有興趣的可以了解一下。上圖是有據可查的最早的四階幻方(發現與印度克傑拉霍的一個11或12世紀的碑文里)。這屬於一種特殊類型,叫做「完全幻方」(也稱泛對角幻方或納西克幻方),它甚至比對稱幻方更令人驚訝,除具有幻方的一般特性外,完全幻方在所有的「折對角線」上也具有數字相加之和為常數的特性、例如,方格2、12、15、5,以及方格2、3、15、14都是其折對角線,將兩個完全相同的幻方並排放置在一起就可以把對角線復原。不論是把完全幻方最上面一行的方格移到最下面去或反之,還是把邊上的某一列移到另一邊,得到的仍然是一個完全幻方。如果把很多完全一樣的完全幻方拼在一起組成馬賽克,那麼在這片區域里,任何4×4的方格組都是一個完全幻方,而且任何相鄰四個方格,無論上下、左右還是對角線方向,其數字之和永遠是該階幻方的常數(就是前面說的幻和)。
難過的是,其他階數的幻方暫時還不知道有沒有這麼美妙的性質。以及最後對於關於階,階和階幻方的構造方法有興趣的或者想了解更多的可以看看幻方與素數-娛樂數學兩大經典名題 (豆瓣)和你亦可以造幻方 (豆瓣).終於寫完了,要不要按平常那樣賣個萌再走?( ?? ̄)っ?╰?╯(自動腦補皮卡丘去)!最富戲劇性的展示這種幻方魔力特性的辦法,是康奈爾大學兩位數學家羅瑟(J.Barkley Rosser)和沃克(Robert J.Walker)發表於1938年的論文中所描述的那一個。先把這個完全幻方的頂和底接在一起構成一個圓柱體,然後將它拉伸。扭曲成輪胎狀的圓紋曲面。所有的行、列及對角線現在都成了閉圈。如果我們從任意一個方格開始,沿對角線方向移動兩個,總是會達到同一個方格上。這個方格就叫做開始時那個方格的「対極」。這個魔力輪胎上每一對対極方格的數字相加等於17。每個四格的閉圈,不論直加還是斜加,和都是34,像任何一個幻方中的四格組一樣。
這其實就是一個同餘式。先放一個結論:
1. 如果矩陣滿足條件,那麼對任意,也滿足條件。證明顯然。設為奇數,我們現在構造一個n階幻方包含0到所有數
這裡x,y滿足同餘式待確定。由於該方程組的係數矩陣的行列式為1,所以對任意i,j有唯一解。我們接下來確定a,b:
首先驗證每行每列的和均相等,即
由於對任意i,,當x取遍模n的剩餘類時,也會取遍所有的剩餘類
故每行的和為:
同理驗證每列。對於對角線:令b = n - 1, a = (n-1)/2,可以驗證y = (n - 1)/2, x = i
所以其和為:n*(0 + ... n - 1) + n(n - 1)/2 = n(n-1)(n+1)/2 = n(n^2 - 1)/2偶數不成立是因為, (n-1)/2不能整除。==========這種用同餘式構造組合結構的方法很常見,比如拉丁方的構造、n皇后問題的構造等。謝邀。不會原理。不過下個月可能要參加ACM省賽,先來這練個手。
程序作用:輸入一個n,輸出一個n階幻方。
#include &
#define MAX 100
int d[MAX][MAX];
void dllb(int l,int si,int sj,int sn,int d[][MAX])
{
int n,i=0,j=l/2;
for(n = 1;n &<= l*l;n++)
{
d[i+si][j+sj] = n + sn;
if(n%l)
{
i = i ? (i-1):(l-1);
j = (j==l-1)?0:(j+1);
}
else i = (i==l-1)?0:(i+1);
}
}
void mag_odd(int l,int d[][MAX])
{
dllb(l,0,0,0,d);
}
void mag_k(int l,int d[][MAX])
{
int i,j;
for(i = 0;i &< l;i++)
for(j = 0;j &< l;j++)
d[i][j] = ((i%4==0 ||i%4==3) (j%4==0 ||j%4==3) || (i%4==1 || i%4==2) (j%4==1 || j%4==2))?(l*l-(i*l+j)):(i*l+j+1);
}
void mag_other(int l,int d[][MAX])
{
int i,j,t;
dllb(l/2,0,0,0,d);
dllb(l/2,l/2,l/2,l*l/4,d);
dllb(l/2,0,l/2,l*l/2,d);
dllb(l/2,l/2,0,l*l/4*3,d);
for(i = 0;i &< l/2;i++)
for(j = 0;j &< l/4;j++)
if(i!=l/4 || j)
{
t = d[i][j];
d[i][j] = d[i+l/2][j];
d[i+l/2][j] = t;
}
t = d[l/4][l/4];
d[l/4][l/4] = d[l/4+l/2][l/4];
d[l/4+l/2][l/4] = t;
for(i = 0;i &< l/2;i++)
for(j = l-l/4+1;j &< l;j++)
{
t = d[i][j];
d[i][j] = d[i+l/2][j];
d[i+l/2][j] = t;
}
}
void gen(int l,int d[][MAX])
{
if(l%2) mag_odd(l,d);
else if(l%4==0) mag_k(l,d);
else mag_other(l,d);
}
int main()
{
int l;
while(~scanf("%d",l))
{
gen(l,d);
for(int i = 0;i &< l;i++)
{
puts("");
for(int j = 0;j &< l;j++)
printf("%d ",d[i][j]);
}
puts("");
}
return 0;
}
無聊時喜歡手動畫格寫幻方,參照下面的方法多練習幾次,多少階都不在話下了,當然僅限於奇數階,至於雙偶和奇偶幻方,相對複雜一些,手寫就困難多了,電腦還是可以的,因為涉及到移來移去的操作。
奇數階幻方
n為奇數 (n=3,5,7,9,11……) (n=2*k+1,k=1,2,3,4,5……)
奇數階幻方最經典的填法是羅伯特法(也有人稱之為樓梯法)。填寫方法是這樣:
把1(或最小的數)放在第一行正中; 按以下規律排列剩下的n*n-1個數:
(1)、每一個數放在前一個數的右上一格;
(2)、如果這個數所要放的格已經超出了頂行那麼就把它放在底行,仍然要放在右一列;
(3)、如果這個數所要放的格已經超出了最右列那麼就把它放在最左列,仍然要放在上一行;
(4)、如果這個數所要放的格已經超出了頂行且超出了最右列,那麼就把它放在前一個數的下一行同一列的格內;
(5)、如果這個數所要放的格已經有數填入,處理方法同(4)。
這種寫法總是先向「右上」的方向,象是在爬樓梯。
雙偶階幻方
4階方陣,將數字按順序填寫好之後,只須將除主負對角線外的數字進行中心對調即可;
對於n=4k階幻方,我們先把數字按順序填寫。寫好後,按4*4把它劃分成k*k個方陣。因為n是4的倍數,一定能用4*4的小方陣分割,然後:
1)把每個小4階方陣按照4階方陣的方法進行數字對換。
2)如果是n%8=0的方陣,初步對換後,將k*k的方陣看成一個元素,將全方陣看成一個以k*k元素的四階方陣進行數字對換即可。
3)如果是n%8!=0的方陣, 初步兌換後,將4*4的方陣看成一個元素,將全方陣看成一個k階方陣,即奇數階方陣,按照向右上移的方法進行填充即可。
單偶階幻方
n為偶數,且不能被4整除 (n=6,10,14,18,22……) (n=4k+2,k=1,2,3,4,5……)
這是三種裡面最複雜的幻方。
(1) 把方陣分為A,B,C,D四個象限,
B A
D C
這樣每一個象限肯定是奇數階。用樓梯法,依次在A象限,D象限,B象限,C象限按奇數階幻方的填法填數。
(2) 在A象限的中間行、中間格開始,按自左向右的方向,標出k格。A象限的其它行則標出最左邊的k格。
(3) 將這些格,和C象限相對位置上的數,互換位置。
(4) 在B象限任一行的中間格,自右向左,標出k-1列。(註:6階幻方由於k-1=0,所以不用再作B、D象限的數據交換)
(5) 將B象限標出的這些數,和D象限相對位置上的數進行交換,就形成幻方。
有興趣的朋友可以試一試。
小白表示
小時候地攤上買過一本講幻方的書,一直以為掌握了一門絕學。原來大家都知道。哈哈哈
我來說一下對「一居上行正中央,依次斜填切莫忘;上出框時向下放,右出框時向左放;排重便在下格填,右上排重一個樣」的羅伯法的理解……
用「依次填在右上方」的羅伯法畫個三階幻方(藍色正方形),然後向周圍「延拓」就長成上面這樣。可以看出這些數也是把橙色平行四邊形(恰好是123456789的排列順序)「延拓」的結果。也就是說羅伯法的具體步驟就是在這個平行四邊形結構元排成的空間中選取一個正方形的結構元。這樣的正方形中的數的幻方性質的證明就和 @安堇然提到的三階情況巴舍法的證明類似,構造數列求和就好,不過把3換成n,數列構造方式換一下。明天還要考量子力學我就不證了……
當然這種構造幻方的方式應該有拓撲結構上的更深層次的道理,我是不知道……希望有大神告訴我。
下面是五階幻方中平行四邊形結構元的樣子~PS:感覺證明應該不複雜,為什麼網上沒找到……我的文獻檢索能力不過關?推薦閱讀:
※這是用什麼演算法實現的?
※遞歸有什麼意義?
※計算機是怎樣進行開方和冪運算的?
※求一千萬以內由兩個素數相乘的數,並按從小到大排列,如:6=2*3,10=2*5。有什麼比較好的思路嗎?
※在學習數據結構與演算法的時候,一旦出現遞歸就很難理解。請問對於遞歸有沒有什麼好的理解方法?