A voir également:
- Valeur aléatoire dans un Tableau : C
- Tableau croisé dynamique - Guide
- Tableau ascii - Guide
- Comment faire un tableau - Guide
- Trier un tableau excel - Guide
- Comment imprimer un tableau excel sur une seule page - Guide
2 réponses
Char Snipeur
Messages postés
9813
Date d'inscription
vendredi 23 avril 2004
Statut
Contributeur
Dernière intervention
3 octobre 2023
1 298
24 mars 2009 à 09:14
24 mars 2009 à 09:14
Salut.
rand() est une fonction pseudo aléatoire, c'est à dire qu'à chaque fois que tu relances le programme tu aura la même série de nombre aléatoire qui sortirons.
http://www.linux-france.org/article/man-fr/man3/rand-3.html
si tu veux un comportement plus aléatoire, il faut utiliser srand(int) au préalable qui permet d'avoir différentes séquences pseudo aléatoire, en passant par exemple l'heure à srand().
Ensuite, pour ton mélange de carte, il faut revoir l'algorithme.
Tu peux utiliser plusieurs algorithme de mélange.
Tu as une pile de carte et tu choisi une carte au hasard que tu met sur une seconde pile.
tu tires deux cartes au hasard et tu les inverses (répété n fois mélangera ton jeu)
Tu coupe, à partir d'un nombre tiré au hasard, tu inverse le début et la fin.
rand() est une fonction pseudo aléatoire, c'est à dire qu'à chaque fois que tu relances le programme tu aura la même série de nombre aléatoire qui sortirons.
http://www.linux-france.org/article/man-fr/man3/rand-3.html
si tu veux un comportement plus aléatoire, il faut utiliser srand(int) au préalable qui permet d'avoir différentes séquences pseudo aléatoire, en passant par exemple l'heure à srand().
Ensuite, pour ton mélange de carte, il faut revoir l'algorithme.
Tu peux utiliser plusieurs algorithme de mélange.
Tu as une pile de carte et tu choisi une carte au hasard que tu met sur une seconde pile.
tu tires deux cartes au hasard et tu les inverses (répété n fois mélangera ton jeu)
Tu coupe, à partir d'un nombre tiré au hasard, tu inverse le début et la fin.
"tu tires deux cartes au hasard et tu les inverses (répété n fois mélangera ton jeu) "
C'est faux.
Il faut utiliser Fisher-Yates:
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
C'est faux.
Il faut utiliser Fisher-Yates:
http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
Char Snipeur
Messages postés
9813
Date d'inscription
vendredi 23 avril 2004
Statut
Contributeur
Dernière intervention
3 octobre 2023
1 298
14 mai 2012 à 15:46
14 mai 2012 à 15:46
en quoi est-ce faux ?
Si ton algorithme consiste entièrement en cette ligne (citée), alors cela sous-entend qu'il suffit de répéter n fois: echange(rand(n), rand(n));
Et ceci ne marche pas. Je ne peux pas te faire la démonstration ici, mais pose toi juste la question: Pourquoi itérer l'échange n fois ? Pour info, ça ne te donne pas la garantie que les n éléments vont être considérés par l'algorithme. À la limite, si tu fais tendre le nombre d'itérations vers l'infini, tu peux augmenter la qualité des permutations.
Et ceci ne marche pas. Je ne peux pas te faire la démonstration ici, mais pose toi juste la question: Pourquoi itérer l'échange n fois ? Pour info, ça ne te donne pas la garantie que les n éléments vont être considérés par l'algorithme. À la limite, si tu fais tendre le nombre d'itérations vers l'infini, tu peux augmenter la qualité des permutations.
Char Snipeur
Messages postés
9813
Date d'inscription
vendredi 23 avril 2004
Statut
Contributeur
Dernière intervention
3 octobre 2023
1 298
14 mai 2012 à 16:45
14 mai 2012 à 16:45
ok, c'est surement la méthode la moins bonne de celles que je donne (à noter que la première est celle de Fisher Yates naïve que tu donnes en exemple). Le but de mélanger est de perdre toute information sur l'ordre des cartes les unes par rapport aux autres. Pour faire cela il n'y a pas besoin de prendre toutes les cartes en permutation, je ne vois toujours pas en quoi cet algorithme est faux : tu ne sais pas quelle carte ne va pas être impactée.
Démonstration rapide, par l'absurde du caractère biaisé de l'algorithme (toujours faux en 2012)
Algorithme = répéter n fois: echange(rand(n), rand(n));
Prenons n=3.
Il existe 9 ( 3*3, car deux appels a rand(3)) exécutions équiprobables pour l'itération 1, 9 pour l'itération 2, et 9 pour l'itération 3. Donc au total, 9*9*9 = 729 permutations sont possiblement générées par l'algorithme.
Or il existe 3! = 6 permutations possibles pour une liste de 3 éléments.
6 ne divise pas 729, (729/6 = 121.5), donc la répartition n'est pas équiprobable;
A noter que ceci ne donne pas la forme de la répartition, ni lesquelles sont favorisées. Ca dit juste que la répartition ne peut pas être uniforme.
Algorithme = répéter n fois: echange(rand(n), rand(n));
Prenons n=3.
Il existe 9 ( 3*3, car deux appels a rand(3)) exécutions équiprobables pour l'itération 1, 9 pour l'itération 2, et 9 pour l'itération 3. Donc au total, 9*9*9 = 729 permutations sont possiblement générées par l'algorithme.
Or il existe 3! = 6 permutations possibles pour une liste de 3 éléments.
6 ne divise pas 729, (729/6 = 121.5), donc la répartition n'est pas équiprobable;
A noter que ceci ne donne pas la forme de la répartition, ni lesquelles sont favorisées. Ca dit juste que la répartition ne peut pas être uniforme.
14 mai 2012 à 17:46
"Tu coupe [sic], à partir d'un nombre tiré au hasard, tu inverse [sic] le début et la fin."