Dubbio su metodo

[dennis87]

Devo scrivere un metodo che, data una lista v di n numeri interi, la funzione maxPrimo applicata a v restituisce il valore del piu grande elemento della lista che non è multiplo proprio di nessun altro elemento della lista.

La mia idea di sviluppo è questa: mi prendo in ingresso una vettore di numeri interi, fra questi elementi salvo in un vettore gli elementi che non sono multipli di nessun altro elemento della lista tranne che di se stessi, fra questi elementi prendo il piu grande e lo restituisco.

Ho provato a scrivere la prima parte del codice, cioè fino ad avere il vettore degli elementi che non multipli di altri elementi tranne se stessi, ma ho incontrato problemi.

int[] maxPrimo(int[] v){
	//int max=0;
	int[] vettore = new int[v.length];
	boolean multiplo;
	for(int i=0;i<v.length;i++){
		multiplo=true;
		for(int j=0;j<v.length;j++){
			if(v[j]!=v[i]&&v[i]%v[j]==0)	
				multiplo=false;
			if(multiplo)
				vettore[i]=v[i];
		}
	}
        return vettore;
}

In pratica mi dichiaro un vettore della stessa lunghezza di v che conterrà gli elementi che ecc ecc..., poi ad ogni elemento indicato da i, faccio scorrere la variabile j, facendo ogni volta il controllo if(v[j]!=v[i]&&v[i]%v[j]==0). Dopo di che dico che se non è multiplo allora metto l'elemento dentro al vettore...ma non funziona...
In pratica se gli passo il vettore int[] v = {6,7,21,5,16,14,18,11,20,15,13};, in teoria mi dovrebbe restituire il vettore {6,7,5,16,11,13} ed eventualmente zeri nelle posizioni rimaste libere, ma invece mi rende il vettore {6,7,21,5,16,14,0,11,20,15,13}
Mi potreste aiutare a capire per favore?

[Andrea1979]

ok, siccome sembra un po' un esercizio, lo facciamo in modo "didattico"... allora, personalmente comincerei con l'ordinare il vettore (in ordine crescente o decrescente come ti pare) e poi comincerei dall'elemento più grande (che diventa il nostro pivot)
In maniera "furba", puoi controllare solo gli elementi pari o minori della metà del tuo pivot. Se trovi un sottomultiplo, scarti quel pivot e prendi come nuovo pivot l'elemento appena più piccolo e ripeti.
Ci sono anche altre piccole ottimizzazioni che potresti voler fare (sempre per tenere la cosa didattica): per esempio, se il tuo pivot è dispari allora è totalmente inutile testare gli elementi pari.

[dennis87]

ma non posso fare che per ogni elemento indicato da i, j mi scorre tutto il resto del vettore alla ricerca di elementi che sono sottomultipli dell'elemento indicato da i? e se vengono trovati allora l'elemento indicato da i viene scsartato e i viene incrementato, altrimenti l'elemento indicato da i entrerà a far parte del vettore degli elementi che non hanno sottomultipli...

[Andrea1979]

certo che puoi, ma a te serve solo l'elemento più grande che non sia multiplo di alcuno degli altri elementi, quindi a te non serve un vettore di elementi che non siano multipli, ma solo 1 elemento. In sostanza, come vuoi fare tu è un tot di extra-lavoro inutile.

[dennis87]

si...non basterebbe aggiungere un controllo in piu nell'if, e invece di restituire il vettore restituire la variabile che contiene l'elemento piu grande non sottomultiplo?

[dennis87]

Originariamente inviato da dennis87
si...non basterebbe aggiungere un controllo in piu nell'if, e invece di restituire il vettore restituire la variabile che contiene l'elemento piu grande non sottomultiplo?

EDIT:
Non potrei anche fare la ricerca del piu grande elemento all'interno del vettore e vedere se questo ha sottomultipli?

[Andrea1979]

sì, ma se poi quell'elemento ha sottomultipli, devi cercare quello immediatamente più piccolo, e poi di nuovo etc etc...

[dennis87]

allora non capisco come posso fare

Mi ordino il vettore in maniera decrescente cosi:

ùint[] maxPrimo(int[] v){
	int temp=0;
	int[] vettore = new int[v.length];
	//boolean multiplo;
	for(int i=0;i<v.length;i++){
		for(int j=0;j<v.length;j++){
			if(v[j]<=v[i]){
				temp=v[j];
				v[j]=v[i];
				v[i]=temp;
			}
		}
	}
}

poi dovrei iniziare dalla prima posizione, che è l'elemento maggiore, e vedere se ha sottomultipli diversi da se stesso?

[Andrea1979]

ho fatto una cosa del genere:

public int maxPrimoRelativo(int[] a) {                
        int index = 0;        
        for (int i = a.length -1; i >= 1; i--) {            
            index = i;
            int divs = 0;
            for (int j = i -1 ; j >= 0 && divs == 0; j--) {                                
                divs += (a[i] % a[j] == 0 ? 1 : 0);                
            }
            if (divs == 0) {
                break;
            }
        }
        return a[index];
    }

dove "a" è ordinato in modo crescente.

Come funziona:
- index è un "cursore" che tiene traccia dell'elemento che sto analizzando
- divs tiene invece traccia del numero di sottomultipli trovati fino a quel momento (ovviamente è inizializzata a zero)
- il ciclo for interno parte da una posizione "in meno" rispetto al ciclo esterno (ovvio - altrimenti troveresti subito un divisore, ossia l'elemento stesso)
- se nel ciclo interno viene trovato un divisore/sottomultiplo, aumento il computo dei sottomultipli.
- l'if verifica se i sottomultipli siano zero, se fosse così, esce dal ciclo esterno e possiamo ritornare l'elemento all'indice in analisi.