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

Stack Overflow用户

提问于 2021-12-27 20:01:49

回答 2查看 756关注 0票数 1

我最近为我正在做的一个项目做了一个算法。

简单地说，我的项目的一部分需要填写一个矩阵，如何完成它的要求如下：

- 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.

最后，我做的代码工作了，这是我最大的努力，我无法对它进行更多的优化，这让我感到有点困扰，因为我不得不使用这么多的ifs，我想知道是否有人可以查看我的代码，看看是否有可能进一步优化它或者进行一些建设性的评论(它很好，但如果它更快一些，因为这个算法将在我的项目中执行几次)。也让其他人可以使用它！

#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;
}

c++

algorithm

matrix

spiral

实时音视频9.9元起，弱网高质量通信

9.9元畅享2万分钟实时音视频通话时长，低成本、低门槛快速接入端到端延时＜300ms 的高品质实时互动通话

回答 2

Stack Overflow用户

回答已采纳

发布于 2021-12-27 21:37:51

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

从每个螺旋的末尾开始，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++;
        }
}

票数 3

Stack Overflow用户

发布于 2021-12-28 05:02:40

我已经看到了很多螺旋形的方法。所有这些基本上都是画出来的，沿着一条路走。

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

因此，没有递归或迭代的解决办法，遵循一条路径或类似的。如果我们有运行数，我们可以直接计算矩阵中的指数。

我将从在一个笛卡尔坐标系中的数学正方向(逆时针方向)的螺旋开始。我们将集中讨论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坐标。凉爽的。

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

有了这些知识，我们现在就可以很容易地计算出完整的矩阵。而且，由于根本不需要运行时活动，所以我们可以让编译器来完成这项工作。我们将简单地对每件事使用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';
    }
}