题目出自面试宝典8.3.2

 

题目描述： 输入n，求一个n*n的矩阵，规定矩阵沿45度线递增，形成一个zigzag数组（JPEG编码里去像素数据的排列顺序），请问如何用C++实现？

例如： n=2

0	1
2	3

n=3

0	1	5
2	4	6
3	7	8

n=5

0	1	5	6	14
2	4	7	13	15
3	8	12	16	21
9	11	17	20	22
10	18	19	23	24

分析每个矩阵中上三角矩阵，可以看到上三角矩阵的元素都满足：

s= i+j;

a[i][j] = s*(s+1)/2 +( (s%2==0)?i:j);

 

此外，下三角的矩阵的每个元素满足 a[i][j] + a[n-1-i][n-1-j] = N-1;

根据上面的分析，可以得到如下的程序：

#include 
     
      using namespace std;int a[100][100]={
   0};void draw(int n){    int i,j,s,N=n*n;    for(i=0;i
      
       >n)    {       draw(n);    }    return 0;}
      
     

程序的结果为：