Vai al contenuto

Esercizi · Pseudocodice

Esercizi · Capitolo 2 · ogni soluzione si apre con un clic · Capitolo 2: Pseudocodice · Eserciziario, volume 1 (PDF)

Esercizio 2.1: Pseudocodice (E1)

Dato un array \(a[1..n]\) di \(n \ge 1\) numeri interi, si consideri il problema di determinare il valore minimo dell'array.

Domande

  1. Scrivere lo pseudocodice di un algoritmo che trova il valore minimo in un array \(a\) di \(n\) numeri interi. L'algoritmo deve:

    • ricevere in input un array \(a[1..n]\) di \(n \ge 1\) numeri interi;

    • restituire il valore minimo \(min\) dell'array;

    • usare una sola scansione dell'array.

  2. Eseguire l'algoritmo passo per passo sulle seguenti istanze:

    • Istanza 1: \(a = [9, 12, 3, 16, 19, 11, 12]\) con \(n=7\);

    • Istanza 2: \(a = [15, 7, 22, 4]\) con \(n=4\);

    • Istanza 3: \(a = [100]\) con \(n=1\).

    Per ogni istanza, mostrare lo stato iniziale delle variabili, il loro stato dopo ogni iterazione e il risultato finale.

  3. Scrivere lo pseudocodice di un algoritmo che trova sia il valore massimo sia il valore minimo con una sola scansione dell'array.

Soluzione

  1. Pseudocodice per trovare il valore minimo in un array:

    Algoritmo: FindMinimum

    Input: Un array \(a[1..n]\) di \(n \ge 1\) numeri interi
    Output: Il valore minimo nell'array \(a\)
    1function FindMinimum(a, n)
    2\(min := a[1]\)
    3for \(i := 2\) to \(n\) do
    4if \(a[i] < min\) then
    5\(min \leftarrow a[i]\)
    6end
    7end
    8return \(min\)
    9end

    • Inizializziamo \(min\) ad \(a[1]\), il primo elemento (esiste, poiché \(n \ge 1\)).

    • Scorriamo ogni elemento restante dell'array, confrontandolo con il minimo corrente.

    • Se l'elemento corrente è più piccolo, aggiorniamo il minimo.

    • Infine, restituiamo il valore minimo trovato.

  2. Esecuzione passo per passo sulle istanze.

    Istanza 1: \(a = [9, 12, 3, 16, 19, 11, 12]\), \(n=7\)

    \(i\) \(a[i]\) \(a[i] < min\)? \(min\)
    – – – \(9\)
    \(2\) \(12\) No \(9\)
    \(3\) \(3\) Sì \(3\)
    \(4\) \(16\) No \(3\)
    \(5\) \(19\) No \(3\)
    \(6\) \(11\) No \(3\)
    \(7\) \(12\) No \(3\)

    Restituisce: \(min = 3\)

    Istanza 2: \(a = [15, 7, 22, 4]\), \(n=4\)

    \(i\) \(a[i]\) \(a[i] < min\)? \(min\)
    – – – \(15\)
    \(2\) \(7\) Sì \(7\)
    \(3\) \(22\) No \(7\)
    \(4\) \(4\) Sì \(4\)

    Restituisce: \(min = 4\)

    Istanza 3: \(a = [100]\), \(n=1\)

    \(i\) \(a[i]\) \(a[i] < min\)? \(min\)
    – – – \(100\)
    nessuna iterazione: il ciclo parte da \(i = 2 > n = 1\)

    Restituisce: \(min = 100\)

  3. Pseudocodice per trovare sia il massimo sia il minimo con una sola scansione:

    Algoritmo: FindMaxMin

    Input: Un array \(a[1..n]\) di \(n \ge 1\) numeri interi
    Output: La coppia \((max, min)\), dove \(max\) è il massimo e \(min\) è il minimo di \(a\)
    1function FindMaxMin(a, n)
    2\(max := a[1]\)
    3\(min := a[1]\)
    4for \(i := 2\) to \(n\) do
    5if \(a[i] > max\) then
    6\(max \leftarrow a[i]\)
    7end
    8if \(a[i] < min\) then
    9\(min \leftarrow a[i]\)
    10end
    11end
    12return \(max\), \(min\)
    13end

    Ad esempio, sull'Istanza 1 (\(a = [9, 12, 3, 16, 19, 11, 12]\)) l'algoritmo restituisce \((19, 3)\).

Esercizio 2.2: Pseudocodice (E2)

Dato un array \(a[1..n]\) di \(n \ge 1\) numeri interi, si consideri il problema di calcolare la somma dei suoi valori.

Domande

  1. Scrivere lo pseudocodice di un algoritmo che calcola la somma di tutti gli elementi di un array \(a\) di \(n\) numeri interi. L'algoritmo deve:

    • ricevere in input un array \(a[1..n]\) di \(n \ge 1\) numeri interi;

    • restituire la somma \(sum\) di tutti gli elementi;

    • inizializzare una variabile \(sum\) a \(0\) e sommarle ogni elemento.

  2. Eseguire l'algoritmo passo per passo sulle seguenti istanze:

    • Istanza 1: \(a = [5, 12, 3, 8]\) con \(n=4\);

    • Istanza 2: \(a = [10, 20, 30]\) con \(n=3\);

    • Istanza 3: \(a = [7]\) con \(n=1\).

    Per ogni istanza, mostrare il valore iniziale della somma, il suo valore dopo l'aggiunta di ogni elemento e il risultato finale.

  3. Modificare lo pseudocodice per calcolare sia la somma sia la media \(avg = \frac{sum}{n}\) degli elementi, con una sola scansione dell'array.

Soluzione

  1. Pseudocodice per calcolare la somma di tutti gli elementi di un array:

    Algoritmo: ArraySum

    Input: Un array \(a[1..n]\) di \(n \ge 1\) numeri interi
    Output: La somma di tutti gli elementi dell'array \(a\)
    1function ArraySum(a, n)
    2\(sum := 0\)
    3for \(i := 1\) to \(n\) do
    4\(sum \leftarrow sum + a[i]\)
    5end
    6return \(sum\)
    7end

    • Inizializziamo \(sum\) a \(0\).

    • Scorriamo ogni elemento dell'array, aggiungendolo alla somma parziale \(sum\).

    • Infine, restituiamo la somma totale \(sum\).

  2. Esecuzione passo per passo sulle istanze.

    Istanza 1: \(a = [5, 12, 3, 8]\), \(n=4\)

    \(i\) \(a[i]\) \(sum\)
    – – \(0\)
    \(1\) \(5\) \(5\)
    \(2\) \(12\) \(17\)
    \(3\) \(3\) \(20\)
    \(4\) \(8\) \(28\)

    Restituisce: \(sum = 28\)

    Istanza 2: \(a = [10, 20, 30]\), \(n=3\)

    \(i\) \(a[i]\) \(sum\)
    – – \(0\)
    \(1\) \(10\) \(10\)
    \(2\) \(20\) \(30\)
    \(3\) \(30\) \(60\)

    Restituisce: \(sum = 60\)

    Istanza 3: \(a = [7]\), \(n=1\)

    \(i\) \(a[i]\) \(sum\)
    – – \(0\)
    \(1\) \(7\) \(7\)

    Restituisce: \(sum = 7\)

  3. Pseudocodice per calcolare sia la somma sia la media:

    Algoritmo: ArraySumAndAverage

    Input: Un array \(a[1..n]\) di \(n \ge 1\) numeri interi
    Output: La coppia \((sum, avg)\), dove \(sum\) è il totale e \(avg\) è la media degli elementi
    1function ArraySumAndAverage(a, n)
    2\(sum := 0\)
    3for \(i := 1\) to \(n\) do
    4\(sum \leftarrow sum + a[i]\)
    5end
    6\(avg := sum / n\)
    7return \(sum\), \(avg\)
    8end

    La precondizione \(n \ge 1\) garantisce che la divisione \(sum / n\) sia definita. Ad esempio, sull'Istanza 1 (\(a = [5, 12, 3, 8]\), \(n=4\)) l'algoritmo restituisce \((28, 7)\), poiché la somma è \(28\) e la media è \(28/4 = 7\).

Esercizio 2.3: Pseudocodice (E3)

Dato un array bidimensionale \(b[1..m][1..n]\) di \(m \times n\) numeri interi e un valore di soglia \(k\), si consideri il problema di contare il numero dei suoi valori strettamente maggiori di \(k\).

Domande

  1. Scrivere lo pseudocodice di un algoritmo che conta quanti elementi di \(b\) sono strettamente maggiori della soglia \(k\). L'algoritmo deve:

    • ricevere in input un array bidimensionale \(b[1..m][1..n]\), le dimensioni \(m\) e \(n\), e la soglia \(k\);

    • restituire il numero di elementi che soddisfano \(b[i][j] > k\);

    • scorrere tutte le posizioni dell'array con due cicli annidati.

  2. Eseguire l'algoritmo passo per passo sulle seguenti istanze, mostrando il valore di \(count\) dopo ogni aggiornamento:

    • Istanza 1: \(b = \begin{bmatrix} 3 & 7 & 1 \\ 5 & 2 & 8 \end{bmatrix}\), \(m=2\), \(n=3\), \(k=4\);

    • Istanza 2: \(b = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}\), \(m=3\), \(n=3\), \(k=5\).

  3. Modificare lo pseudocodice in modo che, oltre al conteggio, l'algoritmo restituisca anche un array di coppie \((i, j)\) che elenca le posizioni di tutti gli elementi dell'array bidimensionale maggiori di \(k\).

Soluzione

  1. Pseudocodice per contare gli elementi maggiori di una soglia:

    Algoritmo: CountGreaterThan

    Input: Un array bidimensionale \(b[1..m][1..n]\), le dimensioni \(m\) e \(n\), e una soglia \(k\)
    Output: Il numero \(count\) di elementi con \(b[i][j] > k\)
    1function CountGreaterThan(b, m, n, k)
    2\(count := 0\)
    3for \(i := 1\) to \(m\) do
    4for \(j := 1\) to \(n\) do
    5if \(b[i][j] > k\) then
    6\(count \leftarrow count + 1\)
    7end
    8end
    9end
    10return \(count\)
    11end

    • Inizializziamo \(count\) a \(0\).

    • Il ciclo esterno scorre le righe \(i = 1, 2, \dots, m\), il ciclo interno le colonne \(j = 1, 2, \dots, n\).

    • Per ogni elemento \(b[i][j]\), se supera \(k\) incrementiamo \(count\).

    • Infine, restituiamo \(count\).

  2. Esecuzione passo per passo sulle istanze.

    Istanza 1: \(b = \begin{bmatrix} 3 & 7 & 1 \\ 5 & 2 & 8 \end{bmatrix}\), \(m=2\), \(n=3\), \(k=4\)

    \(i\) \(j\) \(b[i][j]\) \(b[i][j] > 4\)? \(count\)
    – – – – \(0\)
    \(1\) \(1\) \(3\) No \(0\)
    \(1\) \(2\) \(7\) Sì \(1\)
    \(1\) \(3\) \(1\) No \(1\)
    \(2\) \(1\) \(5\) Sì \(2\)
    \(2\) \(2\) \(2\) No \(2\)
    \(2\) \(3\) \(8\) Sì \(3\)

    Restituisce: \(count = 3\) (elementi \(7\), \(5\), \(8\))

    Istanza 2: \(b = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}\), \(m=3\), \(n=3\), \(k=5\)

    \(i\) \(j\) \(b[i][j]\) \(b[i][j] > 5\)? \(count\)
    – – – – \(0\)
    \(1\) \(1\) \(1\) No \(0\)
    \(1\) \(2\) \(2\) No \(0\)
    \(1\) \(3\) \(3\) No \(0\)
    \(2\) \(1\) \(4\) No \(0\)
    \(2\) \(2\) \(5\) No \(0\)
    \(2\) \(3\) \(6\) Sì \(1\)
    \(3\) \(1\) \(7\) Sì \(2\)
    \(3\) \(2\) \(8\) Sì \(3\)
    \(3\) \(3\) \(9\) Sì \(4\)

    Restituisce: \(count = 4\) (elementi \(6\), \(7\), \(8\), \(9\))

  3. Pseudocodice che restituisce anche le posizioni degli elementi maggiori di \(k\). L'array \(pos\) è dichiarato con \(m \cdot n\) elementi, il massimo numero possibile di posizioni; ne vengono usati solo i primi \(count\) elementi.

    Algoritmo: CountAndListGreaterThan

    Input: Un array bidimensionale \(b[1..m][1..n]\), le dimensioni \(m\) e \(n\), e una soglia \(k\)
    Output: Il numero \(count\) e l'array \(pos[1..count]\) delle coppie \((i,j)\) con \(b[i][j] > k\)
    1function CountAndListGreaterThan(b, m, n, k)
    2\(count := 0\)
    3\(pos := \text{new array}[1..m \cdot n]\)
    4for \(i := 1\) to \(m\) do
    5for \(j := 1\) to \(n\) do
    6if \(b[i][j] > k\) then
    7\(count \leftarrow count + 1\)
    8\(pos[count] \leftarrow (i, j)\)
    9end
    10end
    11end
    12return \(count\), \(pos[1..count]\)
    13end

    Per l'Istanza 1, l'algoritmo restituisce \(count=3\) e \(pos = [(1,2),(2,1),(2,3)]\); per l'Istanza 2, restituisce \(count = 4\) e \(pos = [(2,3),(3,1),(3,2),(3,3)]\).

Esercizio 2.4: Pseudocodice (E4)

Dato un array bidimensionale \(b[1..m][1..n]\) di \(m \times n\) numeri interi, con \(m \ge 1\) e \(n \ge 1\), si consideri il problema di trovare il valore minimo di ciascuna colonna.

Domande

  1. Scrivere lo pseudocodice di un algoritmo che calcola il minimo di ciascuna colonna dell'array bidimensionale \(b\). L'algoritmo deve:

    • ricevere in input un array bidimensionale \(b[1..m][1..n]\) e le dimensioni \(m\), \(n\);

    • restituire un array \(colMin[1..n]\), dove l'elemento \(colMin[j]\) è il minimo della colonna \(j\);

    • scorrere le colonne e le righe con due cicli annidati.

  2. Eseguire l'algoritmo passo per passo sulle seguenti istanze, mostrando ogni aggiornamento dell'array \(colMin\):

    • Istanza 1: \(b = \begin{bmatrix} 4 & 9 & 2 \\ 7 & 1 & 6 \\ 3 & 5 & 8 \end{bmatrix}\), \(m=3\), \(n=3\);

    • Istanza 2: \(b = \begin{bmatrix} 8 & 3 \\ 5 & 7 \\ 2 & 4 \end{bmatrix}\), \(m=3\), \(n=2\).

  3. Modificare lo pseudocodice in modo che, oltre al valore minimo di ciascuna colonna, l'algoritmo restituisca anche l'indice di riga \(rowIdx[j]\) della prima posizione in cui si trova il minimo della colonna \(j\).

Soluzione

  1. Pseudocodice per calcolare i minimi delle colonne:

    Algoritmo: ColumnMinima

    Input: Un array bidimensionale \(b[1..m][1..n]\), le dimensioni \(m \ge 1\) e \(n \ge 1\)
    Output: Un array \(colMin[1..n]\), dove \(colMin[j]\) è il minimo della colonna \(j\)
    1function ColumnMinima(b, m, n)
    2\(colMin := \text{new array}[1..n]\)
    3for \(j := 1\) to \(n\) do
    4\(colMin[j] \leftarrow b[1][j]\)
    5for \(i := 2\) to \(m\) do
    6if \(b[i][j] < colMin[j]\) then
    7\(colMin[j] \leftarrow b[i][j]\)
    8end
    9end
    10end
    11return \(colMin\)
    12end

    • Il ciclo esterno scorre le colonne \(j = 1, 2, \dots, n\).

    • Inizializziamo \(colMin[j]\) a \(b[1][j]\), il primo elemento della colonna \(j\).

    • Il ciclo interno scorre le righe \(i = 2, 3, \dots, m\), confrontando ogni elemento con il minimo corrente della colonna, e aggiorna \(colMin[j]\) quando trova un elemento più piccolo.

    • Infine, restituiamo l'array \(colMin\).

  2. Esecuzione passo per passo sulle istanze.

    Istanza 1: \(b = \begin{bmatrix} 4 & 9 & 2 \\ 7 & 1 & 6 \\ 3 & 5 & 8 \end{bmatrix}\), \(m=3\), \(n=3\)

    Colonna \(j=1\)

    \(i\) \(b[i][1]\) \(<\)? \(colMin[1]\)
    – – – \(4\)
    \(2\) \(7\) No \(4\)
    \(3\) \(3\) Sì \(3\)

    Colonna \(j=2\)

    \(i\) \(b[i][2]\) \(<\)? \(colMin[2]\)
    – – – \(9\)
    \(2\) \(1\) Sì \(1\)
    \(3\) \(5\) No \(1\)

    Colonna \(j=3\)

    \(i\) \(b[i][3]\) \(<\)? \(colMin[3]\)
    – – – \(2\)
    \(2\) \(6\) No \(2\)
    \(3\) \(8\) No \(2\)

    La colonna \(<\)? riporta l'esito del confronto \(b[i][j] < colMin[j]\).

    Restituisce: \(colMin = [3, 1, 2]\)

    Istanza 2: \(b = \begin{bmatrix} 8 & 3 \\ 5 & 7 \\ 2 & 4 \end{bmatrix}\), \(m=3\), \(n=2\)

    Colonna \(j=1\)

    \(i\) \(b[i][1]\) \(<\)? \(colMin[1]\)
    – – – \(8\)
    \(2\) \(5\) Sì \(5\)
    \(3\) \(2\) Sì \(2\)

    Colonna \(j=2\)

    \(i\) \(b[i][2]\) \(<\)? \(colMin[2]\)
    – – – \(3\)
    \(2\) \(7\) No \(3\)
    \(3\) \(4\) No \(3\)

    Restituisce: \(colMin = [2, 3]\)

  3. Pseudocodice che restituisce anche l'indice di riga del minimo di ciascuna colonna. L'aggiornamento usa il confronto stretto \(<\), quindi in caso di parità viene mantenuta la prima riga.

    Algoritmo: ColumnMinimaWithIndex

    Input: Un array bidimensionale \(b[1..m][1..n]\) e le dimensioni \(m \ge 1\) e \(n \ge 1\)
    Output: Gli array \(colMin[1..n]\) e \(rowIdx[1..n]\)
    1function ColumnMinimaWithIndex(b, m, n)
    2\(colMin := \text{new array}[1..n]\)
    3\(rowIdx := \text{new array}[1..n]\)
    4for \(j := 1\) to \(n\) do
    5\(colMin[j] \leftarrow b[1][j]\)
    6\(rowIdx[j] \leftarrow 1\)
    7for \(i := 2\) to \(m\) do
    8if \(b[i][j] < colMin[j]\) then
    9\(colMin[j] \leftarrow b[i][j]\)
    10\(rowIdx[j] \leftarrow i\)
    11end
    12end
    13end
    14return \(colMin\), \(rowIdx\)
    15end

    Per l'Istanza 1, l'algoritmo restituisce \(colMin = [3,1,2]\) e \(rowIdx = [3,2,1]\); per l'Istanza 2, restituisce \(colMin = [2, 3]\) e \(rowIdx = [3, 1]\).

Esercizio 2.5: Pseudocodice (E5)

Dato un array bidimensionale \(b[1..m][1..n]\) di \(m \times n\) numeri interi, si consideri il problema di calcolarne l'array bidimensionale trasposto, cioè l'array bidimensionale \(c[1..n][1..m]\) con \(c[j][i] = b[i][j]\).

Domande

  1. Scrivere lo pseudocodice di un algoritmo che calcola la trasposta di un array bidimensionale \(b[1..m][1..n]\). L'algoritmo deve:

    • ricevere in input un array bidimensionale \(b[1..m][1..n]\) e le dimensioni \(m\), \(n\);

    • allocare un nuovo array bidimensionale \(c[1..n][1..m]\) per il risultato;

    • restituire l'array bidimensionale trasposto \(c\), tale che \(c[j][i] = b[i][j]\).

  2. Eseguire l'algoritmo passo per passo sulle seguenti istanze, mostrando l'array bidimensionale \(c\) che viene riempito elemento per elemento:

    • Istanza 1: \(b = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}\), \(m=2\), \(n=3\);

    • Istanza 2: \(b = \begin{bmatrix} 7 & 2 \\ 3 & 8 \\ 1 & 5 \end{bmatrix}\), \(m=3\), \(n=2\).

  3. Per un array bidimensionale quadrato (\(m = n\)), scrivere lo pseudocodice di un algoritmo che esegue la trasposizione sul posto (senza allocare un nuovo array bidimensionale), scambiando gli elementi \(b[i][j]\) e \(b[j][i]\) per ogni \(i < j\).

Soluzione

  1. Pseudocodice per la trasposizione di un array bidimensionale:

    Algoritmo: Transpose

    Input: Un array bidimensionale \(b[1..m][1..n]\), le dimensioni \(m\) e \(n\)
    Output: L'array bidimensionale trasposto \(c[1..n][1..m]\)
    1function Transpose(b, m, n)
    2\(c := \text{new array}[1..n][1..m]\)
    3for \(i := 1\) to \(m\) do
    4for \(j := 1\) to \(n\) do
    5\(c[j][i] \leftarrow b[i][j]\)
    6end
    7end
    8return \(c\)
    9end

    • Allochiamo \(c\) come un nuovo array bidimensionale \(n \times m\).

    • Il ciclo esterno scorre le righe \(i = 1, 2, \dots, m\) di \(b\), il ciclo interno le colonne \(j = 1, 2, \dots, n\) di \(b\).

    • Ogni elemento \(b[i][j]\) viene copiato nella posizione \(c[j][i]\); ogni elemento di \(c\) viene assegnato esattamente una volta.

    • Infine, restituiamo l'array bidimensionale trasposto \(c\).

  2. Esecuzione passo per passo sulle istanze.

    Istanza 1: \(b = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}\), \(m=2\), \(n=3\), quindi \(c\) è \(3 \times 2\)

    \(i\) \(j\) \(b[i][j]\) assegnamento
    \(1\) \(1\) \(1\) \(c[1][1] \leftarrow 1\)
    \(1\) \(2\) \(2\) \(c[2][1] \leftarrow 2\)
    \(1\) \(3\) \(3\) \(c[3][1] \leftarrow 3\)
    \(2\) \(1\) \(4\) \(c[1][2] \leftarrow 4\)
    \(2\) \(2\) \(5\) \(c[2][2] \leftarrow 5\)
    \(2\) \(3\) \(6\) \(c[3][2] \leftarrow 6\)

    Restituisce: \(c = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix}\)

    Istanza 2: \(b = \begin{bmatrix} 7 & 2 \\ 3 & 8 \\ 1 & 5 \end{bmatrix}\), \(m=3\), \(n=2\), quindi \(c\) è \(2 \times 3\)

    \(i\) \(j\) \(b[i][j]\) assegnamento
    \(1\) \(1\) \(7\) \(c[1][1] \leftarrow 7\)
    \(1\) \(2\) \(2\) \(c[2][1] \leftarrow 2\)
    \(2\) \(1\) \(3\) \(c[1][2] \leftarrow 3\)
    \(2\) \(2\) \(8\) \(c[2][2] \leftarrow 8\)
    \(3\) \(1\) \(1\) \(c[1][3] \leftarrow 1\)
    \(3\) \(2\) \(5\) \(c[2][3] \leftarrow 5\)

    Restituisce: \(c = \begin{bmatrix} 7 & 3 & 1 \\ 2 & 8 & 5 \end{bmatrix}\)

  3. Trasposizione sul posto di un array bidimensionale quadrato (\(m = n\)):

    Algoritmo: TransposeInPlace

    Input: Un array bidimensionale quadrato \(b[1..n][1..n]\), la dimensione \(n\)
    Output: L'array bidimensionale \(b\), trasposto sul posto
    1function TransposeInPlace(b, n)
    2for \(i := 1\) to \(n-1\) do
    3for \(j := i+1\) to \(n\) do
    4\(tmp := b[i][j]\)
    5\(b[i][j] \leftarrow b[j][i]\)
    6\(b[j][i] \leftarrow tmp\)
    7end
    8end
    9return \(b\)
    10end

    Il ciclo interno parte da \(j = i+1\), in modo che ogni coppia di posizioni simmetriche venga scambiata esattamente una volta (scambiarla due volte ripristinerebbe l'array originale) e gli elementi \(b[i][i]\) sulla diagonale non vengano mai spostati. Per \(i = n\) il ciclo interno sarebbe vuoto, quindi il ciclo esterno si ferma a \(n-1\). Ad esempio, su \(b = \begin{bmatrix} 4 & 1 \\ 9 & 6 \end{bmatrix}\) (\(n=2\)) l'unica iterazione scambia \(b[1][2]=1\) e \(b[2][1]=9\), dando \(b = \begin{bmatrix} 4 & 9 \\ 1 & 6 \end{bmatrix}\).

Esercizio 2.6: Pseudocodice (E6)

Dati un array bidimensionale \(a[1..m][1..p]\) di \(m \times p\) numeri interi e un array bidimensionale \(b[1..p][1..n]\) di \(p \times n\) numeri interi, si consideri il problema di calcolarne il prodotto, cioè l'array bidimensionale \(c[1..m][1..n]\) con:

\[ c[i][j] = \sum_{k=1}^{p} a[i][k] \cdot b[k][j] \]

Domande

  1. Scrivere lo pseudocodice di un algoritmo che calcola il prodotto \(c = a \cdot b\). L'algoritmo deve:

    • ricevere in input gli array bidimensionali \(a[1..m][1..p]\) e \(b[1..p][1..n]\), e le dimensioni \(m\), \(p\), \(n\);

    • allocare un nuovo array bidimensionale \(c[1..m][1..n]\), inizializzato a zero;

    • usare tre cicli annidati (su \(i\), \(j\), \(k\)) per calcolare il prodotto con la formula precedente;

    • restituire l'array bidimensionale prodotto \(c\).

  2. Eseguire l'algoritmo passo per passo sulle seguenti istanze, mostrando i valori di \(k\) e \(c[i][j]\) a ogni passo del ciclo più interno:

    • Istanza 1: \(a = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\), \(b = \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix}\), \(m=p=n=2\);

    • Istanza 2: \(a = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 2 & 3 \end{bmatrix}\), \(b = \begin{bmatrix} 4 & 5 \\ 6 & 7 \end{bmatrix}\), \(m=3\), \(p=2\), \(n=2\).

Soluzione

  1. Pseudocodice per il prodotto di due array bidimensionali:

    Algoritmo: MatrixProduct

    Input: Gli array bidimensionali \(a[1..m][1..p]\) e \(b[1..p][1..n]\), le dimensioni \(m\), \(p\), \(n\)
    Output: L'array bidimensionale prodotto \(c[1..m][1..n]\)
    1function MatrixProduct(a, b, m, p, n)
    2\(c := \text{new array}[1..m][1..n]\)
    3for \(i := 1\) to \(m\) do
    4for \(j := 1\) to \(n\) do
    5\(c[i][j] \leftarrow 0\)
    6end
    7end
    8for \(i := 1\) to \(m\) do
    9for \(j := 1\) to \(n\) do
    10for \(k := 1\) to \(p\) do
    11\(c[i][j] \leftarrow c[i][j] + a[i][k] \cdot b[k][j]\)
    12end
    13end
    14end
    15return \(c\)
    16end

    • Allochiamo \(c\) come array bidimensionale \(m \times n\) e inizializziamo a zero tutti i suoi elementi con due cicli annidati.

    • Il ciclo esterno scorre le righe di \(c\), \(i = 1, 2, \dots, m\), e il ciclo intermedio le sue colonne, \(j = 1, 2, \dots, n\).

    • Il ciclo interno calcola la somma \(\sum_{k=1}^{p} a[i][k] \cdot b[k][j]\), aggiungendo un prodotto a ogni iterazione.

    • Infine, restituiamo \(c\).

  2. Esecuzione passo per passo sulle istanze.

    Istanza 1: \(a = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\), \(b = \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix}\), \(m=p=n=2\)

    \(i\) \(j\) \(k\) \(a[i][k]\) \(b[k][j]\) prodotto \(c[i][j]\) (dopo)
    \(1\) \(1\) \(1\) \(1\) \(5\) \(1 \cdot 5 = 5\) \(5\)
    \(1\) \(1\) \(2\) \(2\) \(7\) \(2 \cdot 7 = 14\) \(19\)
    \(1\) \(2\) \(1\) \(1\) \(6\) \(1 \cdot 6 = 6\) \(6\)
    \(1\) \(2\) \(2\) \(2\) \(8\) \(2 \cdot 8 = 16\) \(22\)
    \(2\) \(1\) \(1\) \(3\) \(5\) \(3 \cdot 5 = 15\) \(15\)
    \(2\) \(1\) \(2\) \(4\) \(7\) \(4 \cdot 7 = 28\) \(43\)
    \(2\) \(2\) \(1\) \(3\) \(6\) \(3 \cdot 6 = 18\) \(18\)
    \(2\) \(2\) \(2\) \(4\) \(8\) \(4 \cdot 8 = 32\) \(50\)

    Restituisce: \(c = \begin{bmatrix} 19 & 22 \\ 43 & 50 \end{bmatrix}\)

    Istanza 2: \(a = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 2 & 3 \end{bmatrix}\), \(b = \begin{bmatrix} 4 & 5 \\ 6 & 7 \end{bmatrix}\), \(m=3\), \(p=2\), \(n=2\)

    \(i\) \(j\) \(k\) \(a[i][k]\) \(b[k][j]\) prodotto \(c[i][j]\) (dopo)
    \(1\) \(1\) \(1\) \(1\) \(4\) \(4\) \(4\)
    \(1\) \(1\) \(2\) \(0\) \(6\) \(0\) \(4\)
    \(1\) \(2\) \(1\) \(1\) \(5\) \(5\) \(5\)
    \(1\) \(2\) \(2\) \(0\) \(7\) \(0\) \(5\)
    \(2\) \(1\) \(1\) \(0\) \(4\) \(0\) \(0\)
    \(2\) \(1\) \(2\) \(1\) \(6\) \(6\) \(6\)
    \(2\) \(2\) \(1\) \(0\) \(5\) \(0\) \(0\)
    \(2\) \(2\) \(2\) \(1\) \(7\) \(7\) \(7\)
    \(3\) \(1\) \(1\) \(2\) \(4\) \(8\) \(8\)
    \(3\) \(1\) \(2\) \(3\) \(6\) \(18\) \(26\)
    \(3\) \(2\) \(1\) \(2\) \(5\) \(10\) \(10\)
    \(3\) \(2\) \(2\) \(3\) \(7\) \(21\) \(31\)

    Restituisce: \(c = \begin{bmatrix} 4 & 5 \\ 6 & 7 \\ 26 & 31 \end{bmatrix}\)

    Le prime due righe di \(a\) formano l'identità, quindi le prime due righe di \(c\) coincidono con le due righe di \(b\).