Discussion :

[parano]

Salut,

j'ai écrit une fonction qui est censée me donner un nombre aléatoire entre 0 et 100 mais lorsque je lance plusieurs fois le programme, j'obtiens toujours le même nombre 83.

Voici mon programme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
 
int random(int min, int max){
  return min +(rand() % (max-min));
}
 
int main(){
int tirage = random(0,100);
printf("%d\n",tirage);
return 0;
}

Qu'est-ce qui ne va pas ?

Merci

[Invité(e)]

Bonjour.

Pour utiliser un générateur de nombre aléatoire, il faut l'initialiser :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
#include <ctime>
int main()
{
srand(time());
/*...*/

[Laurent Gomila]

http://c.developpez.com/faq/c/?page=...#NOMBRES_srand

[parano]

J'ai réécrit ma fonction comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
int random(int min, int max){
  srand(time(0));
  return (int) (min + ((float) rand() / RAND_MAX * (max - min + 1)));
}

Je tire des lignes et des colonnes au hasard pour remplir un tableau.
Si la case est occupee, je refais un tirage aléatoire jusqu'à ce que je tombe sur une case vide.
Je demande combien de valeurs doivent être entrées.
Si cette valeur est petite, ça ne pose pas de soucis mais si cette valeur est grande, c'est à dire très proche du nombre max de cases du tableau, le programme met plusieurs minutes avant de se finir
J'ai fait tourner mon programme dans le cas d'un petit tableau 5x4 en demandant de remplir 19 cases et c'est long donc dans le cas d'un tableau de 100x100, ce sera encore pire.

Est-ce qu'il est possible de faire en sorte que la recherche de cases libres soit plus rapide ?
Si c'est le cas, comment ?

Merci

[Médinoc]

Pour commencer, peut-être en sortant srand(), supposé être appelé une seule fois dans tous le processus, de la fonction...

PS: Utiliser time(NULL) au lieu de time(0). On a une notation pour les pointeurs, autant s'en servir, cela a une bonne valeur documentaire...

[Ksempac]

Tout d'abord tu as une legere erreur dans ton programme.
Comme marqué dans la FAQ, l'initialisation avec srand ne doit avoir lieu qu'une seule fois.
EDIT : Grillé par medinoc

Concernant ton probleme, c'est tout a fait normal que ca mette longtemps : Puisque tu ne cherches que les cases vides, plus tu remplis ton tableau, plus il te faut d'iterations pour trouver une case vide.

Par exemple pour un tableau de 20 cases, si tu veux remplir 19 cases, vers la fin tu as une probabilité de 4/20 (1/5) (17eme case), 3/20 (18eme) puis seulement 2/20 (1/10) (19eme case) de reussir a tomber sur une case vide.
Donc pour remplir ces 3 dernieres cases tu as du faire quelquechose comme 20 iterations en moyenne. C'est donc loin d'etre optimal.

Maintenant pour te donner des améliorations possibles de l'algorithme il faudrait savoir ce que tu comptes en faire...
Quel genre de valeurs tu mets dedans (aleatoires ? fixées ? issus d'une liste ?) ? Quel est la proportion moyenne du tableau occupé (90% ? 10%) ? etc...

Exemple simple : si ton programme est prevu pour remplir 90% de la grille a chaque fois, tu pourrais prendre le probleme a l'envers : Tu tires au hasard et marques les 10% de cases qui ne seront pas remplies, et ensuite tu remplies les 90% restants dans l'ordre. Mais la encore c'est pas forcement applicable dans tous les cas (ca depend de ce que tu veux mettre dedans...)

[Médinoc]

Avec un srand() dans chaque appel, la valeur change une fois par seconde.
Donc, cela fait au minimum une seconde par case -->

La technique que j'utilise pour remplir un tableau, c'est généralement le remplir de manière déterministe et le mélanger ensuite.

Pour le mélanger, j'utilise généralement un tri sur des valeurs aléatoires.
Exemple en pseudocode:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct valeur { 
   int val, rnd;
}
 
int tri(struct valeur a, b)
{
   return a.rnd-b.rnd;
}
 
void remplir(struct valeur *tab, int max) {
   for( i, 1..max) {
      tab[i].val = i;
      tab[i].rnd = rand();
   }
   qsort(tab, tri);
}

Ça ne compile pas et ce n'est pas fait pour : C'est un pseudocode qui montre l'idée générale...

[thewho]

Bonjour,

J'ai réécrit ma fonction comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
int random(int min, int max){
  srand(time(0));
  return (int) (min + ((float) rand() / RAND_MAX * (max - min + 1)));
}

Il ne faut pas mettre l'initialisation du générateur

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  srand(time(0));

dans ta fonction random, mais une fois pour toute AVANT le 1er appel de cette fonction.

Est-ce qu'il est possible de faire en sorte que la recherche de cases libres soit plus rapide ?
Si c'est le cas, comment ?

Pas vraiment,

SAUF : Faire ce que je t'ai dit plus haut (sortir srand de ta fonction) devrait améliorer les choses, car l'initialisation avec time(0) te renverra toujours la même valeur, tant que l'horloge système n'aura pas suffisamment avancé pour que time(0) renvoie un résultat différent du précédent (je n'ai plus en tête la précision renvoyée par time(0), mais il y a de bonnes chances que ta boucle de génération de nombre aléatoire fasse plusieurs tours en obtenant la même initialisation).

----- Édité ---

Et hop, croisé avec Médinoc et Ksempac.