Newsgroup: it.scienza.informatica
Titolo: Esercizio di Algoritmi, aiuto

Chiedo anticipatamente scusa se ho sbagliato ng, nel qual caso vi
pregherei di indirizzarmi verso un ng piu' adatto
Devo fare questo esercizio di Algoritmi1 e non riesco a capirlo:
Esercizio:
Sia A un vettore di lunghezza n tale che 1<= A[i]<=n  per ogni 
1<= i<=n.
Scrivere una procedura che restituisce il numero di elementi distinti
contenuti in A. 
La complessita' della procedura deve essere O(n).
Non riesco a capire che particolarita' ha questo vettore.
Come dovrebbe essere fatto un array in cui A[i] e' compreso tra 1 e n,
per ogni  i compreso tra 1 e n.
Potete farmi un esempio ?
Grazie.

Allora 1<= A[i]<=n vuol dire semplicemente che non potrai mai avere un i
tale per cui A[i]=0 o A[i]>n. Esempio:
Per n=1 avrai esattamente un elemento cioè A[1]=1.
per n=2 avrai A[1]=1 oppure A[1]=2 e A[2]=1 oppure A[2]=1 ....così con
tuttle le combinazioni...questo è il vettore.
Per la soluzione bisogna ragionarci un pò ma non dovrebbe essere così
difficile.


Supponiamo che la dimensione del vettore A sia n=5. Ogni valore
A[i] contenuto nel vettore sara' tale che
1 <= A[i] <= 5
Alcuni esempi di vettore di questo tipo per n=5 potrebbero essere
A1 = [3,2,5,4,2]
A2 = [5,1,3,2,2]
A3 = [1,4,2,3,3]
Alcuni esempi errati potrebbero essere invece:
A3 = [1,3,6,3,4] <-- contiene un valore maggiore della dimensione n
A4 = [5,2,3,0,1] <-- contiene un valore <1
ciao.
Matteo
-- 
Actualize.it - Il software libero, le tue esigenze
Web Aziendale - 
www.Actualize.it
Web Personale - 
www.MatteoMoro.net
ICQ#: 91902715, JID: 
emme...@jabber.linux.it

 ha scritto nel messaggio
news:4rblf019d8mrdd1si...@4ax.com...

semplicemente se n=5 l'array ha 5 elementi, ognuno dei quali può essere un
numero da 1 a 5
--
Pela

 Potete farmi un esempio ?
In che senso? Intendi come codifica? O un esempio di vettore?

 Potete farmi un esempio ?
In che senso? Intendi come codifica? O un esempio di vettore?

 Grazie.
Prego!

 Potete farmi un esempio ?
A = (1, 2, 3, 4, 5)
L'array A e` di lunghezza n = 5, e ciascuno dei suoi elementi e` 
compreso tra 1 e n = 5.
-- 
Enrico `Trippo' Porreca



Non c'e' proprio nessuno che puo' aiutarmi ?
La soluzione dell' esercizio e' questa:
CountDistinct(A)
1: length(B) = lenght(A)
2: for i = 1 to length(B) do
3:     B[i] = 0
4: end for
5: count = 0
6: for i = 1 to length(A) do
7:   if B[ A[i] ] == 0 then
8:     B[ A[i] ] = A[i]
9:     count = count + 1
10: end if
11: end for
12: return count
Nonostante la soluzione non riesco proprio a capire come deve essere
fatto l'array in questione. Cioe' non capisco proprio quello che vuole
l'esercizio.
Perfavore...aiutatemi.

Il Sun, 18 Jul 2004 17:16:02 +0000, Manuele80 ha scritto:
Scusate per il triplo (!) post ma ieri avevo il server che non mi dava
segnali di vita... Chiedo venia!

l'esercizio.
L'array e' semplicissimo: ogni elemento e' un valore non superiore a
n=lunghezza di A.
Una proprieta' e' che esiste un vettore che soddisfa la condizione ed
ha n elementi distinti. Generalmente un vettore A che soddisfa la
condizione ha 1, 2, ..., oppure n elementi distinti.
Da questa proprieta' l'idea piu' ovvia e' leggere in sequenza il
vettore e memorizzare per ognuno dei al piu' n elementi diversi il
numero di occorrenze: a tal scopo basta avere un vettore di n interi,
che si puo' chiamare Occorrenze, Presenze, o come vuoi.
Contando il numero di elementi di valore non 0 nel vettore ausiliario
hai il numero di elementi distinti.
Anzi il vettore ausiliario ti dice le occorrenze per ogni elemento. Ci
si rende allora conto che ci sono troppe informazioni: e' sufficiente
usare un vettore booleano che memorizza la presenza di ogni numero, ed
e' pressapoco quello che viene fatto nella soluzione.
La spiegazione e' piu' che prolissa per un esercizio del genere. Qui
non c'e' bisogno di studi approfonditi sugli algoritmi. Forse c'e'
solo bisogno di un po' di concentrazione, perche' ti stai
semplicemente perdendo in un bicchier d'acqua.
-- 
Linux Registered User #181013
[Exokernels] Although one approach to eliminating bloated, buggy,
unreliable operating systems is to make them smaller, a more radical
one is to eliminate the operating system altogether.