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];
int i, valore;
cout<<"inseriamo gli elementi nell'array: "<<endl;
for (i=0; i<N; i++){
cout<<"inserisci elemento: ";
cin>>a[i];
}
cout<<"Quale valore dobbiamo cercare?: ";
cin>>valore;
i=0;
while (valore!=a[i] && i<N-1) i++;
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];
int i, valore;
cout<<"inseriamo gli elementi nell'array: "<<endl;
for(i=0; i<N; i++){
cout<<"inserisci elemento: ";
cin>>a[i];
}
cout<<"Quale valore o suo multiplo dobbiamo cercare?: ";
cin>>valore;
for(i=0; i<N; i++)
if(a[i]%valore==0)
cout<<" valore trovato in posizione: "<<i;
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];
int n,valore;
cout<<"inseriamo gli elementi nell'array: "<<endl;
for(int i=0; i<N; i++){
cout<<"inserisci elemento: ";
cin>>a[i];
}
cout<<"Quanti numeri dobbiamo cercare?: ";
cin>>n;
for(int j=0;j<n;j++) {
cout<<"Dammi il numero: ";
cin>>valore;
for(i=0; i<N; i++)
if(valore==a[i])
cout<<" valore trovato in posizione: "<<i;
}
return 0;
}
Chiaramente questi sono solo dei semplici esempi di ricerca sequenziale in C++ che possono essere implementati anche con altre soluzioni.
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, media;
for(i=0; i<N; i++){
cout<<"inserisci elemento: ";
cin>>a[i];
}
//troviamo il maggiore
max=a[0];
for(i=0; i<N; i++) {
if (a[i]>max) {
max=a[i];
}
}
//troviamo il minore
min=a[0];
for(i=0; i<N; i++) {
if (a[i]<min){
min=a[i];
}
}
//troviamo la media
media=a[0];
for(i=0; i<N; i++) {
media+=a[i];
}
media=media/N;
cout<<"il valore massimo e': "<<max<<" il valore minmo e': "<<min<<endl;
cout<<"la media e': "<<media;
return 0;
}
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];
int i;
//inserimento elementi dell'array
cout<<"primo array"<<endl;
for(i=0; i<N; i++){
cout<<"inserisci elemento: ";
cin>>a[i];
}
cout<<"secondo array"<<endl;
for(i=0; i<N; i++){
cout<<"inserisci elemento: ";
cin>>b[i];
}
cout<<"array dei valori massimi"<<endl;
for(i=0; i<N; i++){
if (a[i]>b[i]) {
c[i]=a[i];
}
else {
c[i]=b[i];
}
cout<<c[i]<<endl;
}
return 0;
}
Chiaramente abbiamo realizzato solo dei semplici esercizi 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];
}
for(int i=0; i<N; i++)
if (i%2==0)
sommap += a[i];
else
sommad += a[i];
cout<<"somma pari: "<<sommap<<" somma 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.
#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 dell'array
for(i=0; i<N; i++){
cout<<"inserisci elemento: ";
cin>>a[i];
}
cout<<"secondo array"<<endl;
for(i=0; i<N; i++){
cout<<"inserisci elemento: ";
cin>>b[i];
}
cout<<"array delle somme"<<endl;
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++.
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].
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.
