«

»

feb 09

Contare le coppie adiacenti in una sequenza in tempo nLog(n)

Contare le coppie adiacenti in una sequenza in tempo nLog(n) (Appello Settembre 2010)

il testo recita:

Sia data una sequenza di interi a1 , a2 , . . . , an . Diciamo che la sequenza contiene una coppia di numeri consecutivi se esistono due interi ai e aj tali che ai = aj + 1. Implementare un algoritmo per contare il numero di coppie consecutive contenute nella sequenza, che impieghi una complessità di tempo complessiva di n log n e una quantità di memoria aggiuntiva di O(n).

Implementazione attraverso un albero binario

Il problema può essere risolto implementando una treesort e facendo in modo che in fase di inserimento si verifichi l’esistenza delle coppie adiacenti

#define N 10
#include "util.h"
#include "strutture.h"
#include <string.h>  // NULL è definito qui

int piazza(nodo *base, nodo *nodo, int coppie){
    int x=nodo->val-base->val;
    if(x==1 || x==-1){//ho trovato una coppia
        coppie++;
        printf("coppia %d <-> %d (%d) \n",nodo->val,base->val, coppie);
    }
    if(x>0){//maggiore, vado a destra
        if(base->r==NULL){//è vuoto, lo piazzo
            base->r=nodo;
        }else{//non è vuoto, richiamo
            coppie=piazza(base->r, nodo, coppie);
        }
    }else{//è minore, vado a sinistra
        if(base->l==NULL){//è vuoto, lo piazzo
            base->l=nodo;
        }else{//non è vuoto, richiamo
            coppie=piazza(base->l, nodo, coppie);
        }
    }
    return coppie;
}

void trovacoppie(int len, int v[len])
{
    int coppie=0,n;
    nodo *nodi=malloc(sizeof(nodo)*len);

    for(n=0; n<len; n++)
    {
        nodi[n].val=v[n];
        nodi[n].l=NULL;
        nodi[n].r=NULL;
        if(n>0)coppie=piazza(nodi, &nodi[n], coppie);
    }
    free(nodi);
    printf("Un totale di %d coppie trovate\n", coppie);
}

Il contatore delle coppie viene passato a ogni chiamata ricorsiva e viene ritornato in output dalla funzione di ordinamento, in questo modo l’output finale conterrà il conto totale, questo approccio ha complessità O(n*log(n)) , non possono esistere soluzioni con un ordine di complessità minore inquanto non esistono ordinamenti più veloci essendo n*log(n) la dimensione dell’albero generato dalle decisioni necessarie per un ordinamento.
L’albero viene allocato dentro un vettore per facilitarne la deallocazione.

Share Button