求魔方阵的十种算法.docx
《求魔方阵的十种算法.docx》由会员分享,可在线阅读,更多相关《求魔方阵的十种算法.docx(29页珍藏版)》请在冰点文库上搜索。
求魔方阵的十种算法
求魔方阵的十种算法
魔方阵,古代又称“纵横图”,是指组成元素为自然数一、2…n的平方的n×n的方阵,其中每一个元素值都不相等,且每行、每列和主、副对角线上各n个元素之和都相等。
如3×3的魔方阵:
8 1 6
3 5 7
4 9 2
魔方阵的排列规律如下:
(1)将1放在第一行中间一列;
(2)从2开始直到n×n止各数依次按下列规则存放;每一个数存放的行比前一个数的行数减1,列数加1(例如上面的三阶魔方阵,5在4的上一行后一列);
(3)如果上一个数的行数为1,则下一个数的行数为n(指最下一行);例如1在第一行,则2应放在最下一行,列数同样加1;
(4)当上一个数的列数为n时,下一个数的列数应为1,行数减去1。
例如2在第3行最后一列,则3应放在第二行第一列;
(5)如果按上面规则确定的位置上已有数,或上一个数是第一行第n列时,则把下一个数放在上一个数的下面。
例如按上面的规定,4应该放在第1行第2列,但该位置已经被占据,所以4就放在3的下面;
1居上行正中央
依次右上切莫忘
上出框时往下写
右出框时左边放
右上有数下边写
右上出框也一样
一、魔方阵的简介
二、
三、1.何谓矩阵?
矩阵就是由方程组的系数及常数所构成的方阵。
把用在解线性方程组上既方便,又直观。
四、
五、2.何谓n阶方阵?
若一个矩阵是由n个横列与n个纵行所构成,共有个小方格,则称这个方阵是一个n阶方阵。
六、
七、3.何谓魔方阵?
492357816概念:
由n*n个数字所组成的n阶方阵,具有各对角线,各横列与纵行的数字和都相等的性质,称为魔方阵。
而那个相等的和称为魔术数字。
若填入的数字是从1到n*n,称此种魔方阵为n阶正规魔方阵。
八、
九、4.最早的魔方阵相传古时为了帮忙治水专家大禹统治天下,由水中浮出两只庞大动物背上各负有一图,只有大禹才可指挥其中之由龙马负出的为河图,出自黄河;另一由理龟负出的洛书出自洛河。
洛书
十、
十一、5.最早的四阶魔方阵最先的四阶方阵刻在印度一所庙宇石上,年代大约是十一世纪。
古代印度人十分崇拜这种幻方,至今从古神殿的遗址,墓碑上常常还能够发觉四阶幻方的遗迹。
十二、
十三、6.欧洲最早的魔方阵欧洲最先的方阵是公元1514年德国画家AlbrechtDure在他著名的铜板画Melencolia上的4×4幻方,有趣的是,他连创造年代(1514)也镶在那个方阵中,而且上下左右,四个小方阵的和皆为34,是欧洲最古老的幻方。
十四、
十五、
十六、二、魔方阵的变形
十七、
十八、1.相异魔方阵对应方格所填的数字不相同的两个魔方阵,如下图
十九、1602031301150414051110081206090709070612130316020414150108100511
二十、
二十一、2.相等魔方阵每一个对应方格所填的数字都相同的两个魔方阵,如下图492492357357816816
二十二、
二十三、3.全等魔方阵若一个魔方阵能够通过旋转或镜射的方式变成和另一个魔方阵相等,称这两个魔方阵全等。
在计算魔方阵个数时,咱们把全等的魔方阵视为同一种。
276834951159438672
二十四、
二十五、4,刚性变形法
(1)顺时针方向旋转90
(2)顺时针方向旋转180(3)顺时针方向旋转270(4)左右翻转(绕铅直对称轴镜射)(5)上下翻转(绕水平对称轴镜射)(6)左上右下翻转(绕右上至左下对角线镜射)(7)右上左下翻转(绕左上至右下对角线镜射)
二十六、
二十七、原始方阵旋转90。
旋转180。
旋转270。
01031614120813010705101214040907131502041006150309110608160211050806110905110216040215130315061012100507070904141416030101130812
二十八、
二十九、左右翻转上下翻转左上右下翻转右上左下翻转141603011210050707090414011308120402151308061109051102160315061009110608131502041006150316021105070510120103161412081301140409075.加值变形法正规魔方阵:
首项是1,公差是1加值变形后的魔方阵:
首项是a,公差是r
三十、
三十一、原始魔方首项为5公差为1首项为5公差为2141603011820070531350905040215130806191711073329091106081315101221251519070510121109141617132327
三十二、
三十三、6.互补变形法就是将魔方阵中的每一个数字都替换成互补数的变形方式。
在n阶魔方阵中,数字k的互补数=(1+n*n)–k
三十四、
三十五、原始魔方阵互补变形魔方阵1416030103011416040215131315020409110608080611090705101210120705
三十六、
三十七、7.田字变形法以中心点为准将魔方阵分成四个相等的小方阵。
当n为奇数时,中央的行列要独立出来。
三十八、
三十九、n是偶数时n是奇数时ABAA1BDC?
D1EB1DC1C将魔方阵如下重组:
CD?
CC1D?
BAB1ED1BA1A
四十、
四十一、可参考下面的范例:
原始4阶魔方阵4阶田字变形魔方阵原始5阶魔方阵5阶田字变形魔方阵010316141109080618220110141317092105131502040507121004081216252403200711080611091614010315192302060206231519121005070204131521050913171014011822071120240316251204088.井字对换变形法
(1)任选一数k,1<=k<=n。
(2)将方阵的第k行和其互补行(第n+1-k行)对换。
(3)将方阵的第k列和其互补列(第n+1-k列)对换。
(4)为方便称号,现在姑且命名为k值井字对换变形。
四十二、
四十三、原始魔方阵1值井字对换魔方阵2值井字对换魔方阵1,2值井字对换魔方阵010316140710051201160314070510121315020404150213081106090911060808061109090611081302150404021513121005071403160112051007141603019.拓朴变形法
(1)任选不相等的两数1<=k1,k2<=n,但当(n+1)/2为奇数时,k1及k2不能等于(n+1)/2。
(2)将座标含k1值的全改成k2。
含k2值的全改成k1。
含n+1-k1值的全改成n+1-k2。
含n+1-k2值的全改成n+1-k1。
(3)为方便称号,现在姑且命名为k1,k2拓朴变形。
四十四、
四十五、可参考下面的3阶1,3拓朴变形示意图(1,1)(1,2)(1,3)(3,3)(3,2)(3,1)(2,1)(2,2)(2,3)(2,3)(2,2)(2,1)(3,1)(3,2)(3,3)(1,3)(1,2)(1,1)
四十六、
四十七、可参考下面的范例原始魔方阵1,2拓朴变形魔方阵1822011014080412251604081216252218011410151923020619152306022105091317110720032407112024030521091713注:
其实对换变形、田字变形可包括于拓朴变形中,只因想法不同故列出参考
四十八、
四十九、
五十、三、奇数阶魔方阵的建构法
五十一、
五十二、1.杨辉法发明者:
杨辉适用:
三阶魔方阵方式:
九子斜排,上下对易,左右相更,四维挺进
五十三、
五十四、***1*****4*2**492*7*5*3* 357**8*6** 816***9***
五十五、
五十六、杨辉法推广-菱形法发明者:
BachetdeMeziriac适用:
奇数阶魔方阵方式:
数字斜排,上下对易,左右相更,四维挺进
五十七、
五十八、********01**************06**02******?
?
?
****11**07**03****1124072003**16**12**08**04**041225081621**17**13**09**051705132109**22**18**14**10**1018011422****23**19**15****?
2306190215******24**20**************25********
五十九、
六十、2.简捷连续填制法发明者:
DeLaLoubere适用:
奇数阶魔方阵方式:
1立首列中,右一上一,受阻下一
六十一、
六十二、**1****1****1****1****18*17241815***********5****5****57**23571416**********4****46***46***46132022**************3****310***3101219213********2****2****2*11**2911182529简捷连续填制法推广适用:
奇数阶魔方阵方式:
(1)1立首列中,右1上1,受阻下1;
(2)1立中央上,右1下2,受阻上2;(3)1立首行中,右2下1,受阻右1;(4)1立首列中,右1下2,受阻下4;(5)1立中央上,右1上1,受阻上2;(6)1立首行中,左1上1,受阻右1。
六十三、
六十四、3.辅助方阵法适用:
五阶以上奇数阶魔方阵方式:
(1)制作辅助方阵一:
在左上端填入1,依照走马的方式往右二下一的方向填入1至底,接着在每列的1的右边依序填入二、3、4…n1****1234512345**1****1**45123****1****123451*1****1***51234***1****1*34512
(2)制作辅助方阵二:
在左上端填入0,依照走马的方式往右一下二的方向填入0至底,接着在每列的0的下面依序填入n、2n、3n…n(n-1)0****0155201011782415***0*5201001592511218*0***10015520123191021****01552010020622134**0**2010015523145167(3)将辅助方阵一与二的对应方格内之数相加填到一个新的方阵对应方格内,则新的方阵即为一个魔方阵。
六十五、
六十六、4.扩阶法适用:
n阶魔方阵,n为大于5的正整数方式:
(1)先建构出一个n-2阶的魔方阵
(2)将
(1)所成立的魔方阵每一个数字再加上2n-2(3)将步骤
(2)的魔方阵外面再加上一圈,这一圈有4n-4个空格,填入的数为1~(2n-2)和(-2n+3)~n*n,先算出魔术数字会比较好填。
六十七、
六十八、816160914230102201935711131522160914044921217100511131521081217101807252406035.方阵合成法适用:
当魔方阵的阶数n可分解成两个大于2之整数p、q的乘积方式:
假设A=[(a)ij]与B=[(b)ij]别离代表m阶与n阶魔方阵,对每一个t=1,2…m*m,令At=[(a)ij+m*m(t–1)]。
接着咱们将方阵B中的数t以m阶魔方阵(A)t代替,就可以够取得一个m.n阶魔方阵。
六十九、
七十、可参考下面的范例魔方阵A魔方阵B352833261924716469816438303234212325666870357951313629222720677265492276807378443742080106757779394143030507A4A3A8768174404538040902A9A5A1171015625560534651A2A7A6121416575961485052131811586356495447
七十一、
七十二、
七十三、四、偶数阶魔方阵的建构法
七十四、
七十五、1、杨辉法发明者:
杨辉适用:
4阶魔方阵方式:
以十六子,依次递作四行排列,先之外四子对换,一换十六、四换十三,以四内角对换,六换十一、七换十,横直上下斜角,皆三十四数,对换止可施之于小。
七十六、
七十七、010203041602031316020313050607080506070805111008091011120910111209070612131415160414150104141501
七十八、
七十九、杨辉法推广-消去对角线法适用:
四之倍数阶魔方阵方式:
(1)先将整个方阵划分成k*k个4阶方阵,然后在每一个4阶方阵的对角线上做记号
(2)由左而右、由上而下,碰到没有记号的位置才填数字,但无论是不是填入数字,每移动一格数字都要加1(3)自右下角开始,由右而左、由下而上,碰到没有数字的位置就填入数字,但每移动一格数字都要加1
八十、
八十一、2.井字法适用:
四之倍数阶魔方阵方式:
(1)把1~n*n从左上角依序填入方阵内
(2)用两条铅直线和两条水平线将方阵分隔成四个角落各有一个n/4阶的子方阵,和中心位置有一个n/2阶的子方阵(3)以方阵中心为对称点,将五个子方阵的数字作对称互换,其它的数字不要动。
如此的方阵会是一个魔方阵
八十二、
八十三、0102030416020313050607080506070809101112091011121314151604141501
八十四、
八十五、3.辅助方阵法适用:
偶数阶魔方阵(因非四的倍数作法相当复杂,在此只介绍四的倍数的作法)方式:
(1)制作辅助方阵一:
第一列由左向右排列1至n,第二列由右向左排列1至n,第三列同第二列,第四列同第一列,若超过四列,重复一至四列的作法,完成辅助方阵一
(2)制作辅助方阵二:
将第一个辅助方阵各方格内的数字x换成n(x-1),再做行列互换,完成辅助方阵二(3)将辅助方阵一与二的对应方格内之数相加填到一个新的方阵对应方格内,则新的方阵即为一个魔方阵010203040012120001141504040302010408080408111005040302010804040812070609010203041200001213020316
八十六、
八十七、4.扩阶法同奇数阶之作法
八十八、
八十九、5.方阵合成法同奇数阶之作法
九十、具体做法:
九十一、
九十二、方法一;
九十三、
九十四、/*此程序使我按照上面介绍的魔方阵的规律编写的,不过只能求奇数魔方阵,通过测试能够算到508阶*/
九十五、#defineN7
九十六、#include<>
九十七、voidmain()
九十八、{
九十九、 inta[N][N],i,j,k;
一百、 for(i=0;i一百零一、 for(j=0;j一百零二、 {
一百零三、 a[i][j]=0; /*先令所有元素都为0*/
一百零四、 }
一百零五、 j=(N-1)/2; /*判断j的位置*/
一百零六、 a[0][j]=1; /*将1放在第一行中间一列*/
一百零七、 for(k=2;k<=N*N;k++) /*再从2开始处理*/
一百零八、 {
一百零九、 i=i-1; /*存放的行比前一个数的行数减1*/
一百一十、 j=j+1; /*存放的列比前一个数的列数加1*/
一百一十一、 if((i<0)&&(j==N)) /*前一个数是第一行第N列时,把下一个数放在上一个数的下面*/
一百一十二、 {
一百一十三、 i=i+2;
一百一十四、 j=j-1;
一百一十五、 }
一百一十六、 else
一百一十七、 {
一百一十八、 if(i<0) /*当行数减到第一行,返回到最后一行*/
一百一十九、 i=N-1;
一百二十、 if(j>N-1) /*当列数加到最后一行,返回到第一行*/
一百二十一、 j=0;
一百二十二、 }
一百二十三、 if(a[i][j]==0) /*如果该元素为0,继续执行程序*/
一百二十四、 a[i][j]=k;
一百二十五、 else /*如果该元素不为0,就说明要填的数的位置已经被占,则该数放在上一个数的下面*/
一百二十六、 {
一百二十七、 i=i+2;
一百二十八、 j=j-1;
一百二十九、 a[i][j]=k;
一百三十、 }
一百三十一、 }
一百三十二、 for(i=0;i一百三十三、 {
一百三十四、 for(j=0;j一百三十五、 printf("%5d",a[i][j]);
一百三十六、 printf("\n\n");
一百三十七、 }
一百三十八、 }
一百三十九、方式二:
一百四十、
一百四十一、/*这个是网友qfyzy为帮助我找错而提供的,可以算到99阶*/
一百四十二、#defineN7
一百四十三、#include<>
一百四十四、voidmain()
一百四十五、{
一百四十六、 inta[N][N]={0},i=0,j,k; /*先令所有元素都为0*/
一百四十七、 j=(N-1)/2;
一百四十八、 i=0;
一百四十九、 for(k=1;k<=N*N;) /*开始处理*/
一百五十、 {
一百五十一、 if((i<0)&&(j==N)) /*前一个数是第一行第N列时,把下一个数放在上一个数的下面*/
一百五十二、 {
一百五十三、 i=i+2;
一百五十四、 j=j-1;
一百五十五、 }
一百五十六、 else if(i<0) /*当行数减到第一行,返回到最后一行*/
一百五十七、 i=N-1;
一百五十八、 else if(j>N-1) /*当列数加到最后一行,返回到第一行*/
一百五十九、 j=0;
一百六十、 else if(!
a[i][j]){ /*如果该元素为0,继续执行程序*/
一百六十一、 a[i][j]=k++;
一百六十二、 i=i-1;
一百六十三、 j=j+1;
一百六十四、 }
一百六十五、 else /*如果该元素不为0,就说明要填的数的位置已经被占,则该数放在上一个数的下面*/
一百六十六、 {
一百六十七、 i=i+2;
一百六十八、 j=j-1;
一百六十九、 }
一百七十、 }
一百七十一、 for(i=0;i一百七十二、 {
一百七十三、 for(j=0;j一百七十四、 printf("%5d",a[i][j]);
一百七十五、 printf("\n\n");
一百七十六、 }
一百七十七、 }
一百七十八、方式三:
一百七十九、
一百八十、/*此程序是在网上找到的c程序设计习题的答案,只能算奇数阵,可以算到15阶*/
一百八十一、#include<>
一百八十二、voidmain()
一百八十三、{inta[16][16],i,j,k,p,m,n;
一百八十四、p=1;
一百八十五、while(p==1)
一百八十六、 {printf("请输入阶数:
"); /*原答案没有这个输出语句*/
一百八十七、 scanf("%d",&n);
一百八十八、 if((n!
=0)&&(n<=15)&&(n%2!
=0))p=0;
一百八十九、 }
一百九十、for(i=1;i<=n;i++)
一百九十一、 for(j=1;j<=n;j++)
一百九十二、 a[i][j]=0;
一百九十三、j=n/2+1;
一百九十四、a[1][j]=1;
一百九十五、fo