Utilisation fonction rand et trier le tableau en c
pasc006
-
Hxyp Messages postés 401 Date d'inscription Statut Membre Dernière intervention -
Hxyp Messages postés 401 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
Voila, j'ai un exo à faire je débute en c si quelqu'un peut me donner un coup de main
Ecrire une fonction qui vérifie qu'un tableau passé en paramètre est bien `trié'.
Faire tourner ces méthodes de tri sur des tableaux de 'double' de taille 1000, 10000, 100000, 1000000 - alloués
avec la fonction malloc() -, qui seront chargés avec des valeurs aléatoires prises dans l'intervalle [-1.0 +1.0] fonction rand() + constante RANDMAX -; Mesurer le temps d'exécution - fonction clock() - de chacune des
méthodes, pour chacune des tailles de tableau (un seul programme main(), qui ne demande aucune intervention
de l'utilisateur; c'est le programme appelant qui calcule et affiche les temps d'exec, pas les fonctions.)
Voila, j'ai un exo à faire je débute en c si quelqu'un peut me donner un coup de main
Ecrire une fonction qui vérifie qu'un tableau passé en paramètre est bien `trié'.
Faire tourner ces méthodes de tri sur des tableaux de 'double' de taille 1000, 10000, 100000, 1000000 - alloués
avec la fonction malloc() -, qui seront chargés avec des valeurs aléatoires prises dans l'intervalle [-1.0 +1.0] fonction rand() + constante RANDMAX -; Mesurer le temps d'exécution - fonction clock() - de chacune des
méthodes, pour chacune des tailles de tableau (un seul programme main(), qui ne demande aucune intervention
de l'utilisateur; c'est le programme appelant qui calcule et affiche les temps d'exec, pas les fonctions.)
1 réponse
-
Bonjour,
Pour générer avec rand entre -1.0 et 1.0 vous avez RAND_MAX donc
double r = (double)rand();
va générer un nombre entre 0 et RAND_MAX, par exemple :
1504814432 si on le divise par RAND_MAX on va obligatoirement tombé sur un nombre entre 0.0 et 0.999.. Vu que le nombre généré est toujours inférieur à RAND_MAX
Maintenant à partir de là il reste à trouver le moyen de générer le "-", on sait que rand() va retourné un aléa qui peut être pair ou impair, donc on utilise modulo 2 pour savoir si l'aléa est pair ou impair et par exemple s'il est pair on lui soustrait 1. s'il est impair on ne fait rien.
double Rand() { double r=(double)rand(); if((int)r%2) { r/=RAND_MAX; r-=1; } else r/=RAND_MAX; return r; }
Il vous faudra peut-être aussi jetez un oeil sur srand : http://www.cplusplus.com/reference/cstdlib/srand/
L'allocation d'un tableau de double avec malloc peut se faire ainsi :
un pointeur de type double
double *tableau;
allocation de 1000 cases' type double
tableau=malloc(sizeof(double)*1000);
pour le remplir ensuite pouvez faire une petite fonction :
void gen(double *tab,int n)
{
int i; for(i=0;i<n;i++) tab[i]=Rand();
}
S'utilisant comme ça : gen(tableau,1000);
N'oubliez pas de libérer la mémoire avec un free(tableau) lorsque vous n'avez plus besoin du tableau.
Pour clock() utilisez CLOCKS_PER_SEC, exemple :
clock_t debut, fin;
debut=clock();
//ici on fait quelque chose
fin=clock();
//affichage de la différence en secondes :
printf("%f\n",(double)(fin-debut)/CLOCKS_PER_SEC);-
-
Ah, j'ai pensé que rand() retournait RAND_MAX-1 au maximum vu que 0 est une valeur, comme avec le reste en fait
Dans le standard «The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX.»
Et ici : http://www.cplusplus.com/reference/cstdlib/rand/
«( value % 100 ) is in the range 0 to 99
( value % 100 + 1 ) is in the range 1 to 100»
...
testez ça :#include <stdio.h> #include <stdlib.h> #include <time.h> #define test rand() % 2 int main() { int i; srand(time(NULL)); for(i=0;i<10000000;i++) if(test==2) printf("boom!\n"); return 0; }
Ça ne tombera jamais sur 2
On tombera entre 0 et 1 plutôt. Il faut diviser par RAND_MAX +1.0
Non pas entre 0 et 1 j'ai utilisé un type double la division est correcte -
Ah, j'ai pensé que rand() retournait RAND_MAX-1 au maximum vu que 0 est une valeur, comme avec le reste en fait
Non. La valeur maximum est RAND_MAX. RAND_MAX signifie que c'est la valeur maximum que peut prendre rand(). De même qu'on trouve INT_MAX, etc.
Dans le standard «The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX.»
Oui, mais RAND_MAX sera compris dedans... Ce n'est pas entre 0 et RAND_MAX mais de 0 à RAND_MAX.
«( value % 100 ) is in the range 0 to 99
( value % 100 + 1 ) is in the range 1 to 100»
Ce n'est pas un argument. Le modulo 100 est un opérateur qui te garantit d'avoir un nombre entre 0 et 99 (reste de la division).
Ça ne tombera jamais sur 2
Beh oui puisque tu fais un modulo et encore heureux. Sinon cela signifierait que la machine ne sait plus prendre le reste d'une division ;-))).
Non pas entre 0 et 1 j'ai utilisé un type double la division est correcte
Quand je dis entre 0 et 1, cela sous entend que je parle en double... Sinon j'aurais dit : 0 et 1. Ce que je voulais surtout dire c'est que quand tu disais dans ton premier post :
si on le divise par RAND_MAX on va obligatoirement tombé sur un nombre entre 0.0 et 0.999.. Vu que le nombre généré est toujours inférieur à RAND_MAX
C'est que tu te trompes. Ce n'est pas entre entre 0.0 et 0.000 puisque
(double)rand() / RAND_MAX te donne un double dans l'intervalle [0; 1] car rand() prend la valeur RAND_MAX au maximum. Il faut donc diviser par RAND_MAX+1.0 -
OH, j'ai eu du mal mais à la dernière ligne de ton explication là je viens juste de comprendre ahahah c'était *ù$^ù!
Alors oui j'ai fait une Erreur ça peut très bien tombé sur 1 ! en plus dans mon explication j'ai inversé pair et impair par rapport au code... enfin avec la moule que j'ai si RAND_MAX est impair ça donnera 0 héhéhé
Merci pour tout les détails et explications fiddy
-
