沿45°递增的n*n数组

问题

给定一个n，求一个n*n的二维数组，该数组的值沿45°方向的斜线依次递增。如n=4时，数组为

  1   2   4   7
  3   5   8  11
  6   9  12  14
 10  13  15  16

思路

将数组分成上三角（包括对角线）和下对角两个部分分别计算。

对于上三角，共有n条斜线，每条斜线上的数字个数分别为cnt = 1，2，3，…，n。每条斜线的起点是(row,col) =(0,i)，其中i=0 ,1,…, n-1。数组下标从0开始。每条斜线的下一个位置是当前行数row+1，当前列数col-1.

对于下三角，共有n-1条斜线，每条斜线上的数字个数分别为cnt=n-1,n-2,…,1。每条斜线的起点是(row,col)=(i+1,n-1)，其中i=0，1，…,n-2。数组下标从0开始。每条斜线的下一个位置是当前行数row+1，当前列数col-1.

代码

[cpp]//Problem:给定一个n，求一个n*n的二维数组，该数组的值沿45°方向的斜线依次递增.
//Author: JarvisChu
//Blog: zhujiangtao.com
//Date: 2014-3-9

#include <iostream>
#include <iomanip> // setw()

using namespace std;

int main(int argc, char* argv[])
{
const int n = 4; //数组大小 n
int data[n][n]; //数组
int num=1; //起始数字

//计算上三角（包括对角线）
for(int i=0;i<n;i++)// n 条 右上到左下的斜线
{
int row = 0,col = i, cnt=0;
while (cnt<(i+1)) //第i斜行 有i+1个数
{
data[row++][col--] = num++; //下一个位置是(row+1,col-1)
cnt++;
}
}

//计算下三角（不包括对角线）
for(int i=0;i<n-1;i++) //n-1 条斜线
{
int row = i+1,col=n-1,cnt = 0;
while(cnt <(n-i-1))//第i斜行 有 n-i-1 个数字
{
data[row++][col--] = num++;
cnt++;
}
}

//打印结果
for(int i=0;i<n;i++)
{
for(int j=0;j< n;j++)
{
cout<<setw(3)<<data[i][j]<<" ";
}
cout<<endl;
}
return 0;
}[/cpp]

作者：JarvisChu
原文链接：沿45°递增的n*n数组
版权声明：自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0