对平é¢å¹»æ¹çæé ï¼å为ä¸ç§æ
åµï¼N为å¥æ°ãN为4çåæ°ãN为å
¶å®å¶æ°(4n+2çå½¢å¼)
â´ N 为å¥æ°æ¶ï¼æç®å
(1) å°1æ¾å¨ç¬¬ä¸è¡ä¸é´ä¸å;
(2) ä»2å¼å§ç´å°nÃnæ¢åæ°ä¾æ¬¡æä¸åè§ååæ¾ï¼
æ 45°æ¹åè¡èµ°ï¼å¦åå³ä¸
æ¯ä¸ä¸ªæ°åæ¾çè¡æ¯åä¸ä¸ªæ°çè¡æ°å1ï¼åæ°å 1
(3) å¦æè¡åèå´è¶
åºç©éµèå´ï¼ååç»ã
ä¾å¦1å¨ç¬¬1è¡ï¼å2åºæ¾å¨æä¸ä¸è¡ï¼åæ°åæ ·å 1;
(4) å¦ææä¸é¢è§åç¡®å®çä½ç½®ä¸å·²ææ°ï¼æä¸ä¸ä¸ªæ°æ¯ç¬¬1è¡ç¬¬nåæ¶ï¼
åæä¸ä¸ä¸ªæ°æ¾å¨ä¸ä¸ä¸ªæ°çä¸é¢ã
âµ N为4çåæ°æ¶
éç¨å¯¹ç§°å
ç´ äº¤æ¢æ³ã
é¦å
ææ°1å°nÃnæä»ä¸è³ä¸ï¼ä»å·¦å°å³é¡ºåºå¡«å
¥ç©éµ
ç¶åå°æ¹éµçææ4Ã4åæ¹éµä¸ç两对è§çº¿ä¸ä½ç½®çæ°å
³äºæ¹éµä¸å¿ä½å¯¹
称交æ¢ï¼å³a(i,j)ä¸a(n-1-i,n-1-j)交æ¢ï¼ææå
¶å®ä½ç½®ä¸çæ°ä¸åã
(æè
å°å¯¹è§çº¿ä¸åï¼å
¶å®ä½ç½®å¯¹ç§°äº¤æ¢ä¹å¯)
ⶠN 为å
¶å®å¶æ°æ¶
å½n为é4åæ°çå¶æ°(å³4n+2å½¢)æ¶ï¼é¦å
æ大æ¹éµå解为4个å¥æ°(2m+1é¶)åæ¹éµã
æä¸è¿°å¥æ°é¶å¹»æ¹ç»å解ç4个åæ¹éµå¯¹åºèµå¼
ä¸å·¦åéµæå°(i)ï¼ä¸å³åéµæ¬¡å°(i+v)ï¼ä¸å·¦åéµæ大(i+3v)ï¼ä¸å³åéµæ¬¡å¤§(i+2v)
å³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è¯è¨å®ç°
#include"stdio.h"
#include"math.h"
int a[256][256];
int sum;
int check();
void ins(int n);
main()
{
int i,j,n,k,t,p,x;
scanf("%d",&n);
sum=(n*n+1)*n/2;
if(n%2==1)//å¥æ°å¹»æ¹
{
ins(n);
k=n;
}
if(n%4==2)//åå¶æ°å¹»æ¹
{
k=n/2;
ins(k);
for(i=0;i<k;i++)
for(j=0;j<k;j++)
{
a[j+k]=a[j]+2*k*k;
a[i+k][j]=a[j]+3*k*k;
a[i+k][j+k]=a[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[j];a[j]=a[i+k][j];a[i+k][j]=p;
}
if((j<t)&&(i>k-t-1))
{
p=a[j];a[j]=a[i+k][j];a[i+k][j]=p;
}
if((i>=t&&i<=k-t-1)&&(j>=t&&j<t*2))
{
p=a[j];a[j]=a[i+k][j];a[i+k][j]=p;
}
if(j>1&&j<=t)
{
p=a[j+k];a[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[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;
else if(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[j]);
printf("\n");
}
return ;
}
}
int check(int n)//æ£éªæ¯å¦æ¯å¹»æ¹
{
int i,j,sum1=0,sum2;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
sum1+=a[j];
if(sum1!=sum) return 0;
sum1=0;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
sum1+=a[j];
if(sum1!=sum) return 0;
sum1=0;
}
for(sum1=0,sum2=0,i=0,j=0;i<n;i++,j++)
{
sum1+=a[j];
sum2+=a[n-j-1];
}
if(sum1!=sum) return 0;
if(sum2!=sum) return 0;
else return 1;
}
void ins(int n)//åå¶æ°å¹»æ¹çè¾å
¥
{ int x,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;
}
}
}
å¥é¶å¹»æ¹
å½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æ³çæç7é¶å¹»æ¹ï¼
30 39 48 1 10 19 28
38 47 7 9 18 27 29
46 6 8 17 26 35 37
5 14 16 25 34 36 45
13 15 24 33 42 44 4
21 23 32 41 43 3 12
22 31 40 49 2 11 20
horseæ³çæå¥é¶å¹»æ¹
å
å¨ä»»æä¸æ ¼å
æ¾å
¥1ãå左走1æ¥ï¼å¹¶ä¸èµ°2æ¥æ¾å
¥2(称为马æ¥)ï¼å左走1æ¥ï¼å¹¶ä¸èµ°2æ¥æ¾å
¥3ï¼ä¾æ¬¡ç±»æ¨æ¾å°nãå¨nçä¸æ¹æ¾å
¥n+1ï¼ç§°ä¸ºè·³æ¥ï¼ï¼åæä¸è¿°æ¹æ³æ¾ç½®å°2nï¼å¨2nçä¸è¾¹æ¾å
¥2n+1ãå¦ä¸å¾ç¨Horseæ³çæç5é¶å¹»æ¹ï¼
77 58 39 20 1 72 53 34 15
6 68 49 30 11 73 63 44 25
16 78 59 40 21 2 64 54 35
26 7 69 50 31 12 74 55 45
36 17 79 60 41 22 3 65 46
37 27 8 70 51 32 13 75 56
47 28 18 80 61 42 23 4 66
57 38 19 9 71 52 33 14 76
67 48 29 10 81 62 43 24 5
ä¸è¬çï¼ä»¤ç©éµ[1,1]为åå³èµ°ä¸æ¥ï¼åä¸èµ°ä¸æ¥ï¼[-1,0]为å左走ä¸æ¥ãå马æ¥å¯ä»¥è¡¨ç¤ºä¸º2X+Yï¼{Xâ{[1,0], [-1,0]},Yâ{[0,1], [0,-1]}}âª{Yâ{[1,0], [-1,0]},Xâ{[0,1], [0,-1]}}ã对äº2X+Yç¸åºçè·³æ¥å¯ä»¥ä¸º2Y,-Y,X,-Y,X,3X,3X+3Yãä¸é¢ççæ¯Xåè·³æ¥ãHorseæ³çæçå¹»æ¹ä¸ºé鬼幻æ¹ã
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)ã
åèèµæï¼http://baike.baidu.com/view/5058.html?wtp=tt