Matrici (array bidimensionali) in C++

Cos’è e come si memorizza e lavora con una matrice in C++?

Le matrici per farla breve non sono altro che array bidimensionali; cosa si intende per bidimensionali?

Capiamolo con un esempio: se per immaginare un classico array possiamo aiutarci pensando a una cassettiera i cui cassetti rappresentano le celle dell’array, per una matrice possiamo pensare a un insieme di cassettiere una a fianco all’altra, in cui analogamente ogni cassetto rappresenterà una cella della matrice.

Nelll’array ogni cassetto, e fuori di metafora ogni cella, sarà individuato da una coordinata ovvero da un numero che rappresenta l’ordine in altezza del cassetto nella cassettiera o la posizione della cella nell’array; in una matrice ogni cassetto o fupr di metafora ogni cella sarà individuata da una coppia di coordinate che rappresenteranno in quale cassettiera si trova un cassetto e di quale cassetto stiamo parlando ovvero in che riga e colonna della matrice si trova la cella prescelta.

Un altro esempio per provare a comprendere il significato di matrice è la griglia di battaglia navale, ogni casella della griglia è individuata dal numero della riga e dal numero della colonna.

Cos’è una matrice

Le matrici sono array bidimensionali ovvero insiemi ordinati* di r x c variabili dello stesso tipo, dove r è il numero di righe e c il numero di colonne.

* per ordinati non si intende i cui contenuti siano ordinati!

Vedremo poi che la bellezza delel matrici , come per gli array, è che ci si potrà muovere agevolmente tra le variabili interne di un array grazie a degli indici.

Dichiarare una matrice in C++

Per dichiarare una matrice bisogna utilizzare un’istruzione formata così:

tipoVariabile nomeMatrice [numeroRighe][numeroColonne];

Dove tipoVariabile è il tipo di dato di cui si vuole costruire la matrice (può essere int, char, float, double, bool…), mentre numeroRighe e numeroColonne devono essere dei valori costanti e rappresentano come dice il nome il numero di righe e di colonne della matrice.

Ad esempio:

//dichiaro una matrice m di int con 4 righe e 5 colonne
int m[4][5]

Come per gli array le celle delle righe e delle colonne si contano a partire da 0.

Per cui la matrice dell’esempio precedente avrà:
– 4 righe con i numeri di riga che andranno da 0 a 3,
– 5 colonne con i numeri di colonna che andranno da 0 a 4.

Lavorare con una cella della matrice in C++

Ogni cella della matrice funziona esattamente come una variabile, tuttavia per richiamarla bisogna usare il nome della matrice e indicare il numero di riga e di colonna della cella della matrice.
La seguente istrizione:

nomeMatrice [numeroRiga][numeroColonna] = valoreDaMemorizzare;

memorizza valoreDaMemorizzare nella cella della matrice nomeMatrice data dalle coordinate numeroRiga e numeroColonna 

Ad esempio l’istruzione:

m[2][4]=10;

memorizza nella cella della matrice m con nomero di riga 2 e numero di colonna 4 il valore 10.

Bisogna porre molta attenzione ai valori degli indici di riga e di colonna in C++ perché, a differenza rispetto a quanto avviene in altri linguaggi di programmazione, non vengono visualizzati errori o eccezioni se si superano i limiti del numero di righe o di colonne di una matrice, in questi casi si va a lavorare in delle aree di memoria dove chissà cosa è memorizzato.

Lavorare con tutte le celle di una matrice in C++

Per lavorare con tutte le celle di una matrice di norma la cosa più comoda è lavorare con due cicli for annidati uno dentro l’altro: uno servirà per scorrere gli indici di riga e l’altro per gli indici di colonna (o viceversa a seconda di quanto neessario).

Il seguente estratto di codice di esempio stampa il contenuto di una matrice m, una cella alla volta procedendo per riga e all’interno di ogni riga in ordine di ccrescente di colonna.

// il codice stampa il contenuto di una matrice m 
// con numeroDiRighe righe e numeroDiColonne colonne

// l'indice i scorre le righe
for(int i=0;i<numeroDiRighe;i++)
{
    //l'indice j scorre le colonne
    for(int j=0;j<numeroDiColonne;j++)
    {
        //si stampa la cella con riga i e colonna j
        cout<<m[i][j]<<" ";
    }
    //dopo ogni riga si va a capo
    cout<<endl;
}

Inizializzare una matrice in C++

inizializzazione da console

Per inizializzare una matrice a dei dati inseriti dall’utente da console di norma si procede con due for annidati:

//l'indice i scorre le righe
for(int i=0;i<numeroDiRighe;i++)
{
   //l'indice j scorre le colonne
   for(int j=0;j<numeroDiColonne;j++) 
   {
      //si memorizza il valore della cella
      //con riga i e colonna j di m
      cin>>m[i][j]; 
   }
}

Inizializzazione a zeri

Per inzializzare tutta a zero una matrice durante la dichiarazione si può usare la seguente istruzione:

int m[numeroDiRighe][numeroDiColonne]={};

che crerà una matrice m con numeroDiRighe righe e numeroDiColonne colonne con tutti zeri.

Inizializzazione a valori predefiniti

Allo stesso modo si può inizializzare una matrice a dei valori iniziali durante la dichiarazione inserendoli all’interno delle grafe divisi da virgole, questi verranno memorizzati in ordine nelle celle a partire dalla cella m[0][0] per poi passare alla cella m[0][1] fino a riempire la prima riga per poi passare alla seconda e così via, le cellenon inizializzate esplicitamente in questo caso saranno poste a zero.

Ad esempio l’estratto di codice

//si dichiara e inizializza la matrice
int m[4][3]={1,2,3,4,5};

//si stampa la matrice

//l'indice i scorre le righe
for(int i=0;i<4;i++) 
{
   //l'indice j scorre le colonne
   for(int j=0;j<3;j++) 
   {
      //si stampa la cella con riga i e colonna j di m
      cout<<m[i][j]<<" "; 
   }
//dopo ogni riga si va a capo
cout<<endl; 
}

stamperà:

1 2 3  
4 5 0 
0 0 0 
0 0 0

Esercizi con le matrici in C++

Se ora che hai capito come funzionano le matrici vuoi metterti alla prova vai alla pagina 20 esercizi matrici in C++ dove troverai un po’ di esercizi!

TRASFORMAZIONI TRA NUMERI DECIMALI IN BINARI MODULO E SEGNO E VICEVERSA

Come si rappresentano i numeri negativi coi numeri binari?
Ci sono più modalità per poterlo fare, le più famose e utilizzate sono:
– rappresentazione in binario con modulo e segno
– rappresentazione in binario in complemento a due

La rappresentazione in modulo e segno è più facile, anche se presenta alcuni difetti che andremo a mostrare successivamente.

In questo articolo affronteremo quella con modulo e segno, per quella in complemento a due rimandiamo all’articolo in merito: rappresentazione in complemento a due.

RAPPRESENTAZIONE NUMERI BINARI CON MODULO E SEGNO

La rappresentazione dei numeri binari con modulo e segno si usa appunto per rappresentare i numeri interi che, a differenza dei naturali per i quali si usa la rappresentazione dei numeri binari classica, possono essere anche negativi.
Con la rappresentazione modulo e segno è necessario sapere con quanti bit (che equivalgono a quante cifre) si vogliono rappresentare i numeri in binario prima di iniziare a procedere.

DA DECIMALE A BINARIO MODULO E SEGNO CON N BIT

1) SI PRENDE IL NUMERO IN VALORE ASSOLUTO E LO SI TRASFORMA IN BINARIO
2) SI AGGIUNGONO A SINISTRA DEL NUMERO TROVATO EVENTUALI ZERI FINO AD ARRIVARE A N-1 BIT
3) SI METTE A SINISTRA DEL NUMERO UNO ZERO SE IL NUMERO ERA POSITIVO E UN UNO SE IL NUMERO ERA NEGATIVO

Esempio
trasformare il numero decimale 6 in binario con modulo e segno con 8 bit
1) il numero decimale 6 in binario diventa 110
2) il numero 110 ha tre cifre aggiungo quattro 0 per arrivare a sette cifre: 0000110
3) aggiungo davanti uno 0 perché il numero iniziale era positivo 00000110

Esempio 2
trasformare il numero decimale -6 in binario con modulo e segno con 8 bit
1) il numero decimale -6 ha valore assoluto 6 che in binario diventa 110
2) il numero 110 ha tre cifre, aggiungo quattro 0 per arrivare a sette cifre: 0000110
3) aggiungo davanti uno 1 perché il numero iniziale era negativo 10000110

NOTA: due numeri opposti di segno hanno la stessa rappresentazione a meno della cifra più a sinistra.
Segue l’analisi di alcune problematiche di questa rappresentazione.

OVERFLOW

Cosa succede qualora volessi provare  a rappresentare il numero decimale 9 con 4 bit con modulo e segno?
Il numero decimale 9 in rappresentazione binaria “classica” si rappresenta così: 1001, (con modulo e segno con 4 bit il numero binario 1001 in decimale corrisponde a -1 😥) quindi sorge spontaneo il problema se: ho a disposizione solo 4 bit non riesco a rappresentarlo.

Generalizzando l’overflow è il problema che si manifesta quando si prova a memorizzare all’interno di un numero limitato di bit qualcosa che per cui quel numero di bit è troppo piccolo per riuscire a rappresentarlo.
In informatica questo accadimento si chiama overflow, parola inglese che vuol dire tracimare; avete presente quando vi state versando l’acqua nel bicchiere, vi distraete, continuate a versare e l’acqua esce dal bicchiere? Esatto, quello è l’overflow!
Quando si prova a memorizzare in un numero limitato di bit un numero che non ci sta avviene l’overflow; è una condizione particolare che va verificata e gestita, se non ce ne si accorge può generare errori gravi, perché si memorizza un numero per un altro senza accorgersene.

L’overflow non si verifica solo con la rappresentazione in modulo e segno ma con qualunque rappresentazione che permette di rappresentare un insieme finito di numeri.

PROBLEMI SPECIFICI DELLA RAPPRESENTAZIONE MODULO E SEGNO

La rappresentazione in complemento a due ha due problemi principali:
una doppia rappresentazione dello zero:
se lavoriamo con 8 bit abbiamo due scritture per rappresentare lo zero: quella data da tutti zeri e quella da un 1 seguito da zeri. Se ad esempio usiamo 8 bit questa scrittura 0000000 indicherà +0 e questa scrittura 1000000 indicherà -0.
si perde la possibilità di rappresentare un numero:
avendo n bit a disposizione il numero di combinazioni di n bit sono 2^n  (leggasi 2 alla n) tuttavia avendo una doppia rappresentazione dello zero sprechiamo la possibilità di rappresentare un ulteriore numero.
Per capire meglio facciamo un esempio: con 8 bit posso rappresentare i numeri da -127 a +127 che sono 255 numeri diversi (da 1 a 127 sono 127 numeri, da -1 a -127 sono altri 127 numeri, più c’è lo zero, quindi 127+127+1=255) mentre con 8 bit ho a disposizione 256 combinazioni diverse di uni e zeri cui associare dei valori.

Ricerca Binaria o Dicotomica in un array in C++ versione iterativa e ricorsiva

Come cercare un elemento all’interno di un array?
La ricerca di un elemento in un array si può sempre effettuare con il classico algoritmo di ricerca sequenziale: si verifica in ogni elemento dell’array se è presente il valore da cercare; tuttavia nel caso si abbia che fare con il problema della ricerca di un elemento in un array ordinato si può usare un algoritmo più performante che è quello della Ricerca Binaria spesso anche chiamata Ricerca Dicotomica; Qui sotto vi spiegherò il suo funzionamento proponendovi tra l’altro due versione dello stesso: una usando l’iterazione e l’altra usando la ricorsione.

Mi raccomando che la condizione necessaria per poter usare questo algoritmo con successo è che l’array sul quale lo si applica sia ordinato; se si prova ad applicarlo a un array disordianto l’algoritmo generalmente non funziona.

Versione iterativa dell’algoritmo di ricerca binaria

Per comprendere il funzionamento dell’algoritmo di ricerca binaria vi invito a guardare questo video che ho realizzato e in cui presento la sua versione iterativa e ne scrivo il codice in C++.

Qui sotto trovate il codice realizzato nel video:

codice dell'algoritmo della ricerca binaria in C++
il codice dell’algoritmo di ricerca binaria versione iterativa in C++ realizzato nel video

Al seguente link trovate il codice della ricerca binaria iterativa in C++ realizzato nel video.

Ovviamente si può implementare il codice della ricerca binaria all’interno di una funzione, in modo che poi lo si possa riutilizzare e ci si possa lavorare con array di lunghezza arbitraria.

Perché è vantaggioso l’algoritmo di ricerca binaria?
Perché l’algoritmo di ricerca binaria è più performante rispetto alla ricerca sequenziale: nel caso peggiore andrà a fare log(l) confronti tra il valore da cercare e gli elementi dell’array, dove l è la lunghezza dell’array,  rispetto agli l confronti della ricerca sequenziale.

Versione ricorsiva dell’algoritmo di ricerca binaria

Si può anche realizzare una versione ricorsiva di questo algoritmo di ricerca.

Nel video una breve spiegazione della versione ricorsiva e la realizzazione del suo codice.

Qui sotto trovate il codice realizzato nel video:

il codice in C++ dell'algoritmo della ricerca binaria in C++
il codice dell’algoritmo di ricerca binaria versione ricorsiva in C++ realizzato nel video

Al seguente link trovate il codice della ricerca binaria ricorsiva in C++ realizzato nel video.

Quanto detto della versione iterativa sul numero di confronti vale anche per la versione ricorsiva, tuttavia come regola generale è sempre bene preferire la versione iterativa, a quella ricorsiva di un algoritmo in quanto grava meno sulla memoria e diminuisce il  numero di operazioni non essendoci le operazioni relative al copiare i valori delle variabili passate per valore.