PDA

Visualizza la versione completa : [C++] riempire matrice quadrata con successione di interi...


hfish
02-11-2004, 18:47
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 :cry: :cry: :cry: :cry: :cry:

anx721
02-11-2004, 23:10
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;
}

:ciauz:

hfish
02-11-2004, 23:16
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;
}

:ciauz:

grazie mille...

se tu fossi una ragazza ti bacerei! :smack:

edriv
03-11-2004, 20:33
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;
}
}

Loading