RISOLTO [C] Problema su esercizio ricorsione

ilfe98

Moderatore
Staff Forum
Utente Èlite
2,432
944
CPU
Intel i7 7700K
Dissipatore
Bequiet Dark rock pro 4
Scheda Madre
Msi pc mate z270
HDD
Seagate barracuda 1tb, silicon power NVME 500gb
RAM
Patriot viper steel 3733Mhz
GPU
Inno 3d gtx 1080 herculez design
Monitor
Asus mg279q
PSU
Corsair HX750
Case
Itek lunar 23
Net
Tiscali ftth
OS
windows 10,mint,debian,Arch linux
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);
}
 
Ultima modifica:

Andretti60

Utente Èlite
5,214
3,797
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

Moderatore
Staff Forum
Utente Èlite
2,432
944
CPU
Intel i7 7700K
Dissipatore
Bequiet Dark rock pro 4
Scheda Madre
Msi pc mate z270
HDD
Seagate barracuda 1tb, silicon power NVME 500gb
RAM
Patriot viper steel 3733Mhz
GPU
Inno 3d gtx 1080 herculez design
Monitor
Asus mg279q
PSU
Corsair HX750
Case
Itek lunar 23
Net
Tiscali ftth
OS
windows 10,mint,debian,Arch linux
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
Post automatically merged:

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?
 
Ultima modifica:

Andretti60

Utente Èlite
5,214
3,797
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

Moderatore
Staff Forum
Utente Èlite
2,432
944
CPU
Intel i7 7700K
Dissipatore
Bequiet Dark rock pro 4
Scheda Madre
Msi pc mate z270
HDD
Seagate barracuda 1tb, silicon power NVME 500gb
RAM
Patriot viper steel 3733Mhz
GPU
Inno 3d gtx 1080 herculez design
Monitor
Asus mg279q
PSU
Corsair HX750
Case
Itek lunar 23
Net
Tiscali ftth
OS
windows 10,mint,debian,Arch linux
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
 

ilfe98

Moderatore
Staff Forum
Utente Èlite
2,432
944
CPU
Intel i7 7700K
Dissipatore
Bequiet Dark rock pro 4
Scheda Madre
Msi pc mate z270
HDD
Seagate barracuda 1tb, silicon power NVME 500gb
RAM
Patriot viper steel 3733Mhz
GPU
Inno 3d gtx 1080 herculez design
Monitor
Asus mg279q
PSU
Corsair HX750
Case
Itek lunar 23
Net
Tiscali ftth
OS
windows 10,mint,debian,Arch linux

ilfe98

Moderatore
Staff Forum
Utente Èlite
2,432
944
CPU
Intel i7 7700K
Dissipatore
Bequiet Dark rock pro 4
Scheda Madre
Msi pc mate z270
HDD
Seagate barracuda 1tb, silicon power NVME 500gb
RAM
Patriot viper steel 3733Mhz
GPU
Inno 3d gtx 1080 herculez design
Monitor
Asus mg279q
PSU
Corsair HX750
Case
Itek lunar 23
Net
Tiscali ftth
OS
windows 10,mint,debian,Arch linux
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

Utente Èlite
4,139
1,904
OS
Windows 10 Pro
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ò).
 

Entra

oppure Accedi utilizzando

Discussioni Simili