In questa lezione svilupperemo l’algoritmo bubble sort in C++. Il bubble sort è l’algoritmo di ordinamento più semplice da implementare, ma è anche poco efficiente.
Il bubble sort è
utilizzato in ambito didattico per far apprendere le logiche e le
basi della programmazione.
Il metodo che
utilizza consiste nel confrontare elementi vicini tra loro portando
l’elemento maggiore in ultima posizione durante la prima “passata”
(eseguendo n-1 confronti), poi il secondo massimo in penultima
posizione e così via finché l’array non è ordinato.
La complessità è O(n2), sia nel caso peggiore che nel caso migliore.
Innanzitutto inseriamo gli elementi nell’array e dopo procediamo all’ordinamento.
Per fare l’ordinamento, confronto se l’elemento in posizione i è maggiore dell’elemento in posizione i +1. Se è vero effettuo lo scambio. Per scambiare gli elementi utilizzo una variabile di appoggio temp.
Il ciclo interno non è sufficiente per effettuare l’ordinamento. Dunque per ottenere l’ordinamento completo bisogna ripetere n-1 volte il procedimento e questo lo otteniamo con un ciclo for più esterno controllato dall’indice j che va da 0 a n-1.
Dunque segue il listato del bubble sort in C++.
#include <iostream>
#define N 10
using namespace std;
int main()
{
int a[N], i, j, temp;
cout << "Inserisci gli elementi:\n";
for(i = 0; i < N; i++)
cin >> a[i];
// Ordino gli elementi
for(j = 0; j < N - 1; j++)
for(i = 0; i < N - 1; i++)
if(a[i] > a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
cout << "Array ordinato con bubble sort:";
for(i = 0; i < N; i++)
cout << " " << a[i];
return 0;
}
Come potete notare l’algoritmo è molto semplice, ma purtroppo poco efficiente perché anche nel caso in cui l’array fosse ordinato ripeterebbe in ogni caso n-1 volte il ciclo esterno.
Ottimizzazione bubble sort – ordinamento per scambio con sentinella
Pensiamo a delle ottimizzazioni dell’algoritmo. Ad esempio interrompendo il ciclo esterno se al termine del ciclo interno non si è fatto nessuno scambio.
Quindi utilizziamo una variabile flag che inizializzo a zero. Dopo, nel ciclo interno se effettuo almeno uno scambio la variabile flag la imposto uguale a 1. Potevo anche utilizzare una variabile booleana.
Se rimane a zero, vuol dire che non c’è nulla da ordinare e quindi interrompo il ciclo esterno.
Con valori iniziali poco disordinati questa prima ottimizzazione porta ad un certo guadagno di tempo.
Ecco dunque il listato completo del bubble sort in C++ ottimizzato.
#include<iostream>
using namespace std;
#define N 10
int main()
{
int a[N], i, j, temp, k;
cout << "Inserisci gli elementi:\n";
for(i = 0; i < N; i++)
cin >> a[i];
// Ordino gli elementi
do {
k = 0;
for(i = 0; i < N - 1; i++)
if(a[i] > a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
k = 1;
}
} while (k == 1);
cout << "Array ordinato con bubble sort:";
for(i = 0; i < N; i++)
cout << " " << a[i];
return 0;
}
Seconda ottimizzazione dell’algoritmo bubble sort in C++
Un’altra possibile ottimizzazione si può ottenere considerando che ad ogni incremento di j almeno gli ultimi j+1 elementi sono già ordinati. Questa considerazione è possibile perché di volta in volta, per ogni iterazione, l’elemento più grande è spostato verso destra.
Quindi ad ogni iterazione accorciamo il ciclo dei confronti. Infatti all’n-esima iterazione si può fare a meno di toccare gli ultimi n-1 elementi che ormai sono nella loro posizione definitiva. Dunque decrementiamo n di uno ad ogni iterazione (- -n), in modo da diminuire di 1, di volta in volta, il numero dei confronti effettuati.
Ecco dunque il listato modificato del bubble sort in C++.
#include<iostream>
using namespace std;
int main()
{
int N = 6;
int a[N], i, j, temp, k;
cout << "Inserisci gli elementi:\n";
for(i = 0; i < N; i++)
cin >> a[i];
// Ordino gli elementi
do {
k = 0;
for(i = 0; i < N - 1; i++)
if(a[i] > a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
k = 1;
}
--N;
} while (k == 1);
cout << "Array ordinato con bubble sort ottimizzato:";
N = 6;
for(i = 0; i < N; i++)
cout << " " << a[i];
return 0;
}
Terza ottimizzazione
Facciamo un’ulteriore ottimizzazione all’algoritmo bubble sort. Infatti consideriamo che ogni ciclo interno si interrompe proprio dove, la volta prima, è avvenuto lo scambio. Pertanto alla fine di ogni iterazione più elementi si trovano nella posizione definitiva e si può evitare di trattarli.
Quindi memorizziamo in una variabile x la posizione i+1 dell’ultimo scambio e ad n assegniamo il valore di x.
#include<iostream>
using namespace std;
int main()
{
int N = 6;
int a[N], i, j, temp, k, x;
cout << "Inserisci gli elementi:\n";
for(i = 0; i < N; i++)
cin >> a[i];
// Ordino gli elementi
do {
k = 0;
for(i = 0; i < N - 1; i++)
if(a[i] > a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
k = 1;
x = i + 1;
}
N = x;
} while (k == 1);
cout << "Array ordinato con bubble sort ottimizzato:";
N = 6;
for(i = 0; i < N; i++)
cout << " " << a[i];
return 0;
}
Questi esempi di implementazione del bubble sort in C++ sono utili a scopo didattico.
L’algoritmo di ricerca binaria o dicotomica è un algoritmo che viene utilizzato per trovare elementi in un array ordinato. Si usa il termine dicotomica (dal greco: tagliare in due) perché si procede a divisioni successive dell’array.
Questo algoritmo rientra dunque nella famiglia degli algoritmi che utilizzano il metodo divide et impera.
Utilizzare la ricerca binaria in un array ordinato è molto più efficiente rispetto alla ricerca sequenziale, in special modo se l’array contiene tanti elementi.
Questo algoritmo viene utilizzato in molte applicazioni in maniera naturale, come ad esempio il gioco indovina numero, la ricerca di una parola in un vocabolario o la ricerca di un contatto telefonico in una rubrica. Quindi ad esempio in quest’ultimo caso, si apre la rubrica, verso l’elemento centrale (poi vedremo come migliorare la ricerca con un algoritmo di ricerca interpolato), quindi si confronta il valore trovato con la chiave da cercare.
Se la chiave è uguale abbiamo trovato subito l’elemento.
Altrimenti, se la chiave è maggiore allora si confronta con i valori successivi, scartando quelli precedenti, cioè gli elementi a destra del valore centrale.
Infine se la chiave è minore si confronta con i valori precedenti, scartando i successivi, cioè gli elementi a sinistra del valore centrale.
Questo chiaramente per un array ordinato in ordine crescente.
Algoritmo di ricerca binaria in C++
Quindi iniziamo confrontando l’elemento x da ricercare con l’elemento intermedio dell’array. L’indice m di questo elemento viene calcolato sommando l’indice inferiore i dell’array in posizione 0 con quello superiore j in posizione N-1 e dividendolo per due: m=(i+j)/2.
Quindi si possono presentare i casi descritti sopra per cui se l’elemento coincide con x allora setto la variabile pos a 1 in modo da uscire dal do while. Altrimenti continuo a cercare tra i valori maggiori o minori a seconda che la chiave x sia maggiore o minore. In ogni caso continuo a cercare finché i non sarà minore o uguale a j.
Ecco quindi il listato completo dell’algoritmo per la ricerca binaria in C++.
#include <iostream>
using namespace std;
#define x 15
#define N 5
int main() {
int a[N] = {1, 5, 8, 10, 15}; // Dichiarazione e inizializzazione dell'array ordinato
int i = 0, j = N - 1, m, pos = -1; // Inizializzazione degli indici e variabile per la posizione del numero trovato
// Ciclo di ricerca binaria
do {
m = (i + j) / 2; // Calcolo dell'indice medio
if (a[m] == x) { // Se il numero è stato trovato
pos = m; // Memorizza la posizione del numero
} else if (a[m] < x) { // Se il numero nella posizione media è minore di x, cerca nella metà superiore
i = m + 1;
} else { // Se il numero nella posizione media è maggiore di x, cerca nella metà inferiore
j = m - 1;
}
} while (i <= j && pos == -1); // Continua finché gli indici non si sovrappongono o il numero è stato trovato
// Stampa il risultato
if (pos != -1) {
cout << "Numero trovato in posizione: " << pos << endl;
} else {
cout << "Numero non trovato" << endl;
}
return 0;
}
Il caso peggiore si ha quando la chiave non viene trovata nell’array e in questo caso l’iterazione viene eseguita log2 N volte.
La ricerca binaria ha quindi complessità asintotica O(log N). Spesso infatti questo algoritmo viene definito di ricerca logaritmica.
Ricordiamo che la
ricerca sequenziale invece
passa da O(n) come caso peggiore a O(n/2) nel caso medio, fino a O(1)
se l’elemento si trova in prima posizione.
Prossimamente vedremo l’algoritmo per la ricerca binaria sviluppato in maniera ricorsiva.
Proponiamo un problema di ricerca in un array ordinato.
Prendere in input un array di N numeri interi, ordinato in modo crescente. Viene fornito in input un numero intero X. Dire se nell’array è presente una coppia di numeri tali che sommati diano come risultato il numero X.
Dato che l’array è ordinato posso procedere in questo modo:
Prendo due indici i e j. Faccio in modo che il primo indice parta da 1 e il secondo invece dall’ultimo elemento.
Sommo quindi i due elementi puntati dai due indici e dopo controllo se la somma è uguale ad un numero X preso in input.
Se vero ho già trovato la coppia di numeri, altrimenti, se la somma è inferiore scorro l’indice i, in quanto ho bisogno di un numero maggiore. Mentre se la somma è superiore scorro l’indice j, in quanto ho bisogno di un numero inferiore.
Allego il listato completo della ricerca in un array ordinato in cui ho già inizializzato l’array con 5 elementi.
#include <iostream>
using namespace std;
#define x 15
#define N 5
int main() {
int a[N] = {1, 3, 5, 10, 11}; // Dichiarazione e inizializzazione dell'array
int i = 0; // Inizializzazione dell'indice di partenza
int j = N - 1; // Inizializzazione dell'indice finale
int somma; // Variabile per memorizzare la somma di due elementi
// Ciclo per trovare la coppia di numeri che somma x
while (i < j) {
somma = a[i] + a[j]; // Calcolo della somma di due elementi
if (somma == x) { // Se la somma è uguale a x, la coppia è stata trovata
cout << "Coppia trovata, numeri in posizione: " << i << ", " << j << endl;
break; // Esci dal ciclo
} else if (somma < x) { // Se la somma è minore di x, aumenta l'indice i
i++;
} else { // Se la somma è maggiore di x, diminuisci l'indice j
j--;
}
}
return 0;
}
Chiaramente potete anche inserire voi N numeri nell’array e poi effettuare la ricerca degli elementi la cui somma deve essere uguale a X.
Questo è solo un esempio di come effettuare la ricerca in un array ordinato, proponete pure le vostre soluzioni così da discuterne assieme.
In questo tutorial impareremo a creare un semplicissimo jQuery slider.
Realizzeremo questo slider utilizzando i metodi che abbiamo studiato in precedenza, ma più avanti vedremo altri metodi con cui poter realizzare uno slider in jQuery.
Quindi i metodi che ci serviranno per questo esempio sono: fadeIn(), fadeOut(), eq(), click(), addClass() e removeClass().
Esempio di utilizzo di jQuery slider
Potete vedere l’esempio seguendo il link: slider immagini con jQuery (ho messo un po’ di immagini della mia città, voi mettete pure le immagini che preferite).
Scegliete 5 immagini qualsiasi e salvatele nella cartella images, chiaramente il numero delle immagini può essere superiore o inferiore.
Codice html per lo slider
Cominciamo a costruire la nostra pagina web partendo dal codice html. Inseriamo un livello (div) a cui assegniamo una classe di nome container che conterrà le nostre immagini dello slider. Quindi inseriamo le immagini utilizzando il tag figure a cui assegniamo la classe imageslide.
Poi inseriamo le frecce per scorrere lo slide. Daremo, in seguito, una formattazione con il foglio di stile per visualizzare le frecce ai lati delle immagini. Attenzione per avere la freccia verso sinistra ❮, dunque il pulsante prev dovete inserire questo carattere speciale ❮ seguito dal ; mentre per il carattere freccia destra ovvero il pulsante next ❯ dovete inserire ❯ separato dal ;.
Infine creiamo il menù di navigazione a pallini (dot o punti) che di solito va in basso. Questo menù è utile perché agevola lo scorrimento delle immagini in maniera non sequenziale.
Ecco il codice html completo per creare il nostro semplicissimo jQuery slider.
Dopo cominciamo a creare il foglio di stile, dando una formattazione adeguata.
Innanzitutto diamo margine 0 al body, in modo che le immagini risultino attaccate ai bordi.
Inoltre è importante impostare questa classe:
.imageslide{ display: none; }
Altrimenti le immagini verrebbero visualizzate una sotto l’altra. Con questa proprietà le rendo invisibili e successivamente tramite il codice jQuery ne permetto la visualizzazione.
Infatti successivamente con $(‘.imageslide:first’).show(); mostro la prima immagine.
Le frecce prev e next sono posizionate a una distanza dall’alto del 35%, con larghezza automatica, dimensione del font di 60 pixel, di colore grigio e con una trasparenza (opacity 0.7). Inoltre facciamo in modo che quando siamo sulle frecce compare la manina del mouse impostando cursor: pointer.
Poi, per posizionare la freccia destra dò un margine di soli 4 pixel dal bordo destro.
Lo stesso discorso per il menù di navigazione a pallini (dot). Creiamo i pallini di altezza e larghezza 18 px, utilizziamo la proprietà border-radius: 50% per creare gli angoli arrotondati (altrimenti avremmo dei quadrati) e li coloriamo di grigio chiaro: #ccc.
Infine la classe grigio, a cui diamo un colore grigio scuro e una trasparenza, verrà applicata ai dot quando l’immagine relativa è selezionata.
Imposto anche le media queries per le diverse visualizzazioni.
Come dicevamo con $(‘.imageslide:first’).show(); mostro la prima immagine.
Impostiamo una variabile current_img, che rappresenta l’indice delle nostre immagini, che parte da 0 e si ferma a 4, perché ho deciso di inserire 5 immagini.
Dopo selezioniamo il primo dei pallini (punti- dot) in basso e gli diamo un colore grigio scuro tramite il metodo addClass(): (‘.pulsanti>span:first’).addClass(‘grigio’);
Infatti il primo dot rappresenta la prima immagine.
Dopo costruiamo la navigazione dei pulsanti in basso, facendo in modo che quando si clicca su di un pallino l’immagine precedente si nasconde con il metodo hide() e quella selezionata compare con effetto dissolvenza grazie al metodo fadeIn().
Per selezionare l’indice corrente utilizzo il metodo eq().
Allo stesso modo ci costruiamo i pulsanti next e prev, facendo attenzione all’indice dell’immagine. Infatti, se l’indice è minore di 4 vado avanti nella sequenza, altrimenti lo riporto a 0.
Ma Euclide riuscì a risolvere il problema senza calcolare tutti i divisori!
L’idea è stata questa: anziché calcolare il MCD tra i due numeri a e b, si divide a per b e si calcola il resto r.
Dopo si ricava il MCD tra b ed r e si procede fino a quando si ha resto 0. L’ultimo divisore è il MCD cercato.
Facciamo un esempio:
Prendiamo i due numeri 40 e 15 e procediamo secondo l’algoritmo di Euclide.
Primo passaggio: a/b cioè 40/15=2 resto 10
Secondo passaggio scambiamo a con b e b con r cioè 15/10=1 resto 5
Terzo passaggio scambiamo a con b e b con r cioè 10/5=2 resto 0.
Abbiamo trovato resto zero, quindi il MCD è 5.
Facciamo ancora un altro esempio:
Consideriamo i due numeri 84 e 48.
Avremo questi passaggi:
84/48=1 resto 36
48/36=1 resto 12
36/12=3 resto 0
Allora MCD è 12.
Algoritmo di Euclide per il MCD con Scratch
Bene una volta capito il procedimento sviluppiamo l’algoritmo di Euclide con Scratch.
Innanzitutto scegliamo uno sfondo e uno sprite qualsiasi.
Dopo creiamo le variabili necessarie:
Poi realizziamo il nostro codice a blocchi.
– Prendiamo inizialmente i nostri due numeri in input.
– Dopo finché il secondo numero non diventa zero facciamo queste operazioni:
– Memorizziamo nella variabile resto il resto della divisione di numero1 per numero2.
– Nella variabile numero1 memorizziamo il valore di numero2 e nella variabile numero2 memorizziamo il resto.
Provando con l’esempio sopra:
numero1=84 e numero2=48
quindi resto=numero1%numero2 cioè resto=84%48 ovvero resto=36.
Poi memorizziamo in numero1 il valore di numero2 e in numero2 il valore di resto e quindi numero1=48 e numero2=36.
E così via, faccio questi passaggi finché non ottengo più il resto.
Notate che dopo il ciclo ho inserito un’istruzione condizionale: se il numero1 che corrisponde al nostro massimo comune divisore è negativo allora diventa positivo. Perché ad esempio il MCD(84,48)=MCD(-84,48)=MCD(84, -48)=MCD(-84, -48).
Ecco il diagramma a blocchi completo.
Chiaramente si poteva introdurre il controllo per verificare che i numeri presi in input siano interi. Provate a farlo, vi darò la soluzione in un prossimo articolo.
Come si nota l’algoritmo di Euclide per il massimo comune divisore è una soluzione molto più semplice rispetto alla precedente.
Commenti recenti