Visualizzazione dei risultati da 1 a 4 su 4
  1. #1

    [java] Algoritmo k-esimo elemento

    Ma questo programma di preciso che fa non lo riesco a sapere è stupida la domanda ma è cosi(Il famoso algoritmo dell'k-esimo elemento)
    Saluti Grazie
    codice:
    /* Il metodo selection dato un array non ordinato "v" e un intero "rank", restituisce il "rank"-esimo minimo, cioe' l'elemento dell'array che occuperebbe la posizione "rank" qualora l'array venisse ordinato. Il problema potrebbe essere risolto ordinando l'array, ma l'algoritmo qui proposto permette di risolvere il problema con una complessita' computazionale attesa inferiore, in quanto il tempo atteso e' O(n) invece dell'O(n log n) necessario a ordinare l'array. L'algoritmo utilizza lo stesso approccio del Quick Sort. Viene chiamato il metodo partiziona, identico a quello utilizzato dal Quick Sort, e in base alla posizione restituita si continua la ricerca del k-esimo elemento su una sola delle due porzioni. L'algoritmo termina nel caso in cui il metodo partiziona restituisca esattamente la posizione k. */ 
    import javax.swing.JOptionPane; 
     public class Selection 
    { 
      public static int selection(int[] v, int rank) 
      { 
        // NON DOVREI MODIFICARE L'ARRAY!!! meglio copiarlo in un altro 
       // array, e restituire l'int con il rank voluto invece di void 
       return quickSelection(v, 0, v.length-1, rank); 
      } 
       public static int quickSelection(int[] v, int from, int to, int rank) 
       { 
     // posiziona correttamente l'elemento con rank richiesto. Si assume che from <= rank <= to  
         if(from>=to) 
          return v[rank]; 
         else 
         { 
           int separazione=partiziona(v, from, to); 
            if(separazione==rank) 
             return v[rank]; 
            else if(separazione > rank) 
            { 
              return quickSelection(v, from, separazione-1, rank); 
             } 
               else 
               { 
                 return quickSelection(v, separazione+1, to, rank); 
             } 
            } 
          } 
            public static int partiziona(int[] v, int from, int to) 
            { 
              // le due righe seguenti realizzano la scelta random del separatore 
              int sceltaSeparatore = (from+to)/2; 
              scambia(v, sceltaSeparatore, from); 
              int separatore = v[from]; 
              int i = from+1; 
              int j = to; 
              while(i<j) 
              { 
               while(i<j && v[i]<=separatore) 
                i++; 
                // ora i indica un valore maggiore di separatore 
                // oppure i e' maggiore di j 
               while(i<j && v[j]>=separatore) 
                 j--; 
                // ora j indica un valore minore di separatore 
                // oppure i e' maggiore di j 
                if(i<j) scambia(v, i, j); 
              } 
                if(v[i]>separatore) 
                  i--; 
                // posiziona correttamente il separatore 
               scambia(v, i, from); 
               return i; 
         } 
           public static void scambia(int[] v, int pos1, int pos2) 
           { 
             int app = v[pos1]; 
             v[pos1] = v[pos2]; 
             v[pos2] = app; 
            } 
              /*public static int[] randomArray() 
                 { 
                   int[] a=new int[26]; 
                   for(int i=0; i<a.length; i++) 
                    a[i] = (int)(Math.random()*100); 
                  return a; 
                 }*/    //Lo messo io come commento per fare una cosa più semplice
                   public static void printlnArray(int[] v) 
                   { 
                     int i; 
                     for(i=0; i<v.length; i++) 
                       System.out.print(" "+v[i]); 
                     System.out.println(); 
                   } 
                     public static void main(String[] args) 
                     { 
                       int[] vettore={1, 30, 55, 2, 0, 66, 34, 100, 10, 12, 13, 11};                     //vettore=randomArray(); 
                       System.out.println("array random:"); printlnArray(vettore); 
                        int x = Integer.parseInt(JOptionPane.showInputDialog("digita il rank      dell'elemento da cercare")); 
                        int elemento = selection(vettore, x); 
                        System.out.println("l'elemento di rank "+x+" e' "+elemento); 
                        System.exit(0); 
                      } 
    }
    Alcune cose già c'erano di commenti prima il programma creare una sequenza random io ho messo dei valori fissi per capire meglio di cosa si trattava ma ugualmente non ci riesco
    Scusate ancora e cosa più importante grazie grazie grazie

  2. #2
    Ragazzi perfavore rispondetevi ho riletto e forse non si capisce se cosi è ditemelo che riscrivo tutto

  3. #3

    problema risolto

    La sequenza era disordinata ed mi sono confuso comunque tu dici la posizione e lui ti restituisce il valore di quella posizione
    Grazie e alla prossima discussione
    Saluti

  4. #4
    Moderatore di Programmazione L'avatar di alka
    Registrato dal
    Oct 2001
    residenza
    Reggio Emilia
    Messaggi
    24,465

    Moderazione

    Originariamente inviato da Federicot
    La sequenza era disordinata ed mi sono confuso comunque tu dici la posizione e lui ti restituisce il valore di quella posizione
    Forse leggendo il commento nel codice che riportava questo

    /* Il metodo selection dato un array non ordinato "v" e un intero "rank", restituisce il "rank"-esimo minimo, cioe' l'elemento dell'array che occuperebbe la posizione "rank" qualora l'array venisse ordinato. Il problema potrebbe essere risolto ordinando l'array, ma l'algoritmo qui proposto permette di risolvere il problema con una complessita' computazionale attesa inferiore, in quanto il tempo atteso e' O(n) invece dell'O(n log n) necessario a ordinare l'array. L'algoritmo utilizza lo stesso approccio del Quick Sort. Viene chiamato il metodo partiziona, identico a quello utilizzato dal Quick Sort, e in base alla posizione restituita si continua la ricerca del k-esimo elemento su una sola delle due porzioni. L'algoritmo termina nel caso in cui il metodo partiziona restituisca esattamente la posizione k. */


    avresti saputo subito a cosa serviva.

    In ogni caso, ripeto per l'ennesima volta, e il numero di tentativi così come la pazienza è in esaurimento, che il forum non è adatto a questo genere di richieste: qui non si compilano programmi altrui per dire cosa fa - o non fa - un pezzo di codice, ma si ragiona sul codice che viene scritto dagli utenti che postano e lo propongono poiché contiene un errore o non funziona correttamente, chiedendo aiuto su come correggerlo.
    MARCO BREVEGLIERI
    Software and Web Developer, Teacher and Consultant

    Home | Blog | Delphi Podcast | Twitch | Altro...

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2025 vBulletin Solutions, Inc. All rights reserved.