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

Sequenza BBA

  1. #1
    maxpix non è in linea Novello
    Post
    18
    Like Inviati  
    0
    Like Ricevuti  
    0
    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.

    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 12:34 

+ Rispondi al messaggio

Potrebbero interessarti anche ...

  1. Sequenza di Numeri
    Da Nemesi nel forum C/C++
    Risposte: 3
    Ultimo Post: 30-06-2014, 19:47
  2. Sequenza dei processi
    Da systemgvp nel forum PHP
    Risposte: 5
    Ultimo Post: 10-04-2014, 15:21
  3. Numeri in sequenza
    Da oilcrovara nel forum Microsoft Excel
    Risposte: 3
    Ultimo Post: 10-12-2012, 19:06
  4. Sequenza di Fibonacci
    Da igor90 nel forum Microsoft Excel
    Risposte: 3
    Ultimo Post: 16-10-2012, 23:33
  5. Indovina la sequenza
    Da Fix nel forum Pausa caffè
    Risposte: 5
    Ultimo Post: 25-08-2010, 23:01