2616人阅读
面试C/C++（17）
同样是找规律的。
面试题目：
输入n，求一个nXn矩阵，规定矩阵沿45度递增，形成一个zigzag数组(JPEG编码里取像素数据的排列顺序)，请问如何用C++实现？
（中国台湾著名硬件公司2007年11月面试题）（自程序员面试宝典第四版92页）
看了网上的好几篇文章，由于本人 愚钝，未能理解，故自己认真想了想，总结如下。
对zigzag数组，可以理解为一个矩阵，分为两部分来解决：右上部分和左下部分。
图1 给出了一个n=7时候的矩阵的下标变化情况，例如“24”表示矩阵的第2行第4列（从0开始）。
右上部分数字依次增大的顺序如图2的红色箭头所示，该部分包括矩阵的对角线。
注意下面的分析中，最终的规律都要转化到下标上，因为该二维数组是和下标紧密相关的。
对右上部分来说：结合图1和图2可以看出几个规律：
（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时，就是矩阵的对角线，这个作为左上部分结束的条件。
&&&&&&& 左下部分并不符合右上部分的规律，但该部分的规律也是十分明显的。该部分的图如下所示（在右侧同时给出了图2用于对比），图中显示的该部分相对于n* n所应该减去的值，这里n*n=7*7= 49。例如最左侧第一条斜线上数字48 = n*n - 1，所以图3该位置标为-1，这是为了方便找规律。
左下部分从最左侧的斜线开始，也符合以下几个规律：
（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 &stdio.h&
#include &iostream&
int **printnxn(int **pSpace,int N) {
int s,i,j;
pSpace = (int **)malloc(N*sizeof(int *));
if(pSpace == NULL)
for(i=0; i&N; i++) { //注意这里的内存分配和释放
if ((pSpace[i] = (int *)malloc(N*sizeof(int))) == NULL) {
while (--i&0) {
free(pSpace[i]);
free(pSpace);
squa = N*N;
for (i=0; i&N; i++) {
for (j=0; j&N; j++) {
if (s&N)//解决右上部分，判断条件是下标和i+j小于输入的n
pSpace[i][j] = s*(s+1)/2 + (((i+j)%2 != 0) ? i : j);
else//解决右下部分
s = (N-1-i) + (N-1-j);
pSpace[i][j] = squa - s*(s+1)/2 -(N-(((i+j)%2 != 0)? i : j)); //注释B
for (i=0;i&N; i++) {
for (j=0; j&N; j++) {
printf(&%6d&,pSpace[i][j]);
printf(&\n&);
int main() {
scanf(&%d&,&N);
printnxn(p,N);
注：《程序员面试宝典》第93页该题的代码中，与上面代码注释A、B处的两行代码对应位置用了“==”，会得到下图所示的错误结果，与该书代码前边注释给出的示例数组不符。正确的应为上面代码注释A、B处那样为“!=”。上述文字已经给出了详细分析。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：313526次
积分：5179
积分：5179
排名：第4342名
原创：207篇
转载：25篇
评论：20条
文章：32篇
阅读：50786
文章：21篇
阅读：25256
文章：32篇
阅读：36556
(1)(3)(6)(5)(1)(2)(6)(10)(14)(33)(43)(52)(6)(23)(10)(5)(14)//、输入n，建立n*n维的动态二维数组，使用其保存n阶矩阵，并进行转置运算//、输入n，建立n*n维的动态二维数组，使用其保存n阶矩阵，并进行转置运算#include &iostream&void main(){ & int i,j,t,n; & cout&&&please enter the dimensions of the matrix&&& & cin&&n; & int a[5][5]; & for(i=0;i&n;i++) & {
for(j=0;j&n;j++)
cin&&a[i][j];
} & } & for(i=0;i&n;i++) & { &
for(j=0;j&n;j++) {
a[i][j]=a[j][i];
t=a[i][j];
a[i][j]=a[j][i];
a[j][i]=t;
cout&&a[i][j]; } cout&&&&&& & }}//结果是 ：14//哪错了呢？请大侠指点
回答1： if (i=j)a[i][j]=a[j][i];
//-&可以改成continue；else{t=a[i][j];a[i][j]=a[j][i];a[j][i]=t;}cout$<$a[i][j];
//-&最好改成cout$<$a[i][j]$<<$ '}cout$<<$&$<$ //-&改成cout$<$ }PS:矩阵必须是5*5，n必须是5
回答2：楼主可以用下面的代码，我运行了，没问题，只是没法动态二维数组，定义多大就是多大#include &iostream&void main(){
int i,j,t,n;
cout$<<$please enter the dimensions of the matrix:&$<$
int a[5][5];
cout$<<$please enter the data:&$<$
for(i=0;i&n;i++)
for(j=0;j&n;j++)
cin$>$a[i][j];
for(i=0;i&n;i++)
for(j=i+1;j&n;j++)
//注意这里，避免重复交换，就是说交换两次回到起点，等于没交换
//注意此处应为“==”
a[i][j]=a[j][i];
t=a[i][j];
//其实这个循环体只要这行开始的三行就行，不必使用if...else...语句
a[i][j]=a[j][i];
a[j][i]=t;
for(i=0;i&n;i++)
for(j=0;j&n;j++)
cout$<$a[i][j]$<<$\t&;
}}我很认真写的，要给分啊!
lianxiang789
回答3：探讨楼主可以用下面的代码，我运行了，没问题，只是没法动态二维数组，定义多大就是多大#include &iostream&void main(){
int i,j,t,n;
cout$<<$please enter the dimensions of the matrix:&$<$
int a[5][5……&#xe621; 上传我的文档
&#xe602; 下载
&#xe60c; 收藏
该文档贡献者很忙，什么也没留下。
&#xe602; 下载此文档
正在努力加载中...
C大作业内容
下载积分：800
内容提示：C大作业内容
文档格式：DOCX|
浏览次数：28|
上传日期： 10:14:44|
文档星级：&#xe60b;&#xe612;&#xe612;&#xe612;&#xe612;
该用户还上传了这些文档
C大作业内容
官方公共微信