21⚓︎

Letti in input due insiemi di elementi \(I_1\) e \(I_2\), di cardinalità rispettivamente \(n\) e \(m\), scrivere un algoritmo in grado di:

individuare gli elementi comuni ai due insiemi;
unire i due insiemi in un unico insieme;
calcolare la differenza tra i due insiemi;
stampare a video tutti i risultati.

Considerare i controlli sui dati di input. Realizzare come prima cosa la decomposizione funzionale.

Iniziare immediatamente con lo pseudo-codice potrebbe essere controproducente, dunque analizziamo prima le macro-operazioni.

Come prima cosa è necessario ricevere gli insiemi in input, dunque

Text Only

leggere insieme I1
leggere insieme I2

Successivamente sono presenti le operazioni sugli insiemi, quindi:

Text Only

calcolare I1 ∩ I2
calcolare I1 ∪ I2
calcolare I1 ∖ I2

e, infine:

Text Only

stampare i risultati

Si tratta di una sequenza di azioni. Quelle appena elencate non sono altro che delle sotto-operazioni dell'operazione principale.

Tralasciando ancora lo pseudo-codice, leggere leggere insieme [...] fa immediatamente pensare a LeggereDaTastiera(), ma per fare questo è necessaria la cardinalità dell'insieme, dopodiché i valori dell'insieme e infine verificare i vincoli sui dati. Quindi le operazioni distinte da effettuare sono quattro.

Analizzando ora stampare i risultati, bisogna stampare gli insiemi Unione, Intersezione e Differenza, vedremo dopo come.

Per quanto riguarda le operazioni sugli insiemi, il calcolo dell'intersezione è stato visto precedentemente. Il calcolo dell'unione è molto simile, bisogna prima inserire tutti gli elementi del primo insieme e poi controllare quali elementi del primo sono presenti nel secondo e se non è presente, aggiungerlo. Anche la differenza è simile in quanto si effettua una ricerca.

L'algoritmo va ora risolto per ogni operazione separata, ogni operazione ha un suo algoritmo separato delle altre.

Ora che son state analizzate brevemente le varie operazioni, possiamo creare un albero di lavoro:

TestoDiagramma

Albero di lavoro

Operazioni su insiemi
  Leggere insieme I1
    leggere cardinalità n di I1
    verificare i vincoli di n
    leggere i valori di I1
    verificare i vincoli di I1
  Leggere insieme I2
    leggere cardinalità m di I2
    verificare i vincoli di m
    leggere i valori di I2
    verificare i vincoli di I2
  Calcolare intersezione
    ricercare elemento in insieme
  Calcolare unione
    ricercare elemento in insieme
  Calcolare Differenza
    ricercare elemento in insieme
  Stampare i risultati
    stampare l'insieme intersezione
    stampare l'insieme unione
    stampare l'insieme differenza

flowchart LR;
  %% main node
  ops(Operazioni su insiemi);

  %%% secondary nodes
  rI1("leggere l'insieme I₁"); rI2("leggere l'insieme I₂");
  cc(calcolare l'insieme);
  pp(stampare i risultati); ppi(stampare l'insieme);

  %%%% tertiary nodes
  rcI1(leggere la cardinalità n); rcI2(leggere la cardinalità m);
  vvn(verificare i vincoli di n); vvm(verificare i vincoli di m);
  rvI1("leggere i valori di I₁"); rvI2("leggere i valori di I₂");
  vvI1("verificare i vincoli di I₁"); vvI2("verificare i vincoli di I₂");

  cint(intersezione); cuni(unione); cdif(differenza);
  pint(intersezione); puni(unione); pdif(differenza);

  %% from main
  ops ---> rI1 & rI2 & cc & pp;

  %%% from secondary
  rI1 --> rcI1 --> vvn;
  rI1 --> rvI1 --> vvI1;

  rI2 --> rcI2 --> vvm;
  rI2 --> rvI2 --> vvI2;

  cc --> cint & cuni & cdif;

  pp ---> ppi --> pint & puni & pdif;

Operazioni sugli insiemi⚓︎

Rappresenta il problema nella sua interezza.

INPUT:: \(I_1\) – primo insieme di \(n\) elementi, insieme; \(I_2\) – secondo insieme di \(m\) elementi, insieme; \(n\) – cardinalità di \(I_1\), con \(n \in \N^\ast\); \(m\) – cardinalità di \(I_2\), con \(m \in \N^\ast\)
OUTPUT:: intersezione – insieme di elementi comuni a \(I_1\) e \(I_2\), insieme; unione – insieme di elementi di \(I_1\) e \(I_2\) distinti, insieme; differenza – insieme di elementi di \(I_1\) non comuni a \(I_2\), insieme

Bozza
1 2 3 4 5 6	`leggere insieme I1 leggere insieme I2 calcolare intersezione calcolare unione calcolare differenza stampare risultati`

Questa è un'idea di come l'algoritmo debba funzionare. Poiché diventi un vero algoritmo andrebbe scritto in pseudo-codice.

ALGORITMO:

La lettura degli insiemi, come le altre operazioni saranno delle funzioni:

Operazioni

n := LeggereCardinalità()
I1 := LeggereInsieme(n)
m := LeggereCardinalità()
I2 := LeggereInsieme(m)

Intersezione := CalcolareIntersezione(I1, n, I2, m)
Unione := CalcolareUnione(I1, n, I2, m)
Differenza := CalcolareDifferenza(I1, n, I2, m)

StampareRisultati(
  Intersezione, cardinalitàIntersezione,
  Differenza, cardinalitàDifferenza,
  Unione, cardinalitàUnione,
)

L'algoritmo non si discosta molto dall'albero di lavoro.

Leggere cardinalità⚓︎

Poiché la cardinalità degli insiemi è un dato continuamente utilizzato, è necessario richiederlo in input.

INPUT:: vuoto – non è presente input
OUTPUT:: cardinalità – numero di elementi di un insieme, naturale

ALGORITMO:

Text Only
1 2 3 4 5	`ESEGUI StampareAVideo("Inserire il numero di elementi dell'insieme: ") cardinalità := LeggereDaTastiera() FINCHÉ (cardinalità <= 0) FINE`

Leggere insieme⚓︎

INPUT:: cardinalità – numero di elementi dell'insieme \(I\), appartiene a \(\N^\ast\)
OUTPUT:: \(I\) – insieme di elementi, insieme

ALGORITMO:

Text Only
1 2 3 4 5	`SE (cardinalità > 0) ALLORA leggere i valori di I verificare i vincoli di I ALTRIMENTI StampareAVideo("Il numero immesso è negativo") FINE`

È necessario dare la possibilità di controllare la cardinalità e, finché questa non sia corretta, l'algoritmo non produce risultato.

Alcune di queste operazioni possono essere riscritte, ad esempio:

Text Only
1 2	`cardinalità := LeggereCardinalità() I := LeggereValoriInsieme(cardinalità)`

Per quanto riguarda la verifica dei vincoli, sarebbe meglio che questi vengano uniti alla lettura dei valori dell'insieme:

Text Only
1 2 3 4 5	`ESEGUI I := LeggereValoriInsieme(cardinalità) verificato := VerificareVincoli(I) FINCHÉ (verificato = FALSO) FINE`

La precedente soluzione è funzionale, però non risulta essere comoda per l'utente poiché nel caso in cui anche un singolo valore sia errato, è necessario reinserire anche gli altri.

Calcolare⚓︎

Intersezione⚓︎

INPUT:: \(I_1\) – primo insieme di cui effettuare l'intersezione, insieme; \(I_2\) – secondo insieme di cui effettuare l'intersezione, insieme; \(n\) – cardinalità di \(I_1\), appartiene a \(\N^\ast\); \(m\) – cardinalità di \(I_2\), appartiene a \(\N^\ast\)
OUTPUT:: intersezione – insieme risultante dell'intersezione tra \(I_1\) e \(I_2\), insieme
LAVORO:: \(p\) – posizione degli elementi di \(I_1\), appartiene a \(\N^\ast\); \(q\) – posizione degli elementi di intersezione, appartiene a \(\N^\ast\); trovato – indica se un elemento è presente in un insieme, booleano

ALGORITMO:

Text Only

q := 1
p := 1
MENTRE ( p <= n)
  trovato := RicercaElemento(p-esimo elemento di I1, I2, m)
  SE (trovato = VERO)
    ALLORA q-esimo elemento di intersezione := p-esimo elemento di I1
    q := q + 1
  FINE
  p := p + 1
FINE

>> per rappresentare la fine dell'insieme
>> q-esimo elemento di intersezione := VALORE_FINALE

Differenza⚓︎

INPUT:: \(I_1\) – primo insieme di cui effettuare l'intersezione, insieme; \(I_2\) – secondo insieme di cui effettuare l'intersezione, insieme; \(n\) – cardinalità di \(I_1\), appartiene a \(\N^\ast\); \(m\) – cardinalità di \(I_2\), appartiene a \(\N^\ast\)
OUTPUT:: differenza – insieme risultante dell'intersezione tra \(I_1\) e \(I_2\), insieme
LAVORO:: \(p\) – posizione degli elementi di \(I_1\), appartiene a \(\N^\ast\); \(q\) – posizione degli elementi di differenza, appartiene a \(\N^\ast\); trovato – indica se un elemento è presente in un insieme, booleano

ALGORITMO:

Text Only

p := 1
q := 1
MENTRE (p <= n)
  trovato := RicercareElemento(p-esimo elemento di I1, I2, m)
  SE (Trovato=FALSO)
    ALLORA q-esimo elemento di differenza := p-esimo elemento di I1
    q := q+1
  FINE
  p := p+1
FINE

Unione⚓︎

INPUT:: \(I_1\) – primo insieme di cui effettuare l'intersezione, insieme; \(I_2\) – secondo insieme di cui effettuare l'intersezione, insieme; \(n\) – cardinalità di \(I_1\), appartiene a \(\N^\ast\); \(m\) – cardinalità di \(I_2\), appartiene a \(\N^\ast\)
OUTPUT:: unione – insieme risultante dell'intersezione tra \(I_1\) e \(I_2\), insieme
LAVORO:: \(p\) – posizione degli elementi di \(I_1\), appartiene a \(\N^\ast\); \(q\) – posizione degli elementi di unione, appartiene a \(\N^\ast\); trovato – indica se un elemento è presente in un insieme, booleano

ALGORITMO:

Text Only

p := 1
MENTRE (p <= n)
  p-esimo elemento di unione := p-esimo elemento di I1
  p := p+1
FINE

q := 1
MENTRE (q <= m)
  trovato := RicercareElemento(p-esimo elemento di I2, Unione, p - 1)
  SE (trovato = FALSO)
    ALLORA p-esimo elemento di unione := p-esimo elemento di I2
    p := p + 1
  FINE
  q := q + 1
FINE

Stampare risultati⚓︎

INPUT:

intersezione – insieme di elementi comuni a \(I_1\) e \(I_2\), insieme

differenza – insieme di elementi di \(I_1\) non comuni a \(I_2\), insieme

unione – insieme di elementi di \(I_1\) e \(I_2\) distinti, insieme

cardinalitàIntersezione – numero di elementi di intersezione, appartiene

a \(\N^\ast\)

cardinalitàDifferenza – numero di elementi di differenza, appartiene a
\(\N^\ast\): cardinalitàUnione – numero di elementi di unione, appartiene a \(\N^\ast\)

OUTPUT:

nullo – non è previsto output

ALGORITMO:

Algoritmo 1

p := 1
MENTRE (p < cardinalitàIntersezione)
  StampareAVideo(p-esimo elemento di intersezione)
  p := p + 1
FINE

p := 1
MENTRE (p < cardinalitàDifferenza)
  StampareAVideo(p-esimo elemento di differenza)
  p := p + 1
FINE

p := 1
MENTRE (p < cardinalitàUnione)
  StampareAVideo(p-esimo elemento di unione)
  p := p + 1
FINE

Questa soluzione è certamente funzionale ma risulta essere estremamente brutta. L'alternativa più piacevole è la seguente:

Algoritmo 2
1 2 3	`StampareInsieme(Intersezione, cardinalitàIntersezione) StampareInsieme(Differenza, cardinalitàDifferenza) StampareInsieme(Unione, cardinalitàUnione)`

In questo modo introduciamo una nuova funzione, StampareInsieme(), la quale va specificata con le appropriate liste di input, output, etc. Quindi:

INPUT:: \(I\) – insieme di elementi da stampare, insieme; cardinalità – numero di elementi dell'insieme da stampare, appartiene a \(\N^\ast\)
OUTPUT:: nullo – non è previsto output
LAVORO:: \(p\) – posizione degli elementi dell'insieme \(I\), appartiene a \(\N^\ast\)

ALGORITMO:

Text Only
1 2 3 4 5	`p := 1 MENTRE (p < cardinalità) StampareAVideo(p-esimo elemento di I) p := p + 1 FINE`

In questo modo, anziché avere tre cicli MENTRE diversi, utilizziamo una funzione, che risulta essere una soluzione più elegante.

Calcolo della cardinalità⚓︎

Per ovviare al problema di chiedere continuamente come dato di input la cardinalità di ogni insieme, sarebbe possibile calcolarla.

INPUT:: \(I\) – insieme di elementi di cui calcolare la cardinalità, insieme
OUTPUT:: \(C\) – cardinalità dell'insieme \(I\), appartiene a \(\N^\ast\)

ALGORITMO:

Text Only
1 2 3 4 5	`p := 1 MENTRE (p-esimo elemento di I != VALORE_FINALE) p := p + 1 FINE C := p - 1`

Ma cos'è VALORE_FINALE? Si tratta di un elemento di controllo che non contribuisce ad aumentare la cardinalità dell'insieme ma permette all'algoritmo di terminare. Un insieme potrebbe dunque essere il seguente:

Text Only

I = {1, 3, 7, 9 VALORE_FINALE}

In questo modo è possibile calcolare la cardinalità di un insieme, avendo la certezza di fermare l'iterazione al momento corretto.

È importante notare che, se la cardinalità viene utilizzata molte volte, risulta più efficiente¹ o conservare il valore della stessa o chiederla in input.

Più efficiente dal punto di vista computazionale. ↩