Ricerca sequenziale in C++

Ricerca sequenziale in C++

Realizziamo in questo semplice tutorial alcuni esempi che riguardano la ricerca sequenziale in C++, detta anche ricerca lineare. Vedremo in seguito invece la ricerca binaria in un array.

In una ricerca di tipo sequenziale gli elementi vengono confrontati appunto in sequenza e quando si trova il valore si termina la ricerca. Quindi tutti gli elementi al più vengono confrontati tutti con la chiave. Se l’elemento viene trovato non è necessario proseguire la ricerca.

Ricerca sequenziale di un elemento in un array in C++

Il primo degli esempi che voglio proporvi è la ricerca sequenziale di un elemento in un array.

Inseriamo gli elementi nel vettore e poi chiediamo l’elemento da ricercare per trovarne la posizione o le posizioni (chiaramente si potrebbe anche impostare un array con elementi già inizializzati).

Utilizziamo un ciclo while che continua finché l’array non è terminato oppure finché non trova l’elemento da ricercare.

#include <iostream>
using namespace std;

#define N 10

int main() {
    int a[N]; // Dichiarazione di un array di dimensione N
    int i, valore; // Dichiarazione di variabili intere per l'indice e il valore da cercare

    // Inserimento degli elementi nell'array
    cout << "Inseriamo gli elementi nell'array:" << endl;
    for (i = 0; i < N; i++) {        
        cout << "Inserisci elemento: ";
        cin >> a[i];
    }
    
    // Richiesta del valore da cercare
    cout << "Quale valore dobbiamo cercare?: ";
    cin >> valore;

    i = 0;
    // Ciclo while per cercare il valore nell'array
    while (valore != a[i] && i < N - 1) {
        i++;
    }

    // Verifica se il valore è stato trovato e se è divisibile per il valore cercato
    if (a[i] % valore == 0) {
        cout << "Valore trovato in posizione: " << i;
    } else {
        cout << "Valore non presente";
    }

    return 0;    
}

Se invece vogliamo vedere se l’elemento si trova in altre posizioni, dobbiamo continuare la ricerca. Allora avremmo potuto scrivere:

	for (i = 0; i < N; i++)	
		if (a[i] % valore == 0)
			cout << " valore trovato in posizione: " << i; 

Ricerca di un numero e dei suoi multipli

Un altro semplice esempio riguarda la ricerca di un numero e dei suoi multipli.

Per realizzare questo semplice algoritmo basterà cambiare la seguente condizione: if (a[i] % valore == 0).

Ecco dunque il listato d’esempio sulla ricerca sequenziale in C++.

#include <iostream>
using namespace std;

#define N 10

int main() {
    int a[N]; // Dichiarazione di un array di dimensione N
    int i, valore; // Dichiarazione di variabili intere per l'indice e il valore da cercare

    // Inserimento degli elementi nell'array
    cout << "Inseriamo gli elementi nell'array:" << endl;
    for (i = 0; i < N; i++) {        
        cout << "Inserisci elemento: ";
        cin >> a[i];
    }
    
    // Richiesta del valore o del suo multiplo da cercare
    cout << "Quale valore o suo multiplo dobbiamo cercare?: ";
    cin >> valore;

    // Ciclo per scorrere gli elementi dell'array
    for (i = 0; i < N; i++) {        
        // Verifica se l'elemento è un multiplo del valore cercato
        if (a[i] % valore == 0) {
            cout << "Valore trovato in posizione: " << i << endl;
        }
    }

    return 0;    
}

Ricerca di più elementi in un array

Poniamo questa volta la necessità di voler ricercare più elementi in un vettore.

Se vogliamo trovare più di un elemento in un vettore possiamo utilizzare un altro ciclo for con indice j.

#include <iostream>
using namespace std;

#define N 10

int main() {
    int a[N]; // Dichiarazione di un array di dimensione N
    int n, valore; // Dichiarazione di variabili per il numero di valori da cercare e il valore da cercare

    // Inserimento degli elementi nell'array
    cout << "Inseriamo gli elementi nell'array:" << endl;
    for (int i = 0; i < N; i++) {        
        cout << "Inserisci elemento: ";
        cin >> a[i];
    }
    
    // Richiesta del numero di valori da cercare
    cout << "Quanti numeri dobbiamo cercare?: ";
    cin >> n;

    // Ciclo per ciascun valore da cercare
    for (int j = 0; j < n; j++) { 
        cout << "Dammi il numero: ";
        cin >> valore;
        
        // Ciclo per scorrere gli elementi dell'array e cercare il valore
        for (int i = 0; i < N; i++) {
            if (valore == a[i]) {
                cout << "Valore trovato in posizione: " << i << endl;
            }
        }
    }
                
    return 0;    
}

Chiaramente questi sono solo dei semplici esempi di ricerca sequenziale in C++ che possono essere implementati anche con altre soluzioni.

Alcuni link utili

Indice argomenti linguaggio C++

Array in C++

Passaggio di parametri per valore o per riferimento

Equazioni di secondo grado in C++

Le variabili globali e loali in C++

Uso delle funzioni in C++

Funzioni in C++

Definizione di funzioni in C++

Libreria cmath

Come usare il for in C++

Massimo tra n numeri in C++

Iterazioni in C++

Ciclo while in C++

Ciclo do while

Operatori logici in C++

Esercizi con switch case in C++

If else in C++

Casting in C++

Successione di Fibonacci in C++

Esercizi con gli array in C++

Esercizi con gli array in C++

In questa lezione vedremo altri semplici esercizi con gli array in C++, al fine di comprendere meglio l’argomento.

Abbiamo, nelle scorse lezioni, già definito gli array in C++ e abbiamo anche proposto alcune esercitazioni.

Continuiamo presentando altri esercizi da poter risolvere con gli array.

Esercizio 1 con gli array in C++

Ecco il primo degli esercizi con gli array in C++ che oggi vi volevo proporre.

Inizializzare un array con numeri interi, determinare il valore massimo, il minimo e la media dei numeri.

Dichiariamo il vettore e le variabili necessarie per calcolare il max, il min, la media e l’indice i.

Inseriamo gli elementi nel vettore e dopo troviamo il maggiore. Per trovare il maggiore impostiamo il valore max uguale al primo elemento dell’array e dopo confrontiamo ciascun elemento dell’array con max. Se tale valore è maggiore allora lo sostituiamo.

Faremo lo stesso per il minimo.

Infine calcoliamo la media semplicemente sommando tutti gli elementi dell’array e infine dividendola per N, cioè il numero degli elementi.

Ecco dunque il listato completo di uno degli esercizi con gli array in C++ proposti oggi.

#include <iostream>
using namespace std;

#define N 10

int main(){
	int a[N];
	int i, max, min, sum = 0;

	// Input degli elementi nell'array
	for(i = 0; i < N; i++){		
		cout << "Inserisci elemento: ";
		cin >> a[i];
		sum += a[i];
	}

	// Inizializzazione di max e min con il primo elemento
	max = min = a[0];

	// Calcolo del massimo e del minimo
	for(i = 1; i < N; i++) {	
		if (a[i] > max) {
		     max = a[i];	
        }
		if (a[i] < min) {
		     min = a[i];
        }
	}

	// Calcolo della media
	float media = sum / (float)N;

	// Output dei risultati
	cout << "Il valore massimo è: " << max << ", il valore minimo è: " << min

Esercizio 2

Dati due array, inserire in input gli elementi. Dopo calcolare il valore massimo degli elementi con lo stesso indice ed inserire tali valori in un terzo array.

Dichiariamo i tre array e poi chiediamo l’inserimento degli elementi, per gli array a e b.

Dopo controlliamo ciascun elemento di indice uguale e inseriamo in un terzo array i valori così trovati.

Ad esempio a[0]=5 e b[0]=9, dato che 9 è maggiore di 5 allora c[0]=9.

Ecco il listato completo di uno degli esercizi con gli array in C++ che oggi vi volevo proporre.

#include <iostream>
using namespace std;

#define N 10

int main() {
    int a[N], b[N], c[N];

    // Inserimento elementi del primo array
    cout << "Primo array:" << endl;
    for(int i = 0; i < N; i++) {		
        cout << "Inserisci elemento: ";
        cin >> a[i];
    }
	
    // Inserimento elementi del secondo array
    cout << "Secondo array:" << endl;
    for(int i = 0; i < N; i++) {		
        cout << "Inserisci elemento: ";
        cin >> b[i];
    }		
	
    // Creazione dell'array dei valori massimi
    cout << "Array dei valori massimi:" << endl;
    for(int i = 0; i < N; i++) {
        c[i] = (a[i] > b[i]) ? a[i] : b[i];
        cout << c[i] << endl;
    }

    return 0;	
}

Chiaramente abbiamo realizzato solo dei semplici esercizi sugli array in C++.

Alcuni link utili

Indice argomenti linguaggio C++

Array o vettori in C++

Approfondimento vettori in C++

Esercitazione sugli array in C++

Massimo elemento di un vettore

Ricerca sequenziale in C++

Ricerca in un array ordinato

Array con numeri random

Ricerca binaria

Successione di Fibonacci in C++

Esercitazione sugli array in C++

Esercitazione sugli array in C++

Oggi faremo qualche semplice esercitazione sugli array in C++, al fine di consolidare l’argomento.

Nella scorsa lezione abbiamo visto come si dichiarano e inizializzano gli array in C++, di seguito il link per chi volesse consultare la lezione prima di affrontare gli esercizi: array in C++.

Primo esercizio

Cominciamo la nostra esercitazione sugli array in C++ con questo semplice esercizio.

Dichiarare un array di interi di 10 elementi. Popolare ciascun elemento di un array con indice pari (compreso lo zero) con il numero zero e quelli di indice dispari con il numero uno.

Scorriamo l’array con un ciclo for, utilizzando un indice i che parte da 0 e arriva ad N – 1.

Dopo controlliamo l’indice di ogni elemento e se l’indice è pari allora assegniamo all’elemento il valore zero, altrimenti gli assegniamo il valore 1.

Per controllare se un indice è pari basta verificare che il resto della divisione per due è uguale a zero: i % 2 == 0.

Stampiamo infine tutti gli elementi dell’array.

Ecco dunque il listato completo dell’esercitazione sugli array in C++.

#include <iostream>
using namespace std;

#define N 10

int main() {
    int a[N];

    for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            a[i] = 0;
        } else {
            a[i] = 1;
        }
        cout << "indice: " << i << " elemento: " << a[i] << endl;
    }   

    return 0;
}

Secondo esercizio

Propongo ancora un’esercitazione sugli array in C++.

Dichiarare un array di interi di 10 elementi. Popolarlo con dei numeri da tastiera inseriti a piacere. Dopo, sommare gli elementi con indice pari e quelli con indice dispari separatamente.

Innanzitutto dichiariamo le variabili necessarie e inizializziamo a zero le variabili sommap e sommad. Queste variabili servono a contenere rispettivamente la somma dei numeri pari e quella dei numeri dispari.

Dopo con un ciclo for inseriamo gli elementi nell’array.

Poi con un altro ciclo for leggiamo gli elementi dell’array e sommiamo separatamente gli elementi con indice pari in sommap e gli elementi con indice dispari in sommad.

Per vedere se un indice è pari basta al solito controllare che i % 2 == 0.

Ecco quindi il listato completo di quest’altra esercitazione sugli array in C++.

#include <iostream>
using namespace std;

#define N 10

int main() {
    int a[N];
    int sommap = 0, sommad = 0;
    
    // Inserimento elementi nell'array
    for(int i = 0; i < N; i++) {        
        cout << "Inserisci elemento: ";
        cin >> a[i];
    }   

    // Calcolo delle somme
    for(int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            sommap += a[i];
        } else {
            sommad += a[i];
        }
    }

    // Output delle somme
    cout << "Somma dei numeri pari: " << sommap << ", Somma dei numeri dispari: " << sommad << endl;
    
    return 0;    
}

Terza esercitazione array C++

Prendere due array a e b della stessa lunghezza (ad esempio N=10) ed inserire in input gli elementi. Dopo effettuare la somma degli elementi con indice uguale memorizzandola in un altro array c, ovviamente di uguale dimensione.

Ecco di seguito il codice completo:

#include <iostream>
using namespace std;

#define N 10

int main() {
    int a[N], b[N], c[N];
    int i, sommap = 0, sommad = 0;

    cout << "Primo array" << endl;
    // Inserimento elementi del primo array
    for (i = 0; i < N; i++) {
        cout << "Inserisci elemento: ";
        cin >> a[i];
    }

    cout << "Secondo array" << endl;
    // Inserimento elementi del secondo array
    for (i = 0; i < N; i++) {
        cout << "Inserisci elemento: ";
        cin >> b[i];
    }

    cout << "Array delle somme" << endl;
    // Calcolo e visualizzazione delle somme degli elementi
    for (i = 0; i < N; i++) {
        c[i] = a[i] + b[i];
        cout << c[i] << endl;
    }

    cout << "Somma pari: " << sommap << " somma dispari: " << sommad << endl;
    return 0;
}

Quelle proposte sono solo delle semplici esercitazioni sugli array in C++.

Alcuni link utili

Indice argomenti linguaggio C++

Array o vettori in C++

Approfondimento vettori in C++

Massimo elemento di un vettore

Esercizi con gli array

Ricerca sequenziale in C++

Ricerca in un array ordinato

Array con numeri random

Ricerca binaria


Array in C++

Array in C++

Gli array in C++ sono delle strutture omogenee che contengono elementi dello stesso tipo.

Gli array, detti anche vettori, contengono elementi dello stesso tipo, immagazzinati in locazioni di memoria contigue.

E’ possibile identificare ciascun elemento di un array tramite un indice numerico che parte da zero. Quindi ad esempio per un array di n elementi l’indice parte da 0 ed arriva ad n-1.

Un array è identificato da un nome. Occorre prestare attenzione alla scelta del nome, dando sempre nomi sensati ed evitando le keywords.

Dunque, si accede a ciascun elemento indicando il nome del vettore (array) seguito dalle parentesi quadre dove è racchiuso l’indice. Difatti, considerando un vettore a, se, ad esempio, volessi accedere all’elemento con indice 6 dovrei indicare: a[6].

Nel libro “50 algoritmi per imparare C++” parlo della libreria standard <array> che introduce una nuova classe template chiamata std::array e della libreria standard <vector> che introduce una nuova classe template chiamata std::vector . Possiamo dire che std::array è adatto quando la dimensione è fissa e nota a tempo di compilazione, invece std::vector è più flessibile e adatto quando la dimensione può variare dinamicamente a tempo di esecuzione.

Ecco il libro disponbile su Amazon:

Dichiarare un array in C++

Quindi vediamo alcuni esempi di come dichiarare un array in C++.

#define N 10
const int M=100

int A[N]; //dichiara ad esempio un array di 10 elementi

float V[10]; //dichiara un array di 10 elementi float

int B[M]; //dichiara un array di 100 elementi

int C = {3,5,6,2,1} 
//array di interi con la dimensione definita implicitamente

int D[10] = {3,5,6,2,1} 
//array di interi parzialmente inizializzato

int E[10] = {3,5,6,2,1,8,4,7,9,0} 
//array di interi totalmente inizializzato

int F[N] = {0}; 
//si può anche indicare {} inizializza gli elementi dell'array a zero

Inizializzare un array in C++ con un ciclo for

Supponiamo adesso di voler popolare un array di 11 elementi con i numeri che vanno da 0 a 50 a step di 5. In questo caso ci viene in auto un’istruzione iterativa, un ciclo, che utilizza un indice i per scorrere tutto l’array. L’indice parte da 0 e finchè non arriva a 10, all’interno del ciclo esegue la seguente operatione:

a[i]=i*5;

Cioè, alla prima iterazione, avremo: a[0] = 0*5 = 0.

Alla seconda iterazione, dopo che l’indice i è stato incrementato di 1, avremo: a[1]=1*5=5, e così via fino al numero 50.

Ecco dunque il listato completo dell’esempio di inizializzazione di un array in C++.

#include <iostream>
using namespace std;

#define N 11

int main(){
	int a[N];

	for (int i = 0; i < N; i++){		
		a[i] = i * 5;
		cout << a[i] <<" ";
	}
   return 0;
}

Inizializzazione a zero degli elementi

In questo secondo esempio inizializziamo gli elementi dell’array a zero.

#include <iostream>
using namespace std;

#define N 10

int main(){
	int a[N] = {0}; //si può anche indicare {}

	for (int i = 0; i < N; i++)	
		cout << a[i] <<" "; //stampiamo i valori per verificare

   return 0;
}

Inizializzazione parziale degli array in C++

In questo esempio i primi 4 elementi avranno valore pari a quelli specificati tra parentesi graffe, mentre i restanti 6 elementi avranno valore pari a zero.

#include <iostream>
using namespace std;

#define N 10

int main(){
	float a[N] = {0.9, 1.3, 2.4, 3.6};

	for (int i = 0; i < N; i++)	
		cout << a[i] << endl;  //stampiamo i valori per verificare
   return 0;
}

Inizializzazione array di char

Facciamo infine un esempio dove inizializziamo un array di caratteri. In questo caso i primi 5 elementi saranno inizializzati alle prime 5 lettere dell’alfabeto, i restanti 5 caratteri sono i caratteri ‘/0’.

#include <iostream>
using namespace std;
#define N 10


int main(){
	char a[N] = {'a','b','c','d','e'};

	for (int i = 0; i < N; i++)	
		cout << a[i] << endl;  //stampiamo i valori per verificare

  return 0;
}

Chiaramente questi sono solo dei semplici esempi di utilizzo degli array in C++. Nella prossima lezione ci eserciteremo ancora su questi argomenti e ne proporrò dei nuovi.

Alcuni link utili

Indice argomenti linguaggio C++

Approfondimento vettori in C++

Esercitazione sugli array in C++

Massimo elemento di un vettore

Esercizi con gli array

Ricerca sequenziale in C++

Ricerca in un array ordinato

Array con numeri random

Ricerca binaria