Pagina 1 di 1

[Algoritmi, C] Funzione ricorsiva per verifica di sottoinsiemi

MessaggioInviato: 12/07/2019, 17:57
da universo
Nell'ultima traccia d'esame si richiedeva di scrivere una funzione ricorsiva che verificasse se un insieme è un sottoinsieme dell'altro.Tra le varie richieste vi era quella di scrivere una funzione int app(char c, Set *A) che restituisse 1 se A è sottoinsieme di B, 0 altrimenti. Il prototipo era fissato come:
Codice:
int sub(Set *A, Set *B);

e la struttura Set, che rappresenta insiemi di soli caratteri, andava definita come segue:
Codice:
struct Set
{
    char *p
    int n;
}

dove p è il puntatore ai caratteri (non è stato imposto di usare stringhe o array di caratteri) ed n rappresenta la cardinalità dell'insieme. Un altro cavillo riguarda i caratteri ASCII non stampabili: andrebbero inclusi o scartati? Io seguendo la filosofia KISS (Keep It Simple Stupid) ho ignorato la questione, ossia "ogni carattere è valido". Un insieme vuoto è così definito:
Codice:
Set empty = {NULL, 0};

dunque se p = NULL allora l'insieme è vuoto.
Su prototipi e tipi di variabile non c'era possibilità di scelta, anche se per esempio un unsigned long per la cardinalità sarebbe stato meglio.
Per la funzione ricorsiva int sub(Set *A, Set *B) è richiesto l'uso della funzione app. In questo caso non saprei come implementare ricorsivamente la funzione:
Codice:
//non si esclude A = B
int sub(Set *A, Set *B)
{
    //soliti controlli sui parametri

    //se un elemento di A non appartiene a B, A non e' sottoinsieme di B
    if(condizione con chiamata ad app)
    {
        return 0;
    }
    else
    {
        //chiamata a sub
    }
}

L'idea sarebbe questa, di più non sono riuscito a fare per questa funzione infatti l'ho scritta in versione iterativa durante la prova.
Modifica: corretto il prototipo della funzione app.

Re: [Algoritmi, C] Funzione ricorsiva per verifica di sottoinsiemi

MessaggioInviato: 13/07/2019, 08:53
da caulacau
Una funzione che controlla se una lista è sottolista di un'altra è questa:
Codice:
sublist :: Eq a => [a] -> [a] -> Maybe Ordering
sublist xs ys
  | xs == ys          = Just EQ
  | xs `isInfixOf` ys = Just LT
  | ys `isInfixOf` xs = Just GT
  | otherwise         = Nothing


isPrefixOf              :: (Eq a) => [a] -> [a] -> Bool
isPrefixOf [] _         =  True
isPrefixOf _  []        =  False
isPrefixOf (x:xs) (y:ys)=  x == y && isPrefixOf xs ys

isInfixOf               :: (Eq a) => [a] -> [a] -> Bool
isInfixOf needle haystack = any (isPrefixOf needle) (tails haystack)

Il linguaggio è diverso, ma questa è ricorsiva.

(PS: tails è la funzione che prende una lista \((x_1,x_2, \dots)\) e ritorna \((x_1, (x_1, x_2), (x_1,x_2,x_3),\dots)\)).

Re: [Algoritmi, C] Funzione ricorsiva per verifica di sottoinsiemi

MessaggioInviato: 13/07/2019, 14:15
da apatriarca
@caulacau, non sono sicuro che proporre una soluzione in Haskell (o in un linguaggio molto simile) sia utile per una persona che stia imparando a programmare in C. Le funzioni ricorsive hanno caratteristiche molto diverse in C e in Haskell e il migliore approccio in Haskell è raramente il miglior approccio in C. L'insieme sembra inoltre essere semplicemente una stringa di lunghezza fissata, cioè un array di caratteri e non una lista concatenata (qualcosa come una ByteString in Haskell). Infine il codice che hai postato mi sembra calcolare se una lista è una sottolista di un'altra, ma in questo caso si cerca di sapere se un insieme è un sottoinsieme di un altro.

@universo, alcune osservazioni:
1. Per un insieme di caratteri un unsigned long sarebbe stato completamente inutile. Ricordati infatti che rappresentano degli insiemi e quindi dovrebbe esserci al più una copia di ogni valore. Ci sono solo 256 valori char possibili.. e questa è quindi la massima dimensione possibile del tuo insieme. Ovviamente non c'è alcuna garanzia che questa proprietà sia rispettata (al contrario di altri tipi di rappresentazione), ma non è importante in questo caso.
2. Il post è un po' confuso, ma credo tu voglia implementare una funzione con prototipo
Codice:
int app(char c, Set* A);

che verifica se l'elemento c è incluso nell'insieme A e una seconda funzione con prototipo
Codice:
int sub(Set *A, Set *B);

che verifica se A è sottoinsieme di B. La prima funzione è più o meno equivalente a
Codice:
A.p != NULL && memchr(A.p, c, A.n) != NULL

ma suppongo tu non possa fare uso di funzioni standard in questo modo. Hai comunque semplicemente un array di caratteri di un certo numero di elementi e puoi quindi semplicemente iterare su di esso fino a trovare l'elemento cercato. Qualcosa come segue:
Codice:
int app(char c, Set* A)
{
    if (A.p == NULL) { return 0; }

    for (int i = 0; i < A.n; ++i) {
        if (A.p[i] == c) { return 1; }
    }
    return 0;
}

Un discorso simile vale per l'altra funzione. Devi iterare su tutti gli elementi del tuo insieme A e verificare se questo elemento è incluso in B usando la funzione precedente. Se non lo è allora restituisci 0, altrimenti continui. Se tutti gli elementi appartengono a [tt]B[/bb] puoi allora restituire 1.

Re: [Algoritmi, C] Funzione ricorsiva per verifica di sottoinsiemi

MessaggioInviato: 14/07/2019, 10:33
da universo
La funzione app è già implementata, mi manca solo sub che però va realizzata ricorsivamente, non è ammessa la versione iterativa che è molto semplice. La mia difficoltà è su questo punto, sul resto non ci sono problemi di sorta.
Un unsigned long per la cardinalità è comunque opportuno perché poi bisogna fare delle operazioni che coinvolgono malloc(unsigned long). Il fatto elementare per cui ci sono solo 256 caratteri ASCII mi ha fatto venire in mente la possibilità di usare una tabella di ricerca per implementare l'insieme, non so perché non ci ho pensato durante la prova! :( Sarebbe stata una soluzione semplice ed elegante. Grazie per i suggerimenti.

Re: [Algoritmi, C] Funzione ricorsiva per verifica di sottoinsiemi

MessaggioInviato: 14/07/2019, 14:56
da apatriarca
La funzione ricorsiva potrebbe essere qualcosa come segue:
Codice:
int app(char c, Set* A)
{
    // Condizione di uscita dalla ricorsione con Set vuoto
    if (A == NULL || A.p == NULL || A.n == 0) { return 0; }

    // Uscita dalla ricorsione per aver trovato il valore
    if (c == A.p[0]) { return 1; }

    // "Costruisce" un nuovo Set con un elemento in meno e richiama la funzione ricorsivamente
    Set B = {A.p + 1, A.n - 1};
    return app(c, &B);
}


Pensavo che la struttura Set non potesse essere cambiata.. Per cui come avresti implementato la tabella?

Re: [Algoritmi, C] Funzione ricorsiva per verifica di sottoinsiemi

MessaggioInviato: 16/07/2019, 20:29
da universo
Come già detto la funzione app è già stata implementata, mi resta da implementare per ricorsione la funzione sub(Set *A, Set *B).
La struttura Set non può essere modificata, però nessuno vieta di usare l'array come se fosse un vettore di booleani di modo che, se viene inserito il carattere 'A', il programma salvi il valore 1 nella posizione 'A' (credo sia il 65esimo carattere del codice ASCII) così si evita l'uso di realloc e non si rende più necessario effettuare un controllo per vedere se l'elemento esiste già (al limite si assegna un valore già assegnato, ma è sempre meglio di un if ). In più, per implementare le operazioni di intersezione ed unione, basta usare gli operatori bitwise & e | . Un tempo me la cavavo con il C ed i suoi trucchetti, ora si vede che le idee interessanti tardano ad arrivare.

Re: [Algoritmi, C] Funzione ricorsiva per verifica di sottoinsiemi

MessaggioInviato: 16/07/2019, 20:35
da apatriarca
L'idea è sempre la stessa anche per sub..
Codice:
int sub(Set* A, Set* B)
{
    // Condizione di uscita dalla ricorsione con Set vuoto
    if (A == NULL || A.p == NULL || A.n == 0) { return 1; }

    // Verifica se A.p[0] è incluso in B, se non lo è esci dalla ricorsione..
    if (app(A.p[0], B)) { return 0; }

    // "Costruisce" un nuovo Set con un elemento in meno e richiama la funzione ricorsivamente
    Set A2 = {A.p + 1, A.n - 1};
    return sub(&A2, B);
}

Re: [Algoritmi, C] Funzione ricorsiva per verifica di sottoinsiemi

MessaggioInviato: 17/07/2019, 10:06
da universo
Grazie per l'input, l'ho implementata così:
Codice:
//verifica se A e' un sottoinsieme di B
int sub(Set *A, Set *B)
{
    assert(NULL != A && NULL != B);
   
    if(NULL == A->p || 0 == A->n)
    {
        return 1;
    }
   
    if(0 == app(*(A->p), B))
    {
        return 0;
    }
   
    Set C = {A->p + 1, A->n - 1};//questo era il nodo da sciogliere per me
    return sub(&C, B);
}