- 3,052
- 1,278
- 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:
Mentre ecco il mio codice:(So bene che la traccia non chiede quel tipo di input ,ma è per velocizzare le cose)
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 }
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 }
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: