Algoritmo per massima sequenza valori uguali

di
Luly
il
4 risposte
L
Luly
Pochi posts
Iscritto da
giu, 2015
Messaggi:
3

Algoritmo per massima sequenza valori uguali

Salve a tutti,
ho un piccolo problema con un esercizio Java, o forse sono io che penso a chissà quale algoritmo. Il problema chiede ciò: dato in ingresso un array di interi positivi, il metodo dovrà stampare la lunghezza e la posizione della più lunga sequenza contigua di valori uguali.
Un esempio, per V=[1,2,3,3,3,3,5,6,7,7,7] il metodo dovrà stampare: 4,2.

Ora, ho pensato a diverse soluzioni ma non sono arrivata ad una conclusione ferma.
Il problema che non riesco a risolvere secondo me è che ogni volta che vengono trovati elementi uguali, io mi devo memorizzare quel contatore (se così vogliamo chiamarlo) e confrontarlo poi con il contatore dei prossimi elementi uguali e verificare infine quale all’interno dello stesso array è maggiore.
Qualcuno che mi aiuti o che mi dia qualche dritta?
Grazie in anticipo.

4 Risposte

  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6284

    Re: Algoritmo per massima sequenza valori uguali

    Luly ha scritto:

    Qualcuno che mi aiuti o che mi dia qualche dritta?
    Si può fare sicuramente in diversi modi. Non credo la soluzione sia unica e basta.
    Quella che mi viene in mente adesso è questa: ad ogni cambio di numero, es. da quel 2 al primo 3, fai un ciclo annidato che conta quanti 3 ci sono (vai avanti fino a quando o trovi diverso da 3 O l'array è terminato). Se il contatore di questi è maggiore del contatore "max" che devi esserti tenuto ovviamente da qualche parte, allora aggiorni posizione/lunghezza "max".
    Quindi continui con la prossima sequenza (in pratica salti dall'inizio di una sequenza all'inizio di un'altra).

    Chiaramente dovrei provare io a scrivere il codice per verificare se è sensato. Ma in linea di massima credo di sì.
  • L
    Luly
    Pochi posts
    Iscritto da
    giu, 2015
    Messaggi:
    3

    Re: Algoritmo per massima sequenza valori uguali

    Grazie per il suggerimento e scusa il ritardo! Ho provato a prendere spunto e ho elaborato il tutto. Sembra funzioni, ma penso possa essere migliorato! Sono alle prime armi quindi se c'è qualcosa di sbagliato o migliorabile dimmi pure! (per il momento ho solo trovato la massima sequenza che era quello che mi interessava).



    public static int trovaSequenza (int[]v) {
    int cont=1;
    int max=0;

    for (int i=0; i<v.length;i++){
    if (v==v[i+1]){ //se trovo elementi uguali entro in un ciclo annidato
    cont=1; //ridefinisco la variabile cont, affinchè ad ogni controllo torni ad 1
    for (int k=i; v[k]==v[i+1] && k<v.length-1;k++){ //faccio iniziare il ciclo da i, ossia dall'elemento che ho confrontato con il suo successivo (quando esso è uguale al successivo)
    if(v[k]==v[k+1])
    cont++;
    }
    if (cont>max){ //a fine ciclo, se cont è maggiore di max, viene aggiornata la variabile cont affinchè essa possa essere confrontata con una nuova eventuale sequenza di numeri uguali
    max=cont;
    i=cont+1; //l'indice di i ora deve "bypassare" gli elementi uguali già controllati
    }
    else if (cont<max)
    break;
    }
    }
    return max;
  • andbin
    andbin
    Super Famoso
    Iscritto da
    ott, 2013
    Messaggi:
    6284

    Re: Algoritmo per massima sequenza valori uguali

    Luly ha scritto:

    Sembra funzioni, ma penso possa essere migliorato!
    Non solo può essere parecchio migliorato (è un pochino contorto e ti assicuro che è possibile farlo in modo molto più semplice e lineare) ma non è nemmeno corretto al 100%. Sicuramente è errato almeno in un caso, quando l'array ha solo 1 valore e quindi con i=0 il v[i+1] non è valido.
  • L
    Luly
    Pochi posts
    Iscritto da
    giu, 2015
    Messaggi:
    3

    Re: Algoritmo per massima sequenza valori uguali

    Sul fatto che fosse contorto non avevo dubbi! Il fatto è che io penso sempre a soluzioni assurde e complesse e quindi questo si riversa anche nella risoluzione di un algoritmo.
    Per ovviare al problema che tu dici, potrei crearmi un'eccezione all'inizio o un segnale affinchè l'array (immesso da input) non sia composto da un solo elemento. Diciamo che su questo aspetto ho sorvolato perchè questo esercizio mi serviva soprattutto per testare veramente le mie capacità nella risoluzione di questo problema.

    Se comunque qualcuno sarebbe così gentile da migliorare questo codice e renderlo più semplice mi aiuterebbe tantissimo!
    Grazie ancora per i suggerimenti!
Devi accedere o registrarti per scrivere nel forum
4 risposte