- Codice:
ab ab ab ac ac ac ba ba ba bc bc bc ca ca ca cb cb cb
ba bc ca ca cb ba ab ac cb cb ca ab ac ab bc bc ba ac
La complessità dell'algoritmo deve essere O(n2S(n)), dove S(n) è il numero di matrici da stampare.
La mia idea sarebbe quella di non memorizzare l'array in un array bidimensionale, ma in un array monodimensionale.
Lo pseudocodice potrebbe essere:
- Codice:
Matrix( n:lato matrix , h: lunghezza pref. , S: array )
if nxn == h then
print(S , n)
else
for i<-1 to nxn do
for y in {a,b,c} do
if ( isSafe( S , y ) ) then
S[h+1] <- y
Matrix( n, h+1, S )
- Codice:
print( S:array, n: dimensione lato )
for i<-1 to nxn do
print(S[i])
if ( i%n == 0 ) then print(\n)
Adesso mi manca la procedura isSafe per controllare che è possibile aggiungere l'elemento in quella posizione.
Può andare come algoritmo? Rispetta la complessità ?
Buona domenica