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
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
O problema con dvr dahua xvr5116 IP Cam e Videosorveglianza 0
G Problema con Xampp Web Server 1
andrea barletta Problema con miniature comandi Photoshop 0
I problema con alice Posta Elettronica 0
N Problema con position absolute e overflow HTML e CSS 4
L Problema con inner join PHP 11
K [php] Problema con inner join PHP 4
K [PHP] Problema con variabili concatenate. PHP 1
O problema con query PHP 4
I problema con 2 account Posta Elettronica 1
L problema collegamento file css con html HTML e CSS 1
E Problema accesso a file con app sviluppata con MIT APP INVENTOR 2 Sviluppo app per Android 0
M Problema con Try Catch PHP 0
Sergio Unia Problema con gli eventi del mouse su una data table: Javascript 2
T PROBLEMA CON SESSIONI PHP 3
T ALTRO PROBLEMA CON ARRAY PHP PHP 1
R problema con else PHP 0
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 0
S problema con css bootstrap3 HTML e CSS 4
M .load() problema con caricamenti dinamici di js Javascript 0
G Problema con eccessiva nitidezza apertura Camera Raw Photoshop 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

Discussioni simili