[C] Automi a stati finiti

[gila75]

Sto cercando un po' di risolvere, ma non è così facile!!!
Il backtracking, mi sto accorgendo (credo) che è più difficile e penso anche meno prestante.
Richiede una conoscenza sull'attraversamento dei grafi, e del DFS (deep firts search).
Ho provato a ragionare con uno stack, ma arrivo a dei punti che m'incasino.
Per esempio:
parto da q0->q1->q3
stato dello stack: 0,1,3
q3 è un ramo morto, quindi faccio un pop è ho stack 0,1
ok, sono in q1.
ma se non prendo accorgimenti e marco come già visitato, potrei tornare in q3...e così via all'infinito.
Al tempo stesso, lo potrei marcare con un flag, ma potrei avere più diramazioni e non considerarle per il fatto di averlo marcato!!!!
Non so se mi riesco a spiegare.
La verità è che mi mancano le basi sui grafi,alberi ecc...ho del materiale...ma ragazzi...sono cose davvero complesse.

Magari il metodo parallelo è più semplice.
più che altro la tabella di transizione, non so come fare a salvarla.
Nei DFA a ogni cella dell'array è memorizzato un evento... in modo univoco, mentre qui con l'evento x ho più stati...non so forse una struttura.

ho rappresentato il grafo d'esempio con questa matrice di adiacenza:
q0 [0,1,1,1,0]
q1 [0,0,0,1,0]
q2 [0,0,0,1,1]
q3 [0,0,0,0,0]
q4 [0,0,0,0,0]

Forse qui intendevi ...." nello stato vecchio metti 0 ".
sono gli eventi che non riesco a gestire!!!!!
Comunque @spider... non ti voglio stressare....è che sono cose difficili, ma molto, molto interessanti.

[spider-net]

Sto cercando un po' di risolvere, ma non è così facile!!!
Il backtracking, mi sto accorgendo (credo) che è più difficile e penso anche meno prestante.
Richiede una conoscenza sull'attraversamento dei grafi, e del DFS (deep firts search).
Ho provato a ragionare con uno stack, ma arrivo a dei punti che m'incasino.
Per esempio:
parto da q0->q1->q3
stato dello stack: 0,1,3
q3 è un ramo morto, quindi faccio un pop è ho stack 0,1
ok, sono in q1.
ma se non prendo accorgimenti e marco come già visitato, potrei tornare in q3...e così via all'infinito.
Al tempo stesso, lo potrei marcare con un flag, ma potrei avere più diramazioni e non considerarle per il fatto di averlo marcato!!!!
Non so se mi riesco a spiegare.
La verità è che mi mancano le basi sui grafi,alberi ecc...ho del materiale...ma ragazzi...sono cose davvero complesse.

Se non hai familiarità con gli alberi, io passerei al secondo metodo.

Magari il metodo parallelo è più semplice.
più che altro la tabella di transizione, non so come fare a salvarla.
Nei DFA a ogni cella dell'array è memorizzato un evento... in modo univoco, mentre qui con l'evento x ho più stati...non so forse una struttura.

Buona idea. Avevo pensato a tre strutture, una per gli stati, una per rappresentare il grafo come lista di stati e l'altra per le transizioni:

Codice: Seleziona tutto

struct stato{
  char finale;
  int indice;
  struct transizioni *transList;
};
 
struct listaStati {
  int indice;
  struct stato *pStato;
  struct listaStati *next;
};
 
struct transizioni {
  char simbolo;
  struct stato *pStato;
  struct transizioni *next;
};

Dopo aver inizializzato le liste di stati e delle transizioni, si può fare una cosa del genere:

Codice: Seleziona tutto

int nfa(char * input, struct stato *s){
  struct transizione * t;
  int accettato =0;
 
  if(s == NULL){
    return 0;
  }else{
    t = s -> transList;
    if(input[0] == '\0' && s -> finale == 'S'){
      return 1;
    }
     
    while( t != NULL && accettato ==0){
      printf("Simbolo di transizione : %c\n",t->simbolo);
      if(t -> simbolo == input[0]){
        printf("Mi sposto sullo stato : %d\n",t->pStato->indice);
        accettato= nfa(input+1,t->pStato); 
      }
      t = t -> next;
    }
  }
  return accettato;
}

Non l'ho testato però. Potrebbe esserci qualche errore nella funzione NFA().

[spider-net]

Esempio completo:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 100

struct stato {
    char finale;
    int indice;
    struct transizioni *transList;
};

struct listaStati {
    int indice;
    struct stato *pStato;
    struct listaStati *next;
};

struct transizioni {
    char simbolo;
    struct stato *pStato;
    struct transizioni *next;
};

int nfa(char *input, struct stato *s);
void freemem(struct listaStati *sLista);

int main(void) {
    struct listaStati *sList = NULL, *sListPtr = NULL, *tmpListPtr = NULL;
    struct stato *sPtr;
    struct transizioni *tPtr, *tmpTPtr;

    int nStato;
    char finale = 'N';
    char simbolo = ' ';
    char input[MAX_LEN];

    do {
        printf("Inserisci il numero dello stato (-1 per uscire): ");
        scanf("%d", &nStato);
        getchar();

        if (nStato != -1) {
            printf("Stato finale (S/N)? ");
            scanf("%c", &finale);

            if (sList == NULL) {
                sList = malloc(sizeof(struct listaStati));
                sList -> indice = nStato;
                sList -> pStato = malloc(sizeof(struct stato));
                sList -> pStato -> indice = nStato;
                sList -> pStato -> finale = finale;
                sList -> pStato -> transList = NULL;
                sList -> next = NULL;
            } else {
                sListPtr = sList;

                while (sListPtr->next != NULL) {
                    sListPtr = sListPtr -> next;
                }

                sListPtr -> next = malloc(sizeof(struct listaStati));
                sListPtr = sListPtr -> next;
                sListPtr -> indice = nStato;
                sListPtr -> pStato = malloc(sizeof(struct stato));
                sListPtr -> pStato -> indice = nStato;
                sListPtr -> pStato -> finale = finale;
                sListPtr -> pStato -> transList = NULL;
                sListPtr -> next = NULL;
            }
        }
    } while (nStato != -1);

    sListPtr = sList;
    while (sListPtr != NULL) {
        printf("\n\nInserisci la transizione dallo stato %d \n", sListPtr->indice);
        printf("Allo stato (-1 per terminare): ");
        scanf("%d",&nStato);

        while (nStato != -1) {
            tmpListPtr = sList;
            while (tmpListPtr != NULL){
                if (tmpListPtr -> indice == nStato){
                    break;
                }
                tmpListPtr = tmpListPtr -> next;
            }

            if (tmpListPtr == NULL) {
                printf("Stato invalido\n");
            } else {
                getchar();
                printf("Inserisci simbolo: ");
                scanf("%c",&simbolo);
                sPtr = sListPtr -> pStato;

               if (sPtr->transList == NULL) {
                    sPtr->transList = malloc (sizeof (struct transizioni));
                    tPtr = sPtr->transList;
                } else {
                    tPtr = sPtr->transList;
                    while (tPtr->next != NULL) {
                        tPtr = tPtr->next;
                    }
                    tPtr -> next = malloc (sizeof (struct transizioni));
                    tPtr = tPtr ->next;
                }

                tPtr -> simbolo = simbolo;
                tPtr -> pStato = tmpListPtr->pStato;
                tPtr -> next = NULL;
            }

            printf("\nAllo stato (-1 per terminare): ");
            scanf("%d",&nStato);
        }
        sListPtr = sListPtr -> next;
    }

    if (sList != NULL) {
        printf("\nInserisci stringa: ");
        scanf("%s",input);

        while (strcmp(input, "q") != 0) {
            if (nfa(input, sList->pStato)) {
                printf("Stringa accettata.\n");
            } else {
                printf("Stringa non accettata.\n");
            }

            printf("\nInserisci stringa (q per uscire): ");
            scanf("%s",input);
        }
    }

    freemem(sList);
    return EXIT_SUCCESS;
}

int nfa(char *input, struct stato *s) {
    struct transizioni *t;
    int accettato = 0;

    if (s == NULL) {
        return 0;
    } else {
        t = s->transList;

        if (input[0] == '\0' && s->finale == 'S') {
            return 1;
        }

        while (t != NULL && accettato == 0) {
            if (t->simbolo == input[0]) {
                accettato = nfa(input+1, t->pStato);
            }
            t = t->next;
        }
    }
    return accettato;
}

void freemem(struct listaStati *sLista) {
    struct listaStati *tsLista;
    struct stato *tStato;
    struct transizioni *trans, *trans2;

    while (sLista != NULL) {
        tsLista = sLista->next;

        tStato = sLista->pStato;
        trans = tStato->transList;

        while (trans != NULL) {
            trans2 = trans->next;
            free(trans);
            trans = trans2;
        }

        free(tStato);
        free(sLista);
        sLista = tsLista;
    }
}

[gila75]

Ti ringrazio @spider...un po' complesso, ma ci studio su.
Hai usato il backtracking usando le liste?
Stavo proprio vedendo i grafi e i loro modi di attraversamento, ero interessato la depth first search, appropriato per questo caso direi.
Non ho capito alcune cose però, devo studiare.
Per esempio se abbiamo un nodo con più archi, devo pur memorizzare da qualche parte che prima di retrocedere deve esaurire tutti gli archi no?
Mi pare si chiami "grado di libertà" o qualcosa del genere.
Certo che alberi e grafi richiedono mesi solo loro...da autodidatta e col tempo risicato poi!!!!
provo il programma, ancora grazie!

[gila75]

Faccio una parentesi, non dovrei essere OT.
Ho riflettuto un po' sulla dfs per visitare un grafo in profondità.
allego a fine pagina il grafo, che dovrebbe essere non orientato e non pesato.
Questa è la sua matrice di adiacenza:

Codice: Seleziona tutto

        {{0,1,1,0,0,0,0},
                     {1,0,0,0,0,0,0},
                     {1,0,0,1,0,1,1},
                     {0,0,1,0,1,0,0},
                     {0,0,0,1,0,0,0},
                     {0,0,1,0,0,0,0},
                     {0,0,1,0,0,0,0}};

in zero, noto che posso andare nel vertice 1 o 2
bene, vado in 1. Nella matrice alla riga 1 colonna 0 noto che sono connesso a 0, ma da zero ci arrivo.
Quindi credo che appena visito un nodo, vada aggiornata la matrice. cioè se arrivo da zero, nella posizione 0 della matrice vada messo 0.
In modo tale che anche se vado in 2 (che è collegato a zero) non posso più tornare perchè è già stato visitato.
Supponiamo di essere nel vertice 2 (collegato a 0,3,5,6)
Se non avessi azzerato, risulterebbe un arco possibile che da 2 vada a 0, cosa che non voglio, visto che 2 può proseguire solo a 3,5,6.
Unitamente ad uno stack esplicito, una volta che non ho cammini torno a ritroso.
Parto da zero e vado in 1
stack 0,1
non ho altre strade da 1: pop stack 0
vado in 2:
push stack 0,2
e così via.
quindi credo che partendo dalla riga zero della matrice debba fare una scansione della riga per vedere i possibili archi.
Nel caso di 0 ne trovo 2, che portano a 1,2.
Questo è il metodo della DFS?

Quando ho usato la dfs per generare un labirinto, non ho avuto questi problemi, era più semplice.
Generavo un random su 4 direzioni (N,S,O,E), e tutte e 4 le opzioni davano esito negativo, retrocedevo con lo stack al primo punto libero.
Ma qui la faccenda è un po' più complessa

[spider-net]

Ti ringrazio @spider...un po' complesso, ma ci studio su.
Hai usato il backtracking usando le liste?

Il 99% del main è solo inizializzazione delle strutture. la parte importante è la funzione nfa().
Comunque sì, ho usato un backtracking usando le liste, in modo simile a quello che fa DFS.
In pratica, ad ogni simbolo, seguo la prima transizione che mi porterà ad un nuovo stato, e ricorsivamente vado avanti. Quando ad un certo punto, non posso andare avanti, torno indietro per esplorare un'altra transizione, e così via, proprio come in DFS.
Probabilmente nel tuo libro avrai visto che un grafo può essere implementato in due modi: matrice di adiacenza (più veloce ma occupa più spazio) o lista di adiacenza (più lenta, ma più efficiente in termini di spazio). Io ho usato una specie di lista di adiacenza.

Stavo proprio vedendo i grafi e i loro modi di attraversamento, ero interessato la depth first search, appropriato per questo caso direi.
Non ho capito alcune cose però, devo studiare.
Per esempio se abbiamo un nodo con più archi, devo pur memorizzare da qualche parte che prima di retrocedere deve esaurire tutti gli archi no?
Mi pare si chiami "grado di libertà" o qualcosa del genere.
Certo che alberi e grafi richiedono mesi solo loro...da autodidatta e col tempo risicato poi!!!!
provo il programma, ancora grazie!

Per questo DFS usa tre colori per marcare i nodi: bianco (nodo non visitato), grigio (nodo scoperto ma non ancora visitato), nero (non già visitato). Un nodo diventa nero quando ho già visitato tutti i suoi nodi adiacenti. Quando un nodo diventa nero, torno indietro al nodo suo nodo "padre", cioè quel nodo che mi ha portato a lui. E così via finché in nodo di partenza diventa nero e ho esaurito tutto il grafo.

EDIT: ora rispondo all'altra domanda gila.

[spider-net]

in zero, noto che posso andare nel vertice 1 o 2
bene, vado in 1. Nella matrice alla riga 1 colonna 0 noto che sono connesso a 0, ma da zero ci arrivo.
Quindi credo che appena visito un nodo, vada aggiornata la matrice. cioè se arrivo da zero, nella posizione 0 della matrice vada messo 0.
In modo tale che anche se vado in 2 (che è collegato a zero) non posso più tornare perchè è già stato visitato.
Supponiamo di essere nel vertice 2 (collegato a 0,3,5,6)
Se non avessi azzerato, risulterebbe un arco possibile che da 2 vada a 0, cosa che non voglio, visto che 2 può proseguire solo a 3,5,6.

Ecco perché in DFS si usano i tre colori bianco, grigio e nero (come spiegato sopra).

Ti simulo DFS a parole. All'inizio tutti i nodi sono bianchi.
Allora, parto dal nodo 0, zero diventa grigio, vedo che 0 è adiacente a 1 e a 2. Bene scelgo di andare a 1, 1 è adiacente solo a 0, ma dato che zero è già grigio (visito solo i nodi bianchi), non lo visito di nuovo, quindi da 1 non si va da nessuna parte, 1 diventa nero.
Torno a 0 (o tramite pop dello stack o ricorsivamente), l'unico nodo bianco è 2 (1 è nero quindi non lo visito, visito solo quelli bianchi), vado a 2, quindi 2 ora è grigio, da 2 vado a 5, che diventerà grigio, ma da 5 non vado da nessun'altra parte, quindi 5 diventa nero.
Torno a 2 e gli unici due nodi bianchi sono 3 e 6, vado a 6 che diventerà grigio e poi nero, torno ancora a 2 e sta volta vado verso 3, che diventerà grigio.
Da 3 vado a 4 che diventerà grigio e poi nero, quindi torno a 3, da 3 non posso raggiungere più nodi bianchi, quindi 3 diventa nero. Torno a 2, da 2 non posso più raggiungere nodi bianchi, 2 diventa nero. Torno a 0, da lui non posso più raggiungere nodi bianchi, diventa nero. STOP.

[gila75]

Ecco perché in DFS si usano i tre colori bianco, grigio e nero (come spiegato sopra).

Ci sono andato vicino dai... potrebbe funzionare, ma mi attengo alle procedure collaudate.
Faccio il secondo turno, quindi ora è improponibile per me. Rieleggo bene.
Non so come ringraziarti per tutte queste informazioni e per la pazienza

[spider-net]

Figurati!

[gila75]

Sto cercando d'implementare la DFS senza ricorsione con i vari colori e lo stack...ma per sua natura è intrinsecamente ricorsiva...
e non è facile. Uso lo stack i colori ecc...ma per ora nulla.
Cavoli credevo fosse un giochetto....e invece
Proverò ancora

[spider-net]

Come li hai implementati i colori?
La scelta più semplice è usare un vettore di interi, grande quanto il numero di nodi. In cui 0 indica il bianco, 1 il grigio e 2 il nero. Definendo bianco, grigio e nero come costanti. Oppure puoi fare una struttura Nodo, con vari campi tra cui il colore.

Tu gila hai Algorithms in C di Robert Sedgewick o Introduction to Algorithms di Thomas Cormen, Charles Leiserson e Ronald Rivest?
Sono sicuro che Introduction to Algorithms spiega DFS con i colori.

[gila75]

La scelta più semplice è usare un vettore di interi, grande quanto il numero di nodi.

Ho fatto così

In cui 0 indica il bianco, 1 il grigio e 2 il nero

A dire il vero un array di char g,b,n

Tu gila hai Algorithms in C di Robert Sedgewick

Ho questo, ma non mi trovo molto bene...é quasi tutto implementato a ricorsione e liste.
Poi calcola che lo sto leggendo un po' alla buona, fatico dopo 8 ore di lavoro, mestieri a casa ecc..a leggere testi così impegnativi.
Comunque ci riprovo.
Il problema è che anche in versione iterativa...è ricorsivo...non so se riesco a spiegarmi.

[spider-net]

A dire il vero un array di char g,b,n

Va comunque bene. Tanto un char non è altro che un intero.

Ho questo, ma non mi trovo molto bene...é quasi tutto implementato a ricorsione e liste.
Poi calcola che lo sto leggendo un po' alla buona, fatico dopo 8 ore di lavoro, mestieri a casa ecc..a leggere testi così impegnativi.
Comunque ci riprovo.
Il problema è che anche in versione iterativa...è ricorsivo...non so se riesco a spiegarmi.

Ti capisco. Se puoi però ti consiglio di familiarizzare di più con la ricorsione. Come avrai visto gli algoritmi su grafi (e alberi) ne fanno largo uso.
E di solito viene introdotta per "facilitare" la comprensione. Alle volte è utile simulare un algoritmo ricorsivo su carta usando esempi piccoli ma significativi.

[gila75]

Ci proverò ,ma è davvero ostica.
So che la ricorsione (spero non passi MAW) per alcuni problemi agevola e parecchio.
Ora però mi sono un po' intestardito sulla versione iterativa.

[spider-net]

Provaci, poi magari se non ti viene possiamo darti una mano.
Personalmente non ho mai implementato DFS in modo puramente iterativo e con uno stack, magari me la vado a vedere

[gila75]

Eccomi
Partendo da questo grafo (fondo pagina), ottengo questo output:

Codice: Seleziona tutto

______________________________________________________
visito nod 7
______________________________________________________
PUSH: stack [indice 2] contenuto [7]
______________________________________________________
visito nod 1
______________________________________________________
PUSH: stack [indice 3] contenuto [1]
______________________________________________________
visito nod 3
______________________________________________________
PUSH: stack [indice 4] contenuto [3]
______________________________________________________
visito nod 4
______________________________________________________
PUSH: stack [indice 5] contenuto [4]
______________________________________________________
visito nod 2
______________________________________________________
PUSH: stack [indice 6] contenuto [2]
______________________________________________________
visito nod 6
______________________________________________________
PUSH: stack [indice 7] contenuto [6]
POP:  stack [indice 6] contenuto [2]
POP:  stack [indice 5] contenuto [4]
POP:  stack [indice 4] contenuto [3]
POP:  stack [indice 3] contenuto [1]
______________________________________________________
visito nod 5
______________________________________________________
PUSH: stack [indice 4] contenuto [5]
POP:  stack [indice 3] contenuto [1]
POP:  stack [indice 2] contenuto [7]
POP:  stack [indice 1] contenuto [0]
POP:  stack [indice 0] contenuto [0]
finish (stack vuoto)

Ho segnalato i nodi marcati e lo stato dello stack.
Appena riordino il programma lo posto .
@spider: non ho usato la ricorsione classica con stack di sistema, ma uno stack esplicito.
Ho fatto una variante al metodo dei colori. Un po' meno prestante, ma al momento (per me ) meno ostica.
Intanto vorrei capire se l'output è corretto per la DFS. A me sembra di si

[spider-net]

Tutto giusto gila, ottimo lavoro!
Un'altra alternativa ai colori è quella di marcare gli archi, come visitati o meno, e procedere ricorsivamente.

[gila75]

Tutto giusto gila, ottimo lavoro!

Grazie mi ci è voluto un po' però.
Ho usato una matrice di adiacenze (le liste di adiacenza non le so ancora usare).
Poi, al posto dei colori che per ora mi incasinano, cancello gli archi (segnati a 1) e li metto a zero.
Insomma...domani o dopo riordino il programma e lo posto.
Credo si potrebbe migliorare ancora...tempo permettendo....
Sicuramente col metodo ricorsivo in 2 righe risolvi...prima o poi mi ci devo mettere.
è che la ricorsione l'ho studiata, ma non la uso per 1 settimana e già mi risulta ostica. Credo sia innaturale...per l'essere umano.

EDIT:
tutto sommato è abbastanza ok.
Devo cambiare da int a char la matrice (solo per ottimizzare spazio)
Non so se è corretto, ci sono arrivato col ragionamento:
nella matrice, in posizione 0 per ogni riga, ho marcato 0, cioè non visitabile.
Lo 0 nel mio caso è la radice dell'albero o il padre, quindi si parte per forza di cose da li, e di conseguenza si esce solo, senza
mai poterlo visitare, giusto?

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define R 8
#define C 8

void azzera (int matrix[R][C], int i, int  j)
{
    matrix[j][i]=0;
    int r,c;

    for (r=0; r<R; r++)
    {
        for ( c=0; c<C; c++)
        {
            matrix[r][j]=0;
            printf ("%d ", matrix[r][c]);
        }
        puts("");
    }
}
 
          


int main(void) 
{
   int matrix[R][C]={{0,0,0,0,0,0,0,1}, //0
                     {0,0,0,1,0,1,0,1}, //1
                     {0,0,0,0,1,0,1,0}, //2
                     {0,1,0,0,1,0,0,1}, //3
                     {0,0,1,1,0,0,0,0}, //4
                     {0,1,0,0,0,0,0,0}, //5
                     {0,0,1,0,0,0,0,0},//6
                     {0,1,0,1,0,0,0,0}};

  
  int stack_r[200]={0};
  int index_r=1;
  int a;
  int flag=0;
  int i=0;
  int j;

  stack_r[index_r]=0;
  a=0;
  
 
    while (1)
    {
        i=a;
        flag=0;

        do {
                for ( j=0; j<C; j++)
                {
                    if (matrix[i][j]==1  ) 
                    {
                        
                        azzera(matrix,i,j);
                        flag++; 
                        puts("______________________________________________________"); 
                        printf ("visito nod %d\n",j); 
                        puts("______________________________________________________"); 
                        index_r++;
                        stack_r[index_r]=j;
                        a=stack_r[index_r]; 
                        printf ("PUSH: stack [indice %d] contenuto [%d]\n", index_r,a);
                        i++;
                        i=a;
                    }
                    
                }

           }while (flag<0);
          
    if (flag==0)
    {
        index_r--;
        a=stack_r[index_r];
        printf ("POP:  stack [indice %d] contenuto [%d]\n", index_r,a);
        // i=a;

        if (index_r==0)
        {
            puts ("finish (stack vuoto)");
            return 0;
        }     
            
            
                   
    }
           
}  
      
           
              
            
  return 0;      

}  
   

[spider-net]

Tutto giusto gila, ottimo lavoro!

Grazie mi ci è voluto un po' però.
Ho usato una matrice di adiacenze (le liste di adiacenza non le so ancora usare).
Poi, al posto dei colori che per ora mi incasinano, cancello gli archi (segnati a 1) e li metto a zero.

Tecnica interessante, quindi alla fine ti rimane a "1" solo l'arco da 1 a 7 no? Tutti gli altri li "cancelli".

Insomma...domani o dopo riordino il programma e lo posto.
Credo si potrebbe migliorare ancora...tempo permettendo....
Sicuramente col metodo ricorsivo in 2 righe risolvi...prima o poi mi ci devo mettere.
è che la ricorsione l'ho studiata, ma non la uso per 1 settimana e già mi risulta ostica. Credo sia innaturale...per l'essere umano.

E in effetti ricorsivamente con molto poco te la sbrighi. In certi ambiti come nei grafi la ricorsione viene quasi naturale, ti viene di usarla "spontaneamente".

[gila75]

Tecnica interessante, quindi alla fine ti rimane a "1" solo l'arco da 1 a 7 no? Tutti gli altri li "cancelli".

Ho postato anche la matrice come evolve se lanci il programma.
Se una riga è tutta zero (come la casella nera) non mi muovo e faccio un pop.
Ad un certo punto alla fine della matrice, continuo a fare pop (matrice tutta a zero), ma arrivo a esaurire lo stack...quindi ho finito.
Evoluzione della matrice:

Codice: Seleziona tutto

0 0 0 0 0 0 0 0 
0 0 0 1 0 1 0 0 
0 0 0 0 1 0 1 0 
0 1 0 0 1 0 0 0 
0 0 1 1 0 0 0 0 
0 1 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 1 0 1 0 0 0 0 
______________________________________________________
visito nod 7
______________________________________________________
PUSH: stack [indice 2] contenuto [7]
0 0 0 0 0 0 0 0 
0 0 0 1 0 1 0 0 
0 0 0 0 1 0 1 0 
0 0 0 0 1 0 0 0 
0 0 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 0 1 0 0 0 0 
______________________________________________________
visito nod 1
______________________________________________________
PUSH: stack [indice 3] contenuto [1]
0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 1 0 1 0 
0 0 0 0 1 0 0 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 
______________________________________________________
visito nod 3
______________________________________________________
PUSH: stack [indice 4] contenuto [3]
0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 
______________________________________________________
visito nod 4
______________________________________________________
PUSH: stack [indice 5] contenuto [4]
0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 1 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
______________________________________________________
visito nod 2
______________________________________________________
PUSH: stack [indice 6] contenuto [2]
0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
______________________________________________________
visito nod 6
______________________________________________________
PUSH: stack [indice 7] contenuto [6]
POP:  stack [indice 6] contenuto [2]
POP:  stack [indice 5] contenuto [4]
POP:  stack [indice 4] contenuto [3]
POP:  stack [indice 3] contenuto [1]
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
______________________________________________________
visito nod 5
______________________________________________________
PUSH: stack [indice 4] contenuto [5]
POP:  stack [indice 3] contenuto [1]
POP:  stack [indice 2] contenuto [7]
POP:  stack [indice 1] contenuto [0]
POP:  stack [indice 0] contenuto [0]
finish (stack vuoto)
gila@ubuntu:~/Scrivania$