一道有趣的循环题目

insertyou

浏览: 908501 次
性别:
来自: 北京

最近访客更多访客>>

wangyy

u012363178

mail136

kalin001

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1350)

社区版块

存档分类

问题：输入为n，求一个n*n的矩阵，规定沿45度线递增，形成一个zigzag数组（JEPG编码里取像素数据的排列顺序），用C++实现。

本人的实现思路（在《程序员面试宝典》中有另一种解法）：
问题的实质是把[0,n-1]中的整数依之字形填入一个二维数组。于是考虑按之字形遍历数组，遍历时，方向共有三个：
1. 起始时向右一位：
a) 如果没有填充完毕则向左下方斜行；
2. 向左下方斜行；
a) 如果没有碰到边界，则继续向左下方斜行；
b) 如果碰到左边界而没碰到下边界；则向下直行；
c) 如果碰到下边界（不管有没有碰到左边界），则向右直行；
3. 向右上方斜行；
a) 如果没有碰到边界，则继续向右上方斜行；
b) 如果碰到上边界而没有碰到右边界，向右直行；
c) 如果碰到右边界（无论有没有碰到上边界），则向下直行；
填充数字够n*n个时结束填充，C++代码如下：
#include "stdafx.h"
#include <iostream>
#include <iomanip> 
#include <cassert>
using namespace std;
enum Direction{rightDirection,zigzagUp,zigzagDown};
void printN(int n)
{
 assert(n>0);
 int **a;
 a=new int*[n];
 for(int i=0;i<n;++i) a[i]=new int[n];
 int x=0,y=0;
 Direction direction = rightDirection;
 a[0][0]=0;
 for(int i=1;i<n*n;++i)
 {
 switch(direction)
 {
 case rightDirection:
 if(y+1<n)a[x][++y]=i;
 else if(x+1<0) a[++x][y]=i;
 direction=zigzagDown;
 break;
 case zigzagDown:
 if(x+1<n&&y-1>=0)
 {
 a[++x][--y]=i;
 }
 else if(x+1<n&&y-1<0)
 {
 a[++x][y]=i;
 direction=zigzagUp;
 }
 else
 {
 a[x][++y]=i;
 direction=zigzagUp;
 }
 break;
 case zigzagUp:
 if (x-1>=0&&y+1<n)
 {
 a[--x][++y]=i;
 }
 else if (x-1<0&&y+1<n)
 {
 a[x][++y]=i;
 direction=zigzagDown;
 }
 else
 {
 a[++x][y]=i;
 direction=zigzagDown;
 }
 break; 
 }
 }
 for (int i=0;i<n;++i)
 {
 for (int j=0;j<n;++j)
 {
 cout<<setw(3)<<a[i][j]<<',';
 }
 cout<<endl;
 }
 cout<<endl;
 for(int i=0;i<n;++i) delete[] a[i];
 delete[] a;
}

int _tmain(int argc, _TCHAR* argv[])
{
 printN(1);
 printN(2);
 printN(3);
 printN(4);
 printN(5);
 printN(6);
 return 0;
}

分享到：