周小安+趙宇

摘要： 關鍵詞： 中圖分類號： 文獻標志碼： A文章編號： 2095-2163

Abstract： Magic square originated thousands of years ago in China，which is one of the research objects of combinatorial designs. In a square matrix，if the sums of every row，every column and two diagonals are equal， this square matrix is called magic square. Currently， the achievements in the research of magic square have been widely used in image encryption，image scrambling，etc. This paper introduces a new continuous numbering method to structure arbitrary odd order magic square，which is more flexible than traditional construction methods.The new method can not only increase the forms of odd order magic square， but also parallelly structure magic square and reduce the time of structuring it.

0引言

幻方具有非常悠久的歷史，雖然古老但卻是最流行的數(shù)字游戲之一。一個n階幻方的構(gòu)造方法是將整數(shù)1、2、3、…、n2共n2個連續(xù)自然數(shù)，填入到n × n的方陣中，使得每行、每列以及每條對角線上的數(shù)字之和都等于同一個常數(shù)。幻方是組合設計的重要研究對象之一[1]。

《易經(jīng)》中記載的洛書是世界上最早的幻方，之后幻方逐漸傳入世界各地，引起了廣泛關注，并在許多方面取得了研究成果?；梅娇蓱糜谡芾硭枷氲难芯?、美術設計、智力開發(fā)、科學技術等方面[2]。尤其是在科學技術中，隨著計算機的快速發(fā)展，幻方在信息隱藏[3]、數(shù)字圖像[4]、認證與加密[5-6]、量子信息[7]等方面應用前景十分廣闊。

1使用改進的連續(xù)擺數(shù)法構(gòu)造奇數(shù)階幻方

1.1連續(xù)擺數(shù)法

連續(xù)擺數(shù)法是較為古老的幻方構(gòu)造方法，適用于奇數(shù)階幻方的構(gòu)造，一般把數(shù)字1放在幻方中第一行最中間的方格中，然后從這里開始，按對角線方向（比如說按從左下到右上的方向）把其余各數(shù)按從小到大的順序依次放入其它格子中，如果到達頂部，則轉(zhuǎn)向底部；如果到達右側(cè)，則轉(zhuǎn)向左側(cè)；如果需要放入的格子中已經(jīng)有數(shù)存在或者到達了右上角，則需要退至前一格的下方[1]。

按照上述法則建立的5階幻方如圖1所示。

這個方法可以推廣到一般情況，即起始數(shù)1不一定要放在第一行的中間，而下一個數(shù)字也不一定要放在上一個數(shù)的右上方格中，為此本文提出了改進的連續(xù)擺數(shù)法來構(gòu)造奇數(shù)階幻方。

1.2改進的連續(xù)擺數(shù)法

1.2.1算法設計步驟

改進的連續(xù)擺數(shù)法構(gòu)造n階幻方的步驟如下：

步驟1以奇數(shù)階幻方中心位置為坐標原點，建立坐標系；

步驟2將幻方中任意一格的位置用坐標來表示，坐標范圍從（-n-12，-n-12）到（n-12， n-12）；

步驟3定義“起始向量”，表示1的位置；

步驟4定義“偏移向量”，表示一個數(shù)的位置到下一個數(shù)位置所指的方向，依次按順序填寫其它數(shù)字；

步驟5當遇到要填入的格子中已經(jīng)被其它數(shù)字占據(jù)，用“中斷向量”重新計算該數(shù)字的坐標并填入計算后的空格；

步驟6重復步驟4和步驟5，直到所有數(shù)字均填入方格中。

1.2.2算法設計過程

這里，下面將詳述給出改進連續(xù)擺數(shù)法構(gòu)造5階幻方的過程。先以5階幻方中心位置為坐標原點，建立坐標系，每一點的坐標如圖2所示。

接著確定1的位置，連續(xù)擺數(shù)法是基于對稱性的方法，即以5階幻方為例，1～25的中間數(shù)字是13，所以假設要讓13固定在幻方的中心點，那么1就只能選擇除中心點外的其它位置。為此，研究定義一個起始向量（x0，y0），表示1的起始位置，x0、y0滿足條件（x0，y0） ≠ （0，0）。

確定好1的位置后，還需要定義一個偏移向量（u，v），表示一個數(shù)的位置到下一個數(shù)位置所指的方向。當然，偏移向量的選擇在理論上可以是任意的，但是卻需要滿足如下條件：

首先，u和v都不能等于0，否則無法產(chǎn)生偏移；其次，必須要保證（1+n2）/2固定在幻方的中心點，那么選取偏移向量時就要避免讓（1+n2）/2之前的數(shù)字占據(jù)中心位置，就需要據(jù)此原理求解數(shù)個特征方程，這里暫時不考慮這個問題。至此，研究將針對起始向量和偏移向量展開全面的分析論述。

假設階數(shù)n=5，起始向量（x0，y0） = （0，-1），偏移向量（u，v） = （2，1），那么1的位置如圖3所示，2的坐標由1的坐標加上偏移向量所得，即（0，-1） + （2，1） = （2，0），將2填入到圖3中對應位置，3、4、5采用相同的方法依次填入。需要說明的是，3的坐標由2的坐標加上偏移向量所得，即（2，0） + （2，1） = （4，1），在幻方中顯然沒有對應的坐標存在，這里需要把超出范圍的坐標進行“模n加”運算使該坐標在該幻方中尋得對應位置。具體來說，就是坐標（4，1）的橫坐標超出范圍，將（4，1） - （5，0） = （-1，1），于是找到3在幻方中的位置，填入圖3中。對4和5的處理也采取和3類似的方式。endprint

下一步就是確定6的位置。無論是從計算6的坐標位置還是從圖3直接來看，研究發(fā)現(xiàn)不管起始向量和偏移向量的取值是多少，理論上計算得到的6的位置上已經(jīng)有1存在了，這和連續(xù)擺數(shù)法的周期性有關。那么要想確定6的位置，必須引入一個中斷向量（xt，yt），表示發(fā)生沖突時的偏置量。具體來說，就是將數(shù)字正準備填入某一方格時，卻遭遇該方格中已存在數(shù)字的情形，這時即需改變該數(shù)字坐標的計算方法，將中斷向量代替偏移向量，重新計算該數(shù)字的坐標。

繼續(xù)用圖3中的例子來說明，當用偏移向量計算得到的6的位置里已經(jīng)存在1了，這時需要將中斷向量代替偏移向量，重新計算6的坐標，即用5的坐標加上中斷向量。那么如何確定中斷向量的大??？

經(jīng)過推導可知，中斷向量的值與起始向量有關，中斷向量（xt，yt）滿足方程（1）：（xt，yt）=2×（x0，y0）（1）在該例中，（x0，y0） = （0，-1），所以（xt，yt） = （0，-2），這時計算得到的6的坐標為5的坐標加上中斷向量，即（-2，-2） + （0，-2） = （-2，-4），再利用“模5加”運算得到6的坐標為（-2，1），填入幻方中。

緊接著，繼續(xù)用偏移向量完成其后順承數(shù)字的填寫，直到遇到下次被“占位”時才使用中斷向量。于是可以將7、8、9、10依次填入幻方中，如圖4所示。

計算該5階幻方每行、每列及對角線數(shù)字的和均為65，符合幻方的規(guī)律。

經(jīng)過嘗試和推導，可以將改進的連續(xù)擺數(shù)法推廣到任意奇數(shù)階幻方，用來構(gòu)造階數(shù)更多的幻方。由于起始向量和偏移向量是隨機選取的，兩者組合后可以構(gòu)造出許多種完全不同的幻方圖樣，如果事先不知道這兩個向量，就極難復制出一樣的幻方。

2改進連續(xù)擺數(shù)法的通項公式

如果從1到n2逐個去填入幻方的話，顯然可得時間復雜度即為O（n2），而且需要知道一個數(shù)的坐標才能推算出下一個數(shù)的坐標，所以有必要推導出通項公式，可以直接計算出一個數(shù)的坐標，直接填入幻方中，提高構(gòu)造幻方的效率。

參考文獻：

[1]吳鶴齡. 幻方及其他-娛樂數(shù)學經(jīng)典名題[M]. 北京：科學出版社，2005.

[2] 高治源. 幻方的應用前景[J]. 延安教育學院學報，2000（1）：44-46.

[3] 丁瑋，齊東旭. 數(shù)字圖像變換及信息隱藏與偽裝技術[J]. 計算機學報，1998，21（9）：838-843.

[4] ARONOV B， ASANO T， KIKUCHI Y， et al. A generalization of magic squares with applications to digital halftoning[M]//FLEISCHER R， TRIPPEN G：ISAAC 2004， LNCS 3341.Berlin/Heidelberg： Springer-Verlag， 2004：89-100.

[5] XIE T， CHEN H， KANG L. A unified method of magic square-based two-way certificate authentication and key transferring：China，02114288.2 [P].2002.

[6] XIE T. A magic square based signing method for identification and authentication：China， 200410046922.2[P].2004.

[7] RAMZAN M， KHAN M K. Distinguishing quantum channels via magic squares game[J]. Quantum Information Processing， 2010， 9（6）： 667-679.

[8] ZHANG Jie，LU Yang， YANG Shu， et al. NHPPbased software reliability model considering testing effort and multivariate fault detection rate[J]. Journal of Systems Engineering and Electronics， 2016，27（1）： 260-270.

[9] 馬颯颯，王光平，趙守偉. 基于時間序列的軟件可靠性預測模型研究[J]. 計算機工程與設計，2007，28（11）：2520-2523.

[10]賈治宇，康銳. 軟件可靠性預測的ARIMA方法研究[J]. 計算機工程與應用，2008，44（35）：17-19.

[11]何書元. 應用時間序列分析[M]. 北京： 北京大學出版社，2003.

[12]黃雄波. 多周期時序數(shù)據(jù)的傅氏級數(shù)擬合算法[J]. 計算機系統(tǒng)應用，2015，24（7）：142-148.

[13]黃雄波. 基于自相關函數(shù)的非平穩(wěn)時序數(shù)據(jù)的辨識改進[J]. 微型機與應用，2016，35（13）：10-14，18.

[14]劉思峰，楊英杰. 灰色系統(tǒng)研究進展（2004-2014）[J]. 南京航空航天大學學報，2015，47（1）：1-18.

[15]黨耀國，王俊杰，康文芳. 灰色預測技術研究進展綜述[J]. 上海電機學院學報，2015，18（1）：1-7，18.

[16]鄭咸義，姚仰新，雷秀仁，等. 應用數(shù)值分析[M]. 廣州： 華南理工大學出版社，2008.

[17]李慶揚，關治，白峰彬. 數(shù)值計算原理[M]. 北京： 清華大學出版社，2005.endprint