首页 > ACM题库 > HDU-杭电 > hdu 1998 奇数阶魔方-模拟-[解题报告]C++
2013
12-26

hdu 1998 奇数阶魔方-模拟-[解题报告]C++

奇数阶魔方

问题描述 :

一个 n 阶方阵的元素是1,2,…,n^2,它的每行,每列和2条对角线上元素的和相等,这样
的方阵叫魔方。n为奇数时我们有1种构造方法,叫做“右上方” ,例如下面给出n=3,5,7时
的魔方.
3
8 1 6
3 5 7
4 9 2
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
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
第1行中间的数总是1,最后1行中间的数是n^2,他的右边是2,从这三个魔方,你可看出“右
上方”是何意。

输入:

包含多组数据,首先输入T,表示有T组数据.每组数据1行给出n(3<=n<=19)是奇数。

输出:

包含多组数据,首先输入T,表示有T组数据.每组数据1行给出n(3<=n<=19)是奇数。

样例输入:

2
3
5

样例输出:

   8   1   6
   3   5   7
   4   9   2
  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

应该不算太水吧。

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

对于上面的数据,根据题目中的提示,很容易就看到对角线上的数字是11、12、13、14、15。其他的数据,比如说2,从2往右上查就是2、3、4、5、1。描述起来好像很麻烦,但是对着图看一下就可以很容易看明白。

接下来继续观察数据,我们可以看出在第一行实际上是从1开始往右查每个数字逐个加上n+2,往左先是n*n-1,然后依次减去n+2。第一行和最后一行根据中心点对称的两个数字的和是n*n+1,比如说17+9=25+1,24+2=25+1。

有了这两个规律,仅凭直觉,我们都可以确定用来模拟出结果已经足够了。模拟的方法很多,我的方法是将1~n^2分成n段,用第一行的每个数字来确定它所在的斜边的最小值和最大值,比如说对于17,在16、17、18、19、20这个序列中,最小值就是17/5*5+1=16,最大值是(17+5)/5*5=20。有了这两个值,这一个序列的值就很容易确定了。

1A。

#include<stdio.h>
#include<string.h>
#define N 21
int map[N][N];
int main()
{
    int n;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int x=n+1;
        int y=x/2;
        memset(map,0,sizeof(map));
        map[1][y]=1;
        map[n][y]=n*n;
        int temp=n+2;
        int i,j;
        i=y-1;
        j=y+1;
        int tempx,tempy;
        tempx=n*n-1;
        tempy=1+temp;
        while(i>=1&&j<=n)
        {
            map[1][i]=tempx;
            i--;
            tempx-=temp;
            map[1][j]=tempy;
            j++;
            tempy+=temp;
        }
        temp=1+n*n;
        for(i=1; i<=n; i++)
            map[n][i]=temp-map[1][n+1-i];
        int start,end;
        int l,k;
        for(j=1; j<n; j++)
        {
            start=map[1][j]/n*n+1;
            end=(map[1][j]+n)/n*n;
            for(l=2,k=j-1; l<=n&&k>0; l++,k--)
            {
                if(map[l-1][k+1]!=start)
                    map[l][k]=map[l-1][k+1]-1;
                else
                    map[l][k]=end;
            }
            for(l=n-1,k=j+2; l>=1&&k<=n; l--,k++)
            {
                if(map[l+1][k-1]!=end)
                    map[l][k]=map[l+1][k-1]+1;
                else
                    map[l][k]=start;
            }

        }
        for(l=2,k=n-1; l<=n&&k>=1; l++,k--)
        {
             map[l][k]=map[l-1][k+1]-1;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
                printf("%4d",map[i][j]);
            printf("\n");
        }
    }
    return 0;
}

解题转自:http://blog.csdn.net/zizaimengzhongyue/article/details/9237803


  1. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  3. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。