用c++实现一个n*n矩阵，矩阵沿着45度递增，形成zigzag数组

程序员面试宝典上的一道题：

输入n，求一个nXn矩阵，规定矩阵沿45度递增，形成一个zigzag数组(JPEG编码里取像素数据的排列顺序)，请问如何用C++实现？
（中国台湾著名硬件公司2007年11月面试题）（自程序员面试宝典第五版95页）

觉得这道题比较经典，难度适中，因此记录下来。
zigzag数组形状如下：

/*
打印zigzag数组
  1   5   6  14  15  27  28  
  4   7  13  16  26  29  42  
  8  12  17  25  30  41  43  
 11  18  24  31  40  44  53  
 19  23  32  39  45  52  54  
 22  33  38  46  51  55  60  
 34  37  47  50  56  59  61 
 36  48  49  57  58  62  63 
*/

书上的解法是：

int main()
{
	int N;
	int s, i, j;
	int squa;
	scanf_s("%d", &N);
	int **a = (int **)malloc(N * sizeof(int));
	if (NULL == a)
	{
		return 0;
	}


	//空间分配
	for (i = 0; i < N; i++)
	{
		if (NULL == (a[i] = (int*)malloc(N * sizeof(int))))
		{
			while (--i >= 0)
				free(a[i]);
			free(a);
			return 1;
		}
	}
	squa = N * N;


	//求对应位置上应填写的值
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			s = i + j;

			if (s < N)//上三角
			{
				s = i + j;//为了看的更清楚，这里加了这条与下面对称的语句    
				a[i][j] = s * (s + 1) / 2 + ((0 == (i + j) % 2) ? i : j);
			}
			else//下三角
			{
				s = (N - 1 - i) + (N - 1 - j);
				a[i][j] = squa - s * (s + 1) / 2 - (N - ((0 == (i + j) % 2) ? i : j));
			}
		}
	}


	//打印输出
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
			printf("%6d", a[i][j]);
		printf("\n");
	}
	system("pause");
	return 0;
}

其思路是把矩阵分为左上三角和右下三角两个部分。
可以看出，zigzag数组是一个“之”字形排列的数组，按对角线方向递增。
对左上部分来说，有几个规律：

（1）沿着红色箭头的方向，数组的值从0开始，每次加1，逐渐增大。

（2）每条红线上的下标之和均相等，例如第三条红线，下标和都是2；并且下标和从0开始，每次加1，依次增加。矩阵对角线的下标和是6。

（3）第零条红线上数字个数为一个（下标和为0），第一条红线上数字为2个（下标和为1），……，对角线为第六条红线，数字个数为七（下标和为6）。即：第s条红线上数字个数为s + 1个，s = 下标和。设二维数组的某个下标为（i,j），那么下标和s = i + j。

（4）每条斜线上第一个数字（也是最小的数字）是上一行最大数字加1。也等于之前所有斜线上的数字的个数之和，例如第四条斜线上第一个数组是6，它等于第一、二、三条斜线上的数字之和6。

（5）而每条斜线上数字个数是一个等差数列，第0斜线1个，第1斜线2个，……，第s斜线s + 1个。又因为 s = i + j ，因此，前s条（从0条到第s-1条）斜线上一共有1 + 2 + ……+ s个数字，也就是s(s+1)/2个数字；转化为与下标相关：用下标表示(s= i+j)：s(s+1)/2。即，下一斜线的第一个数字值就是s(s+1)/2。

     得到了每条斜线上第一个数字的值，那么该斜线上之后的每个值都是在这个值的基础上依次加1得到的。

（6）下标和为奇数时红线的箭头是向左下方的，且下标i是从0依次增大的；下标和为偶数时箭头是朝右上方的，且下标j是从0依次增大的。因此某斜线上的数字a[i][j]可以表示如下：当s % 2 != 0，即下标和为奇数时，表示为s(s+1)/2 + i；当s%2 ==0，即下标和为偶数时，表示为s(s+1)/2 + j。

因此某个位置上的值为s(s+1)/2 + ((i + j)%2 != 0 ? 0:1)

（7）当下标和s 1等于输入的n - 1时，就是矩阵的对角线，这个作为左上部分结束的条件。

对于右下部分，图中显示的该部分相对于n* n所应该减去的值，这里nn=77= 49。例如最左侧第一条斜线上数字48 = n*n - 1，所以图3该位置标为-1，这是为了方便找规律。

用c++实现一个n*n矩阵，矩阵沿着45度递增，形成zigzag数组
左下部分从最左侧的斜线开始，也符合以下几个规律：

（1）该部分第一条斜线也是由一个元素组成，第二条斜线是由两个元素组成，……

（2）相对于n*n所减去的值不断加1，因此，该部分每个数字值都是n*n减去某个有规律的数。

根据左上部分的规律，也从只有一个元素的斜线来分析该部分：

将下标与斜线条数关联：

第s条（s大于等于0）斜线与下标i和j的关系：s=2n - (i + j) - 2。例如上图左下部分最长的斜线为第5条斜线：5 = 2*7 - 7 - 2。

那么第s条斜线左方所有的斜线上的数字个数之和D为D = 1+2+……+s = s(s+1)/2。

第s条斜线上的第一个元素减去的值为s(s+1)/2 + 1，即D+1，第2个数为D+2，第k个数是D+k，即某斜线第k个数上减去的值为D + i，如何k跟下标发生关系呢？在右上部分时，这个1直接是与i或j相同，但这里分析图1并不能直接与i或j相关，分析可以得到k可以用k = n - ((i + j)%2 != 0 ? i ： j)来表示。

所以某个位置上相对于n*n减去的值是D +k = s(s+1)/2 + n - ((i + j)%2 != 0 ? i ： j)，因此某个位置上的值为n*n - (D + k) = n*n - [s(s+1)/2 + n - ((i + j)%2 != 0 ? i ： j)]。

另外一种解法是：

#include <stdlib.h>
#include <stdio.h>

#define N  8

int a[100][100];

void Print_Zigzag(int n);

int main()
{
    Print_Zigzag(N);
    for(int i=0;i<N;i++)
    {
        printf("\n");
        for(int j=0;j<N;j++)
            printf("%d\t",a[i][j]);
    }    
    return 0;
}


void Print_Zigzag(int n)
{
    int m=0,i,j,k;
    for(k=0;k<2*n-1;k++)        //规定：0作为第0排的数据，1,2作为第1排的数据....k表示第k排.
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
            {
                if(i+j==k)      //第k排的数据符合如下规律：即每个数据的(行+列)=该数据所在的排k
                {
                    if(k%2==0)  //偶数排的数据斜向上递增
                        a[j][i]=m++;
                    if(k%2==1)  //奇数排的数据斜向下递增
                        a[i][j]=m++;
                }
            }    
}

这种方法代码十分简洁，使用a[j][i]也很巧妙。

参考：https://blog.****.net/duotemplar/article/details/79339303
https://www.cnblogs.com/fuxianfeng1988/p/3292531.html

用c++实现一个n*n矩阵，矩阵沿着45度递增，形成zigzag数组

相关推荐