Problema backtracking

di il
3 risposte

Problema backtracking

Ciao,

dunque ho questo esercizio da fare:
Un file di testo contiene la descrizione di un sistema relativo a una schedina del gioco del totocalcio. Il
file è composto da N righe, in ognuna delle quali si possono trovare uno, due oppure tutti e tre i simboli
per i possibili risultati (che sono 1, 2 e X).
Si scriva un programma C che, acquisito il contenuto del file in un’opportuna struttura dati interna,
generi tutte le colonne della schedina appartenenti al sistema letto, espandendo tutte le coppie e le triple
di simboli e generando tutte le possibili combinazioni. Tali combinazioni siano, quindi, memorizzate in
un secondo file, in ragione di una per riga.
Si noti che il valore di N non è noto a priori, né esso compare in alcun modo nel file di ingresso: tale
valore deve essere opportunamente dedotto dal programma a partire dal contenuto del file stesso.
E questo è il mio codice:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10

void calcio(int i, int vet[], char *s[4], int n);

int main(void)
{
    int i=0, n;
    int vet[MAX]={0};
    char tmp[4];
    char c;
    char **s;
    FILE *f;

    f=fopen("calcio.txt", "r");
    while(fscanf(f, "%s", tmp)!=EOF)
        i++;
    rewind(f);
    s=malloc(i*sizeof(char *));
    for(n=0; n<i; n++)
        s[n]=malloc(4*sizeof(char));
    n=0;
    while(fscanf(f, "%s", s[n])==1)
        n++;

    calcio(0, vet, s, i);
    return 1;
}

void calcio(int i, int vet[], char *s[4], int n) {
    int j;

    if(i>=n) {
        for(j=0; j<n; j++)
            printf(" %c ", s[j][vet[j]]);
        printf("\n");
        return;
    }

    if(s[i][0]!='\0') {
        vet[i]=0;
        calcio(i+1, vet, s, n);
    }

    if(s[i][1]!='\0') {
        vet[i]=1;
        calcio(i+1, vet, s, n);
    }


    if(s[i][2]!='\0') {
        vet[i]=2;
        calcio(i+1, vet, s, n);
    }

}
Il problema consiste nel fatto che se provate a eseguirlo con dei dati di prova (ad esempio:
1
12
1X
X
2
1X2
Vengono generate molte più combinazioni di quelle possibili, e in quelle di troppo uno o più valori assumono valore casuale (quindi non 1 2 o x).

Quindi credo che devo aggiungere altre condizioni per far proseguire la ricorsione, ma non capisco quali, avendo già messo che non si può procedere se si sono già elaborati tutti i caratteri di una della stringa in input.

3 Risposte

  • Re: Problema backtracking

    
    void expand(FILE* d,char* b,int idline)
    {
        if (*b == '\n' || *b == '\0') return;
        if (b[2] == '1' || b[2] == 'X' || b[2] == '2')
            fprintf(d,"%d)%c%c%c\n",idline,b[0],b[1],b[2]);
    
        //espansione doppie
        char* ib;
        for (ib = b + 1; *ib != '\n' && *ib != '\0' ;ib++)
        {
            fprintf(d,"%d)%c%c\n",idline,*b,*ib);
        }
    
        expand(d,b+1,idline);
    
        fprintf(d,"%d)%c\n",idline,*b);
    }
    
    int main()
    {
        FILE* s = fopen("schedina.txt","r");
            if (s == NULL) return -1;
    
        FILE* d = fopen("expand.txt","w");
            if (d == NULL) return -1;
    
        char buffer[80];
        int idline = 0;
        while ( fgets(buffer,80,s) != NULL)
            expand(d,buffer,idline++);
    
        fclose(s);
        fclose(d);
    
        return 0;
    }
    
    vedi te se ti può aiutare
  • Re: Problema backtracking

    Ciao,
    il problema alla fine era che dovevo mettere degli else return; dopo ogni if del passo ricorsivo (dove controllo se sono arrivato al carattere di terminazione), altrimenti mi andava a leggere anche le celle successive, che ovviamente non contenevano '\0' ma neanche uno dei caratteri validi, e quindi effettuava la ricorsione ma alla fine stampava quei caratteri casuali.

    Quanto al tuo codice, ora lo proverò, ma in ogni caso non fa al caso mio perché scopo dell'esercizio era proprio usare il backtracking, a prescindere dal fatto che si potessero usare altri metodi, e nel tuo codice non mi pare di vederlo.

    Grazie comunque per aver risposto.
  • Re: Problema backtracking

    A no non c'è(non era nemmeno esplicitamente scritto nel tuo esercizio) come manca " il contenuto del file in un’opportuna struttura dati interna".
    Con questo problema è poco istruttivo fare il suddetto esercizio con quelle regole,anche il mio a dire il vero è abbastanza pessimo,usare la ricorsione per cosi poco.....
    diciamo che voleva essere piu che altro una pacca sulla spalla per incoraggiarti....
Devi accedere o registrarti per scrivere nel forum
3 risposte