Ricerca di un elemento in un array

Ricerca di un elemento in un array

In questa lezione vedremo come effettuare la ricerca di un elemento in un array.

Nella programmazione, spesso è necessario cercare un elemento all’interno di un array. In questo articolo, esploreremo due metodi per affrontare questo problema utilizzando il linguaggio C. Il primo metodo sarà implementato senza l’uso di funzioni, mentre il secondo sfrutterà funzioni per rendere il codice più modulare e leggibile.

Ricerca di un elemento in un array – Metodo Senza Funzioni

In questa prima soluzione, affronteremo il problema senza l’ausilio di funzioni.

Il programma consente all’utente di inserire una serie di numeri in un array e dopo di cercare un numero specifico all’interno di quell’array. Alla fine, viene visualizzato il numero di volte che il numero cercato compare nell’array.

Ecco in dettaglio i passaggi che effettueremo:

  1. Viene dichiarato un array a di interi con dimensione MAX.
  2. Vengono dichiarate le variabili n (per memorizzare il numero di elementi dell’array), i (per contare gli elementi durante il loop), x (il numero da cercare nell’array) e count (per contare quante volte il numero compare nell’array).
  3. Dapprima l’utente inserisce il numero di elementi dell’array tramite scanf() e lo memorizza nella variabile n.
  4. Dopo l’utente inserisce gli elementi dell’array utilizzando un loop for, dove i varia da 0 a n-1. Ogni elemento viene memorizzato nell’array a.
  5. L’utente inserisce il numero da cercare nell’array che sarà memorizzato in una variabile x.
  6. Poi viene eseguito un loop for per attraversare tutti gli elementi dell’array. Ogni elemento viene confrontato con il numero cercato x. Se l’elemento è uguale a x, incrementa count.
  7. Alla fine del loop, il programma determina se count è uguale a zero. Se è così, il numero cercato non è stato trovato nell’array e viene stampato un messaggio appropriato. Altrimenti, viene stampato il numero di volte che il numero cercato appare nell’array.
  8. Il programma restituisce 0 per indicare il completamento senza errori.
Corsi Python
Corso su JavaScript

Algoritmo per la ricerca

Ecco dunque l’implementazione dell’algoritmo:

#include <stdio.h>
#define MAX 100

int main() {
    int a[MAX];
    int n, i, x, count = 0;

    printf("Inserisci il numero di elementi nell'array: ");
    scanf("%d", &n);

    printf("Inserisci gli elementi dell'array:\n");
    for (i = 0; i < n; i++) {
        printf("Elemento %d: ", i + 1);
        scanf("%d", &a[i]);
    }

    printf("Inserisci il numero da cercare nell'array: ");
    scanf("%d", &x);

    for (i = 0; i < n; i++) {
        if (a[i] == x) {
            count++;
        }
    }

    if (count == 0) {
        printf("Il numero %d non è stato trovato nell'array.\n", x);
    } else {
        printf("Il numero %d è stato trovato %d volte nell'array.\n", x, count);
    }

    return 0;
}

Questo metodo è semplice e diretto ma può diventare inefficiente per array molto grandi, poiché richiede un confronto con ogni elemento dell’array.

Potremmo infatti tener conto di varie ottimizzazioni, ad esempio potremmo utilizzare una tabella di frequenza, invece di attraversare l’array ogni volta per contare quante volte appare un numero. Inizializziamo un array di frequenza con dimensione pari al valore massimo possibile (ad esempio, se il massimo è 100, l’array di frequenza sarà di dimensione 101) e quindi attraversiamo l’array una volta sola, incrementando il contatore corrispondente all’indice dell’array di frequenza per ogni numero incontrato. Questo riduce la complessità temporale da O(n^2) a O(n).

#include <stdio.h>
#define MAX 100

int main() {
    int a[MAX] = {0}; // Inizializza l'array con zeri
    int freq[MAX] = {0}; // Tabella di frequenza
    int n, i, x;

    printf("Inserisci il numero di elementi nell'array: ");
    scanf("%d", &n);

    printf("Inserisci gli elementi dell'array:\n");
    for (i = 0; i < n; i++) {
        printf("Elemento %d: ", i + 1);
        scanf("%d", &a[i]);
        freq[a[i]]++; // Incrementa la frequenza del numero inserito
    }

    printf("Inserisci il numero da cercare nell'array: ");
    scanf("%d", &x);

    if (freq[x] == 0) {
        printf("Il numero %d non è stato trovato nell'array.\n", x);
    } else {
        printf("Il numero %d è stato trovato %d volte nell'array.\n", x, freq[x]);
    }

    return 0;
}

Ricerca di un elemento in un array – Metodo con le Funzioni

Sviluppiamo adesso una soluzione, utilizzando le funzioni per suddividere il codice in blocchi più gestibili e leggibili.

Svilupperemo alcune funzioni:

  1. Funzione inserisciArray: Questa funzione consente all’utente di inserire elementi nell’array. Chiede all’utente quanti elementi vuole inserire, quindi utilizza un ciclo for per leggere ciascun elemento dall’input e memorizzarlo nell’array a[]. Restituisce il numero totale di elementi inseriti.
  2. stampaArray: Questa funzione stampa tutti gli elementi dell’array. Utilizza un ciclo for per scorrere l’array e stampare ciascun elemento su una riga separata.
  3. Funzione ricercaElemento: Questa funzione cerca quante volte un certo numero appare nell’array. Chiede all’utente di inserire il numero da cercare e quindi utilizza un ciclo for per scorrere l’array e contare quante volte il numero cercato appare. Alla fine, stampa il numero di occorrenze del numero cercato nell’array.
  4. main: La funzione principale del programma si occupa di dichiarare un array a[] di dimensione MAX e una variabile n per memorizzare il numero di elementi inseriti. Dopo chiama la funzione inserisciArray per inserire gli elementi nell’array, quindi chiama la funzione stampaArray per stampare gli elementi dell’array. Infine, chiama la funzione ricercaElemento per cercare il numero specificato nell’array e stampare il risultato.

Ecco dunque il codice completo:

#include <stdio.h>
#define MAX 100

int inserisciArray(int a[]) {
    int n, i;
    printf("Quanti elementi vuoi inserire nell'array?: ");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        printf("Inserisci elemento %d: ", i + 1);
        scanf("%d", &a[i]);
    }
    return n;
}

void stampaArray(int a[], int n) {
    int i;
    printf("Elementi dell'array:\n");
    for (i = 0; i < n; i++) {
        printf("%d\t", a[i]);
    }
    printf("\n");
}

void ricercaElemento(int a[], int n) {
    int x, i, count = 0;
    printf("Inserisci il numero da cercare nell'array: ");
    scanf("%d", &x);
    for (i = 0; i < n; i++) {
        if (a[i] == x) {
            count++;
        }
    }
    if (count == 0) {
        printf("Il numero %d non è stato trovato nell'array.\n", x);
    } else {
        printf("Il numero %d è stato trovato %d volte nell'array.\n", x, count);
    }
}

int main() {
    int a[MAX], n;
    n = inserisciArray(a);
    stampaArray(a, n);
    ricercaElemento(a, n);
    return 0;
}

Quindi, questo programma fornisce un’interfaccia semplice per manipolare gli array, permettendo all’utente di inserire elementi, visualizzare gli elementi dell’array e cercare quanti volte un certo numero appare nell’array.

Corsi Python
Corso su JavaScript

Ricerca di un elemento in un array – Tabella di frequenza

Possiamo usare una soluzione che utilizza una tabella di frequenza per tenere traccia delle occorrenze di ciascun elemento presente nell’array.

Introduciamo quindi un array di frequenza freq, inizializzato con tutti gli elementi a 0. Ogni volta che incontriamo un elemento nell’array, incrementiamo il contatore corrispondente nell’array di frequenza. Alla fine, controlliamo il valore di frequenza per l’elemento cercato e stampiamo il risultato. Questo approccio riduce la complessità della ricerca a O(1), poiché stiamo semplicemente accedendo direttamente alla frequenza dell’elemento anziché scorrere l’intero array per contare le occorrenze.

Ecco dunque il codice completo:

#include <stdio.h>
#define MAX 100
#define MAX_ELEMENT 1000

int inserisciArray(int a[]) {
    int n, i;
    printf("Quanti elementi vuoi inserire nell'array?: ");
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        printf("Inserisci elemento %d: ", i + 1);
        scanf("%d", &a[i]);
    }
    return n;
}

void stampaArray(int a[], int n) {
    int i;
    printf("Elementi dell'array:\n");
    for (i = 0; i < n; i++) {
        printf("%d\t", a[i]);
    }
    printf("\n");
}

void ricercaElemento(int a[], int n) {
    int freq[MAX_ELEMENT] = {0}; // Array di frequenza
    int x, i;
    printf("Inserisci il numero da cercare nell'array: ");
    scanf("%d", &x);

    // Calcola la frequenza di ciascun elemento nell'array
    for (i = 0; i < n; i++) {
        freq[a[i]]++;
    }

    // Controlla se l'elemento è presente e stampa la sua frequenza
    if (freq[x] == 0) {
        printf("Il numero %d non è stato trovato nell'array.\n", x);
    } else {
        printf("Il numero %d è stato trovato %d volte nell'array.\n", x, freq[x]);
    }
}

int main() {
    int a[MAX], n;
    n = inserisciArray(a);
    stampaArray(a, n);
    ricercaElemento(a, n);
    return 0;
}

Conclusioni

In questa lezione abbiamo esplorato un semplice programma in linguaggio C che consente agli utenti di ricerca elementi in un array. Nelle prossime lezioni continueremo a lavorare con gli array in C.

Link utili:

Corso linguaggio C

Array o vettori

Selection sort

Merge sort

Insertion Sort

Inserire dati in una matrice

Inserire dati in una matrice

Realizziamo un algoritmo che permetta di inserire dati in una matrice, definita anche array bidimensionale, in cui le dimensioni sono definite dall’utente. Potete consultare un piccolo tutorial sulle matrici al seguente link.

Quindi i passaggi da seguire sono semplicemente questi:

  • Richiesta delle dimensioni
  • Inserimento dati
  • Visualizzazione matrice


Algoritmo in linguaggio C per inserire i dati in una matrice

Per prima cosa includiamo la libreria stdio.h tramite il comando

#include <stdio.h>

Poi definiamo il numero massimo di righe e di colonne, impostandole ad esempio al valore 100.

#define N 100
#define M 100

Quindi procediamo chiedendo di inserire il numero di righe e controllando che il valore inserito non sia maggiore di 100 (come definito sopra) e non sia minore di 1.
In poche parole se inserisco un numero minore di 1 oppure maggiore della dimensione massima delle righe il valore viene scartato e si richiede di nuovo l’inserimento.

do {
   printf("Dammi il numero di righe: ");
   scanf("%d", &m);
  } while ((m>M) || (m<1));

Lo stesso ragionamento lo facciamo pure per le colonne.

do {
    printf("Dammi il numero di colonne: ");
    scanf("%d", &n);
  } while ((n>N)|| (n<1));

Un semplice controllo dell’input insomma.

Adesso possiamo inserire i dati nella nostra matrice.
Quindi utilizziamo due cicli, uno più esterno che scandisce mediante la variabile i le righe e un altro più interno che percorre per mezzo della variabile j le colonne.
Iniziamo allora ad inserire l’elemento di posto (0,0) ovvero di riga zero e colonna zero poi l’elemento di posto (0,1) e così via.

Cioè si riempie tutta la prima riga, poi si passa alla seconda riga e così via.

printf("\nInseriamo i dati nella matrice \n");
for (i=0;i<m;i++)
   for (j=0;j<n;j++) {
        printf("Inserisci elemento di riga %d e colonna %d: ", i, j);
        scanf("%d", &a[i][j]);
    }

Infine non ci resta che visualizzare la nostra matrice. Per fare ciò utilizzeremo sempre due cicli for annidati uno nell’altro.

printf("\nStampiamo i dati \n");
    for (i=0;i<m;i++) {
    printf("\n");
       for(j=0;j<n;j++) 
         printf("\t%d", a[i][j]);                
    }

Programma completo per inserire e visualizzare i dati in una matrice.


#include <stdio.h>
#define N 100
#define M 100

int a[M][N];

main() {
int n,m,i,j;

do {
    printf("Dammi il numero di righe: ");
    scanf("%d", &m);
    } while ((m>M) || (m<1));

do {
    printf("Dammi il numero di colonne: ");
    scanf("%d", &n);
    } while ((n>N)|| (n<1));

printf("\nInseriamo i dati nella matrice \n");
for (i=0;i<m;i++)
    for(j=0;j<n;j++) {
        printf("Inserisci elemento di riga %d e colonna %d: ", i, j);
        scanf("%d", &a[i][j]);
    }

printf("\nStampiamo i dati \n");
for (i=0;i<m;i++) {
    printf("\n");
    for(j=0;j<n;j++) 
        printf("\t%d", a[i][j]);                
    }    
}   

Chiaramente ci possono essere altre soluzioni per implementare questo algoritmo, proponete pure la vostra.

Alcuni link utili:

Somma elementi diagonale principale di una matrice in C

Somma elementi cornice esterna in C

Sommare due matrici in C

Sommare i numeri di una matrice in C

Matrice trasposta in C

Prodotto tra matrici in C

Ricerca elementi in una matrice in C

Inserire dati in una matrice in C

Tavola pitagorica in C

Array multidimensionali in C

Programma sui triangoli in C

Media dei numeri in un array in C

Array con numeri random in C

Quick sort in C

Selection sort in C

Merge sort in C

Insertion Sort in C

Tavola Pitagorica in C

Tavola Pitagorica in C

Realizziamo un programma che permetta di visualizzare la tavola Pitagorica in C.

La tavola pitagorica è un classico esempio di matrice di numeri naturali, in cui ogni elemento è il prodotto dei rispettivi indici di riga e colonna. In questo articolo, esploreremo come implementare un programma in linguaggio C per generare e visualizzare la tavola pitagorica.

Introduzione alla Tavola Pitagorica

La tavola pitagorica è un’importante risorsa didattica utilizzata per insegnare le moltiplicazioni ai bambini. È composta da una griglia di numeri disposti in righe e colonne, dove il valore in ogni posizione è il risultato della moltiplicazione tra il numero di riga e il numero di colonna. Ad esempio, il valore nella riga 3 e nella colonna 4 sarebbe 3 * 4 = 12.

Notiamo dunque che la tavola pitagorica è una matrice di numeri naturali caratterizzata dal fatto che il valore presente nella posizione individuata dalla riga i e dalla colonna j è il prodotto di i per j.

Corsi Python
Corso su JavaScript

Implementazione della Tavola Pitagorica in C

Per generare la tavola pitagorica in C, utilizzeremo una matrice bidimensionale. Utilizzeremo due cicli for per iterare su ogni elemento della matrice e assegnare il valore corretto basato sull’indice di riga e colonna.

#include <stdio.h>

#define N 10
#define M 10

int main() {
    int a[M][N], i, j;
    
    // Inserimento degli elementi della tavola pitagorica
    for(i = 0; i < M; i++) { 
        for(j = 0; j < N; j++) {
            a[i][j] = (i + 1) * (j + 1);
        }
    }
    
    // Visualizzazione della tavola pitagorica
    printf("Tavola Pitagorica:\n");
    for(i = 0; i < M; i++) {
        for(j = 0; j < N; j++) {
            printf("%d\t", a[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

In questo codice, abbiamo dichiarato una matrice a di dimensioni M x N, dove M e N rappresentano rispettivamente il numero di righe e colonne della tavola pitagorica. Successivamente, abbiamo utilizzato due cicli for annidati per iterare su ogni elemento della matrice e assegnare il valore corretto basato sull’indice di riga e colonna. In particolare abbiamo usato l’istruzione a[i][j] = (i + 1) * (j + 1); che assegna a ogni elemento della matrice a il valore corrispondente nella tavola pitagorica, garantendo che i numeri vengano moltiplicati correttamente in base ai rispettivi indici di riga e colonna, e considerando che gli indici delle righe e delle colonne iniziano da 1.

Infine, abbiamo stampato la tavola pitagorica utilizzando un altro set di cicli for annidati per scorrere ogni riga e colonna della matrice.

Conclusioni

La tavola pitagorica è un esempio classico di applicazione pratica delle matrici in programmazione. Implementare un programma per generare e visualizzare la tavola pitagorica in C non solo ci aiuta a comprendere i concetti fondamentali delle matrici, ma può anche essere utile nell’ambito educativo per insegnare le moltiplicazioni ai bambini.

Alcuni link utili

Corso linguaggio C

Somma elementi cornice esterna

Come sommare i numeri di una matrice

Ricerca elementi in una matrice

Inserire dati in una matrice

Array multidimensionali

Programma sui triangoli in C

Media dei numeri in un array