Ubuntu-fr

lomdefer

besoin d'aide pour un programme en C[resolu]

Bonjour tout le monde, j'aurais besoin d'une petite aide car j'aimerais créer un petit programme en C qui serait capable de melanger une liste au hasard.
Plus precisement, on donne au programme les elements de la liste, il les met dans un tableau et ensuite melange le tableau.
Ou alors il les met dans un tableau au pif.

Merci

Dernière modification par lomdefer (Le 10/01/2008, à 10:58)

best_friend_fr

Re : besoin d'aide pour un programme en C[resolu]

Salut,

Mets ce que tu as reussi a faire, on t'aidera.

Tu dois utiliser random.

---

sudo apt-get replace langage_sms by grammaire orthographe ponctuation
La documentation est avant tout faite pour ceux qui posent les questions, et non ceux qui y répondent
Best_friend_fr

lomdefer

Re : besoin d'aide pour un programme en C[resolu]

alors voila en gros mon prog se lancerait comme ceci :
>bidule 8 7 6 2

voici le bout de code qui met les element dans un tableau.

nbre_chiffre_combi=argc-1;/* c'est le nombre d'element dans la combinaison */
in x;

for(j=0;j<=nbre_chiffre_combi;j++){
    x=atoi(argv[j+1]);
    tab[j]=x;
  }

comment se sert-on de la fonction random ??

Mathieu147

Re : besoin d'aide pour un programme en C[resolu]

comment se sert-on de la fonction random ??

...blablabla...
int i;
int n;
...blablabla...
i = rand()%n;
...blablabla...

i vaudra un nombre aléatoire entre 0 et n (ou n-1 je sais plus).

---

Pffff…

best_friend_fr

Re : besoin d'aide pour un programme en C[resolu]

i = rand()%n;

c'est un modulo, entre 0 et n-1.

---

sudo apt-get replace langage_sms by grammaire orthographe ponctuation
La documentation est avant tout faite pour ceux qui posent les questions, et non ceux qui y répondent
Best_friend_fr

csoler

Re : besoin d'aide pour un programme en C[resolu]

Si le nombre d'elements dans ta liste n'est pas un nombre premier, tu n'arriveras pas a la remplire de maniere exhaustive avec un modulo (comme propose au dessus). Je te conseille de
1 - ranger la liste des n elements dans un tableau dans l'ordre ou arrivent les elements
2 - faire N fois l'echange de deux elements pris au hazard. (pas besoin de tester que tu pioche 2 fois le meme. Au pire ca fera un coup pour rien).

En calculant la probabilite qu'un element ne soit jamais selectionne au bout de N tirages, on peut en deduire une valeur correcte de N.

CsoL

---

Mon projet chou: http://retroshare.sourceforge.net
(Voir aussi la page ubuntu-fr: http://doc.ubuntu-fr.org/retroshare)

best_friend_fr

Re : besoin d'aide pour un programme en C[resolu]

Salut,

Je ne sais pas si la methode de csoler marche, mais la methode usuellement admise et trivialement demontrables pour melanger un tableau est:

Tu fais varier i de n a 1
-> tu fais k = rand()%i
-> et tu echanges les cases k et i-1

---

sudo apt-get replace langage_sms by grammaire orthographe ponctuation
La documentation est avant tout faite pour ceux qui posent les questions, et non ceux qui y répondent
Best_friend_fr

csoler

Re : besoin d'aide pour un programme en C[resolu]

Je pense que ca revient au meme, voire en plus efficace puisque tu es sur de toucher tous les elements au bout de n passes. Merci pour le truc, je n'y avait pas pense.

---

Mon projet chou: http://retroshare.sourceforge.net
(Voir aussi la page ubuntu-fr: http://doc.ubuntu-fr.org/retroshare)

best_friend_fr

Re : besoin d'aide pour un programme en C[resolu]

Cette methode a l'avantage d'avoir toutes les positions equiprobables, dans le nombre minimal de tirages (il y a n! permutations possibles, et on tire exactement n! combinaison) Donc, je pense que c'est un bon compromis.

Pour repondre a ta methode du 6, comme n! c'est en gros du n^n, si tu veux avoir toutes les possibilites, il faut faire au moins n/2 tirages, donc tu es aussi en O(n). Seulement, prouver que toutes les solutions sont equiprobables me parait vraiment non trivial au premier abord. Je pense que ta methode favorise les boucles de petites taille
(par boucle j'entends des rotations entre des un petit nombre de cases).

Pour avoir une distribution equiprobable, je dirais qu'il faut augmenter le nombre de tirages pour arriver a un truc au moins en n^2, et peut etre meme en n! (et encore, la demonstration me semble non triviale).

---

sudo apt-get replace langage_sms by grammaire orthographe ponctuation
La documentation est avant tout faite pour ceux qui posent les questions, et non ceux qui y répondent
Best_friend_fr

abetsic

Re : besoin d'aide pour un programme en C[resolu]

à  propos de l'utilisation de l'opérateur modulo (%) pour tirer un nombre aléatoire compris entre 0 et le modulo-1 il faut savoir que ce n'est pas la meilleure façon.
Voici un extrait tiré de "man 3 rand"

"If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in

j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));

and never by anything resembling

j = 1 + (rand() % 10);

(which uses lower-order bits)."

Aurel34

Re : besoin d'aide pour un programme en C[resolu]

salut

c'est un problème classique (et utile), et la solution classique est l'algorithme de Fisher-Yates. Une recherche google me donne ça: http://www.stanford.edu/~blp/writings/clc/shuffle.html

lomdefer

Re : besoin d'aide pour un programme en C[resolu]

OK et si le nombre aleatoire revien plusieur foi, il faut que je trouve une condition...
Peut-être que je peux attribuer la valeur de 0 a la place de l'ancienne.
exemple:
tab[i]=3 au départ et ben ensuite je fait tab[i]=0 comme sa je peu mettre la condition si tab[i] != 0 alors je peu continuer sinon je recherche un autre nombre i.

demain je vous met un prototype.

merci a tous

best_friend_fr

Re : besoin d'aide pour un programme en C[resolu]

L'algo que je t'ai donne est complet, c'est a dire que pour que tout soit equiprobable, si tu tires 2 fois le meme nombre, tu echanges 2 fois (les nombres dans les cases auront change).

---

sudo apt-get replace langage_sms by grammaire orthographe ponctuation
La documentation est avant tout faite pour ceux qui posent les questions, et non ceux qui y répondent
Best_friend_fr

lomdefer

Re : besoin d'aide pour un programme en C[resolu]

Je suis désolé maus je comprend pas trop ton algo peux-tu me l'expliquer un peu mieux.Qu'est-ce que le k et le i ?? le i est l'indice ou c'est le k ??
dsl i am a novice !!

best_friend_fr

Re : besoin d'aide pour un programme en C[resolu]

Tu appelle k un indice qui va parcourir le tableau de la fin vers le debut (on appelle n la taille du tableau)

for (k=n; k>0; k--){
}

pour chaque valeur de k, tu choisis une case c situee avant lui (tu fais un rand modulo k, ou tu utilise la methode du message 10), et tui echange le contenu des cases c et k.

for (k=n; k>0; k--){
   int c = rand() % k;
   int temp = t[c];
   t[c] = t[k];
   t[k] = temp;
}

et la, ton tableau est melange.

Tu peux demontrer facilement que tous les melanges sont accessibles, et surtout, qu'ils sont tous equiprobables.

Dernière modification par best_friend_fr (Le 09/01/2008, à 23:34)

---

sudo apt-get replace langage_sms by grammaire orthographe ponctuation
La documentation est avant tout faite pour ceux qui posent les questions, et non ceux qui y répondent
Best_friend_fr

lomdefer

Re : besoin d'aide pour un programme en C[resolu]

Alors voici mon code, il marche a moitié je vais vous expliquer pourquoi mais j'arrive pas a resoudre le probleme:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define MAGNITUDE_MAX 52
typedef int tab[MAGNITUDE_MAX];  /* tableau de maximum 52 valeur */


int main(int argc, char *argv[]){
  int nbre_element,i,j,x,c,temp,k;
  tab depart;
  
  nbre_element=argc-1;

for(j=0;j<=nbre_element;j++){ /* ici on met les elements (ici des entier) dans un tableau */
    x=atoi(argv[j+1]);
    depart[j]=x;
 printf("%d ",x);
  }
printf("\n");

for (k=nbre_element; k>0; k--){  /* ici on est censer les melanger */
   c = rand() % k;
   temp = depart[c];
   depart[c] = depart[k];
   depart[k] = temp;
printf("%d ",temp);
}
printf("\n");
 exit(0);
}

alors quand je met "nbre_element=argc-1;", quand je l'essaie dans mon terminal voici l'erreur qui apparait :

./poker 1 5 8 7 9
Erreur de segmentation (core dumped)

MAis par contre quand je met "nbre_element=argc-2;" voici ce que j'obtien :

luc@luc-desktop:~/Bureau$ ./poker 1 5 8 7 9
1 5 8 7 9 
7 5 9 1

Le programme m'oubli un chiffre ce qui est normale puisque je lui donne pas tout les arguments a cause du "nbre_element=argc-2" il faut que ce soit "nbre_element=argc-1" pour qu'il ait tout les element du tableau !!

Alors comment pui-je parer a cette erreure ??

best_friend_fr

Re : besoin d'aide pour un programme en C[resolu]

Salut,

C'est bon, Il te faut juste faire un peu attention.

- Le nombre d'elements est bien argc-1. Attention, ils sont dans argv avec les indices 1 a argc-1. Il faut donc dans ta premiere boucle t'arreter a argc-1, soit nbre_elements non compris
- La liste que tu affiche n'est pas la liste melangee, mais les pivots. Fait le melange, et affiche apres ta liste
- Pas la peine de faire le zero quand tu melange, puisque ca te fera invariablement echanger le premier element avec lui meme.

---

sudo apt-get replace langage_sms by grammaire orthographe ponctuation
La documentation est avant tout faite pour ceux qui posent les questions, et non ceux qui y répondent
Best_friend_fr

lomdefer

Re : besoin d'aide pour un programme en C[resolu]

Bon voici le code qui marche :

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define MAGNITUDE_MAX 52
typedef int tab[MAGNITUDE_MAX];  /* tableau de maximum 52 valeur */


int main(int argc, char *argv[]){
  int nbre_element,i,j,x,c,temp,k;
  tab depart;
  
  nbre_element=argc-1;

for(j=0;j<nbre_element;j++){ /* ici on met les elements (ici des entier) dans un tableau */
    x=atoi(argv[j+1]);
    depart[j]=x;
 printf("%d ",x);
  }
printf("\n");

for (k=nbre_element; k>0; k--){  /* ici on est censer les melanger */
   c = rand() % k;
   temp = depart[c];
   depart[c] = depart[k];
   depart[k] = temp;
printf("%d ",temp);
}
printf("\n");
 exit(0);
}

J'ai juste un truc a dire, c'est que si je reessaie la même combinaison il y a exactement le même melange...comment pui-je avoir un meilleur melange que sa ??
Avec sa "i + rand() / (RAND_MAX / (n - i) + 1);" mais j'arrive pas a l'utiliser...
Je remplace le i par k et le n par nbre_element ??

lomdefer

Re : besoin d'aide pour un programme en C[resolu]

Et voici ce qu'il se passe quand j'utilise une grande liste !!

luc@luc-desktop:~/Bureau$ ./poker 1 5 8 7 9 8 4 6 8 45 9 3 1 7 11 56 4 6 2 
1 5 8 7 9 8 4 6 8 45 9 3 1 7 11 56 4 6 2 
8 4 45 7 8 2 1 1 11 5 8 3 4 9 56 -1078127884 7 6 9

Souci au niveau du -1078127884 non ??
Je vien de voir que si la liste a plus de 9 elements alors ça "bug" il y a un vieu nombre dans le melange...

Dernière modification par lomdefer (Le 10/01/2008, à 10:17)

best_friend_fr

Re : besoin d'aide pour un programme en C[resolu]

Pour changer de sequence a chaque fois, tu dois initialiser le generateur de nombres.

Mets
srand (time (0));
a un endroit.

Pour le gros nombre, je sais pas encore

---

sudo apt-get replace langage_sms by grammaire orthographe ponctuation
La documentation est avant tout faite pour ceux qui posent les questions, et non ceux qui y répondent
Best_friend_fr

lomdefer

Re : besoin d'aide pour un programme en C[resolu]

Et regarde ce qu'il vien de se passer maintenant :

luc@luc-desktop:~/Bureau$ ./poker 8 75 9 2
8 75 9 2 
9 8 75 2 
luc@luc-desktop:~/Bureau$ ./poker 8 75 9 2
8 75 9 2 
9 0 8 2

J'ai voulu reessaier 2 foi pour voir si j'obtenait un melenge different et sur la deuxieme foi, un 0 vien de se gisser dans le melange e le 75 a disparu...
Foulala le reponse apporte encore plus de question !!

best_friend_fr

Re : besoin d'aide pour un programme en C[resolu]

Ehh, malin !!!

Tu dois echanger depart[c] et depart[k-1], sinon, tu es en dehors des bornes !!

---

sudo apt-get replace langage_sms by grammaire orthographe ponctuation
La documentation est avant tout faite pour ceux qui posent les questions, et non ceux qui y répondent
Best_friend_fr

lomdefer

Re : besoin d'aide pour un programme en C[resolu]

A met oui quel con !!!!

lomdefer

Re : besoin d'aide pour un programme en C[resolu]

Bon ben impecable plus aucune erreur maintenant !!
Merci de tes reponses !! Sa faisait un petit moment que je m'y etait plus remis au C donc il faut que mon cerveau se reconditionne.
Merci beaucoup a tres bientà´t!
Probleme resolu !