螺旋矩阵，是这么一个东西：
1 2 3
8 9 4
7 6 5
这是一个，n*n的矩阵，由外向里一次递增，一环一环，就好像一个螺旋一样。不难想象，如果n=5，那么应该是这样的：
当然，这是的一道笔试程序题，实话说，第一眼看到，还真不会做，因为，c++的数组下标无法从控制台读入。反正就是基础不行，看上去也很难。但是，第二天仔细一想，其实是有规律可循的，于是，就开始做了。因为比较时间有限，而且能力有限，所以有什么更好的方法，欢迎补充。一开始的想法是比较麻烦的，就是每一条螺旋的边，做一个循环，想法是这样的：
1 2 3
8 9 4
7 6 5
先一最上面开始，但是仔细想这样的想法会使得程序比较复杂，因为很明显规律是不太完美的，代码比较多，所以优化了一下，并且还有更多的规律。
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
第一个规律：
如果我们把整个矩阵看成是一层一层最外环构成，那么上面的矩阵就是这样的：
1 2 3 4
12 5
11 6 13 14
10 9 8 7 + 16 15
你可以画更多的矩阵参考，这将作为最外层循环，并且，每次长度减二，这算上不错的发现。
第二个规律：
最外层循环这么实现的话，那么问题是我们每一个外壳，可以这么实现，一次性从1到12，但是你很快会发现，这样的下标将是混乱的，所以有必要在循环里面在分循环，而我的思路是这样的：
1 2 3 4
+ 5 + + 12
6 11
9 8 7 10
这样四步是很有规律的，我们虽然可以用四个循环实现，但是因为这四个不同区域的矩阵是同时递增，那么我可以让四个矩阵同时在一个循环里面同时赋值，很明显，上面的这个循环是3。写到这里，你应该是发现了第一个规律的意义，这样子，整个矩阵分成了完全相同的步骤，一层一层向里面变小，每一层的赋值也得到了保证，但是问题是终结点在哪里呢，算法的有限性。
第三个规律：
考虑到最后的终结点，你可以这么理解，在第一个规律的基础上，我们每一层可能依次减二，那么就有这样的规律，对于任意正整数n，依次减二，最后只有两种结果，一种是完全为零，一种是为一，说白了就是偶数和奇数的两种可能，而这两种可能最后有什么规律呢？我们看两种矩阵：
1 2 3
8 9 4
7 6 5
和
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
很明显，如果是1，那么就是2*2的小矩阵，你可以发现在这个点上，也就是第二个规律中每一条边为1的情况，但是如果是零，那么他是一个数，只有一个，这种情况我们有必要拿出来，因为在上面两种情况，最后是不会出现这种可能性。还是只看我实现的代码吧：
#include <iostream> using namespace std; void sparalMat(int *array[],int n) { int time = 0; int start = 1; //左上角起始点,做个补充，这个是每一个外壳，第一个起始点。 while (time < n) { if (n-1-time==0) { array[time / 2][time / 2] = start; } for (int i = 0; i < n-1-time; ++i) { array[(time / 2)][time/2+i] = start + i; array[time / 2 + i][n - 1 - time / 2] = start + (n - time - 1) + i; array[n-1 - time / 2][n-1 - time / 2 - i] = start + 2 * (n - 1 - time) + i; array[n - 1 - time / 2 - i][time / 2] = start + 3 * (n - 1 - time) + i; } start += 4 * (n - 1 - time); time += 2; } } //主函数入口 int _tmain(int argc, _TCHAR* argv[]) { int ha = 0; cin >> ha; int **a = new int*[ha]; for (int i = 0; i < ha; i++) //这一块仅仅是动态内存分配，与算法无关 { a[i] = new int[ha]; } sparalMat(a, ha); for (int i = 0; i < ha; i++) { for (int j = 0; j < ha; j++) { cout << a[i][j] << "\t"; } cout << endl; } for (int i = 0; i < ha; i++) //内存释放，我觉得有必要释放，即使是在程序结束时。 { delete [] a[i]; } delete[] a; return 0; } |
