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
Discussioni simili
Autore Titolo Forum Risposte Data
M [PHP] Problema con algoritmo struttura iterativa PHP 2
A Algoritmo NDiff, problema con gli attributi Programmazione 0
T PROBLEMA CON SESSIONI PHP 3
T ALTRO PROBLEMA CON ARRAY PHP PHP 1
T PROBLEMA CON ARRAY PHP 8
L problema con query select PHP 2
R Problema query con ricerca id numerico PHP 2
F Problema con risposta PHP 0
S problema con recupero dati tabella mysql PHP 2
Z Problema con il mio tp-l i nk Reti LAN e Wireless 1
L Problema RAM con Tomcat 8 Apache 0
napuleone problema con sort e asort PHP 4
Z Problema con INT MySQL PHP 1
Z Problema database MySQL con XAMPP PHP 0
M Problema con controllo form in real time jQuery 6
Z Problema di sincronizzazione PAYPAL con PHP PHP 1
G Problema con Get page PHP 4
P Problema con require once PHP 6
P Problema con i package Java 1
A Problema login con Safari PHP 14
F INDESIGN: problema esportazione esecutivo per la stampa con foto B/N Webdesign e Grafica 1
S problema con css bootstrap3 HTML e CSS 4
M .load() problema con caricamenti dinamici di js Javascript 0
G Problema ------- con Query PHP 1
G Problema con Query PHP 1
T problema con select dinamica con jquery Javascript 0
S Problema con spazi bianchi HTML e CSS 5
A PROBLEMA: insert mysqli con dati Tagsinput Presentati al Forum 0
Tommy03 Problema con z-index HTML e CSS 3
M Problema inserimento parole con apostrofo nel db PHP 5
C Problema con dati meteo xml XML 1
S Problema con infrarossi videocamera IP Cam e Videosorveglianza 1
V Problema con librerie allegro5 c++ C/C++ 1
M Problema con php per calcolo costo percentuale PHP 7
S Problema con mysqli_num_rows PHP 18
grgfede Problema javascript con aruba Javascript 1
M Problema con visibility e radio button Javascript 2
Marti1! Problema con casella mail cancellata Posta Elettronica 3
L [PHP] Problema con Telegram PHP 1
tomorc [HTML] Problema con scroll bar (risolto) HTML e CSS 0
S Strano problema con i title su Google SEO e Posizionamento 3
P [ASP.Net] Problema ERR_INCOMPLETE_CHUNKED_ENCODING 206 (Partial Content) con Font ASP.NET 4
P [HTML] Problema ERR_INCOMPLETE_CHUNKED_ENCODING 206 (Partial Content) con Font HTML e CSS 1
N [Apache] problema con estensione php Apache 0
C [PHP] Problema con download file PHP 0
M [PHP] Problema con preg_match PHP 1
gandalf1959 [PHP] problema con l'utilizzo di Header PHP 3
M [PHP] Problema con query select PHP 2
S [Javascript] Problema con condizione "if" Javascript 2
K Problema di indicizzazione con dominio vecchio vuoto SEO e Posizionamento 2

Discussioni simili