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

Question

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

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

1 2 3
8 9 4
7 6 5

Answer 1

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

псевдокод:

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 2

Этот вопрос задан в письменном тесте 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);
}

Answer 3

В качестве альтернативы ответу @ Rin, вы можете рассмотреть вопрос о сохранении матрицы в линейном порядке, а затем переотображать индексы при доступе к ней. Если вы находитесь в 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

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

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 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.first / second <0 или> =размер матрицы).

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

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

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

currentMovePosition = (currentMovePosition + 1) % 4;

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

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

Answer 6

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