Chinaunix首页 | 论坛 | 博客
  • 博客访问: 282696
  • 博文数量: 69
  • 博客积分: 2946
  • 博客等级: 少校
  • 技术积分: 800
  • 用 户 组: 普通用户
  • 注册时间: 2010-04-09 04:15
文章分类

全部博文(69)

文章存档

2013年(6)

2012年(16)

2011年(18)

2010年(29)

分类: C/C++

2010-05-12 04:44:33

n阶幻方的生成
分为三种情况:
  1. 奇数阶幻方
  2. 双偶数阶幻方 (n能被4整除)
  3. 但偶数阶幻方 (n能被2整除,但不能被4整除)、
下面分别介绍算法 

1.奇数阶幻方:
这种情况算法比较简单。先把第一行数字填好,填写的规律是
从0到(n-1)/2这些数的填写 a[0][i]=(n+1)/2+i ;
从(n+1)/2 到n-1 这些数的填写规律是 a[0][i]=
=i-(n-1)/2;
然后填第二行用轮移第一行的得到,填第三行的用轮移第二行的得到,一次类推就得到矩阵A;
轮移规律是:a[i][j]=a[i-1][j-1]  a[i][0]=a[i-1][n-1];
最后得到矩阵B,其中对应的公式b[i][j]=(a[i][j]-1)*n ;
最终的结果是 c[i][j]=b[i][j]+a[i][n-1-j];
输出 矩阵C,便是幻方;

2.双偶数阶幻方 :
算法内容比较多些,我提供两个链接,这里写的比较详细,大家可以参考参考:
zhangshourui/blog/item
/20d6374e620129cbd1c86a98.html

%C7%D8%B1%B1%BD%FA%C4%CF/blog/item/ef4d281d36c36368f624e480.html


3.单偶阶幻方

#include<iostream>
#include<cstdlib>
#define max 502
int array[max][max]={0};
int a[max][max] = {0} ;
using namespace std ;

void lun(int i , int n )
{
     for(int j=1;j<n;j++)
     array[i][j]=array[i-1][j-1];
     array[i][0]=array[i-1][n-1];
}

void swap(int i , int k,int t)
{
     int temp ;
     temp = a[i][k];
     a[i][k]=a[i+t][k];
     a[i+t][k]=temp ;
}
     
void setshun(int p , int q , int n)
{
     int temp = n*n + 1 ;
     for(int i=0;i<4;i++)
     {
             a[p-i][q+i]=temp - a[p-i][q+i];
             a[p-3+i][q+i]=temp - a[p-3+i][q+i];
     }
}
           
void quen(int n) //奇幻方
{
     for(int i=0;i<=(n-1)/2;i++)
     array[0][i]=(n+1)/2+i ;
     for(int i=(n+1)/2;i<n;i++)
     array[0][i]=i-(n-1)/2;
     for(int i=1;i<n;i++)
     lun(i,n);
     for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
           a[i][j]=(array[i][j]-1)*n+array[i][n-1-j];
}

void dduen(int n) //双偶幻方
{
    int k =1 ;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
           a[i][j]= k ++ ;
    int flag = n/4 ;
    for(int i= 1 ; i<=flag ;i++)
        for(int j=0;j<flag;j++)
           setshun(4*i-1,4*j,n) ;
}

void duen(int n) //单偶幻方
{
  int t = n/2 ;
  quen(t); //求A部分
  int s = t*t ;
  int * p = new int[t] ;
  
  for(int i=0;i<t;i++) //*p的初始化
  p[i]=0;
  p[(t-1)/2]= (t-1)/2 ;
  
  int flag = (n-2)/4 ;
  for(int i=0;i<t;i++)
     for(int j=0;j<t;j++)
        { //A
             a[i][j+t]=a[i][j]+s*2 ; //B
             a[i+t][j]=a[i][j]+s*3 ; //C
             a[i+t][j+t]=a[i][j]+ s ; //D
        }
  for(int i=0;i<t;i++) //A,C象限交换
     for(int u=0;u<flag;u++)
         swap(i,p[i]+u,t);
  for(int i=t+(t-1)/2 ; i<t+(t-1)/2+flag-1;i++) //B,D象限交换列
       for(int j=0;j<t;j++)
             swap(j,i,t);
 }
int main()
{
    int number ;
    cin>>number ;
    int * p = new int[2*number+2];
    
    if(number%2!=0&&number>2)
    quen(number);
    else if(number%4==0&&number>2)
         dduen(number);
         else if((number%4!=0&&number%2==0)&&number>2)
                duen(number);
    for(int i=0;i<number;i++)
       for(int j=0;j<number;j++)
        {
                cout<<a[i][j]<<" ";
                if(j==number-1)cout<<endl;
        }

    system("pause");
    return 0 ;
}


阅读(1928) | 评论(0) | 转发(1) |
0

上一篇:xmu1008 皇后问题

下一篇:xmu1030 月老的难题

给主人留下些什么吧!~~