|
棋盘的完美覆盖： 一张8行8列的棋盘一共有64个方格，用一些形状相同的多米诺骨牌覆盖，每一张覆盖相邻的两个方格，没有相互重叠，能用32张这样的多米诺骨牌完全覆盖整张棋盘称为多米诺骨牌完美覆盖或者盖瓦。这样的完美覆盖是存在的，而且不止一种方式，一共有12988816=2^4*17^2*53^2种。那么对于一般的m行n列的棋盘是否存在着多米诺骨牌完美覆盖呢？充要条件是m*n是偶数，这等价于分子物理学中的二聚物问题。有这样的问题：如果把8行8列的棋盘的一条对角线上的两个角的方格去掉，那么完美覆盖还有多少种呢？这样分析：每一张骨牌覆盖相邻的两个方格，那么就假设棋盘是黑白相间的，呈现这样的场景（1代表黑，0代表白）： 
去掉的两个方格必然是相同的颜色，于是原来32张黑色和32张白色变成了30黑色(白色)，32白色（黑色）。如果31张骨诺牌能够完美覆盖，那么就产生了这样的关系式：31（black+white)=30black+32white [or: 30white+32black] 这显然是不成立的。所以一种完美覆盖都不存在。 拓展：如果棋盘的规格是m*n，且一张牌的长度是b（称作b格牌），那么这样的棋盘能够被b格牌完美覆盖吗？显然，想要完美覆盖，b必然是m*n的因子，这就是充分条件：b是m或者n的因子（联系实际）。事实上有这样的结论：m*n的棋盘有b格牌的完美覆盖当且仅当b是m或者n的一个因子。 幻方： 一个由数字1,2,3--n^2组成n行n列的n阶的幻方，满足每一行每一列两条对角线上的数字之和是等值的，假设这样的值是s。那么有这样的等式：n*s=1+2+3+--+n^2=(n^2+1)/2*n^2. -->s=n*(n^2+1)/2. 所以我们可以推断2阶的魔方阵是不存在的，不然s=5啊，显然这是不可能的。幻方的构造和很多方法，n为奇数时有这样一种应用较广的构造方法：首先把1放在第一行的中间，然后按照左下方到右上方的顺序摆放各个数字（行数i和列数j的变化趋势：向量(i-1,j+1)），遇到特殊的情况： （1）当下一个数字到达已有数字的位置或者四个对角线方向的方阵外时，直接把新的数字放到上一个数字的下面。 （2）当下一个数字的行数到了0时，行数变为n，列数照常加1。 （3）当下一个数字的列数到了n+1时，列数变为1，行数照常减1。 奇数阶幻方（16阶内）： #include"stdio.h"
void xiabiao(int &a, int &b,int n)
{
a-=1;
b+=1;
if(a<0 && b>n-1){ a+=2; b-=1; }
if(a<0)a=n-1;
if(b>n-1)b=0;
}
main()
{
int m[16][16],n;/*h表示最中间的列数*/
int i,j,k=1;
while(~scanf("%d",&n)&&n) //enter a number n.
{
if(n%2==0 || n<1 || n>16)continue;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
m[i][j]=1;
i=0;
j=n/2;
k=1;
while(k<n*n)
{
xiabiao(i,j,n);
if((m[i][j]<k && m[i][j]!=1) || (i==0 && j==n/2)){ i+=2; j-=1; }
m[i][j]=++k;
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%5d",m[i][j]);
printf("\n");
}
}
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
当n是偶数时分成4k（双偶数）和4k+2（单偶数）阶讨论：对于4k，先说说最简单的4阶情况。先把所有的元素从左到右从上到下顺序填写完整，再把对角线 上的所有元素标记，其他元素按照中心对称位置关系两两互换。即可达到幻方效果。将其推广，当k=2,3,4……时同样先顺序填写，再把整个方阵划分成(n/4)*(n/4)个4阶阵，把所有的四阶阵两条对角线的元素标记固定不动，然后再把n*n的方阵的所有非对角线元素以方阵中心为对称点进行中心对称互换（那么对称点的位置关系就是(x1,y1)+(x2,y2)=(n+1,n+1))，最终即可构成n阶幻方阵。 双偶数阶幻方（16阶内）： #include"stdio.h"
#include"string.h"
int m[17][17],n;
bool vis[17][17];
void swap(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
}
void show(){
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
printf("%5d",m[i][j]);
}
printf("\n");
}
}
void block(){
int i,j,k,re=n/4;
for(i=0;i<re;i++){
for(j=0;j<re;j++){
for(k=1;k<=4;k++){
vis[k+4*i][k+4*j]=vis[k+4*i][4+1-k+4*j]=1;
}
}
}
for(i=1;i<=n/2;i++){
for(j=1;j<=n;j++){
if(vis[i][j])continue;
swap(&m[i][j],&m[n+1-i][n+1-j]);
}
}
}
int main(int argc, char *argv[]) {
freopen("cin.txt","r",stdin);
freopen("cout.txt","w",stdout);
int i,j,k;
while(~scanf("%d",&n)&&n){
memset(vis,0,sizeof(vis));
k=1;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
m[i][j]=k++;
}
}
//show();
block();
show();
}
return 0;
}
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
4k+2阶的幻方则稍复杂一点，有这样的方法：现将方阵划分成两个区，边界上所有元素为一个区A，边界内的所有元素构成一个区B，B区即是一个4k阵，把8k+3--16k^2+8k+2的数字填入双偶数阵按照前面的方法进行变化。然后剩下的元素放到边界进行试调，直到满足幻方的条件即可。当然这样在计算机上很难实现。还有一种易于实现的方法：把方阵分为A，B，C，D四个象限，这样每一个象限肯定是奇数阶。依次在A象限，D象限，B象限，C象限按奇数阶幻方的填法填数。以6阶为例如同： 
在A象限的中间行、中间格开始，按自左向右的方向，标出k格。A象限的其它行则标出最左边的k格。将这些格，和C象限相对位置上的数，互换位置。 
在B象限任每行的中间格，自右向左，标出k-1列。(注：6阶幻方由于k-1=0，所以不用再作B、D象限的数据交换)， 将B象限标出的这些数，和D象限相对位置上的数进行交换，就形成幻方。 
单偶数阶幻方（16阶内）： #include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int m[17][17],tag[17][17],n;
int i,j,k;
void show(){
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
printf("%5d",m[i][j]);
}
printf("\n");
}
}
void inital(){ //(1,1),(1,n/2+1),(1+n/2,1),(1+n/2,1+n/2)
int num;
memset(m,0,sizeof(m));
int lo[4][2]={{0,0},{n/2,n/2},{0,n/2},{n/2,0}};
for(k=0;k<4;k++){
num=1+(n/2)*(n/2)*k;
i=lo[k][0]+1;
j=n/2/2+lo[k][1]+1;
int ik=num;
m[i][j]=ik++;
while(ik<num+(n/2)*(n/2))
{
i-=1;
j+=1;
if(i<lo[k][0]+1&& j>n/2+lo[k][1]){ i+=2; j-=1; }
if(i<lo[k][0]+1)i=n/2+lo[k][0];
if(j>n/2+lo[k][1])j=1+lo[k][1];
if((m[i][j]<ik && m[i][j])){ i+=2; j-=1; }
m[i][j]=ik++;
}
}
}
void write(){
memset(tag,0,sizeof(tag));
j=1+n/2/2;
k=n/4;
while(k--){
tag[n/2/2+1][j++]=1;
}
for(i=1;i<=n/2;i++){
if(i==n/2/2+1)continue;
for(j=1;j<=n/4;j++)tag[i][j]=1;
}
for(i=1;i<=n/2;i++){
j=n/2+n/2/2+1;
k=n/4-1;
while(k--){
tag[i][j--]=1;
}
}
}
void showtag(){
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
printf("%5d",tag[i][j]);
}
cout<<endl;
}
}
void swap(int &a,int &b){
int t=a;
a=b;
b=t;
}
void change(){
for(i=1;i<=n/2;i++){
for(j=1;j<=n;j++){
if(tag[i][j])swap(m[i][j],m[i+n/2][j]);
}
}
}
int main(int argc, char *argv[]) {
freopen("cin.txt","r",stdin);
freopen("cout.txt","w",stdout);
while(cin>>n&&n){
inital();
write();
//showtag();
change();
show();
}
return 0;
}
/*
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
10阶：
92 99 1 8 15 67 74 26 58 65
98 80 7 14 16 73 55 32 64 66
4 6 88 95 22 54 56 38 70 72
85 87 19 21 3 60 62 44 71 53
86 93 25 2 9 61 68 50 52 59
17 24 76 83 90 42 49 51 33 40
23 5 82 89 91 48 30 57 39 41
79 81 13 20 97 29 31 63 45 47
10 12 94 96 78 35 37 69 46 28
11 18 100 77 84 36 43 75 27 34
14阶：
177 186 195 1 10 19 28 128 137 97 50 108 117 126
185 194 154 9 18 27 29 136 145 56 58 116 125 127
193 153 155 17 26 35 37 144 104 57 66 124 133 135
5 14 16 172 181 183 45 103 112 65 74 132 134 143
160 162 171 33 42 44 4 111 113 73 82 140 142 102
168 170 179 41 43 3 12 119 121 81 90 141 101 110
169 178 187 49 2 11 20 120 129 89 98 100 109 118
30 39 48 148 157 166 175 79 88 146 99 59 68 77
38 47 7 156 165 174 176 87 96 105 107 67 76 78
46 6 8 164 173 182 184 95 55 106 115 75 84 86
152 161 163 25 34 36 192 54 63 114 123 83 85 94
13 15 24 180 189 191 151 62 64 122 131 91 93 53
21 23 32 188 190 150 159 70 72 130 139 92 52 61
22 31 40 196 149 158 167 71 80 138 147 51 60 69
*/
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16.
- 17.
- 18.
- 19.
- 20.
- 21.
- 22.
- 23.
- 24.
- 25.
- 26.
- 27.
- 28.
- 29.
- 30.
- 31.
- 32.
- 33.
- 34.
- 35.
- 36.
- 37.
- 38.
- 39.
- 40.
- 41.
- 42.
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50.
- 51.
- 52.
- 53.
- 54.
- 55.
- 56.
- 57.
- 58.
- 59.
- 60.
- 61.
- 62.
- 63.
- 64.
- 65.
- 66.
- 67.
- 68.
- 69.
- 70.
- 71.
- 72.
- 73.
- 74.
- 75.
- 76.
- 77.
- 78.
- 79.
- 80.
- 81.
- 82.
- 83.
- 84.
- 85.
- 86.
- 87.
- 88.
- 89.
- 90.
- 91.
- 92.
- 93.
- 94.
- 95.
- 96.
- 97.
- 98.
- 99.
- 100.
- 101.
- 102.
- 103.
- 104.
- 105.
- 106.
- 107.
- 108.
- 109.
- 110.
- 111.
- 112.
- 113.
- 114.
- 115.
- 116.
- 117.
- 118.
- 119.
- 120.
- 121.
- 122.
|
