[C++] riempire matrice quadrata con successione di interi...

[hfish]

Esercizio: si scriva la funzione:

void init_mat (int mat[N][N]);

che riempie una matrice quadrata con una successione di interi da 1 ad N^2 pro-
cedendo secondo un andamento a spirale in senso orario.

Es (N=5)

1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

Soluzione 1: formalizzazione del procedimento che si seguirebbe dovendo riempi-
re la matrice "a mano". Uso di una variabile enumerata "direzione"

non ho la più pallida di come si faccia

[anx721]

Io seguo un approccio leggermente diverso: data una matrice quadrata, se riesco a compilare i lati esterni in senso orario partendo dal numero 1, poi mi resta da compilare la sottomatrice che ottengo togliendo i 4 lati esterni; dopo la prima passata ottengo:

(O = posizione compilata; X = posizione non compilata)

O O O O O
O X X X O 
O X X X O
O X X X O
O O O O O

overo dopo la prima passata miresta da compilare una sottomatrice quadrata di dimesione (N-2)(N-2)

posso allora ripetere il procedimento per tale sottomatrice.

Quindi posso fare un ciclo, e all'interno di ogni iterazione compilo i 4 lati della sottomatrice corrente. per compilare i 4 lati di una mtrice N*N procedo cosi:

lato superiore: N elementi che raggiungo incrementando la coordinata y;
lato destro: N-1 elementi che raggiungo incrementando la coordinata x;
lato inferiore: N-1 elementi che raggiungo decrementando la coordinata y;
lato sinistro: N-2 elementi che raggiungo decrementanto la coordinata x;

quindi posso fare 4 cicli for, uno per ogni lato per compilare tutti e quattro i lati.


Ecco il programma C++ (non C!)

#include <iostream>
#define N 5

void init_mat(int mat[N][N]){
	//num rappresenta il numero di elementi in un lato
	//della sottomatrice corrente
	int num = N;
	//done rappresenta il numero di elementi compilati in tutto
	int done = 0;
	//x e y rappresentano le coordinate correnti
	int x = 0; int y = -1;

	while(done < N * N){
		//compilo il lato superiore spostandomi a destra
		for(int i = 0; i < num; i++){
			y++;
			done++;
			mat[x][y] = done;
		}
		//compilo il lato destro spostandomi in basso
		for(int i = 0; i < num - 1; i++){
			x++;
			done++;
			mat[x][y] = done;
		}
		
		//compilo il lato inferiore spostandomi a sinistra
		for(int i = 0; i < num - 1; i++){
			y--;
			done++;
			mat[x][y] = done;
		}
		//compilo il lato sinistro spostandomi in alto
		for(int i = 0; i < num - 2; i++){
			x--;
			done++;
			mat[x][y] = done;
		}
		//la nuova prossima sottomatrice avrà dimensione
		//decrementata di 2
		num -= 2;
	}
}

void stampa(int mat[N][N]){
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			std::cout << mat[i][j] << "  ";
		}
		std::cout << "\n";
	}
}


int main(){
	int mat[N][N];
	init_mat(mat);
	stampa(mat);
	return 0;
}

[hfish]

Originariamente inviato da anx721
Io seguo un approccio leggermente diverso: data una matrice quadrata, se riesco a compilare i lati esterni in senso orario partendo dal numero 1, poi mi resta da compilare la sottomatrice che ottengo togliendo i 4 lati esterni; dopo la prima passata ottengo:

(O = posizione compilata; X = posizione non compilata)

O O O O O
O X X X O 
O X X X O
O X X X O
O O O O O

overo dopo la prima passata miresta da compilare una sottomatrice quadrata di dimesione (N-2)(N-2)

posso allora ripetere il procedimento per tale sottomatrice.

Quindi posso fare un ciclo, e all'interno di ogni iterazione compilo i 4 lati della sottomatrice corrente. per compilare i 4 lati di una mtrice N*N procedo cosi:

lato superiore: N elementi che raggiungo incrementando la coordinata y;
lato destro: N-1 elementi che raggiungo incrementando la coordinata x;
lato inferiore: N-1 elementi che raggiungo decrementando la coordinata y;
lato sinistro: N-2 elementi che raggiungo decrementanto la coordinata x;

quindi posso fare 4 cicli for, uno per ogni lato per compilare tutti e quattro i lati.


Ecco il programma C++ (non C!)

#include <iostream>
#define N 5

void init_mat(int mat[N][N]){
	//num rappresenta il numero di elementi in un lato
	//della sottomatrice corrente
	int num = N;
	//done rappresenta il numero di elementi compilati in tutto
	int done = 0;
	//x e y rappresentano le coordinate correnti
	int x = 0; int y = -1;

	while(done < N * N){
		//compilo il lato superiore spostandomi a destra
		for(int i = 0; i < num; i++){
			y++;
			done++;
			mat[x][y] = done;
		}
		//compilo il lato destro spostandomi in basso
		for(int i = 0; i < num - 1; i++){
			x++;
			done++;
			mat[x][y] = done;
		}
		
		//compilo il lato inferiore spostandomi a sinistra
		for(int i = 0; i < num - 1; i++){
			y--;
			done++;
			mat[x][y] = done;
		}
		//compilo il lato sinistro spostandomi in alto
		for(int i = 0; i < num - 2; i++){
			x--;
			done++;
			mat[x][y] = done;
		}
		//la nuova prossima sottomatrice avrà dimensione
		//decrementata di 2
		num -= 2;
	}
}

void stampa(int mat[N][N]){
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			std::cout << mat[i][j] << "  ";
		}
		std::cout << "\n";
	}
}


int main(){
	int mat[N][N];
	init_mat(mat);
	stampa(mat);
	return 0;
}

grazie mille...

se tu fossi una ragazza ti bacerei!

[edriv]

Questa è la mia versione, non ricorsiva.

Ho usato un int al posto dell'enum perchè mi dava strani errori... ma non è per niente difficile sostituirlo.

#include <iostream>
#include <cstdlib>

using namespace std;

void fill_matrix(int*, int);
void disp_matrix(int*, int);

struct point
{
    int x,y;
    // costruttore per inizializzare
    point() {x=0; y=0;}
};     
    
int main()
{
    int n;
    cout << "Larghezza = altezza = ? ";
    cin >> n;
    int *matrice = new int[n*n];
    fill_matrix(matrice, n);
    disp_matrix(matrice, n);
    system("pause");
    return 0;
}    

void fill_matrix(int *mtx, int n)
{
    // x e y correnti
    point a;
    int tot_line_len = n;
    int mancano = tot_line_len;
    // 0=destra
    // 1=giù
    // 2=sinistra
    // 3=su
    int direz = 0;
    int i;

    for(i=1; i<=n*n; i++)
        {     
            // Scrivo il numero nella posizione corrente
            mtx[a.y*n + a.x] = i;
            // La lunghezza che mi manca diminuisce
            mancano--;
            // Se sono al limite cambio direzione
            if(mancano==0)
            {
                direz = (direz+1) % 4;
                if(direz % 2)
                    mancano = --tot_line_len;
                else
                    mancano = tot_line_len;
            }    
            switch(direz)
            {
                // Mi sposto a seconda della direzione
                case 0:
                     a.x++;
                     break;
                case 1:
                     a.y++;
                     break;
                case 2:
                     a.x--; 
                     break;
                case 3: 
                    a.y--; 
                    break;
            }   
            // Prossimo punto! Ora incrementerà il numero da scrivere (i)
        }    
    
}

void disp_matrix(int *mtx, int n)
{
    cout << endl << endl << endl << endl;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cout<< mtx[i*n + j]<<'\t';
        }
        cout << endl << endl << endl << endl;
    }        
}