In questa post studiamo come implementare una funzione in linguaggio C++ per ricercare un elemento all’interno di una matrice di numeri interi (ricerca in una matrice). Se l’elemento è presente la funzione deve restituire true altrimenti false. Se ad esempio la matrice fosse:

il metodo restituirebbe true perchè il valore 2 è presente nella struttura dati.

Analisi della funzione

Per prima cosa formalizziamo quali sono i parametri che la funzione deve prendere in input e quali valori invece dà in output attraverso questo box:

Parametri in input:

• matrice: indica la struttura dati
• r: numero di righe
• c: numero di colonne
• num: numero da ricercare nella matrice

Parametri in output:

• un valore booleano true o false a seconda che la matrice contenga o meno il valore.

Funzione

Definiamo ora la funzione partendo dalla sua intestazione che possiamo costruire leggendo bene quali sono i parametri in input e il tipo di dato che viene dato in output:

bool ricercaValore(int** matrice, int r, int c, int num){

La funzione ricercaValore prende questi valori e restituisce un booleano. Vediamo ora come implementare l’algoritmo di ricerca.

La strategia che utilizziamo è la seguente: visitiamo ogni casella della matrice e se questa contiene il valore da ricercare (num) possiamo direttamente ritornare true perchè è presente.

Alla fine della visita delle caselle possiamo restituire con certezza false perchè mai si è verificato che una casella conteneva il valore ricercato (altrimenti l’algoritmo avrebbe previsto di entrare nella parte vera della selezione di controllo). Ricerca in una matrice

Per visitare ogni cella della matrice impostiamo i due for con gli indici per le righe e per le colonne:

bool ricercaValore(int** matrice, int r, int c, int num)
{
    for(int i=0; i<r; i++)
    {
      for(int j=0; j<c; j++)
      {
           //CODICE PER EFFETTUARE IL CONTROLLO
      }
    }
}

Ricordiamo per indicare la generica casella nel ciclo for possiamo scrivere matrice[i][j]:

bool ricercaValore(int** matrice, int r, int c, int num)
{
    for(int i=0; i<r; i++)
    {
      for(int j=0; j<c; j++)
      {
           if(matrice[i][j]==num)
           {  
                //il numero è presente nella cella i, j          
                return true;
           }
      }
    }
    //ho visitato tutte le celle senza mai trovare il numero
    return false;
}

Prova il codice su ideone.com

Torna a matrici