Esercizio in C

[kodibi]

Salve sono nuovo del forum e vorrei proporvi il mio quesito sul seguente esercizio;

Si consideri un array 2D nxn, con n=32, in cui ogni casella può essere bianca (rappresentata da uno spazio ‘ ‘) o nera (rappresentata da una ’X’). All’inizio l’array è costituito solo da caselle nere. L’algoritmo esamina m=6 volte la scacchiera. Durante ogni passo aggiorna lo stato di tutte le caselle usando un criterio di suddivisione nel seguente modo: al primo passo l’array 2D viene visto come costituito da 4 blocchi, ognuno di 16x16 caselle; al secondo passo, ogni blocco di 16x16 è visto come costituito da 4 blocchi di 8x8 caselle; e così via. La regola di suddivisione è la seguente: quando un blocco ‘grande’ nero viene suddiviso in 4 blocchi ‘più piccoli’ allora i blocchi ‘piccoli’ diagonali vengono marcati con ‘D’ e il blocco piccolo in alto a destra diventa bianco o marchiato con ‘A’; quando un blocco ‘grande’ bianco viene suddiviso in 4 blocchi ‘più piccoli’ allora tutti i blocchi ‘piccoli’ rimangono bianchi. L’algoritmo visualizza tutto l’array 2D al temine di ogni passo. Sviluppare due versioni dell’algoritmo, una iterativa e l’altra ricorsiva.

Per quanto riguarda la versione iterativa non ci sono stati particolari problemi,non lo stesso per la ricorsiva. Chi mi può dare una mano? Grazie mille in anticipo!

 

[ptm]

Riesci a pubblicare il codice della tua versione iterativa? Così cerco di basarmi su quello per lo sviluppo della ricorsiva...

 

[kodibi]

Eccolo!

#include <stdio.h>#include <stdlib.h>
#include <math.h>
#define N 32


void ricerca(char matrice[N][N],int ciclo)
{
int i,j,M,x,y;
i=0;
M=N /(pow(2,ciclo));
j=M;
while(i<N)
{
cerca_in_linea(matrice,i,j,M);
//j=M;
i=(i+(2*M));
}
if (ciclo==1)
{
for(x=0; x<N/2; x++)
{
for(y=0; y<N/2; y++)
matrice[x][y]='D';
}


for(x=N/2-1; x<N; x++)
{
for(y=N/2-1; y<N; y++)
matrice[x][y]='D';
}


for(x=0; x<N/2; x++)
{
for(y=N/2; y<N; y++)
matrice[x][y]=' ';
}


for(x=N/2; x<N; x++)
{
for(y=0; y<N/2; y++)
matrice[x][y]='X';
}


}


printf("\n\t\t\tIterazione %d\n\n",ciclo+1);
stampa_array(matrice,N);


if(ciclo==1)
{ for(x=16; x<N; x++)
{
for(y=0; y<N/2; y++)
{
if(x<=31 && y<=23)
matrice[x][y]='D';
}
}
}


if(ciclo==1)
{
for(x=24; x<N; x++)
{
for(y=0; y<N/4; y++)
matrice[x][y]='X';
}
}


if(ciclo==2)
{
for(x=24; x<28; x++)
{
for(y=0; y<N/8; y++)
matrice[x][y]='D';
}
for(x=28; x<N; x++)
{
for(y=4; y<8; y++)
matrice[x][y]='D';
}
}


if(ciclo==3)
{
for(x=28; x<30; x++)
{
for(y=0; y<2; y++)
matrice[x][y]='D';
}
for(x=30; x<N; x++)
{
for(y=2; y<N/8; y++)
matrice[x][y]='D';
}
}


if(ciclo==4)
{
matrice[30][0]='D';
matrice[31][1]='D';
}








system("PAUSE");
system("cls");
if(M>1)
ricerca(matrice,(ciclo+1));
}


void cerca_in_linea(char matrice[N][N],int i,int j,int M)
{
while(j<=N)
{
if(matrice[j]!=' ')
libera_sottomatrice(matrice,i,j,M);
j=(j+(2*M));
}
}


void libera_sottomatrice(char matrice[N][N],int i,int j,int size)
{
int l,m;
for(l=i;l<(size+i);l++)
{
for(m=j;m<(size+j);m++)
{
matrice[l][m]=' ';


}
}
}
void compila_array(char matrice[N][N],int n,char C)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
matrice[j]=C;
}


}


void stampa_array(char matrice[N][N],int n)
{
int i,j;
printf("+----------------------------------------------------------------+\n");
for(i=0;i<n;i++)
{
printf("|");
for(j=0;j<n;j++)
printf("%c ",matrice[j]);
printf("|");
printf("\n");
}
printf("+----------------------------------------------------------------+\n");


}
void main ()
{
char matrice[N][N];
compila_array(matrice,N,('X'));
printf("\n\t\t\tIterazione 1\n\n");
stampa_array(matrice,N);
system("PAUSE");
system("cls");
ricerca(matrice,1);
}

 

[ptm]

In verità già questa è già una versione ricorsiva...al termine della funzione ricerca, vai a richiamare nuovamente ricerca... Non capisco molto il fatto di dover mettere 'D' dato che non dà informazione in più rispetto al lasciare la 'X' (anche perchè l'inizio del problema dice: "ogni casella può essere bianca (rappresentata da uno spazio ‘ ‘) o nera (rappresentata da una ’X’)").

 

[kodibi]

In verità già questa è già una versione ricorsiva...al termine della funzione ricerca, vai a richiamare nuovamente ricerca... Non capisco molto il fatto di dover mettere 'D' dato che non dà informazione in più rispetto al lasciare la 'X' (anche perchè l'inizio del problema dice: "ogni casella può essere bianca (rappresentata da uno spazio ‘ ‘) o nera (rappresentata da una ’X’)").

se ci fai caso dice quando ogni quadrato grande viene diviso i due diagonali diventano D, e il problema è il quadrato giù a sinistra che si differenzia dagli altri tre visto che i due diagonali diventano tutte D, mentre quello su a destra bianco.
comunque perfetto quindi è ricorsivo? mentre per quello iterativo lo devo gestire tutto tramite dei semplici for?

 

[ptm]

se ci fai caso dice quando ogni quadrato grande viene diviso i due diagonali diventano D, e il problema è il quadrato giù a sinistra che si differenzia dagli altri tre visto che i due diagonali diventano tutte D, mentre quello su a destra bianco.
comunque perfetto quindi è ricorsivo? mentre per quello iterativo lo devo gestire tutto tramite dei semplici for?

Si, quello ho visto... intendevo che come risultato finale si ottengono solo 'D', quindi la sostituzione è un po' senza senso (anche se l'esercizio la richiede). Si, la versione iterativa la costruisci eliminando la ricorsione e racchiudendo tutto (o quasi) in un ciclo (con altri opportuni aggiustamenti)

 

[kodibi]

Si, quello ho visto... intendevo che come risultato finale si ottengono solo 'D', quindi la sostituzione è un po' senza senso (anche se l'esercizio la richiede). Si, la versione iterativa la costruisci eliminando la ricorsione e racchiudendo tutto (o quasi) in un ciclo (con altri opportuni aggiustamenti)

Grazie mille per il tuo aiuto,ma un'ultima cosa. il risultato finale come risulta dal mio codice, non prevede tutte D, bensì un'unica X infondo a sinistra (matrice[31][0]). è giusto con questa X o devono essere tutte D?

 

[ptm]

Quella me l'ero persa si, è giusto che rimanga quell'unica 'X'.
Posso segnare il problema come risolto?

 

[kodibi]

Quella me l'ero persa si, è giusto che rimanga quell'unica 'X'.
Posso segnare il problema come risolto?

Risoltissimo Grazie mille !