从中心以螺旋形式填充矩阵

Question

我最近完成了我正在进行的项目的算法。

简而言之，我的项目的一部分需要填充矩阵，具体操作要求如下：

- Fill the matrix in form of spiral, from the center.
- The size of the matrix must be dynamic, so the spiral can be large or small.
- Every two times a cell of the matrix is filled, //DO STUFF must be executed.

最后，我写的代码成功了，这是我最大的努力，我不能再优化它，不得不使用这么多的if，这让我有点困扰，我想知道是否有人可以看看我的代码，看看是否有可能进一步优化它或一些建设性的评论（它工作得很好，但如果它更快，那就太好了，因为这个算法将在我的项目中执行多次）。也让其他人可以使用它！

#include <stdio.h>

typedef unsigned short u16_t;
const u16_t size = 7; //<-- CHANGE HERE!!! just odd numbers and bigger than 3
const u16_t maxTimes = 2;
u16_t array_cont[size][size] = { 0 };

u16_t counter = 3, curr = 0;
u16_t endColumn = (size - 1) / 2, endRow = endColumn;
u16_t startColumn = endColumn + 1, startRow = endColumn + 1;
u16_t posLoop = 2, buffer = startColumn, i = 0;

void fillArray() {
    if (curr < maxTimes) {
        if (posLoop == 0) { //Top
            for (i = buffer; i <= startColumn && curr < maxTimes; i++, curr++)
                array_cont[endRow][i] = counter++;
            if (curr == maxTimes) {
                if (i <= startColumn) {
                    buffer = i;
                } else {
                    buffer = endRow;
                    startColumn++;
                    posLoop++;
                }
            } else {
                buffer = endRow;
                startColumn++;
                posLoop++;
                fillArray();
            }
        } else if (posLoop == 1) { //Right
            for (i = buffer; i <= startRow && curr < maxTimes; i++, curr++)
                array_cont[i][startColumn] = counter++;
            if (curr == maxTimes) {
                if (i <= startRow) {
                    buffer = i;
                } else {
                    buffer = startColumn;
                    startRow++;
                    posLoop++;
                }
            } else {
                buffer = startColumn;
                startRow++;
                posLoop++;
                fillArray();
            }
        } else if (posLoop == 2) { //Bottom
            for (i = buffer; i >= endColumn && curr < maxTimes; i--, curr++)
                array_cont[startRow][i] = counter++;
            if (curr == maxTimes) {
                if (i >= endColumn) {
                    buffer = i;
                } else {
                    buffer = startRow;
                    endColumn--;
                    posLoop++;
                }
            } else {
                buffer = startRow;
                endColumn--;
                posLoop++;
                fillArray();
            }
        } else if (posLoop == 3) { //Left
            for (i = buffer; i >= endRow && curr < maxTimes; i--, curr++)
                array_cont[i][endColumn] = counter++;
            if (curr == maxTimes) {
                if (i >= endRow) {
                    buffer = i;
                } else {
                    buffer = endColumn;
                    endRow--;
                    posLoop = 0;
                }
            } else {
                buffer = endColumn;
                endRow--;
                posLoop = 0;
                fillArray();
            }
        }
    }
}

int main(void) {
    array_cont[endColumn][endColumn] = 1;
    array_cont[endColumn][endColumn + 1] = 2;
    //DO STUFF

    u16_t max = ((size * size) - 1) / maxTimes;
    for (u16_t j = 0; j < max; j++) {
        fillArray();
        curr = 0;
        //DO STUFF
    }

    //Demostration
    for (u16_t x = 0; x < size; x++) {
        for (u16_t y = 0; y < size; y++)
            printf("%-4d ", array_cont[x][y]);
        printf("\n");
    }

    return 0;
}

Answer 1

注意对角线上的数字 (1, 9, 25, 49) 是奇数的平方。这是一个重要的线索，因为它表明矩阵中心的 1 应该被视为螺旋的 end。

从每一个螺旋的末端开始，x,y坐标要向上和向右调整1。然后通过向下、向左、向上和向右移动，构建下一层螺旋。相同数量。

例如从1的位置开始，向上向右移动（到9的位置），然后按照以下步骤形成一个循环：

 move down, and place the 2  
 move down, and place the 3  
 move left, and place the 4  
 move left, and place the 5  
 etc.

因此代码看起来像这样：

int size = 7;
int matrix[size][size];
int dy[] = { 1,  0, -1, 0 };
int dx[] = { 0, -1,  0, 1 };
int directionCount = 4;

int ringCount = (size - 1) / 2;
int y = ringCount;
int x = ringCount;
int repeatCount = 0;
int value = 1;

matrix[y][x] = value++;
for (int ring = 0; ring < ringCount; ring++)
{
    y--;
    x++;
    repeatCount += 2;
    for (int direction = 0; direction < directionCount; direction++)
        for (int repeat = 0; repeat < repeatCount; repeat++)
        {
            y += dy[direction];
            x += dx[direction];
            matrix[y][x] = value++;
        }
}

Answer 2

我已经看到很多做螺旋的方法。基本上都是按照路径画出来的。

但是，你也可以想出一个解析螺旋的计算公式。

因此，没有通过遵循路径等的递归或迭代解决方案。如果我们有运行个数字，我们可以直接计算矩阵中的索引。

我将从笛卡尔坐标系中数学正方向（逆时针）的螺旋线开始。我们将专注于 X 和 Y 坐标。

我做了一个简短的 Excel 并从中推导出了一些公式。这是一张简短的图片：

根据要求我们知道矩阵将是二次矩阵。这让事情变得更容易。有点棘手的是，让矩阵数据对称。但是用一些简单的公式，从图片中推导出来，这真的不是问题。

然后我们可以用一些简单的语句计算x和y坐标。请参阅下面带有长变量名的示例程序，以便更好地理解。该代码是使用一些逐步方法来说明实现的。当然，它可以很容易地做得更紧凑。反正。一起来看看吧。

#include <iostream>
#include <cmath>
#include <iomanip>

int main() {
    // Show some example values
    for (long step{}; step < 81; ++step) {

        // Calculate result
        const long roundedSquareRoot = std::lround(std::sqrt(step));
        const long roundedSquare = roundedSquareRoot * roundedSquareRoot;
        const long distance = std::abs(roundedSquare - step) - roundedSquareRoot;
        const long rsrIsOdd = (roundedSquareRoot % 2);

        const long x = (distance + roundedSquare - step - rsrIsOdd) / (rsrIsOdd ? -2 : 2);
        const long y = (-distance + roundedSquare - step - rsrIsOdd) / (rsrIsOdd ? -2 : 2);
        // Show ouput
        std::cout << "Step:" << std::setw(4) << step << std::setw(3) << x << ' ' << std::setw(3) << y << '\n';
    }
}

所以，你看我们真的有一个解析解。给定任何数字，我们可以使用公式计算 x 和 y 坐标。酷

在矩阵中获取索引只是添加一些偏移量。

有了这些知识，我们现在可以轻松计算出完整的矩阵。而且，由于根本不需要运行时 activity，我们可以让编译器完成工作。我们将对所有内容简单地使用 constexpr 函数。

然后编译器会在编译时创建这个矩阵。在运行时，什么也不会发生。

请看一个非常紧凑的解决方案：

#include <iostream>
#include <iomanip>
#include <array>

constexpr size_t MatrixSize = 15u;

using MyType = long;
static_assert(MatrixSize > 0 && MatrixSize%2, "Matrix size must be odd and > 0");
constexpr MyType MatrixHalf = MatrixSize / 2;

using Matrix = std::array<std::array<MyType, MatrixSize>, MatrixSize >;

// Some constexpr simple mathematical functions ------------------------------------------------------------------------------
// No need for <cmath>
constexpr MyType myAbs(MyType v) { return v < 0 ? -v : v; }
constexpr double mySqrtRecursive(double x, double c, double p) {return c == p? c: mySqrtRecursive(x, 0.5 * (c + x / c), c); }
constexpr MyType mySqrt(MyType x) {return (MyType)(mySqrtRecursive((double)x,(double)x,0.0)+0.5); }

// Main constexpr function will fill the matrix with a spiral pattern during compile time -------------------------------------
constexpr Matrix fillMatrix() {
    Matrix matrix{};
    for (int i{}; i < (MatrixSize * MatrixSize); ++i) {
        const MyType rsr{ mySqrt(i) }, rs{ rsr * rsr }, d{ myAbs(rs - i) - rsr }, o{ rsr % 2 };
        const size_t col{ (size_t)(MatrixHalf +((d + rs - i - o) / (o ? -2 : 2)))};
        const size_t row{ (size_t)(MatrixHalf -((-d + rs - i - o) / (o ? -2 : 2)))};
        matrix[row][col] = i;
    }
    return matrix;
}
// This is a compile time constant!
constexpr Matrix matrix = fillMatrix();

// All the above has been done during compile time! -----------------------------------------


int main() {

    // Nothing to do. All has beend done at compile time already!
    // The matrix is already filled with a spiral pattern

    // Just output
    for (const auto& row : matrix) {
        for (const auto& col : row) std::cout << std::setw(5) << col << ' '; std::cout << '\n';
    }
}

可以轻松适应不同的坐标系或其他螺旋方向。

编码愉快。

从中心以螺旋形式填充矩阵

Fill Matrix in Spiral Form from center

c++

algorithm

matrix

spiral