Newsgroup: it.comp.programmare
Titolo: Problema algoritmo

Salve a tutti,
qualcuno sa come progettare un algoritmo ricorsivo che dato un vettore
qualsiasi di dimensione n, restituisce true se ci sono almeno 2 interi
uguali.
Deve avere tempo di esecuzione O(n*log n) e non si possono chiamare
procedure che ordinano il vettore.
Grazie per eventuali suggerimenti

 Grazie per eventuali suggerimenti
Fammi indovinare, ricorsivo=homework?

 Fammi indovinare, ricorsivo=homework?
Anche io ho avuto lo stesso sentore ma... è tremendamente divertente!!! :-)
Ciao,
Giulio
-- 


Puoi applicare l'algoritmo di Merge Sort
http://it.wikipedia.org/wiki/Merge_sort
opportunamente modificato in modo che, alla prima coppia di interi
uguali che trova ritorni TRUE, mentre se non ne trova, ritorni FALSE.
E' ricorsivo e ha un tempo di esecuzione che tende a n*log(n), nel tuo
caso usera' questo tempo se non ci sono coppie di interi uguali,
altrimenti finisce prima.

 Puoi applicare l'algoritmo di Merge Sort
A occhio c'è qualcosa che non quadra... :-)
Ciao,
Giulio
-- 

 A occhio c'� qualcosa che non quadra... :-)
s/applicare/adattare/
-- 
-riko

 *opportunamente modificato*
;-)

 Pero' avevo scritto:
Infatti. Era solo per chiarificare. A sto giro mi trovavo completamente
d'accordo con te. Alla fine la struttura e' quella del merge-sort. O se
si preferisce, l'esercizio e il merge-sort hanno la stessa struttura.
Solo che e' piu' facile dire 'ispirati al merge sort'.
Di piu' credo che sia "fare i compiti a casa per OP".
-- 
-riko

Solo che e' piu' facile dire 'ispirati al merge sort'.
"merge-sort"="matrice sparsa"? perch� basta implementare una matrice
(vettore, nel caso specifico) sparsa, in cui l'elemento A(z) contenga la
frequenza dell'intero z nell'insieme; si percorre l'insieme, compilando la
matrice (ce l'ho, ce l'ho, mi manca), e appena si incontra A(z)>1 (ce l'ho)
ci si ferma.
Come implementare (ricorsivamente?) una matrice sparsa con tempi di accesso
O(log n) � lasciato al lettore come compito a casa.
Ciao.

 O(log n) è lasciato al lettore come compito a casa.
Ok, vedo quello che riesco a fare. :-)
Ciao,
Giulio
--

 l'elemento massimo (e di conseguenza la dimensione del vettore sparso)?
O(N) + O(nlogn) chi vince? :-)

l'elemento massimo (e di conseguenza la dimensione del vettore sparso)?
Non � detto. Intanto, potrebbe venire qualcuno a dircelo (la definizione
del problema da parte dell'OP � piuttosto lacunosa: neppure ci dice se il
vettore da analizzare � effettivamente di "interi", o anche solo se
contiene "interi"; dove per "interi", visto dove stiamo parlando, sarebbe
lecito anche intendere la loro rappresentazione, quindi limitata,
all'interno di un linguaggio di programmazione... insomma, non c'� motivo
di escludere che "qualsiasi" possa voler dire "limitato a priori", se ci fa
comodo pensarlo); o altrimenti potremmo inventarci un'implementazione
dinamica del vettore sparso (che ovviamente ha un costo, ma magari
riusciamo lo stesso a star dentro al budget).
Non ho davvero idea se sia possibile trovare una soluzione O(n log n) con
questo metodo, nell'interpretazione pi� generale del problema, ma mi pare
una possibilit� da investigare. Anche perch�, O(n log n) o no, sarebbe il
modo in cui verrebbe naturale di risolverlo a me, in alcuni linguaggi (per
esempio, in Perl, usando magari un hash per memorizzare il vettore, o
magari fidandomi degli array dinamici di Perl).
Ciao.

 O(N) + O(nlogn) chi vince? :-)
Lo so che nel fantastico mondo della "O grande" la N va a farsi 
benedire. La mia era solo una richiesta di chiarimento. :-)
Ciao,
Giulio
-- 

 Ciao.
Contiene "effettivamente" interi.
La soluzione dovrebbe prescindere dal linguaggio in cui si implementa
l'algoritmo, se ne richiede solo lo pseudocodice.
Anche io avevo pensato ad un "adattamento" del mergeSort ma sinceramente
non ho capito come modificare la procedura merge in modo tale da
risolvere il mio problema.
Grazie comunque a chi si sta interessando
Saluti
P.S.:non era un homework ma un esercizio dell'esame di algoritmi 1.  

 wrote:

Imho il modo più semplice è copiare i valori dell'array in un albero
binario.
La prima volta che trovi una foglia occupata restituisci vero.
Scorrere l'array costa O(n), inserire i numeri nell'albero costa
mediamente O(log n).
Ciao
Mattia