C++ random

C++ random – La libreria del linguaggio C++ include alcune funzioni per il calcolo dei numeri pseudo casuali, ovvero dei numeri random.

Avevamo già studiato in C, come generare i numeri random in questa lezione: array con numeri random in C.

Quindi analizzeremo innanzitutto la funzione rand() in C++ che serve a generare dei numeri casuali.

La funzione rand() genera un numero che è compreso nell’intervallo tra 0 e RAND_MAX, dove RAND_MAX è un valore che cambia a seconda del compilatore usato, ad esempio nel caso di Dev C++ è 32767.

Per provarlo basta semplicemente scrivere questo piccolo programma in cui oltre all’header iostream includeremo anche l’header cstdlib.

#include <iostream>
#include <cstdlib>
using namespace std;

#define N 10

int main(){
cout<<"RAND_MAX:"<<RAND_MAX;
}

Ma la funzione rand() dà l’impressione che il numero sia casuale.

Infatti aggiungete questa linea di codice al programma precedente:

cout<<rand()<<endl;

Noterete che il numero generato, se mandate più volte in esecuzione il programma, è sempre lo stesso.

Questo succede perché il nostro numero casuale è prodotto a partire dallo stesso seme. Allora occorre intervenire proprio su questo per generare numeri casuali diversi.

Esempi c++ random

Per generare numeri casuali in C++ potremmo inizializzare i semi utilizzando la funzione srand(). Questa funzione inizializza il generatore di numeri con un valore passato come argomento.

Ad esempio srand(112233);

Facciamo dunque un esempio inserendo in un array dei numeri pseudo-casuali.

Creiamo due semi partendo da due valori diversi. Dopo con la funzione srand() passiamo i semi come argomento e poi con la funzione rand() generiamo dei numeri pseudo-casuali che inseriremo nei nostri array a e b.

#include <iostream>
#include <cstdlib>
using namespace std;

const int seme1 = 111222333; 
const int seme2 = 112233444; 

#define N 10

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

	srand(seme1);
	for (i=0; i<N; i++){		
		a[i]=rand();
	}
	
	srand(seme2);
	for (i=0; i<N; i++){
		b[i]=rand();
	}		
	
	cout<<"stampa primo array"<<endl;
	for (i=0; i<N; i++){		
		   cout<<a[i]<<endl;
	}
		
	cout<<"stampa secondo array"<<endl;
	for (i=0; i<N; i++){		
		   cout<<b[i]<<endl;
	}
	return 0;	
}

Ma ogni volta che manderemo in esecuzione il programma avremo sempre gli stessi numeri.

Uso della funzione time()

La funzione time() restituisce il numero di secondi trascorsi dal 01 Gennaio 1970 rispetto alla data e all’ora corrispondenti all’invocazione di tale funzione.

Per utilizzare questa funzione devo includere l’header ctime.

Ecco quindi il listato completo d’esempio:

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

#define N 10

int main(){
	int a[N];
	int i;

	srand(time(NULL));
	for (i=0; i<N; i++){		
		a[i]=rand();
	}	
	
	cout<<"stampa array"<<endl;
	for (i=0; i<N; i++){		
		   cout<<a[i]<<endl;
	}

	return 0;	
}

In questo modo ogni volta che manderemo in esecuzione il programma, in istanti differenti, otterremo valori diversi.

Ottenere valori random in un determinato intervallo

Adesso vedremo come generare numeri in C++ random ma in un intervallo definito.

Se utilizziamo rand()%N visualizziamo i numeri compresi tra 0 ed N-1.

Quindi ad esempio rand()%10 restituisce i numeri da 0 a 9.

Se aggiungiamo un offset l’intervallo si può modificare, ad esempio rand()%10+1 restituisce tutti i numeri da 1 a 10 anziché da 0 a 9. In pratica aggiungiamo 1 ad entrambi i numeri del range.

Quindi se ad esempio volessimo generare i numeri da 10 a 20, considerando che rand()%11 genera valori da 0 a 10, allora dovremmo aggiungere l’offset 10.

Ecco il listato completo che mostra due array inizializzati uno con i numeri random da 1 a 10 e il secondo con i numeri random da 10 a 20.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

#define N 10

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

	srand(time(NULL));
	for (i=0; i<N; i++){		
		a[i]=rand()%10+1;
	}
	
	srand(time(NULL));
	for (i=0; i<N; i++){		
		b[i]=rand()%11+10;
	}				
	
	cout<<"stampa primo array"<<endl;
	for (i=0; i<N; i++){		
		   cout<<a[i]<<endl;
	}
	
	cout<<"stampa secondo array"<<endl;
	for (i=0; i<N; i++){		
		   cout<<b[i]<<endl;
	}
		
	return 0;	
}

Questi sono solo alcuni possibili esempi sui numeri C++ random, più avanti vi mostrerò altre possibili applicazioni.

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 locali 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++

Continua la lettura su: https://www.codingcreativo.it/c-random/ Autore del post: Coding Creativo Fonte: https://www.codingcreativo.it

Articoli Correlati

Bubble Sort Python

L’algoritmo bubble sort in Python è l’argomento di questa lezione. Il bubble sort è un algoritmo di ordinamento molto semplice da implementare, ma dobbiamo dire che è anche poco efficiente.

Infatti il bubble sort è utilizzato principalmente in ambito didattico per far apprendere le logiche e le basi della programmazione.

Il funzionamento del bubble sort è questo:

Si confrontano gli elementi vicini tra di 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.

Quindi ad ogni passaggio si inserisce nell’elenco il valore successivo più grande al posto giusto.

La complessità dell’algoritmo è O(n2), sia nel caso peggiore, sia nel caso migliore.

Implementazione bubble sort in Python

Implementiamo la soluzione all’algortimo bubble sort in Python in maniera diversa rispetto agli altri linguaggi di programmazione. Questo perchè per lo scambio delle variabili in Python non è necessaria una variabile di appoggio temporanea.

In questa guida tratto l’argomento dello scambio delle variabili. Come scambiare il valore delle variabili

Dunque non sarà necessaria questa operazione:

temp = a;
a = b;
b = temp;

Ma basterà semplicemente scrivere:

a,b = b,a

Questa procedura, detta assegnazione simultanea, mi consente di snellire l’algoritmo bubble sort in Python.

def bubbleSort(array):
for j in range(0, len(array)-1):
for i in range(0, len(array)-1):
if array[i] >array[i+1]:
array[i], array[i+1] = array[i+1], array[i]

array_numbers = [54,26,93,17,77,31,44,55,20]
bubbleSort(array_numbers)

print(array_numbers)

L’algoritmo è molto semplice, basandosi sul confronto di elementi adiacenti.

Ma se l’algoritmo fosse ordinato? In ogni caso dovrei ripetere il ciclo esterno sempre n-1 volte. Possiamo pensare allora a fare delle ottimizzazioni all’algoritmo proposto.

Ottimizzazione bubble sort in Python – ordinamento per scambio con sentinella

Possiamo pensare di interrompere il ciclo for esterno, con un break, se al termine del primo ciclo interno non si è fatto alcuno scambio. Per questo scopo utilizziamo una variabile di appoggio chiamata flag, che inizializziamo a 0. Dopo, cambiamo il valore di questa variabile se nel ciclo interno si effettua almeno uno scambio. In alternativa a 0 ed 1 posso usare una variabile booleana.

Ecco il codice di esempio:

def bubbleSort(array):
for j in range(0, len(array)-1):
flag = False
for i in range(0, len(array)-1):
if array[i] >array[i+1]:
array[i], array[i+1] = array[i+1], array[i]
flag = True
if not(flag):
break

array_numbers = [54,26,93,17,77,31,44,55,20]
bubbleSort(array_numbers)

print(array_numbers)

Seconda ottimizzazione dell’algoritmo bubble sort in Python

Possiamo ottimizzare l’algoritmo bubble sort riflettendo sul fatto che ad ogni incremento di j, almeno gli ultimi j+1 elementi sono già stati ordinati. Questo in considerazione del fatto che ad ogni iterazione, l’elemento più grande è stato 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 codice completo dell’algoritmo ottimizzato:

def bubbleSort(array):
len_array = len(array)
for j in range(0, len_array-1):
flag = False
for i in range(0, len_array-1):
if array[i] >array[i+1]:
array[i], array[i+1] = array[i+1], array[i]
flag = True
len_array = len_array – 1
if not(flag):
break

array_numbers = [54,26,93,17,77,31,44,55,20]
bubbleSort(array_numbers)

Terza ottimizzazione dell’algoritmo bubble sort in Python

Un’ulteriore ottimizzazione all’algoritmo bubble sort in Python può essere sviluppata in considerazione del fatto che il ciclo interno si interrompe proprio dove è avvenuto lo scambio. Quindi, dopo ogni iterazione più elementi si trovano nella posizione definitiva e si può evitare di ordinarli nuovamente.

Occorre memorizzare la posizione ( i+1) dell’ultimo scambio effettuato in una variabile che chiameremo ad esempio pos. Dopo assegniamo alla lunghezza dell’array il valore di pos.

Ecco una possibile implementazione dell’algoritmo ottimizzato:

def bubbleSort(array):
len_array = len(array)
for j in range(0, len_array-1):
flag = False
for i in range(0, len_array-1):
if array[i] >array[i+1]:
array[i], array[i+1] = array[i+1], array[i]
flag = True
pos = i + 1
if not(flag):
break
else:
len_array = pos

print(i,j)

array_numbers = [54,26,93,17,77,31,44,55,20]
bubbleSort(array_numbers)

print(array_numbers)

Conclusioni

In questa lezione ho realizzato alcune implementazioni dell’algoritmo bubble sort in Python, cercando di ottimizzare un algoritmo semplice da implementare, ma lento. Nelle prossime lezioni spiegherò altri algoritmi di ordinamento.

Alcuni link utili

Indice tutorial sul linguaggio Python

1 – Introduzione al linguaggio Python

2 – Le variabili

3 – Operatori aritmetici e di assegnazione

4 – Stringhe

5 – Casting

6 – Input e print

7 – Primi esercizi in Python

8 – Errori in Python

9 – Script Python

10 – Scambio di variabili

11 – Modulo math

Algoritmo Bubble Sort Python

L’algoritmo bubble sort in Python è l’argomento di questa lezione. Il bubble sort è un algoritmo di ordinamento molto semplice da implementare, ma dobbiamo dire che è anche poco efficiente.

Infatti il bubble sort è utilizzato principalmente in ambito didattico per far apprendere le logiche e le basi della programmazione.

Il funzionamento del bubble sort è questo:

Si confrontano gli elementi vicini tra di 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.

Quindi ad ogni passaggio si inserisce nell’elenco il valore successivo più grande al posto giusto.

La complessità dell’algoritmo è O(n2), sia nel caso peggiore, sia nel caso migliore.

Implementazione dell’algoritmo bubble sort in Python

Implementiamo la soluzione all’algortimo bubble sort in Python in maniera diversa rispetto agli altri linguaggi di programmazione. Questo perchè per lo scambio delle variabili in Python non è necessaria una variabile di appoggio temporanea.

In questa guida tratto l’argomento dello scambio delle variabili. Come scambiare il valore delle variabili

Dunque non sarà necessaria questa operazione:

temp = a;
a = b;
b = temp;

Ma basterà semplicemente scrivere:

a,b = b,a

Questa procedura, detta assegnazione simultanea, mi consente di snellire l’algoritmo bubble sort in Python.

def bubbleSort(array):
for j in range(0, len(array)-1):
for i in range(0, len(array)-1):
if array[i] >array[i+1]:
array[i], array[i+1] = array[i+1], array[i]

array_numbers = [54,26,93,17,77,31,44,55,20]
bubbleSort(array_numbers)

print(array_numbers)

L’algoritmo è molto semplice, basandosi sul confronto di elementi adiacenti.

Ma se l’algoritmo fosse ordinato? In ogni caso dovrei ripetere il ciclo esterno sempre n-1 volte. Possiamo pensare allora a fare delle ottimizzazioni all’algoritmo proposto.

Ottimizzazione dell’algoritmo bubble sort in Python – ordinamento per scambio con sentinella

Possiamo pensare di interrompere il ciclo for esterno, con un break, se al termine del primo ciclo interno non si è fatto alcuno scambio. Per questo scopo utilizziamo una variabile di appoggio chiamata flag, che inizializziamo a 0. Dopo, cambiamo il valore di questa variabile se nel ciclo interno si effettua almeno uno scambio. In alternativa a 0 ed 1 posso usare una variabile booleana.

Ecco il codice di esempio:

def bubbleSort(array):
for j in range(0, len(array)-1):
flag = False
for i in range(0, len(array)-1):
if array[i] >array[i+1]:
array[i], array[i+1] = array[i+1], array[i]
flag = True
if not(flag):
break

array_numbers = [54,26,93,17,77,31,44,55,20]
bubbleSort(array_numbers)

print(array_numbers)

Seconda ottimizzazione dell’algoritmo bubble sort in Python

Possiamo ottimizzare l’algoritmo bubble sort riflettendo sul fatto che ad ogni incremento di j, almeno gli ultimi j+1 elementi sono già stati ordinati. Questo in considerazione del fatto che ad ogni iterazione, l’elemento più grande è stato 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 codice completo dell’algoritmo ottimizzato:

def bubbleSort(array):
len_array = len(array)
for j in range(0, len_array-1):
flag = False
for i in range(0, len_array-1):
if array[i] >array[i+1]:
array[i], array[i+1] = array[i+1], array[i]
flag = True
len_array = len_array – 1
if not(flag):
break

array_numbers = [54,26,93,17,77,31,44,55,20]
bubbleSort(array_numbers)

Terza ottimizzazione dell’algoritmo bubble sort in Python

Un’ulteriore ottimizzazione all’algoritmo bubble sort in Python può essere sviluppata in considerazione del fatto che il ciclo interno si interrompe proprio dove è avvenuto lo scambio. Quindi, dopo ogni iterazione più elementi si trovano nella posizione definitiva e si può evitare di ordinarli nuovamente.

Occorre memorizzare la posizione ( i+1) dell’ultimo scambio effettuato in una variabile che chiameremo ad esempio pos. Dopo assegniamo alla lunghezza dell’array il valore di pos.

Ecco una possibile implementazione dell’algoritmo ottimizzato:

def bubbleSort(array):
len_array = len(array)
for j in range(0, len_array-1):
flag = False
for i in range(0, len_array-1):
if array[i] >array[i+1]:
array[i], array[i+1] = array[i+1], array[i]
flag = True
pos = i + 1
if not(flag):
break
else:
len_array = pos

print(i,j)

array_numbers = [54,26,93,17,77,31,44,55,20]
bubbleSort(array_numbers)

print(array_numbers)

Conclusioni

In questa lezione ho realizzato alcune implementazioni dell’algoritmo bubble sort in Python, cercando di ottimizzare un algoritmo semplice da implementare, ma lento. Nelle prossime lezioni spiegherò altri algoritmi di ordinamento.

Alcuni link utili

Indice tutorial sul linguaggio Python

1 – Introduzione al linguaggio Python

2 – Le variabili

3 – Operatori aritmetici e di assegnazione

4 – Stringhe

5 – Casting

6 – Input e print

7 – Primi esercizi in Python

8 – Errori in Python

9 – Script Python

10 – Scambio di variabili

11 – Modulo math

Vuoi rimanere aggiornato sulle nuove tecnologie per la Didattica e ricevere suggerimenti per attività da fare in classe?

Sei un docente?

soloscuola.it la prima piattaforma
No Profit gestita dai

Volontari Per la Didattica
per il mondo della Scuola. 

 

Tutti i servizi sono gratuiti. 

Associazione di Volontariato Koinokalo Aps

Ente del Terzo Settore iscritta dal 2014
Tutte le attività sono finanziate con il 5X1000