In questa lezione, esploreremo un semplice algoritmo per la ricerca di elementi uguali in un array. Utilizzeremo diverse funzioni per gestire l’inserimento degli elementi nell’array, la stampa degli elementi e la ricerca degli elementi uguali.
Nel mondo della programmazione, l’operazione di ricerca di elementi uguali in un array è un’attività comune e spesso necessaria. In questa lezione, esploreremo un semplice ma efficace algoritmo per eseguire questa operazione utilizzando il linguaggio di programmazione C. Attraverso l’implementazione di diverse funzioni, vedremo come gestire l’inserimento degli elementi nell’array, la loro visualizzazione e infine la ricerca degli elementi uguali.
Ricerca di elementi uguali in un array – Procedimento
L’algoritmo di ricerca che implementeremo funziona in modo intuitivo e diretto:
- Confronto Elementi: Iniziamo confrontando ogni elemento dell’array con gli elementi successivi.
- Identificazione di Elementi Uguali: Quando due elementi uguali vengono trovati, li visualizziamo in output.
- Continuazione del Confronto: L’algoritmo continua a confrontare gli elementi fino a quando non sono stati esaminati tutti.
Questo procedimento ci consente di individuare rapidamente e in modo efficiente gli elementi duplicati all’interno di un array, fornendo una soluzione pratica a una delle sfide più comuni nella gestione di dati in array.
Ricerca di elementi uguali in un array senza l’uso di funzioni
In questo primo approccio non utilizzeremo le funzioni.
#include <stdio.h>
#define MAX 100
int main() {
int n, i, j;
int a[MAX];
// Input del numero di elementi
printf("Inserisci il numero di elementi: ");
scanf("%d", &n);
// Input degli elementi dell'array
printf("Inserisci gli elementi dell'array:\n");
for (i = 0; i < n; i++) {
printf("Elemento %d: ", i + 1);
scanf("%d", &a[i]);
}
// Ricerca di elementi uguali
printf("Elementi uguali trovati: ");
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
if (a[i] == a[j]) {
printf("%d ", a[i]);
break; // Esci dal ciclo interno se trovi un duplicato
}
}
}
printf("\n");
return 0;
}
Questo approccio utilizza due cicli for annidati per confrontare ogni elemento con tutti gli altri nell’array. Se trova un elemento uguale, lo stampa come duplicato. Tuttavia, questo metodo può risultare inefficiente in termini di prestazioni, specialmente per array di grandi dimensioni, poiché ha una complessità computazionale di O(n^2). Un’ottimizzazione possibile consiste nell’utilizzare un algoritmo più efficiente per individuare gli elementi duplicati, riducendo la complessità computazionale dell’algoritmo. Un approccio efficace potrebbe essere l’utilizzo di un set per memorizzare gli elementi già incontrati durante la scansione dell’array. In questo modo, possiamo individuare gli elementi duplicati in modo più efficiente.
Ecco un esempio di codice che utilizza un set per trovare gli elementi duplicati:
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
#define RANGE 1000 // Massimo valore per gli elementi casuali
int main() {
int n, i;
int a[MAX];
bool set[RANGE] = {false}; // Inizializza un set di flag per memorizzare gli elementi
// Input del numero di elementi
printf("Inserisci il numero di elementi: ");
scanf("%d", &n);
// Input degli elementi dell'array
printf("Inserisci gli elementi dell'array:\n");
for (i = 0; i < n; i++) {
printf("Elemento %d: ", i + 1);
scanf("%d", &a[i]);
}
// Ricerca di elementi uguali utilizzando un set
printf("Elementi uguali trovati: ");
for (i = 0; i < n; i++) {
if (set[a[i]]) { // Se l'elemento è già presente nel set
printf("%d ", a[i]); // Stampa l'elemento duplicato
} else {
set[a[i]] = true; // Imposta il flag per l'elemento nel set
}
}
printf("\n");
return 0;
}
Con questo approccio, evitiamo il bisogno di confrontare ogni elemento con tutti gli altri nell’array, riducendo la complessità computazionale dell’algoritmo a O(n). Utilizzando un set, possiamo memorizzare gli elementi incontrati finora durante la scansione dell’array e individuare gli elementi duplicati in modo più efficiente.
Ricerca di elementi uguali in un array con l’uso di funzioni
Il codice che segue illustra l’implementazione completa dell’algoritmo in linguaggio C. Utilizzando diverse funzioni per gestire le varie operazioni, rendiamo il codice modulare, facile da leggere e manutenibile.
Ecco dunque il codice completo:
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// Funzione per l'inserimento degli elementi nell'array
int insert_array(int a[]) {
int i, n;
printf("Quanti elementi vuoi inserire?: ");
scanf("%d", &n);
for(i = 0; i < n; i++) {
printf("Inserisci elemento %d: ", i);
scanf("%d", &a[i]);
}
return n;
}
// Funzione per la stampa degli elementi dell'array
void stampa_array(int a[], int n) {
int i;
printf("Elementi dell'array: ");
for(i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
// Funzione per la ricerca di elementi uguali
void ricerca_uguali(int a[], int n) {
int i, j, found = 0;
for(i = 0; i < n - 1; i++) {
j = i + 1;
while(j < n && !found) {
if(a[i] == a[j]) {
printf("\nElementi uguali trovati: %d e %d", a[i], a[j]);
found = 1;
}
j++;
}
}
if(!found)
printf("\nNon ci sono elementi uguali nell'array.\n");
}
int main() {
int n, a[MAX];
n = insert_array(a);
stampa_array(a, n);
ricerca_uguali(a, n);
return 0;
}
Al termine si confronta la variabile che tiene traccia del conteggio e si visualizza in output il messaggio opportuno.
Ottimizzazione dell’algoritmo per la ricerca di elementi uguali in un array
Possiamo ottimizzare l’algoritmo per la ricerca di elementi uguali nell’array in C. Una possibile ottimizzazione riguarda l’uso di un approccio basato su un set, che ci consente di memorizzare gli elementi dell’array incontrati finora e verificare rapidamente se un nuovo elemento è già stato visto.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
#define RANGE 1000 // Massimo valore per gli elementi casuali
// Funzione per l'inserimento degli elementi nell'array
int insert_array(int a[]) {
int i, n;
printf("Quanti elementi vuoi inserire?: ");
scanf("%d", &n);
for(i = 0; i < n; i++) {
printf("Inserisci elemento %d: ", i);
scanf("%d", &a[i]);
}
return n;
}
// Funzione per la stampa degli elementi dell'array
void print_array(int a[], int n) {
int i;
printf("Elementi dell'array: ");
for(i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
// Funzione per la ricerca di elementi uguali
void find_duplicates(int a[], int n) {
int i, set[RANGE] = {0}; // Inizializza un set di flag per memorizzare gli elementi
printf("Elementi uguali trovati: ");
for(i = 0; i < n; i++) {
if(set[a[i]]) { // Se l'elemento è già presente nel set
printf("%d ", a[i]); // Stampa l'elemento duplicato
} else {
set[a[i]] = 1; // Imposta il flag per l'elemento nel set
}
}
printf("\n");
}
int main() {
int n, a[MAX];
n = insert_array(a);
print_array(a, n);
find_duplicates(a, n);
return 0;
}
Con questa ottimizzazione, evitiamo il bisogno di confrontare ogni elemento con tutti gli altri, riducendo la complessità computazionale e migliorando le prestazioni complessive dell’algoritmo.
Conclusioni
In questa lezione abbiamo esaminato due approcci per la ricerca di elementi uguali in un array utilizzando il linguaggio C. Nel primo approccio, abbiamo utilizzato due cicli for annidati per confrontare ogni elemento con tutti gli altri nell’array. Se troviamo un elemento uguale, lo stampiamo come duplicato. Tuttavia, questo metodo ha una complessità computazionale di O(n^2), che può diventare inefficiente per array di grandi dimensioni.
Per migliorare l’efficienza, ho dunque introdotto un secondo approccio che utilizza un set per memorizzare gli elementi già incontrati durante la scansione dell’array. Questo ci consente di individuare gli elementi duplicati in modo più efficiente, riducendo la complessità computazionale dell’algoritmo a O(n). Utilizzando un set, possiamo evitare il confronto di ogni elemento con tutti gli altri nell’array, migliorando le prestazioni complessive dell’algoritmo.
È importante considerare l’efficienza degli algoritmi quando si lavora con array di grandi dimensioni, poiché un algoritmo più efficiente può ridurre i tempi di esecuzione e migliorare le prestazioni complessive del programma. Scegliere il metodo di individuazione degli elementi duplicati dipende dalle specifiche esigenze dell’applicazione e dalle dimensioni dell’array su cui si sta lavorando.
Ci vediamo nelle prossime lezioni per parlare ancora di array e ricerca.
Alcuni link utili
Allocazione dinamica della memoria con malloc
Esercitazione sulle struct in C
Realizzare un menù di scelta in C
Come sommare gli elementi della cornice esterna
Ricerca elementi in una matrice