Sujet Précédent Sujet Suivant

Remplir un tableau de 52 cartes à jouer aléatoirement

Fermé
georges - 14 sept. 2014 à 14:08
KX Messages postés 16754 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 17 sept. 2014 à 18:21
Je voudrais remplir un tableau de 52 chiffres entiers, tous différents et complet en c+ avec la fonction random().
je sais tirer un a un les 52 numéros, mais le test pour vérifier s'ils ont déjà été tirés est trop long. Il doit exister une méthode je pense à mélanger les 52 chiffres plutôt qu'à les tirer aléatoirement.
Autrement dit quelqu'un peut-il m'aider à m"langer aléatoirement les 52 premiers nombres ?
Merci d'avance
A voir également:

2 réponses

Réponse 1 / 2
KX Messages postés 16754 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 020
14 sept. 2014 à 14:22
Bonjour,

Voici une idée d'algorithme :

Etape 0 : tu remplis un tableau de 52 cases avec tes 52 cartes.

Etape 1 : tu choisis un nombre aléatoirement entre 0 et 51, par exemple 12, tu permutes la carte de la case 12 avec la carte de la case 51.

Etape 2 : tu choisis un nombre aléatoirement entre 0 et 50, par exemple 36, tu permutes la carte de la case 36 avec la carte de la case 50.

Etape n : tu choisis un nombre aléatoirement entre 0 et (52-n), par exemple p, tu permutes la carte de la case p avec la carte de la case (52-n).

Etape 52 : ton tableau est mélangé.
3
Char Snipeur Messages postés 9813 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 3 octobre 2023 1 298
17 sept. 2014 à 15:11
Une méthode similaire, est d'avoir deux listes et de vider aléatoirement l'une dans l'autre. C'est même mieux, à mon avis, car ça évite des mécanismes de bord. Dans ton cas, la carte 51 de la liste de départ ne sera jamais en dernière position, sauf si tu inclus dans ton tirage aléatoire le nombre 51 (la carte permute avec elle même).
0
KX Messages postés 16754 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 020 > Char Snipeur Messages postés 9813 Date d'inscription vendredi 23 avril 2004 Statut Contributeur Dernière intervention 3 octobre 2023
17 sept. 2014 à 18:21
Bonjour,

Effectivement, quand je dis entre 0 et 51, c'est inclus (même si en pratique ce sera sûrement 52 exclu).

On pourrait bien sûr optimiser pour ne pas permuter dans le cas où la destination est identique à la source. Mais je ne sais pas ce qui est le mieux : permuter de temps en temps un pointeur pour rien, ou faire un test systématique pour savoir si on est dans le cas particulier...

Remarque : cet algorithme s'appelle Fisher-Yates Shuffle
0
Réponse 2 / 2
Utilisateur anonyme
14 sept. 2014 à 14:16
Bonjour, si tu sais manipuler les bits en C, tu peux jouer avec 52 bits (0 ou 1) pour savoir si le numéro est tiré ou non. Méthode plus simple, tenir un tableau d'entiers de 52 éléments et mettre 0 ou 1 dans l'élément correspondant. De cette façon, tu peux tester si tab[10] est égal à 1 alors la carte 11 a déjà été tirée et répéter donc l'opération pour obtenir un nouveau nombre.
0
KX Messages postés 16754 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 020
14 sept. 2014 à 15:22
Le problème avec ce genre d'algorithme c'est que tu ne sais pas combien de fois tu vas recommencer, et puisque c'est aléatoire ça peut être très grand.

Je viens de faire quelques tests et en moyenne tu vas faire 236 tirages aléatoires avant d'avoir pu obtenir chacune des 52 valeurs différentes. Mon maximum est de 1040... mais en théorie ça pourrait être infini.

Voici à quoi ressemble la courbe, en abscisse le nombre de tirages nécessaires pour obtenir 52 valeurs différentes, en ordonnées la probabilité que cela arrive (j'ai fait 10 millions d'essais)


Remarque : 52 est une valeur relativement petite, mais plus on augmente ce nombre, plus on augmente le nombre moyen de tirages aléatoires nécessaires.

Cet algorithme n'est pas vraiment le plus efficace !
0
Utilisateur anonyme
14 sept. 2014 à 16:45
C'est clair qu'en efficacité il n'est pas le meilleur, c'était ce qui m'était venu à l'idée là comme ça :-), le tiens le fait en temps constant. Mea culpa et +1.
0

Discussions similaires

Arnaque ou pas?
Pauline -
bonjour -

24 réponses