Как создать круговую матрицу?

Question

Я хочу создать круговую матрицу в C или C++.

Как я могу сгенерировать матрицу ниже, для n = 3?

1 2 3 
8 9 4 
7 6 5 

Answer 1

В матрице «круговой», «средний» его круговое тоже за исключением того, что она не начинается с 1. Так бегать по периметру и Recurse.

void cmat_step(int** M, int a, int i, int j, int dim) 
{  
int k; 
    /* fill perimeter */ 
    for(k=0; k<dim; ++k)  M[i][j+k]  = a++; 
    for(k=1; k<dim; ++k)  M[i+k][j+dim-1] = a++; 
    for(k=dim-2; k>=0; --k)  M[i+dim-1][j+k] = a++; 
    for(k=dim-2; k>=1; --k)  M[i+k][j]  = a++; 
    if (dim >=2)  
    { /* fill middle */ 
     cmat_step(M, a, i+1, j+1, dim-2); 
    } 
} 
void cmat(int** M, int dim) { cmat_step(M, 1, 0, 0, dim); } 

Answer 2

Я сделал это несколько раз назад ...

псевдокод:

min_x = 0; 
min_y = 0; 
max_x = X; 
max_y = Y; 

while(!all_fields_filled){ 

    // move right ------------------------- 
    for(i = min_x; i <= max_x; i++){ 
    array[min_y][i] = fields_number; 
    fields_number++; 
    } 

    min_y++ 

    // it is important to check that condition after each for 
    // (our total field number could be not divided by 4) 
    if(filled_fields == fields_amount) break; 
    // edn "move right" procedure ----------- 


    // ETC. for move DOWN, next LEFT and UP 
    // remember to increase min_x/min_y and decrease max_y/max_y 

} 

Answer 3

В качестве альтернативы @ ответ Рин, вы могли бы рассмотреть возможность сохранения матрицы в линейном порядке, а затем снова - сопоставление индексов при доступе к нему. Если вы находитесь в C++, вы можете инкапсулировать это повторное отображение с помощью функций доступа, например .:

class WierdMatrix 
{ 
public: 
    ... 

    int get(int x, int y) const 
    { 
     /* Mapping goes here */ 
     return M_[x_mapped][y_mapped]; 
    } 
private: 
    int M_[3][3]; 
}; 

Answer 4

#define N 3 

int coords[N*N]; 

void printn() { 
    int i,j; 
    for (i = 0 ; i < N ; i++) { 
    for (j = 0 ; j < N ; j++) { 
     printf("%2d ",coords[i*N+j]); 
    } 
    printf("\n"); 
    } 
} 

void gennum(int n,int ox,int oy,int lx) { 
    int i,j,k,l; 
    for (j = ox; j < n ;j++) { 
    coords[ (oy*N)+j ]= j-ox + lx; 
    } 

    for (i = oy+1; i < n ;i++) { 
    coords[ (i*N) + n-1 ] = (i-1) -(oy) + (j-ox) + lx; 
    } 

    for (l = n-2 ; l >=ox ;l--) { 
    coords[ (n-1)*N + l ] = (n-l-2)+ (i-1) -(oy) + (j-ox) + lx ; 
    } 

    for (k = n-2; k >= oy+1 ;k--) { 
    coords[ (k*N)+ox ] = (n-k-2)+(n-l-2)+ (i-1) -(oy) + (j-ox) + lx ; 
    } 
    if (n > 2) { 
    gennum(n-1,ox+1,oy+1,(n-k-2)+(n-l-2)+ (i-1) -(oy) + (j-ox) + lx); 
    } 
} 

int main() { 
    memset(coords,0,N*N*sizeof(int)); 
    gennum(N,0,0,1); 
    printn(); 
    return 0; 
} 

Answer 5

Сначала сделайте Вашу матрица пуста. В моем примере я использую std :: map на std :: pair, но вы также можете использовать двумерный массив. Я использую std :: map, потому что легче видеть, когда элемент отсутствует.

typedef std::pair<int,int> Coordinate; 
typedef std::map<Coordinate,int> Matrix; 

Затем создайте коллекцию, которая содержит разные направления, в которых вы хотите переместить. Если сначала нужно переместить вправо, это означает увеличение X на 1 и оставление Y как есть. Затем мы переходим вниз, то есть увеличивающиеся Y на 1 и оставляя X.

typedef std::vector<Coordinate> Moves; 
Moves moves; 
moves.push_back(std::make_pair(1,0)); 
moves.push_back(std::make_pair(0,1)); 
moves.push_back(std::make_pair(-1,0)); 
moves.push_back(std::make_pair(0,-1)); 

Инициализировать ваш начальную координату и их двигаться, пока не достигнут «границы». Граница либо граница или клетка, которая уже заполнена.

Coordinate currentPosition = std::make_pair(0,0); 
int currentValue = 1; 
int currentMovePosition = 0; 

Затем в цикле (но я оставляю это как для вас физические упражнения, чтобы написать на это :-)) просто заполнить матрицу :

matrix[currentPosition] = currentValue; 
++currentValue; 

и перейти к следующему местоположению;

Coordinate nextPosition = currentPosition; 
nextPosition.first += moves[currentMovePosition].first; 
nextPosition.second += moves[currentMovePosition].second; 

Проверьте nextPosition, чтобы увидеть, если вы находитесь за пределами вашей матрицы (nextPosition.first/второй < 0 или> = размер матрицы).

Если вы все еще в использовании матрицы станд :: найти на карте, чтобы увидеть, если эта запись уже заполнена:

if (matrix.find(nextPosition)!=matrix.end()) /* valid position */ 

Если вы натыкаетесь на границах матрицы или врезаться запись, которая уже была заполнена, снова возьмет текущую позицию, увеличьте currentMovePosition, чтобы изменить направление и повторите попытку. Обязательно оберните currentMovePosition вокруг, если вы измените направление.

currentMovePosition = (currentMovePosition + 1) % 4; 

Продолжайте делать это до тех пор, пока матрица не будет полностью заполнена.

Чтобы определить, полностью ли заполнена матрица, вы можете проверить, все ли все 4 направления перемещаются к уже заполненным элементам, но проще всего просто подсчитать количество заполненных ячеек и остановиться, если он равен размеру * размер матрицы.

Answer 6

Этот вопрос задан в письменном тесте Microsoft. Следовательно, учитывая полный код.

Ниже код работает для любого количества строк и любого количества столбцов, заданных во время выполнения. Нет необходимости в жестком кодировании размеров.

#include <iostream> 
using namespace std; 

//Prints matrix in Spiral fashion. 
void printSpiral(const int& numRows, int& numCols) 
{ 
    int **v = new int*[numRows]; //Allocation for rows 
    for(int i = 0; i< numRows; i++) //Allocation for columns 
    { 
     v[i] = new int[numCols]; 
    } 
    int curRow = 0, curCol = -1; //for storing current position while moving. 
    //Below variables are for remembering boundaries 
    //That is already traversed row/column 
    int minRowLimit = -1, maxRowLimit = numRows; 
    int minColLimit = -1, maxColLimit = numCols; 

    int num = 1; //Start filling from 1 
    //Total number of elements to be filled 
    int totalElements = numRows * numCols; 
    while(1) 
    { 
     while(curCol < maxColLimit-1) //Move right 
     { 
      ++curCol; 
      v[curRow][curCol] = num; 
      num++; 
     } 
     if(num > totalElements) break; //Filling completed. 
     minRowLimit++; 

     while(curRow < maxRowLimit-1) //Move down 
     { 
      ++curRow; 
      v[curRow][curCol] = num; 
      num++; 
     } 
     if(num > totalElements) break; //Filling completed. 
     maxColLimit--; 

     while(curCol > minColLimit+1)  //Move left 
     { 
      --curCol; 
      v[curRow][curCol] = num; 
      num++; 
     } 
     if(num > totalElements) break; //Filling completed. 
     maxRowLimit--; 

     while(curRow > minRowLimit+1) //Move up 
     { 
      --curRow; 
      v[curRow][curCol] = num; 
      num++; 
     } 
     if(num > totalElements) break; //Filling completed. 
     minColLimit++; 
    } 
    //Print the matrix for verification. 
    for(int i = 0; i < numRows; i++) 
    { 
     for(int j=0; j < numCols; j++) 
     { 
      cout<<v[i][j]<<"\t"; 
     } 
     cout<<endl; 
    } 

    //Clean up. 
    for(int i = 0; i<numRows; i++) 
    { 
     delete []v[i]; 
    } 
    delete []v; 
} 

int main() 
{ 
    //Enter rows and columns according to your choice 
    //regarding matrix dimensions. 
    int nRows, nCols; 
    cout<<"Enter number of rows"<<endl; 
    cin>>nRows; 
    cout<<"Enter number of cols"<<endl; 
    cin>>nCols; 
    printSpiral(nRows, nCols); 
}