View Full Version : Mi suggerite l'algoritmo? [Java]
Ciao a tutti. Sto scrivendo un programmino che memorizza in array una sequenza di numeri che vengono digitati dall'utente e successivamente devono essere stampati in ordine cardinale.
La grandezza dell'array viene definita dall'utente stesso all'inizio del programma...
Io fino ad ora ho scritto questo che serve a memorizzare nell'array i numeri digitati:
//lettura
for (pos = 1; pos < numeri.length; pos++) {
int numero = in.readInt("Numero? ");
numeri[pos] = numero;
}
ma nel passaggio successivo non riesco a metterli in ordine!
per quanto riguarda la stampa a video ho semplicemente scritto questo:
//scrittura
for ( pos = 1; pos < numeri.length; pos++){
out.println(numeri[pos]);
}
quello che ho provato a fare è questo, ma evidentemente non funziona :mbe:
for (pos = 1; pos < numeri.length; pos++) {
if (numeri[pos] > numeri[pos++])
numeri[pos] = numeri[pos++];
}
grazie :D
tacchinox
29-12-2011, 22:55
Fatti un vettore copia e riempilo gia ordinato, che e' piu facile.
Comunque sono due for annidati, uno per riempire il vettore e uno per fare la scansione dei numeri inseriti dall'utente e scegliere quello con l'ordine giusto.
Poi per ottimizzarlo ci sono tanti modi.
for (pos = 1; pos < numeri.length; pos++) {
if (numeri[pos] > numeri[pos++])
numeri[pos] = numeri[pos++];
}
Si è completamente sbagliato,..
Comunque ricorda che:
- Quando scrivi pos++, la variabile pos viene incrementata!
quindi nella riga sotto quel pos è equivalente a "pos + 1";
- scrivendo numeri[pos] = numeri[pos++]; stai sovrascrivendo il valore
contenuto in numeri[pos], e quest'ultimo che fai? lo perdi?
Ciao :)
Per ordinare un vettore puoi usare uno dei tanti algoritmi esistenti.
Ovviamente ognuno ha la sua complessità temporale che tipicamente varia tra O(n^2) e O(nLog(n)), esistono alcuni ordinamenti O(n) ma si possono usare solo in casi particolari. La complessità temporare da indicazione del tempo che impiega a ordinare: per ordinare 1000 valori un algoritmo O(n) impiega 1000 unità di tempo, un algoritmo O(n^2) impiega 1000000 unità di tempo. Lavorando con grandi quantitativi di dati questo si sente molto.
Un algoritmo molto semplice è quello descritto da tacchinox, che prevede la selezione del più basso dal vettore e la copia in un nuovo vettore, e ha complessità O(n^2).
Un altro algoritmo semplice potrebbe essere il selection sort, che non necessita di un altro vettore. Divide il vettore di partenza in una parte ordinata e una non ordinata e ad ogni ciclo sostituisce il primo valore della parte non ordinata con il valore più basso della stessa. Per esempio:
6 2 5 1 7 9 3
inizialmente tutto il vettore costituisce la parte non ordinata, la prima mossa è trovare il valore inferiore e metterlo al primo posto della sequenza non ordinata (inverto 1 con 6):
1 2 5 6 7 9 3
In verde è la sequenza ordinata. Ora cerco il minore tra i non ordinati: è 2 e si trova già al primo posto della parte non ordinata, quindi non faccio niente
1 2 5 6 7 9 3
Continuando trovo 3 e lo sostituisco con il 5
1 2 3 6 7 9 5
5 con il 6
1 2 3 5 7 9 6
e via dicendo...
Ci sono algoritmi ben più raffinati e prestanti ma richiedono più attenzione (merge sort, quicksort...) su wikipedia ne trovi molti, con anche del pseudocodice se vuoi implementarli http://it.wikipedia.org/wiki/Categoria:Algoritmi_di_ordinamento
ps: fai attenzione anche a quello che ha scritto Dan___88: è un errore comune copiare un valore al posto di uno già esistente senza tenersi una copia di quello che c'era prima (perdi il dato)
Per ordinare un vettore puoi usare uno dei tanti algoritmi esistenti.
Ovviamente ognuno ha la sua complessità temporale che tipicamente varia tra O(n^2) e O(nLog(n)), esistono alcuni ordinamenti O(n) ma si possono usare solo in casi particolari. La complessità temporare da indicazione del tempo che impiega a ordinare: per ordinare 1000 valori un algoritmo O(n) impiega 1000 unità di tempo, un algoritmo O(n^2) impiega 1000000 unità di tempo. Lavorando con grandi quantitativi di dati questo si sente molto.
Un algoritmo molto semplice è quello descritto da tacchinox, che prevede la selezione del più basso dal vettore e la copia in un nuovo vettore, e ha complessità O(n^2).
Un altro algoritmo semplice potrebbe essere il selection sort, che non necessita di un altro vettore. Divide il vettore di partenza in una parte ordinata e una non ordinata e ad ogni ciclo sostituisce il primo valore della parte non ordinata con il valore più basso della stessa. Per esempio:
6 2 5 1 7 9 3
inizialmente tutto il vettore costituisce la parte non ordinata, la prima mossa è trovare il valore inferiore e metterlo al primo posto della sequenza non ordinata (inverto 1 con 6):
1 2 5 6 7 9 3
In verde è la sequenza ordinata. Ora cerco il minore tra i non ordinati: è 2 e si trova già al primo posto della parte non ordinata, quindi non faccio niente
1 2 5 6 7 9 3
Continuando trovo 3 e lo sostituisco con il 5
1 2 3 6 7 9 5
5 con il 6
1 2 3 5 7 9 6
e via dicendo...
Ci sono algoritmi ben più raffinati e prestanti ma richiedono più attenzione (merge sort, quicksort...) su wikipedia ne trovi molti, con anche del pseudocodice se vuoi implementarli http://it.wikipedia.org/wiki/Categoria:Algoritmi_di_ordinamento
ps: fai attenzione anche a quello che ha scritto Dan___88: è un errore comune copiare un valore al posto di uno già esistente senza tenersi una copia di quello che c'era prima (perdi il dato)
grazie a tutti.
senza andare troppo sul difficile, come posso implementare l'algoritmo descritto da te e tacchinox?
creo un nuovo array copia del precedente (già ordinato), ma per ordinarlo... un altro ciclo for come quello che avevo già fatto? :confused:
Un algoritmo semplice è questo:
Ti crei un vettore vuoto (stessa dimensione),
Poi cicli n volte sul vettore, ad ogni ciclo trovi l'elemento più piccolo e lo pushi nel vettore copia (ovviamente devi ricordati quali numeri hai già preso, ad esempio se sono numeri positivi, puoi sostituire ogni elemento con -1 quando lo copi nel nuovo vettore
VegetaSSJ5
30-12-2011, 17:14
Arrays.sort(numeri);
ok ho provato a implementare aggiungendo questa porzione di codice:
int[] newArray = new int[MAX+1];
for (pos = 1; pos < numeri.length; pos++) {
if (numeri[pos] > numeri[pos++])
numeri[pos] = newArray[pos];
}
ma non funzina lo stesso.
continuo a sbagliare su questo esercizio :muro:
@Vegeta: devo risolvere attraverso una struttura dati, non mi serve una funzione del linguaggio :)
ovviamente non va bene,..
e poi stai mettendo dentro numeri[pos] il contenuto di newArray[pos].. che senso ha??
Il minimo (o massimo) di un array lo sai calcolare?
Se non sai farlo, dovresti esercitarti prima su qualcosa di più semplice.
Devi fare due cicli innestati (tu ne hai fatto solo uno..), nel primo ciclo scorri newArray, nel secondo trovi di volta in volta il minimo dell'array e lo metti dentro newArray (nella posizione data dall'indice del primo ciclo).
ok ho provato a implementare aggiungendo questa porzione di codice:
int[] newArray = new int[MAX+1];
for (pos = 1; pos < numeri.length; pos++) {
if (numeri[pos] > numeri[pos++])
numeri[pos] = newArray[pos];
}
ma non funzina lo stesso.
continuo a sbagliare su questo esercizio :muro:
@Vegeta: devo risolvere attraverso una struttura dati, non mi serve una funzione del linguaggio :)
Non voglio assolutamente fare la parte dell'antipatico ma... dovresti rivederti le basi del java in modo serio...
L'algoritmo che ri serve è molto semplice ma sarebbe didatticamente inutile se ti venisse proposto un algoritmo dal nulla da copia-incollare. Il mio consiglio è di buttare giù uno schema o uno pseudocodice che ti permetta di lavorare sulla logica dell'algoritmo prima della semantica da usare per applicarlo al Java.
Posso però proporti alcune riflessioni e consigli: innanzi tutto il vettore...
MAX suppongo sia il numero di valori massimo che deve contenere il vettore.
perchè crei un array di dimensione MAX+1? cosa ti serve quel +1? se MAX è il numero di elementi che vuoi far contenere all'array, usa MAX da solo.
E quando poi nel for accedi all'array, perchè parti con pos=1 e non pos=0? il primo elemento del vettore è numeri[0], non numeri[1].
Poi ancora, la condizione
if (numeri[pos] > numeri[pos++])
non sarà mai vera perchè pos++ è un postincremento (ma anche se fosse un preincremento penso non cambierebbe) quindi tu di fatto confronti numeri[pos] con numeri[pos] stesso e solo dopo incrementi di 1 l'indice. Incremento che comunque penso sia sbagliato perchè già il for prevede un incremento a ogni ciclo, quindi tra l'altro tu esegui il confronto solo su elementi in posizione pari per via di un doppio incremementodi pos a ogni ciclo: pos[1] > pos[1] , pos[3] > pos[3] , pos[5] > pos[5]... (attenzione l'indice dispari indica elementi in posizione pari perchè l'indice del primo elemento è 0).
Il minimo (o massimo) di un array lo sai calcolare?
Se non sai farlo, dovresti esercitarti prima su qualcosa di più semplice.sto provando a fare un bubble sort ma non ci riesco; chiaramente se lo avessi saputo fare non avrei chiesto!
Devi fare due cicli innestati (tu ne hai fatto solo uno..), nel primo ciclo scorri newArray, nel secondo trovi di volta in volta il minimo dell'array e lo metti dentro newArray (nella posizione data dall'indice del primo ciclo).
edit: ho rivisto il codice finale grazie agli accorgimenti di demos:
int[] newArray = new int[MAX];
for (pos = 0; pos < newArray.length; pos++) {
for (i = 0; i < newArray.length; i++) {
if (numeri[pos] > newArray[i])
newArray[i] = numeri[pos];
}
}
for (i = 0; i < newArray.length; pos++)
out.println(newArray[pos]);
credo comunque sia sbagliato perchè sto confrontando un array vuoto con un array con i numeri.
Non voglio assolutamente fare la parte dell'antipatico ma... dovresti rivederti le basi del java in modo serio...
L'algoritmo che ri serve è molto semplice ma sarebbe didatticamente inutile se ti venisse proposto un algoritmo dal nulla da copia-incollare. Il mio consiglio è di buttare giù uno schema o uno pseudocodice che ti permetta di lavorare sulla logica dell'algoritmo prima della semantica da usare per applicarlo al Java.
Posso però proporti alcune riflessioni e consigli: innanzi tutto il vettore...
MAX suppongo sia il numero di valori massimo che deve contenere il vettore.
perchè crei un array di dimensione MAX+1? cosa ti serve quel +1? se MAX è il numero di elementi che vuoi far contenere all'array, usa MAX da solo.
E quando poi nel for accedi all'array, perchè parti con pos=1 e non pos=0? il primo elemento del vettore è numeri[0], non numeri[1].
Poi ancora, la condizione
if (numeri[pos] > numeri[pos++])
non sarà mai vera perchè pos++ è un postincremento (ma anche se fosse un preincremento penso non cambierebbe) quindi tu di fatto confronti numeri[pos] con numeri[pos] stesso e solo dopo incrementi di 1 l'indice. Incremento che comunque penso sia sbagliato perchè già il for prevede un incremento a ogni ciclo, quindi tra l'altro tu esegui il confronto solo su elementi in posizione pari per via di un doppio incremementodi pos a ogni ciclo: pos[1] > pos[1] , pos[3] > pos[3] , pos[5] > pos[5]... (attenzione l'indice dispari indica elementi in posizione pari perchè l'indice del primo elemento è 0).
sto cercando di fare esercizi sugli array, visto che non riesco ad usarli...
grazie per le spiegazioni ;)
Intanto ragioniamo su come trovare il minimo di un array:
ci serve una variabile temporanea su cui memorizzare il minimo locale (la settiamo ad un valore sufficientemente grande):
int min = 9999999
Poi scorriamo l'array, e confrontiamo questo valore con ogni valore dell'array, se questo è minore lo aggiorniamo:
for (pos = 0; pos < numeri.length; pos++) {
if (numeri[pos] < min)
min = numeri[pos];
}
alla fine del ciclo, siamo sicuri che min contrerrà il valor minimo dell'array.
Nel tuo caso, per ordinare devi fare così:
int min = 99999
for (int i = 0; i < newArray.length; i++) {
for (pos = 0; pos < numeri.length; pos++) {
if (numeri[pos] < min)
min = numeri[pos];
numeri[pos] = 99999 // così al prossimo ciclo non verrà considerato
}
newArray[i] = min;
}
L'ho scritto di fretta, spero di non aver fatto qualche errore :)
ok fino a qui ci sono. ho provato a stampare a video newArray[i] per vedere se effettivamente mi ha posizionato il minor valore in quella posizione, ma mi da un errore... ma non entriamo in merito perchè faccio già abbastanza casino...
ora devo confrontare gli elementi degli array. il metodo che avevo usato sopra funziona?
Il codice che ho scritto nella parte finale
int min = 99999
for (int i = 0; i < newArray.length; i++) {
for (pos = 0; pos < numeri.length; pos++) {
if (numeri[pos] < min)
min = numeri[pos];
numeri[pos] = 99999 // così al prossimo ciclo non verrà considerato
}
newArray[i] = min;
}
è già bello e pronto.
Alla fine della sua esecuzione, newArray dovrebbe contenere i valori di numeri ordinati
Intanto ragioniamo su come trovare il minimo di un array:
ci serve una variabile temporanea su cui memorizzare il minimo locale (la settiamo ad un valore sufficientemente grande):
int min = 9999999
alla fine del ciclo, siamo sicuri che min contrerrà il valor minimo dell'array.
Mi permetto di fare il pignolo, almeno in ambito didattico (poi nella realtà si sa, si tramaccia di continuo :D ).
Fissare min a una costante, anche se grande, non è logicamente corretto.
Innanzi tutto perchè anche se la costante è grande, non si sa se sia effettivamente maggiore di ogni elemento dell'array, se il numero più basso fosse 10000000, non funzionerebbe.
Il numero "sicuro" da assegnare sarebbe il massimo previsto da int, e corrisponde alla costante
Integer.MAX_VALUE
In questo caso sei sicuro che il codice funziona (in realtà no, perchè se dentro l'array c'è proprio un valore uguale a Integer.MAX_VALUE, sei fregato), tuttavia rimane il problema "logico" che se si lavora su un set di dati, non è corretto logicamente rendere un dato non appartenente al set un possibile (se pur solo logicamente) risultato, che quindi sarebbe sbagliato.
A questo punto, propongo anche una mia soluzione che ricalca l'algoritmo selection sort, che è quello che ho descritto qualche post sopra (consiglio vivamente di rileggere l'esempio pratico che ho fatto sopra, non ha senso copiare senza capirlo):
public static void selectionSort(int[] array){
int j, tmp, min = 0; //inizializzazione variabili, j e min sono indici,
//tmp è una variabile temporanea per gli spostamenti
for (int i = 0; i < array.length; i++){ //ciclo esterno, ripete n volte (n = dimensione array)
for (j = min = i; j < array.length; j++) //ciclo interno, ripete n - i volte
if (array[j] < array[min]) //Se l'elemento in indice j è inferiore a quello in indice min
min = j; //allora min = j
//le seguenti 3 istruzioni invertono il primo elemento non ordinato
//con l'elemento minore della sottostringa non ordinata
tmp = array[i]; //copio il primo elemento non ordinato in variabile temporanea
array[i] = array[min]; //copio l'elemento minore al posto del primo elemento non ordinato
array[min] = tmp; //copio l'elemento non ordinato precedentemente salvato
//in tmp al posto dell'elemento minore trovato
}
}
è fortemente commentato, per essere il più possibile chiaro :)
Consiglio anche una visitina a wikipedia per la descrizione teorica dell'algoritmo selection sort: http://it.wikipedia.org/wiki/Selection_sort
Il codice che ho scritto nella parte finale
int min = 99999
for (int i = 0; i < newArray.length; i++) {
for (pos = 0; pos < numeri.length; pos++) {
if (numeri[pos] < min)
min = numeri[pos];
numeri[pos] = 99999 // così al prossimo ciclo non verrà considerato
}
newArray[i] = min;
}
è già bello e pronto.
Alla fine della sua esecuzione, newArray dovrebbe contenere i valori di numeri ordinati
mmmh così a prima vista mi sa che non funziona...
innanzi tutto nel ciclo interno if numeri[pos] < min
si può verificare più volte nello stesso ciclo del for interno, quindi finisci per sovrascrivere più di una casella dell'array numeri con 99999, perdendo quindi valori.
Poi a ogni completamento del for interno, la variabile min andrebbe impostata nuovamente al valore grande, altrimenti riempi l'intero array con numeri tutti uguali (uguali al minore dell'array di partenza).
amico ti mancano proprio le basi :D
non ci sto capendo più una cippa :mbe:
io ho riscritto tutto seguendo il consiglio di dan_88 ma evidentemente non funziona correttamente perchè mi stampa un unico valore.
int MAX = in.readInt("Quanti numeri vuoi inserire? ");
//creo array
int[] numeri = new int[MAX];
//ciclo for lettura
for (int i = 0; i < numeri.length; i++) {
int num = in.readInt("Numero? ");
numeri[i] = num;
}
//creo nuovo array
int[] nuovo = new int[MAX];
//trovo minimo dell'array
int min = 99999;
for (int h = 0; h < nuovo.length; h++) {
for (int i = 0; i < numeri.length; i++) {
if (numeri[i] < min)
min = numeri[i];
numeri[i] = 99999;
}
nuovo[h] = min;
out.println(nuovo[h]);
}
...ora riprovo cercando di capire cosa suggerisce demos.
facci sapere se hai bisogno :)
ok mi rivolgo a demos per il codice che mi ha lui stesso suggerito:
in questa riga di codice,for (j = min = i; j < array.length; j++) //ciclo interno, ripete n - i volte posso semplicemente scrivere j = 0, giusto?
qui if (array[j] < array[min]) si presuppone che entrambi gli array siano stati riempiti un precedente ciclo for?
nelle istruzioni successive non ho capito che senso ha assegnare a tmp = array[i], in quanto comunque la variabile è già a 0 e sarà modificata 2 istruzioni dopo. per il resto le istruzioni mi tornano (ci ho messo qualche minuto a capire), proverò a compilare più tardi :)
ok mi rivolgo a demos per il codice che mi ha lui stesso suggerito:
in questa riga di codice,for (j = min = i; j < array.length; j++) //ciclo interno, ripete n - i volte posso semplicemente scrivere j = 0, giusto?
No, j deve essere inizializzato all'indice del primo numero della sottosequenza non ordinata, ovvero i (il cui incremento è gestito dal for esterno). Perchè tu, cerchi il minore tra i numeri che non sono ancora ordinati, quelli già ordinati li lasci stare (e si trovano tra l'indice 0 e i-1)
qui if (array[j] < array[min]) si presuppone che entrambi gli array siano stati riempiti un precedente ciclo for?
l'array è uno solo e si chiama appunto "array", solo che accedi a indici diversi.
L'array, prima dell'algoritmo viene riempito e passato come parametro della funzione selectionSort(int[] array)
nelle istruzioni successive non ho capito che senso ha assegnare a tmp = array[i], in quanto comunque la variabile è già a 0 e sarà modificata 2 istruzioni dopo. per il resto le istruzioni mi tornano (ci ho messo qualche minuto a capire), proverò a compilare più tardi :)
Come detto sopra, stiamo lavorando su un unico array, quindi se sovrascrivo un valore dentro all'array, perdo quello precedente. Tmp mi serve per ricordarmi che valore c'era in array[i], e lo scambio con array[min], quindi:
prima faccio una copia di array[i] in tmp
poi copio array[min] in array[i]. A questo punto all'indice min e i ho lo stesso valore, però io devo rimettere dentro il valore che ho sostuito, e lo rimetto in array[min], quindi
array[min] = tmp
Tutto questo perchè il selection sort è un algoritmo in-place, lavora quindi sulla struttura dati stessa, spiegazione su wikipedia: http://it.wikipedia.org/wiki/Algoritmo_in_loco
ah ok, capito. ho letto attentamente la voce su wiki.
questo funziona giusto, non avevo ben realizzato stessi usando un algoritmo completamente diverso!
...unica cosa è che mi sono fossilizzato sul far funzionare il Bubble Sort; ora ho trovato questo esempio di codice: http://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Bubble_sort :muro:
ci riprovo un'altra volta ora, grazie per la pazienza :S
...unica cosa è che mi sono fossilizzato sul far funzionare il Bubble Sort; ora ho trovato questo esempio di codice: http://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Bubble_sort :muro:
ci riprovo un'altra volta ora, grazie per la pazienza :S
Cosa non ti è chiaro del bubblesort?
Il nome stesso (bubble) suggerisce il metodo in cui lavora, l'algoritmo lavora sempre secondo il concetto di substringa ordinata e non ordinata, solo che quella ordinata non è all'inizio ma alla fine.
Il nome "bubble" dipende dal fatto che l'algoritmo parte dall'inizio della sequenza di valori e fa "salire" come una bolla i valori maggiori (come nell'esempio, ma possono anche essere i minori per avere ordinamento decrescente) fino alla cima.
Nell'algoritmo che hai visto in quel sito, che riporto:
public void bubbleSort(int[] x)
{
int temp = 0;
int j = x.length-1;
while(j>0)
{
for(int i=0; i<j; i++)
{
if(x[i]>x[i+1]) //scambiare il '>' con '<' per ottenere un ordinamento decrescente
{
temp=x[i];
x[i]=x[i+1];
x[i+1]=temp;
}
}
j--;
}
}
j è l'indice che deve essere riempito con il valore maggiore tra i non ordinati, mentre i è l'indice che cerca il valore maggiore.
Concettualmente è simile al selection sort, solo che ad ogni comparazione, se la disuguaglianza è vera, sposta un elemento in modo da "avvicinarlo" alla sequenza ordinata. Esempio:
5 8 1 6 4 3
1° ciclo:
j = 5, i = 0; 5 >= 8 ? no, quindi non fare nulla
5 8 1 6 4 3
j = 5, i = 1; 8 >= 1 ? si, quindi inverti 8 con 1
5 1 8 6 4 3
j = 5, i = 2; 8 >= 6 ? si, quindi inverti 8 con 6
5 1 6 8 4 3
j = 5, i = 3; 8 >= 4 ? si, quindi inverti 8 con 4
5 1 6 4 8 3
j = 5, i = 4; 8 >= 3 ? si, quindi inverti 8 con 3
5 1 6 4 3 8
j = 5, i = 5; i = j -> ciclo finito, gli elementi da j in poi sono ordinati (j è ancora uguale a 5)
5 1 6 4 3 8
j--
2° ciclo:
5 1 6 4 3 8
j = 4, i = 0; 5 >= 1? si, quindi inverti 5 con 1
1 5 6 4 3 8
j = 4, i = 1; 5 >= 6 ? no, quindi non fare nulla
1 5 6 4 3 8
j= 4, i = 2; 6 >= 4 ? si, quindi inverti 6 con 4
1 5 4 6 3 8
j = 4, i = 3; 6 >= 3 ? si, quindi inverti 6 con 3
1 5 4 3 6 8
j = 4, i = 4; i = j -> ciclo finito, gli elementi da j in poi sono ordinati (j = 4)
1 5 4 3 6 8
3° ciclo:
penso ti sia chiaro... ;)
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.