從中心以螺旋形式填充矩陣-有解無憂

我最近為我正在從事的一個專案完成了一個演算法。

簡而言之，我的專案的一部分需要填充一個矩陣，如何做到這一點的要求是：

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

從中心以螺旋形式填充矩陣

uj5u.com熱心網友回復：

從中心以螺旋形式填充矩陣

請注意，沿對角線 (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  ;
        }
}

uj5u.com熱心網友回復：

我已經看到了很多做螺旋的方法。基本上都是按照路徑繪制它。

但是，您也可以想出一個螺旋的分析計算公式。

因此，通過遵循路徑等沒有遞回或迭代解決方案。如果我們有運行數，我們可以直接計算矩陣中的索引。

我將從笛卡爾坐標系中數學正方向（逆時針）的螺旋開始。我們將專注于 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';
    }
}

可以輕松適應不同的坐標系或其他螺旋方向。

快樂編碼。

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/395974.html

標籤：C 算法矩阵螺旋

上一篇：該程序如何在分支總和python代碼中實際流動

下一篇：變數符號靜態分析的偽代碼演算法——檢查每個操作的符號