[Java] Piccoli problemi
Ciao a tutti!ho svolto la porva scritta di programmaz..e vorrei sapere quali sono le soluzioni di questi esercizi...in modo che arrivi all'orale domani già preparato!..forse esigo troppo...però nn vi posso dare le mie possibili soluzioni..perchè io proprio nn ne ho idea!
1)Supponiamo di rappresentare un insieme di numeri interi con un array che ne elenca i suoi elementi e di voler realizzare l'operazione di intersezione
-scrivi specifiche del problema
-scrivi codice di un metodo che lo risolve
2)Un insieme di elementi può essere rappresentato ocme una lista dei suoi elementi; in questo caso le tipiche operazioni insiemistiche possono essere realizzate da opportuni algoritmi sulle liste.
-definire la struttura dati concretae la segnatura delle operazioni fondamentali
-scrivere specifiche e codice dell'operazione di unione
-discutere complessità di quest'operazione con particolare riferimento alla rappresentazione dei dati
3)Sia dato un albero di ricerca;fissato uno specifico valore v si vuole ottenere l'albero di ricerca che si ottiene togliendo tutti gli elemtni più piccoli di tale valore mantenendo x quanto possibile la strutture dell'albero stesso
-definire in astratto la funzione corrispondente
-scrivi specifiche e codice algoritmo che realizza tale funzione
Vi chiedo di svolgere anche solo alcuni punti...sareste la mia salvezza!grazie!
1)Supponiamo di rappresentare un insieme di numeri interi con un array che ne elenca i suoi elementi e di voler realizzare l'operazione di intersezione
-scrivi specifiche del problema
-scrivi codice di un metodo che lo risolve
2)Un insieme di elementi può essere rappresentato ocme una lista dei suoi elementi; in questo caso le tipiche operazioni insiemistiche possono essere realizzate da opportuni algoritmi sulle liste.
-definire la struttura dati concretae la segnatura delle operazioni fondamentali
-scrivere specifiche e codice dell'operazione di unione
-discutere complessità di quest'operazione con particolare riferimento alla rappresentazione dei dati
3)Sia dato un albero di ricerca;fissato uno specifico valore v si vuole ottenere l'albero di ricerca che si ottiene togliendo tutti gli elemtni più piccoli di tale valore mantenendo x quanto possibile la strutture dell'albero stesso
-definire in astratto la funzione corrispondente
-scrivi specifiche e codice algoritmo che realizza tale funzione
Vi chiedo di svolgere anche solo alcuni punti...sareste la mia salvezza!grazie!
Risposte
Focalizziamo il punto 1)
affinchè si faccia una intersezione, i vettori non dovrebbero essere almeno 2 ?
affinchè si faccia una intersezione, i vettori non dovrebbero essere almeno 2 ?
Partiamo dal primo. In questo esercizio si suppone di rappresentare un insieme finito di interi elencandoli in un array. Il tuo metodo riceverà quindi in input due array che contengono un certo numero di interi disgiunti e ne deve restituire un terzo che contiene gli elementi comuni ad entrambi gli insiemi. Se non dovessi programmare il programma in Java ma trovare l'intersezione ad esempio degli insiemi seguenti, cosa faresti? Sei in grado di descrivere un procedimento che ti permette di trovarla?
$\{ 1, 2, 5, 6, 10, 15, 3 \} \cap \{ 3, 5, 7, 9, 11 \} = ???$
$\{ 1, 2, 5, 6, 10, 15, 3 \} \cap \{ 3, 5, 7, 9, 11 \} = ???$
Primo metodo:
si seleziona un vettore, si scorre e per ogni elemento si verifica se lui è presente nell'altro vettore, se è presente si salva sul vettore di output.
Metodo pessimo perchè si ha una complessità di n*m, ma si ha il risultato voluto.
Secondo metodo:
Si ordinano i vettori e si applica il metodo di prima, si ha un piccolo miglioramento perchè in questo modo la ricerca termina quando si trova un elemneto
maggiore di quello cercato, ma nel caso pessimo si ha sempre n*m.
Terzo metodo:
Ci si crea un vettore di appoggio C, si scorre il primo vettore A e nella posizione C(A(i)) si mette 1.
Dopo si scorre il secondo vettore B e se nella posizione C(B(j)) c'è 1 significa che l'elemnento è presente in A
quindi lo mettiamo in output.
complessità n+m, di meglio non mi viene in mente
si seleziona un vettore, si scorre e per ogni elemento si verifica se lui è presente nell'altro vettore, se è presente si salva sul vettore di output.
Metodo pessimo perchè si ha una complessità di n*m, ma si ha il risultato voluto.
Secondo metodo:
Si ordinano i vettori e si applica il metodo di prima, si ha un piccolo miglioramento perchè in questo modo la ricerca termina quando si trova un elemneto
maggiore di quello cercato, ma nel caso pessimo si ha sempre n*m.
Terzo metodo:
Ci si crea un vettore di appoggio C, si scorre il primo vettore A e nella posizione C(A(i)) si mette 1.
Dopo si scorre il secondo vettore B e se nella posizione C(B(j)) c'è 1 significa che l'elemnento è presente in A
quindi lo mettiamo in output.
complessità n+m, di meglio non mi viene in mente
Nel secondo metodo la complessità non è $n*m$. Prima di tutto bisogna considerare l'ordinamento. Supponiamo che questa operazione abbia complessità $n*log(n) + m*log(m)$. Una volta che gli array sono ordinati si possono usare strategie diverse per calcolare l'intersezione. Un primo metodo è quello da te proposto di scorrerne uno e fare la ricerca lineare nell'altro. Questo metodo però non è ottimale. Un primo modo per ottimizzarlo potrebbe essere quello di effettuare una ricerca binaria nel secondo passando da $n*m$ a $n*log(m)$. Ma il metodo secondo me ottimale consiste nello scorrere contemporaneamente i due array come quando si fa il merge nel mergesort e inserire nell'array di output i valori uguali. Quest'ultimo metodo ha complessità $n + m$ e quindi in totale abbiamo complessità $n*(log(n) + 1) + m*(log(m) + 1)$.
Il terzo metodo richiede una sacco di memoria ma può essere conveniente se l'intervallo di valori possibili è piccolo.
Un ultimo metodo possibile potrebbe essere quello di scorrere i due array e inserire i valori all'interno di un albero binario o forse una hashtable, e inserire valori nell'array di output quando viene inserito un valore già presente nella struttura dati. Questo metodo si presta bene ad essere usato per generare in contemporanea l'unione e l'intersezione utilizzando l'array dell'unione come un albero.
Il terzo metodo richiede una sacco di memoria ma può essere conveniente se l'intervallo di valori possibili è piccolo.
Un ultimo metodo possibile potrebbe essere quello di scorrere i due array e inserire i valori all'interno di un albero binario o forse una hashtable, e inserire valori nell'array di output quando viene inserito un valore già presente nella struttura dati. Questo metodo si presta bene ad essere usato per generare in contemporanea l'unione e l'intersezione utilizzando l'array dell'unione come un albero.
Possiamo sapere quale strada ha fatto Andro89 ?
"Pietro_Bonf":
Primo metodo:
Secondo metodo:
Terzo metodo:
Dalle risposte date, vedo che state considerando due vettori.
Il metodo 3 è inaccettabile. A parte la grandezza del vettore (già citata da patriarca), prova a pensare cosa succede se nel vettore ci sono valori decimali...
Il metodo 1 è sicuramante poco efficiente.
La migliore soluzione, per me, è quella citata da patriarca con gli indici che camminano simultaneamente (incrementando di volta in volta l'elemento piu' piccolo). Questo metodo sfrutta al massimo il fatto che i due vettori sono ordinati, ed ancora potrebbe essere usato nel caso in cui i vettori siano piu' di 2.
Solo per chiarezza:
nel testo si parla di numeri interi, ovviamente questo metodo, che altro non è una riedizione del counting sort, può essere applicato su numeri interi e di grandezza limitata.
Vista la logica del compito ho supposto che il primo esercizio fosse sugli algoritmi dei vettori, per questo ho evitato di utilizzare metodi che utilizzassero altro.
nel testo si parla di numeri interi, ovviamente questo metodo, che altro non è una riedizione del counting sort, può essere applicato su numeri interi e di grandezza limitata.
Vista la logica del compito ho supposto che il primo esercizio fosse sugli algoritmi dei vettori, per questo ho evitato di utilizzare metodi che utilizzassero altro.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo