ZigZag数组的C++实现程序员面试宝典读书笔记（一）

  1 // 一道有趣的面试题.cpp : 定义控制台应用程序的入口点。
  2 
  3 /*************************************************
  4    设计者：cslave
  5    版本说明：本代码免费用于商用，拷贝，转移，使用，但是
  6    有本代码导致的问题，本人概不负责。
  7    设计时间：2012.7.10
  8    分发原则：遵守GNU规范。
  9  **************************************************/
 10 /**************************************************
 11 
 12 题目：输入n 求一个n*n的矩阵，规定矩阵沿45度角线递增，
 13 形成一个zigzag数组，请问如何用C++实现
 14 如图：
 15 
 16 Please Input The Number!
 17 8
 18      0     1     5     6    14    15    27    28
 19      2     4     7    13    16    26    29    42
 20      3     8    12    17    25    30    41    43
 21      9    11    18    24    31    40    44    53
 22     10    19    23    32    39    45    52    54
 23     20    22    33    38    46    51    55    60
 24     21    34    37    47    50    56    59    61
 25     35    36    48    49    57    58    62    63
 26 
 27 
 28 分析：
 29 先看矩阵，发现矩阵对角线上部元素与下部对应元素之和为N^2-1
 30 即为 Arr[i][j]+Arr[N-1-i][N-1-j]=N^2-1
 31 
 32 所以我们只需要处理上三角即可，下三角可推出。
 33 观察上三角中。
 34 数组各项横纵坐标与值的关系
 35 0  0  0
 36 0  1  1
 37 1  0  2
 38 2  0  3
 39 1  1  4
 40 0  2  5
 41 0  3  6
 42 1  2  7
 43 2  1  8
 44 3  0  9
 45 4  0  10
 46 从中分析 发现（i+j）的和与结果有关系
 47 令 s=i+j
 48 s=0  只有0 1个元素落在这个范围
 49 s=1  有2个
 50 s=2  有3个
 51 s=3  有4个
 52 s=4  。。。
 53 这样 
 54 任意一项Arr[i][j],令s=i+j
 55 则该项之前的s-1项有
 56 1+2+...+s=s(s+1)/2这么多个数，那么该数位于哪个位置?
 57 我们再看看 添加其前s-1项的和
 58 0  0  0   0
 59 0  1  1   1
 60 1  0  2   1
 61 2  0  3   3
 62 1  1  4   3
 63 0  2  5   3
 64 0  3  6   6
 65 1  2  7   6
 66 2  1  8   6
 67 3  0  9   6
 68 4  0  10  10
 69 从中我们可以看出 ，当s能够被2整除时 Arr[i][j]=s(s+1)/2+j
 70 否则 Arr[i][j]=s(s+1)/2+i;
 71 
 72 ****************************************************/
 73 
 74 
 75 
 76 #include "stdafx.h"
 77 #include <iostream>
 78 #include <iomanip>
 79 using namespace std;
 80 
 81 int _tmain(int argc, _TCHAR* argv[])
 82 {
 83     int N;
 84     int s,i,j;
 85     cout<<"Please Input The Number!"<<endl;
 86     cin>>N;
 87     int** Arr=new int*[N];//int** Arr=(int **)malloc(N*sizeof(int));
 88     for(i=0;i<N;i++)
 89         Arr[i]=new int[N];//Arr[i]=(int*)malloc(N*sizeof(int));严格来讲这里应该加强防错处理。
 90     for(i=0;i<N;i++)
 91         for(j=0;j<N-i;j++)
 92         {
 93             s=i+j;
 94             if(s<N)
 95             {
 96                 Arr[i][j]=s*(s+1)/2+((s%2==0)? j:i);
 97             }
 98         }
 99         for(i=N-1;i>0;i--)
100             for(j=N-i;j<N;j++)
101             {
102                 Arr[i][j]=N*N-1-Arr[N-1-i][N-1-j];
103             }
104     for(i=0;i<N;i++)
105     {
106         for(j=0;j<N;j++)
107             cout<<setw(6)<<Arr[i][j];
108         cout<<endl;
109     }
110     return 0;
111 }