In questa lezione proponiamo un esercizio sui vettori in C++.
Dato in input un array non ordinato, per ogni elemento dell’array stampare in output il successivo numero più grande. Se il numero più grande non esiste stampare in output il valore -1.
Quindi ad esempio, avendo come input:
[4, 5, 2, 25, 10]
l’output sarà pertanto:
[5 25 25 -1 -1]
Per la risoluzione di questo algoritmo sui vettori in C++, presenteremo due possibili soluzioni. Chiaramente ce ne sono delle altre, se volete potete aggiungerle nei commenti sotto.
La prima soluzione, più ovvia, ha complessità O(n2), mentre la seconda più sofisticata, ha complessità O(n) ed utilizza anche lo stack.
Prima soluzione esercizio sui vettori in C++
Nella prima soluzione dunque inizializziamo un vettore di 5 elementi e utilizziamo due cicli for.
Il ciclo più esterno scorre il vettore con un indice i che va dalla posizione 0 fino ad N-1. Mentre, il ciclo più interno utilizza un indice j che parte dalla posizione 1 fino ad arrivare ad N-1.
La variabile m rappresenta invece il valore che, di volta in volta, viene sostituito al valore corrente ed è inizializzata a -1 all’interno del ciclo più esterno.
Questa variabile non cambia valore se la condizione richiesta nel ciclo più interno non è verificata, cioè se il valore contenuto in a[i] non è minore del valore contenuto in a[j], in quanto vuol dire che non ci sono elementi maggiori.
Se invece a[i] è minore di a[j], m diventa a[j].
Ecco dunque il listato completo:
#include<iostream>
using namespace std;
#define N 5
int main() {
int a[] = {4, 5, 2, 25, 10}; // Array di input
int m, i, j;
// Iterazione attraverso gli elementi dell'array
for (i = 0; i < N; i++) {
m = -1; // Inizializzazione della variabile per il prossimo elemento maggiore
// Iterazione attraverso gli elementi successivi nell'array
for (j = i + 1; j < N; j++) {
// Se l'elemento successivo è maggiore dell'elemento attuale
if (a[i] < a[j]) {
m = a[j]; // Assegna l'elemento successivo come prossimo elemento maggiore
break; // Esci dal ciclo
}
}
cout << m << "\t"; // Stampa il prossimo elemento maggiore
}
return 0;
}
Ecco la dimostrazione dell’algoritmo passo passo:
Partendo dall’array iniziale: [4, 5, 2, 25, 10]
for (i = 0; i < N; i++) { // i=0
m = -1; //m=-1
for (j = i + 1; j < N; j++) { //j=1
if (a[i] < a[j]) { //a[0]<a[1] è vero in quanto 4 è minore di 5
m = a[j]; //quindi in m memorizzo 5
break; //esco fuori
}
}
cout<<m<<“\t”; //stampo 5 (cioè il primo valore)
}
Secondo passo:
for (i = 0; i < N; i++) { // i=1
m = -1; //m=-1
for (j = i + 1; j < N; j++) { //j=1
if (a[i] < a[j]) {
//a[1]<a[2] è falso in quanto 5 non è minore di 2
//a questo punto continuo con il ciclo interno:
for (j = i + 1; j < N; j++) { //incremento j=2
if (a[i] < a[j]) { //a[1]<a[3] è vero in quanto 5 è minore di 25
m = a[j]; //sostituisco m con 25
break; //esco fuori dal ciclo
}
}
cout << m << “\t”; //stampo 25 (cioè il secondo valore)
}
e così via, alla fine avrò in output. [5 25 25 -1 -1].
Come dicevamo la complessità è O(n2) . Infatti, se tutti gli elementi sono ordinati in ordine decrescente si ha il caso peggiore.
Seconda soluzione ottimizzata con l’uso dello stack
Nella seconda soluzione utilizzeremo lo stack, includendo quindi per semplicità l’header opportuno.
Definiamo un vettore di 5 elementi e lo inizializziamo come abbiamo fatto anche nel primo metodo.
Utilizziamo un ciclo for per i che va da N-1 fino a 0, quindi partiamo da destra.
Dunque faremo l’operazione di estrazione, pop, finché l’elemento a[i] è maggiore dell’elemento in cima allo stack o se lo stack non è vuoto.
Se lo stack è vuoto, chiaramente vuol dire che non c’è alcun elemento a destra più grande, rispetto a quello attuale e quindi inserisco -1, altrimenti prelevo l’elemento in cima.
Ho inserito volutamente queste linee di codice:
cout << “passo: ” << i << “, dimensione pila:” << s.size() << endl;
e
cout << “passo: ” << i << “, dimensione pila: ” << s.size() << “, elemento top: ” << s.top() << endl;
Per spiegare il funzionamento dell’algoritmo, ma si potevano anche omettere.
#include <iostream>
#include <stack>
using namespace std;
#define N 5
int main() {
int a[N] = {4, 5, 2, 25, 10}; // Array di input
stack<int> s; // Stack per tracciare gli elementi successivi maggiori
int v[N]; // Array per memorizzare i prossimi elementi maggiori
int i;
// Iterazione inversa attraverso gli elementi dell'array
for (i = N - 1; i >= 0; i--) {
// Finché lo stack non è vuoto e l'elemento in cima allo stack è minore dell'elemento attuale
while (!s.empty() && (s.top() < a[i]))
s.pop(); // Rimuovi gli elementi minori dall'alto dello stack
// Se lo stack è vuoto, non ci sono elementi successivi maggiori
if (s.empty()) {
v[i] = -1;
cout << "Passo: " << i << ", Dimensione stack: " << s.size() << endl;
} else {
// Altrimenti, l'elemento in cima allo stack è il prossimo elemento maggiore
v[i] = s.top();
cout << "Passo: " << i << ", Dimensione stack: " << s.size() << ", Elemento in cima allo stack: " << s.top() << endl;
}
// Aggiungi l'elemento attuale allo stack
s.push(a[i]);
}
// Stampa l'array con i prossimi elementi maggiori
for (i = 0; i < N; i++)
cout << v[i] << endl;
return 0;
}
Questi come vi dicevo sono due possibili soluzioni all’algoritmo sui vettori in C++, ma proponete pure la vostra nei commenti sotto.
Alcuni link utili
Indice argomenti sul linguaggio C++
Passaggio di parametri per valore o per riferimento
Equazioni di secondo grado in C++
Esercizi con switch case in C++
Successione di Fibonacci in C++