打印一个特殊矩阵

---

    打印一个特殊矩阵
    作者：tyc611.cublog.cn，2008-10-01

---

【问题描述】
考查下面的矩阵的特征:
n=3:
1 2 1
1 2 1
1 1 1

n=4:
1 2 2 1
1 2 2 1
1 2 2 1
1 1 1 1

n=5:
1 2 2 2 1
1 2 3 2 1
1 2 3 2 1
1 2 3 2 1
1 1 1 1 1

n=6:
1 2 2 2 2 1
1 2 3 3 2 1
1 2 3 3 2 1
1 2 3 3 2 1
1 2 3 3 2 1
1 1 1 1 1 1

n=7:
1 2 2 2 2 2 1
1 2 3 4 3 2 1
1 2 3 4 3 2 1
1 2 3 4 3 2 1
1 2 3 4 3 2 1
1 2 3 3 3 2 1
1 1 1 1 1 1 1

当 i = 17 时:
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
1 2 3 4 4 4 4 4 4 4 4 4 4 4 3 2 1
1 2 3 4 5 6 6 6 6 6 6 6 5 4 3 2 1
1 2 3 4 5 6 7 8 8 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 7 7 7 7 6 5 4 3 2 1
1 2 3 4 5 5 5 5 5 5 5 5 5 4 3 2 1
1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 2 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1. 编写打印n阶矩阵的函数，接口如下：
void PrintMatrix(int n);

2. 额外要求，函数的空间复杂度为O(1)（目的是不让使用矩阵空间暂存结果，实现线性扫描）

【实现】
下面的函数PrintMatrix1借助了一个辅助矩阵，而PrintMatrix2直接打印输出矩阵。

#include
#include
using namespace std;

// 借助矩阵，空间复杂度为O(n^2)
void PrintMatrix1(int n)
{
    vector > matrix(n, vector(n, 0));
    int low = 0;
    int high = n - 1;
    int horizon = n - 1;
    int num = 1;

    for (int i = 0; i < (n + 1) / 2; ++i, ++num) {
        for (int k = low; k <= high; ++k) {
            matrix[k][i] = num;
            matrix[k][n - 1 - i] = num;
        }

        for (int k = i + 1; k < n - 1 - i; ++k)
            matrix[horizon][k] = num;

        if (horizon == low) {
            horizon = high;
            ++low;
        } else {
            horizon = low;
            --high;
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int k = 0; k < n; ++k)
            cout << matrix[i][k] << ' ';
        cout << '\n';
    }
}

// 不借助辅助空间，直接打印输出，空间复杂度为O(1)
void PrintMatrix2(int n)
{
    int num = (n + 1) / 2;

    for (int i = 1; i <= num / 2; ++i) {
        int d = 2 * i;
        for (int k = 1; k <= d - 1; ++k)
            cout << k << ' ';
        for (int k = 0; k < n - 2 * (d - 1); ++k)
            cout << d << ' ';
        for (int k = d - 1; k >= 1; --k)
            cout << k << ' ';
        cout << '\n';
    }

    for (int i = 0; i < n - num; ++i) {
        for (int k = 1; k <= n / 2; ++k)
            cout << k << ' ';
        for (int k = n - n / 2; k >= 1; --k)
            cout << k << ' ';
        cout << '\n';
    }

    for (int i = num - num / 2; i >= 1; --i) {
        int d = 2 * i - 1;
        for (int k = 1; k <= d - 1; ++k)
            cout << k << ' ';
        for (int k = 0; k < n - 2 * (d - 1); ++k)
            cout << d << ' ';
        for (int k = d - 1; k >= 1; --k)
            cout << k << ' ';
        cout << '\n';

    }
}

int main()
{
    int i = 15;
    cout << "当 i = " << i << " 时:\n";
    cout << "Print1:\n";
    PrintMatrix1(i);
    cout << "Print2:\n";
    PrintMatrix2(i);
    cout << endl;

    return 0;
}

程序运行结果:
当 i = 15 时:
Print1:
1 2 2 2 2 2 2 2 2 2 2 2 2 2 1
1 2 3 4 4 4 4 4 4 4 4 4 3 2 1
1 2 3 4 5 6 6 6 6 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 7 7 6 5 4 3 2 1
1 2 3 4 5 5 5 5 5 5 5 4 3 2 1
1 2 3 3 3 3 3 3 3 3 3 3 3 2 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Print2:
1 2 2 2 2 2 2 2 2 2 2 2 2 2 1
1 2 3 4 4 4 4 4 4 4 4 4 3 2 1
1 2 3 4 5 6 6 6 6 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 7 7 6 5 4 3 2 1
1 2 3 4 5 5 5 5 5 5 5 4 3 2 1
1 2 3 3 3 3 3 3 3 3 3 3 3 2 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

---