Newsgroup: it.comp.lang.pascal
Titolo: Unione e Intersezione di Array

Come da oggetto, qualcuno potrebbe darmi il listato dei programmi di unione
ed intersezione di due array?
Grazie Mille a tutti quelli ke mi aiuteranno o semplicemente visioneranno
questo post.
Byez Gianni

 wrote in message
mxdc8.18333$8F6.7...@twister2.libero.it...

Se per esempio hai
const
n = 10; {CD : n indica la dimensione degli array}
var
i : integer;
A, B, C, D : array[1..n] of boolean;
{CD : A e B sono gli array su cui compiere le operazioni ed in C, D vengono
riportati i risultati }
[...]
{CM : intersezione di due array }
for i : = 1 to n do
C[i] : = A[i] and B[i];
[ ...]
{CM : unione di due array }
for i  : = 1 to n do
D[i] : = A[i] or B[i]
[ ... ]
Questo era un caso semplice di due array A e B di booleani. Se pero' mi
spieghi un po' meglio nello specifico il tuo problema ti posso aiutare
meglio. Cioč tu hai array di che cosa ?
Ciao

Perplesso....
Cooper.


> Perplesso....
assai... :-)
--
Dreadnaut
(Life would be easier if I had the source code)

Dreadnaut <Drea...@liberoDALLASPAM.it> wrote in message
lEwc8.761$Zf3....@twister2.libero.it...

Allora senti, rispondi tu al quesito cosi' rimango perplesso anche io

 ha scritto nel messaggio
news:a4u8ga$l9u$1...@pegasus.tiscalinet.it...


 anomala....  intanto che c'entrano gli operatori booleani?   nel codice
Come vedi in tal caso i booleani *c'entrano e come*
Altra rappresentazione del tipo astratto insieme.
II) Rappresentazione mediante *Lista Semplice*
Il generico insieme S viene rappresentato mediante una lista semplice che
contiene ogni elemento di S una ed una sola volta. Tutte le operazioni sul
tipo astratto sono facilmente esprimibili mediante operazioni sulle liste.
L'insieme vuoto e' rappresentato mediante la lista vuota
type puntInsieme = ^elemInsieme;
tipoBase = integer; {Per esempio}
elemInsieme = record
info : tipoBase;
next : puntInsieme
end;
function verificaInsiemeVuoto (a : puntInsieme) : boolean;
begin
verificaInsiemeVuoto : = (a = nil)
end; {verificaInsiemeVuoto}
function appartenenza (a : puntInsieme; elem : tipoBase) : boolean;
{Funzione ricorsiva}
begin
if verificaInsiemeVuoto (a)
then appartenenza : = false
else if a^.info = elem
        then appartenenza : = true
        else appartenenza : = appartenenza(a^.next, elem)
end; {appartenenza}
E cosi' di seguito si realizzano le altre operazioni.
Chiaramente se la cardinalita' di A non e' grande e' meglio la
rappresentazione I) mentre se e grande e' meglio la II) per occupazione di
memoria ma ci si perde in efficienza nel realizzare le operazioni
Buona Notte o Buon Giorno non saprei ......

La differenza fra me e te è che io sono più portato ad analizzare un
problema e trovare una possibile soluzione... tu invece a dare la soluzione
già codificata...
Chiaramente in questo modo la comprendi soltanto tu... e gli altri solo dopo
che ci avranno perso del tempo a capire a fondo tutto il codice.
Io quindi ho puntato più che altro a far vedere e cercare di far capire come
sono arrivato alla soluzione, quindi senza entrare nei dettagli tecnici del
pascal...
In ogni caso SE la tua soluzione funziona SEMPRE e per QUALSIASI tipo di
insieme senza alcuna eccezione o modifica nel codice.... ben venga... :-)
Ciao a presto :-)
Cooper.

 Cooper.
Ciao, Leonardo :-)

 Ciao, Leonardo :-)
Cooper :-)

> I) Rappresentazione mediante il *Vettore Caratteristico*
ehhehe allora ok :-) pero' dillo che vai giu' pesante di
bitvector... cosi' funziona, pero' occhio che Cooper si
lamenta perche' non puoi rappresentare insiemi _infiniti_ :-)


 [ ... ]
Credo tu voglia dire : Cosa si fa se l'insieme universale V e' infinito?
Ovviamente non si può utilizzare questo metodo, ma anche nel rappresentare
insiemi S per cui mediamente e'
cardinalita'(S) << cardinalita'(V) il metodo e' poco efficiente riguardo
all'occupazione di memoria in quanto gran parte delle locazioni di memoria
dell'array sono _false_  ma questo metodo e' *molto efficiente* riguardo
alla
realizzazione delle operazioni sugli insiemi sia primitive che non. Comunque
in generale la risposta e solo una e cioè : *Tutto Dipende* . Mi spiego
meglio. Se per esempio si sa che si devono rappresentare insiemi per cui
card(V) non e' "molto grande" allora conviene utilizzare la rappresentazione
mediante il *Vettore Caratteristico* in tal caso la memoria coinvolta non
sarà tantissima e si riescono a realizzare ad esempio le operazioni di
unione e intersezione con una complessità computazionale molto buona e cioè
O(n) dove n e' la dimensione dell'array. La rappresentazione dell'insieme
mediante *Lista Semplice* (record e puntatori) presenta il vantaggio di
avere una occupazione di memoria proporzionale al numero di elementi
dell'insieme e non come prima che l'occupazione di memoria comunque e' fissa
e proporzionale a card(V). Pero' se in questo caso si realizza l'operazione
di unione (un ragionamento analogo può essere fatto per l'intersezione) si
dovrebbe utilizzare l'algoritmo proposto da Cooper e cioè si dovrebbe
scandire una lista mettiamo A che rappresenta un insieme elemento per
elemento e per ognuno di essi si deve controllare se e' presente nella
seconda lista mettiamo B che rappresenta l'altro insieme. Se si indicano con
n
e m rispettivamente il numero di elementi della lista A e della lista B si
può verificare facilmente che nel caso più sfavorevole l'algoritmo richiede
m*n confronti tra elementi. In particolare il caso più sfavorevole si
verifica quando i due insiemi sono disgiunti, cioè A e B non hanno elementi
comuni. Da ciò si capisce che l'algoritmo può diventare molto inefficiente.
In realtà per migliorare l'efficienza si modifica un po' la rappresentazione
mediante lista. Non parlo di questa modifica altrimenti il discorso si fa
troppo lungo.Quindi diciamo che passando dalla rappresentazione mediante
*Vettore Caratteristico* a quella mediante *Lista Semplice* si ha il
vantaggio di realizzare una molto migliore utilizzazione della memoria ma lo
svantaggio che le operazioni di unione e intersezione possono diventare
molto poco efficienti. In pratica per poter decidere quale rappresentazione
utilizzare od eventualmente idearne un'altra bisogna vedere nello specifico
il problema che si deve risolvere. Ciò vale in generale per tutte le
*strutture dati*
Ciao, Leonardo :-)

> ultra mega snip
si era quello che volevo dire, solo che non volevo la prosopopea,
gia' me la son sorbita all'univ  :-)
