Problema con algoritmo ricorsivo [backtracking] java

Gabriele Saturni

Nuovo Utente
30 Dic 2014
1
1
0
Ciao ragazzi , ho dei problemi con questo algoritmo ricorsivo..spero che qualche anima pia possa aiutarmi.
Allora il testo dell'esercizio è il seguente:
Fornire lo pseudocodice di un algoritmo che preso in input un intero n stampi tutte le matrici contenenti le lettere ={a,b,c} nxn tali che le a precedono le b che precedono le c. ad esempio per n=2 l'output deve essere :
output:
aa aa aa ab ab bb aa aa ac cc bb bb bc bc ab ab ac
aa ab bb ab bb bb ac cc ac cc bc cc bc cc bc cc bc

Vi posto anche il mio codice, è scritto in java ,è semplicemente una funzione statica.
Codice:
public class EsercizioNovBT {
    public static void main(String[] args) {
        int n=2 , i , j;
        char[][] m = new char [n][n];
        /* array di booleani che indicano se esiste una b o una c nella riga/colonna i/j ad esempio:
        isBR[i] è true se è stata messa una b nella riga i , isBC[j] è true se è stata messa una b nella colonna j ,stesso    discorso per gli altri array*/
        boolean[] isBR = new boolean [n];
        boolean[] isBC = new boolean [n];
        boolean[] isCR = new boolean [n];
        boolean[] isCC = new boolean [n];
       /* inizializzazione dei vettori e della matrice */
        for(i=0;i<n;i++)
            isBR[i]=false;
        for(i=0;i<n;i++)
            isBC[i]=false;
        for(i=0;i<n;i++)
            isCR[i]=false;
        for(i=0;i<n;i++)
            isCC[i]=false;
        for (i=0 ; i<n ; i++)
            for(j=0 ; j<n ;j++)
                m[i][j]='d';
        i=0;j=0;
        scriviSuM(m,isBR,isBC,isCR,isCR,i,j,n);



    }



    static void scriviSuM(char[][]M , boolean[] isRB,boolean[] isCB,boolean[] isRC,boolean[] isCC,int i, int j , int n)
    {
        if(i==n)
        {
            for (int r=0 ; r<n ; r++)
            {
                for(int c=0 ; c<n ;c++)
                {
                    System.out.print(M[r][c]);
                }
                System.out.print("\n");
            }
            System.out.println();
        }
        else
        {
            if(j==n)
            {
                j=0;
                scriviSuM(M,isRB,isCB,isRC,isCC,i+1,j,n);
            }
            else
            {

                    if (! (isRC[i]) && !(isCC[j])) // se non ci sono delle c
                    {
                        if( ! (isRB[i]) && !(isCB[j]) )  // se non ci sono già delle b e delle c allora puoi prendere a
                        {
                            M[i][j]='a';
                            scriviSuM(M,isRB,isCB,isRC,isCC,i,j+1,n);
                        }

                        isRB[i]=isCB[j]=true;
                        M[i][j]='b'; // se non ci sono  c posso comunque prendere delle b
                        scriviSuM(M,isRB,isCB,isRC,isCC,i,j+1,n);
                        isRB[i]=isCB[j]=false;
                    }
                    isRC[i]=isCC[j]=true;
                    M[i][j]='c'; // posso sempre prendere c
                    scriviSuM(M,isRB,isCB,isRC,isCC,i,j+1,n);

            }


        }
    }
}
ora l'output è:
aa
aa

aa
ab

aa
ac

aa
bc

aa
cc

ab
cc

ac
cc

bc
cc

cc
cc

Quello che stampa è corretto...ma è solo una parte di quello che dovrebbe stampare...evidentemente taglio troppo lo spazio di ricerca.

Ora oltre a farmi capire cosa sbaglio in questo esercizio specifico , mi piacerebbe che qualcuno possa darmi delle dritte su come risolvere i problemi con la tecnica del backtracking.
Grazie in anticipo :):)
 
  • Like
Reactions: ottofonsuppost

narc0x

Utente Attivo
10 Ott 2008
128
2
18
Allora per quanto riguarda il codice (tralasciando il forte mal di testa che mi e' venuto leggendo la sintassi :D), hai controllato se restituisce delle eccezioni ?
E' possibile che hai raggiunto il limite massimo di ricorsioni sullo stack della virtual machine (impostato di default a 400k), puoi provare a forzare il garbage collector ?

Per la spiegazione sul backtracking.

Il backtracking e' una tecnica per risolvere dei problemi comuni nella ricerca di determinate condizioni in un albero di dati. Principalmente serve per comparare in maniera ricorsiva tutte le possibili combinazioni di una specifica condizione partendo dalla piu' bassa e andando verso la piu' alta. Per farti un esempio in codice python (ed evitare la nausea da codice Java):

Codice:
def prop(x,y):
    return (x and y)

vals = [False, True]
for x in vals:
    print("x=", x)
    for y in vals:
            print("y=", y)
            if prop(x,y):
                    print("\tSI")
            else:
                    print ("\tNO")
Questo sopra produce come risultato:

x= False
y= False NO
y= True NO

x= True
y= False NO
y= True SI
Il codice di sopra ha comparato tutte le possibili combinazioni tra i 2 valori della lista:

True == True
True == False

False == True
False == False
Fonte: http://it.wikipedia.org/wiki/Backtracking
 
Ultima modifica:
  • Like
Reactions: ottofonsuppost