Vai al contenuto

Esercizio del 14/10/2021⚓︎

Dati due insiemi di elementi \(I_1\) e \(I_2\), di cardinalità rispettivamente \(n, m\), scrivere un algoritmo in grado di individuare gli elementi comuni ai due insiemi.

Iniziamo ad elencare i dati.

INPUT
\(I_1\) – insieme di elementi, insieme
\(n\) – cardinalità di \(I_1\), appartiene a \(\N^\ast\)
\(I_2\) – insieme di elementi, insieme
\(m\) – cardinalità di \(I_2\), appartiene a \(\N^\ast\)
OUTPUT
\(I_3\) – insieme di elementi comuni a \(I_1\) e \(I_2\)

Consideriamo ad esempio \(I_1 = \{3, 12, 7, 41, 35\}\) e \(I_2 = \{8, 5, 62, 7, 27, 56\}\), ne risulta che \(I_3 = \{7\}\). Che procedimento è stato utilizzato?

Bozza
1
2
3
Prendere ogni elemento di I1
Controllare se è presente in I2
Se è presente, aggiungerlo a I3

Non è un algoritmo, ma il procedimento è sostanzialmente questo. Vediamolo:

Algoritmo, v1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
p := 1
MENTRE (p <= n)
  q := 1
  MENTRE (q <= m)
    SE (elemento p-esimo di I1 = elemento q-esimo di I2) ALLORA 
      inserire l'elemento p-esimo di I1 in I3
    FINE SE
    q := q + 1
  FINE MENTRE
  p := p + 1
FINE MENTRE

Questa è una possibile soluzione. Iteriamo all'interno del primo insieme e confrontiamo il primo elemento di questo con tutti gli elementi dell'altro insieme, e così via. C'è tuttavia un errore, non viene specificato l'inserimento dell'elemento nell'insieme \(I_3\). Inoltre l'algoritmo potrebbe essere reso più efficiente interrompendo il ciclo dopo aver trovato il numero in comune. Dunque

Algoritmo, v2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
p := 1
r := 1
MENTRE (p <= n)
  q := 1
  MENTRE (q <= m)
    SE (elemento p-esimo di I1 = elemento q-esimo di I2)
      ALLORA elemento r-esimo di I3 := elemento p-esimo di I1
      r := r + 1
    FINE
    q := q + 1
  FINE
  p := p + 1
FINE

Questo algoritmo però non funziona tutte le volte poiché nel caso in cui l'insieme \(I_3\) sia vuoto, questo dovrebbe essere \(I_3 = \emptyset\) ma il valore di \(r\) parte da uno e non da zero. Bisogna tener conto del fatto che la cardinalità è maggiorata di uno nel momento in cui sia necessario dare la soluzione, dunque r - 1 = 0, allora \(I_3 = \emptyset\).

Dopo aver letto la sezione sull'Algebra Booleana, è possibile scrivere un algoritmo migliore, che utilizza un valore booleano che indica se l'elemento è presente o meno nell'insieme \(I_2\).

Algoritmo, v3
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
p := 1
r := 1
trovato := FALSO
MENTRE (p <= n) ∧ (trovato = FALSO)
  q := 1
  MENTRE (q <= m)
    SE (elemento p-esimo di I1 = elemento q-esimo di I2)
      ALLORA elemento r-esimo di I3 := elemento p-esimo di I1
      trovato := VERO
      r := r + 1
    FINE
    q := q + 1
  FINE
  p := p + 1
FINE

Controllo⚓︎

Controlliamo che l'algoritmo sia corretto. Siano \(I_1 = \set{5, 10, 31}\) e \(I_2 = \set{7, 10}\), dunque \(I_3 = \set{10}\). Inoltre \(n = 3\) e \(m = 2\).

Controllo
1
2
3
4
5
6
I1 = {5, 10, 31}    n = 3
I2 = {7, 10}        m = 2
r -> 1; 2;
p -> 1; 2; 3; 4;
q -> 1; 2; 3; / 1; 2; 3; / 1; 2; 3; /
trovato -> FALSO