Comment générer une matrice circulaire?

Question

Je veux générer une matrice circulaire en C ou C++.

Comment puis-je générer la matrice ci-dessous, pour n = 3?

1 2 3 
8 9 4 
7 6 5 

Answer 1

Dans une matrice « circulaire », le « milieu » de celui-ci est trop circulaire, sauf qu'il ne commence pas par 1. donc courir autour du périmètre et récursion.

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

Je l'ai fait il y a quelques temps ...

pseudocode:

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

Comme alternative à @ la réponse de Rin, vous pourriez envisager de stocker la matrice dans un ordre linéaire, puis re -mapping des indices lors de l'accès. Si vous êtes en C++, vous pouvez encapsuler cette re-mapping via les fonctions accesseurs, .: par exemple

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

d'abord votre matrice vide. Dans mon exemple, j'utilise un std :: map sur une paire std ::, mais vous pouvez aussi utiliser un tableau à deux dimensions. J'utilise std :: map parce qu'il est plus facile de voir quand un élément est manquant.

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

Puis créez une collection contenant les différentes directions dans lesquelles vous souhaitez vous déplacer. Si vous souhaitez d'abord déplacer vers la droite, cela signifie que X est incrémenté de 1 et que Y reste tel quel. Ensuite, nous passons vers le bas, ce qui signifie incrémenter Y par 1 et en laissant 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)); 

votre départ Initialize coordonner et de les déplacer jusqu'à une « limite ». Une limite est soit la frontière ou une cellule qui a déjà été rempli.

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

Puis dans une boucle (mais je laisse cela comme une excercise pour vous d'écrire ceci :-)) il suffit de remplir la matrice :

matrix[currentPosition] = currentValue; 
++currentValue; 

et de passer à la position suivante;

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

vérifier la nextPosition pour voir si vous êtes en dehors de votre matrice (nextPosition.first/seconde < 0 ou> = taille de la matrice).

Si vous êtes encore dans l'utilisation de la matrice std :: trouver sur la carte pour voir si cette entrée a déjà été remplie:

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

Si vous vous cognez contre les limites de la matrice ou vous croiserez une entrée qui a déjà été renseignée, reprenez la position actuelle, incrémentez currentMovePosition pour changer de direction et réessayez. Assurez-vous d'entourer currentMovePosition lorsque vous changez de direction.

currentMovePosition = (currentMovePosition + 1) % 4; 

Continuez jusqu'à ce que la matrice soit complètement remplie. Pour déterminer si la matrice est complètement remplie, vous pouvez vérifier si les 4 directions se déplacent toutes vers des éléments déjà remplis, mais une approche plus simple consiste simplement à compter le nombre de cellules remplies et à arrêter si elle est égale à la taille * taille de la matrice.

Answer 6

Cette question a été posée dans le test écrit de Microsoft. D'où l'idée de donner le code complet. Le code ci-dessous fonctionne pour n'importe quel nombre de lignes et n'importe quel nombre de colonnes donné au moment de l'exécution. Pas besoin de coder en dur les dimensions.

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