+ Rispondi al Thread
Visualizzazione dei risultati da 1 a 1 su 1

Discussione: Sequenza BBA

  1. #1
    maxpix non è in linea Novello
    Post
    18

    Sequenza BBA

    Buongiorno a tutti, vorrei essere sicuro se la soluzione che ho pensato per questo esercizio è corretta.

    Scrivere un algoritmo che risolva il seguente problema, utilizzando la tecnica divide-et-impera: dato in input un vettore A[1..n] contenente n lettere dell’alfabeto italiano, determinare quante volte nel vettore compare la sequenza BBA.
    Scrivere poi l’equazione di ricorrenza che esprime il tempo di calcolo di tale algoritmo, e risolverla utilizzando un metodo a piacere.

    codice:
    ContaSequenza(A, i , j) {
    if length(A) == 3 AND A[i] == B AND A[i+1] == B AND A[j] == A
     return 1;
    if length(A) <= 3 AND A[i] != B OR A[i+1] != B OR A[j] != A
     return 0;
    else
     l = i+j/2;
    add = 0;
    if A[l] == B AND A[l+1] == B AND A[l+2] == A OR A[l] == B AND A[l-1] == B AND A[l+1] == A 
     add = 1; //Mi assicuro che "spezzando" non perdo una sequenza. E' meglio fare due if separati?
    a = ContaSequenza(A, i, l);
    b = ContaSequenza(A, l+1, j);
    return(a+b+add);
    per l'equazione di ricorrenza avevo pensato di fare cosi:

    T(n) = {Teta(1) per n<=3
    {2T(n/2)+Teta(1) per n>3

    da cui segue che

    f(n) = teta(1)

    teta(1) = nlogba = n;

    quindi T(n) = Teta(n). Giusto?

    Grazie in anticipo
    Ultima modifica di maxpix; 06-06-2014 11:34 

+ Rispondi al Thread

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi