RISOLTO [C] Problema su esercizio ricorsione

ilfe98 · 3 Giugno 2019

Salve ragazzi, ormai sono andato nel pallone. Non riesco a capire dove sto sbagliando, sapreste aiutarmi?
La traccia dell''esercizio è questa:

Nel file sottogruppi.c definire la funzione corrispondente alla seguente dichiarazione:

extern int Sottogruppi(const char *filename, int k);

La funzione prende in input il nome di un file di testo (filename) e un intero k. Il file
contenente i nomi degli alunni di una classe separati da \n. Il file contiene in totale n
nomi (senza spazi) i quali sono costituiti al massimo da 19 caratteri. Il numero n non è
noto a priori, ma si deve determinare leggendo il file. La funzione deve aprire il file e
leggerne il contenuto e, utilizzando un algoritmo di backtracking ricorsivo, individuare
tutti i possibili sottogruppi di K studenti con i seguenti vincoli:

1. due nomi che iniziano con la stessa lettera non devono mai appartenere allo stesso
sottogruppo. Esempio: Andrea e Aldo hanno la stessa iniziale “A”, quindi non possono
appartenere allo stesso sottogruppo.
2. due nomi con iniziali consecutive non devono mai appartenere allo stesso gruppo.
Esempio: Bianca e Alfredo hanno iniziali consecutive nell’alfabeto, quindi non possono
mai appartenere allo stesso sottogruppo.
3. l’ordine è significativo. Esempio (k = 2) i gruppi { Andrea, Carlo } e { Carlo, Andrea }
sono da considerarsi gruppi distinti e quindi dovrebbero comparire entrambi nella soluzione.

La funzione deve stampare su standard output tutti i possibili sottogruppi, uno per riga con
il seguente formato:

{ Nome1, Nome2, …, NomeK }

La funzione deve quindi ritornare il numero di soluzioni trovate. Se non è possibile aprire il
file o se il valore k in input è minore o uguale a 0 o maggiore di n la funzione deve ritornare -1.

Si consiglia di utilizzare una funzione ausiliaria per implementare il backtracking. Si consiglia
inoltre di leggere i dati da file fuori dalla funzione ricorsiva.

Esempio:
File es5_input1.txt
Anna
Giovanni
Francesco
Giorgio
Bianca

Con k = 2, l’output dovrebbe essere:

{ Anna, Giovanni }
{ Anna, Francesco }
{ Anna, Giorgio }
{ Giovanni, Anna }
{ Giovanni, Bianca }
{ Francesco, Anna }
{ Francesco, Bianca }
{ Giorgio, Anna }
{ Giorgio, Bianca }
{ Bianca, Giovanni }
{ Bianca, Francesco }

Mentre ecco il mio codice:(So bene che la traccia non chiede quel tipo di input ,ma è per velocizzare le cose)

Codice:

#define _CRT_SECURE_NO_WARNINGS
struct studente
{
    char nome[19];

};
typedef struct studente n_stud;
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
void ricorsione(n_stud *v, int k, int s, int n, bool* presi, int prof) {
    int cont = 0;
    if (s == k || prof==n)
    {
        for (size_t i = 0; i < n; i++)
            if (presi[i] == 1)
                cont++;
        if (cont == k) {
            for (size_t i = 0; i < n; i++)
                if (presi[i] == 1)
                    printf("%s   ", v[i].nome);
            printf("\n");
        }
        return;
    }
    for (size_t i = 0; i < n; i++) {
        if (presi[i] != 1) {
            presi[i] = 1;
            s++;
        }
        for (size_t j = 0; j < n; j++) {
            if (strcmp(v[i].nome, v[j].nome) != 0) {
                presi[j] = 1;
                ricorsione(v, k, s + 1, n, presi, prof + 1);
                presi[j] = 0;
            }
        
                
            ricorsione(v, k, s, n, presi, prof + 1);
        }
        presi[i] = 0;
        s--;
    }
}
 int Sottogruppi(const char* filename, int k) {
    FILE* f = fopen(filename, "rt");
    if (!f)
        return 0;
    n_stud* bo = NULL;
    char tmp[19];
    int cont = 0;
    while (!feof(f)) {
        int t = fscanf(f, "%s", &tmp);
        if (t == 1)
        {
            cont++;

            bo = realloc(bo, cont * sizeof(n_stud));

            strcpy(bo[cont - 1].nome, tmp);
        }
    }
    printf("%d", cont);
    fclose(f);
    bool* p = calloc(cont , sizeof(bool));
ricorsione(bo, k, 0,cont,p,0);
    return 0;
}
int main(void) {

    
    Sottogruppi("input.txt",2);
}

Andretti60 · 3 Giugno 2019

Beh, non hai detto quale sia il problema. Hai errori di compilazione? I risultati non sono quelli che prevedi? Il programma va in crash mentre gira?
Iniziamo con un problema alla volta. Guarda questa definizione, c'e' una grossa svista di allocazione di memoria. La massima lunghezza del nome e' 19 caratteri, ma nel linguaggio C devi anche considerare il carattere di terminazione.

Codice:

struct studente
{
    char nome[19];
};

ilfe98 · 4 Giugno 2019

Andretti60 ha detto:
Beh, non hai detto quale sia il problema. Hai errori di compilazione? I risultati non sono quelli che prevedi? Il programma va in crash mentre gira?
Iniziamo con un problema alla volta. Guarda questa definizione, c'e' una grossa svista di allocazione di memoria. La massima lunghezza del nome e' 19 caratteri, ma nel linguaggio C devi anche considerare il carattere di terminazione.

Codice:

struct studente { char nome[19]; };

Ciao Andretti, si certo mi ricordo del carattere \0, tuttavia quello è l'ultimo dei problemi, il mio codice li ha molti errori considerando anche che cerco in un albero di soluzioni sbagliato rispetto all'insieme che lo delimita, quindi richiamo troppe volte la funzione ricorsivamente, comunque il problema è che non fa ciò che deve, i risultati sono sbagliati
--- i due messaggi sono stati uniti ---

Codice:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<ctype.h>
#include<string.h>

struct studente
{
    char nome[20];

};
typedef struct studente n_stud;

bool verificaini(n_stud* presi, int k) {
    bool ret = true;
    char c1, c2;
    for (size_t i = 0; i < k; i++) {
        c1 = presi[i].nome[0]; 
        for (size_t j = 1; j <= k; j++) {
        c2 = presi[j].nome[0];
            if (isalpha(presi[i].nome[1]) && isalpha(presi[j].nome[1])) {

                

                if (c1 - c2 == 0){
                    ret = false;
                    break;
                }
                if (c1 - c2 == 1 || c1 - c2 == -1) {
                    ret = false;
                    break;
                }
            }
            
        }
    
    }
    return ret;
}
void ricorsione(n_stud * v, int k, int s, int n, n_stud * presi, int prof, int* sol) {
    int cont = 0;
if (s == k || prof == n)
    {
        for (size_t i = 0; i < k; i++)
            if (isalpha(presi[i].nome[0]))
                cont++;
        if (cont == k) {
            *sol = *sol + 1;
            for (size_t i = 0; i < k; i++)
                printf("%s   ", presi[i].nome);
            printf("\n");
        }
        return;
    }
    for (size_t i = 0; i < n; i++) {
        if (!isalpha(presi[s].nome[1])) {
            strcpy(presi[s].nome, v[i].nome);
            s++;
        }
        for (size_t j = 0; j < n; j++) {
            if (strncmp(presi[i].nome,presi[j].nome,1)!=0 && verificaini(presi,s)) {
                strcpy(presi[s].nome, v[j].nome);
                if (verificaini(presi, s)) {
                    ricorsione(v, k, s + 1, n, presi, prof + 1, sol);
                    memset(presi[s].nome, 0, 20 * sizeof(char));
                }
                else
                    memset(presi[s].nome, 0, 20 * sizeof(char));
            }


        }
        memset(presi[s - 1].nome, 0, 20 * sizeof(char));
        s--;
    }
}
int Sottogruppi(const char* filename, int k) {
    if (k <= 0)
    {
        return -1;
    }
    FILE * f = fopen(filename, "rt");
    if (!f)
    {
        fclose(f);
        return -1;
    }
    n_stud * bo = NULL;
    char tmp[20];
    int cont = 0;
    while (!feof(f)) {
        int t = fscanf(f, "%s", &tmp);
        if (t == 1)
        {
            cont++;

            bo = realloc(bo, cont * sizeof(n_stud));

            strcpy(bo[cont - 1].nome, tmp);
        }
    }
    if (cont == 0) {
        fclose(f);
        return 0;
    }
    if (k == 1) {
        fclose(f);
        for (size_t i = 0; i < cont; i++)
            printf("%s \n", bo[i].nome);
        free(bo);
        return cont;
    }
    
    if (k > cont ) {
        fclose(f);
        free(bo);
        return -1;
    }
    int sol = 0;
    fclose(f);
    n_stud * p = calloc(k, sizeof(char));
    ricorsione(bo, k, 0, cont, p, 0, &sol);
  free(p);
  free(bo);

return sol;
}

Per quale ignoto motivo sulle free si pianta il programma?

Andretti60 · 4 Giugno 2019

beh, c'e' questa allocazione sbagliata per cominciare: n_stud * p = calloc(k, sizeof(char));
Dopodiche' nella funzione ricorsione() lo utilizzi come un vettore di lunghezza ben maggiore.
In genere quando la free() si pianta il problema sta in una corruzione di memoria, ossia hai usato il puntatore in maniera sbagliata. Mi stupisco che il programma non si pianti prima.

ilfe98 · 4 Giugno 2019

Andretti60 ha detto:
beh, c'e' questa allocazione sbagliata per cominciare: n_stud * p = calloc(k, sizeof(char));
Dopodiche' nella funzione ricorsione() lo utilizzi come un vettore di lunghezza ben maggiore.
In genere quando la free() si pianta il problema sta in una corruzione di memoria, ossia hai usato il puntatore in maniera sbagliata. Mi stupisco che il programma non si pianti prima.

Per quale motivo è sbagliata l'allocazione?

Inviato da LG-H870 tramite App ufficiale di Tom\'s Hardware Italia Forum

Andretti60 · 4 Giugno 2019

Perche' allochi lo spazio di solo un carattere per un puntatore di tipo n_stud

ilfe98 · 4 Giugno 2019

Andretti60 ha detto:
Perche' allochi lo spazio di solo un carattere per un puntatore di tipo n_stud

Oddio,che obbrobrio,era una cosa idiota, grazie mille

Inviato da LG-H870 tramite App ufficiale di Tom\'s Hardware Italia Forum

Andretti60 · 4 Giugno 2019

Non è una cosa idiota, è un errore da principianti :)

ilfe98 · 4 Giugno 2019

Andretti60 ha detto:
Non è una cosa idiota, è un errore da principianti :)

Beh onestamente è stata una disattenzione, successivamente ho cercato l'errore altrove e debuggando alla cieca la parte dell'allocazione... Non ho di certo anni di esperienza, ma solitamente non faccio questi errori. Ti ringrazio per avermi aiutato a trovare l'errore :)

Inviato da LG-H870 tramite App ufficiale di Tom\'s Hardware Italia Forum

Ibernato · 5 Giugno 2019

ilfe98 ha detto:
Beh onestamente è stata una disattenzione, successivamente ho cercato l'errore altrove e debuggando alla cieca la parte dell'allocazione... Non ho di certo anni di esperienza, ma solitamente non faccio questi errori. Ti ringrazio per avermi aiutato a trovare l'errore :)

Inviato da LG-H870 tramite App ufficiale di Tom\'s Hardware Italia Forum

Bello questo esercizio.
Qui ci sta tutto una bella soluzione in parallelo (non è il tuo caso però).