c++实现螺旋矩阵分析总结

螺旋矩阵，是这么一个东西：

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 = ;

    int start = ; //左上角起始点,做个补充，这个是每一个外壳，第一个起始点。

    while (time < n)

    {

        if (n--time==)

        {

            array[time / ][time / ] = start;

        }

        for (int i = ; i < n--time; ++i)

        {

            array[(time / )][time/+i] = start + i;

            array[time /  + i][n -  - time / ] = start + (n - time - ) + i;

            array[n- - time / ][n- - time /  - i] = start +  * (n -  - time) + i;

            array[n -  - time /  - i][time / ] = start +  * (n -  - time) + i;

        }

        start +=  * (n -  - time);

        time += ;

    }

}

//主函数入口

int _tmain(int argc, _TCHAR* argv[])

{

    int ha = ;

    cin >> ha;

    int **a = new int*[ha];

    for (int i = ; i < ha; i++)   //这一块仅仅是动态内存分配，与算法无关

    {

        a[i] = new int[ha];

    }

    sparalMat(a, ha);

    for (int i = ; i < ha; i++)

    {

        for (int j = ; j < ha; j++)

        {

            cout << a[i][j] << "\t";

        }

        cout << endl;

    }

    for (int i = ; i < ha; i++)    //内存释放，我觉得有必要释放，即使是在程序结束时。

    {

        delete [] a[i];

    }

    delete[] a;

    return ;

}

没错，我决定还是相当简洁的，我用了动态内存释放，之前不知道，但是数组下标无法从控制台读入，所以很麻烦，只能这么玩。思路就是这样。现在看看它的运行结果吧，我取

1,3,6,7,10。这五种情况：

1：

3：

6：

7：

10：

最后，就是这样，见笑了。

巴特西

c++实现螺旋矩阵分析总结

最新文章

热门文章