Bit(es) et probe(abilité)
Je travaille en C pour un projet pour la fac et je veux faire une fonction qui prends un nombre n entre 1 et 8 et qui renvoie un char avec n bits de remplis de façon aléatoire.
En bref, pour n==4
j'aurai un résultat du genre 01100011 (99), ou 11101000 (232), ou 00110101 (53), etc...
Il y a des solutions mais jusqu'ici j'ai rien trouvé de propre et joli...
Rand()%255 jusqu'à avoir 4 bit => SALE
11110000 et on mélange les bits => SALE
La boucle classique pour te sortir un x valeurs différentes dans un tableau => propre, mais moche pour 8 petits bits et c'est surement optimisable...
Des idées ?
Selon la fonction que t'utilises pour faire ton mélange je pense que la 2ème est vraiment pas mal.
Elle ne varie pas en fonction de n contrairement à la majorité des solutions que j'ai trouvé.
Je ne connais pas bien les bibliotheques C mais j'ai une autre solution (moins bien que ta seconde option je trouve) qui "ignore" aussi n, c'est de faire un tableau :
0 - 1
1 - 2
2 - 4
3 - 8
4 - 16
5 - 32
6 - 64
7 - 128
En gros t'instancies ton tableau, et pour chaque n tu fais un rdm sur le nombre de lignes du tableau, tu choppes la valeur et supprimes la ligne, autant de fois qu'il y a de n. (Au passage tu peux faire un if si n = 8)
En parallèle t'additionnes et t auras donc le numérique de ton char.
Un peu de la merde mais ca peut t ouvrir de nouvelles perspectives de ne pas passer par les bits.
@Oznek: C'est pas si mal ça, et en plus c'est du temps constant donc c'est pas mal. Je vais voir si il existe une solution miracle en faisant un peu de math mais ta solution est sympa.
@Golsh: c'est aussi une solution mais pour du temps constant il te faut remplir une liste chainée et des que tu as pris un element tu recolle ta chaine et un fais un rand% nbelement de la liste chainée et ainsi de suite
Et la temps est fixe est calculable a l'avance
J'arrive pas à trouver comme ça de "méthode magique", qu'est ce qui te va pas avec ta dernière méthode?
Pourquoi tu ferais pas n rand() % 8 ? Ou tu vire les doublons et rerand si tu en as.
Edit : un truc du genre
bits = malloc(sizeof(char) * 4);
count = 0;
res = "00000000";
while (count < 4)
{
tmp_bit = rand() % 8;
if (strchr(bits, tmp_bit) == NULL)
{
bits[count] = tmp_bit;
count++;
}
}
Et après tu fill ta string
@Defrabob: J'arrive pas à comprendre pourquoi t'assignes 4 octets au début et pourquoi tu fais bits[count] = tmp_bit* au lieu de *bits[tmp_bit] = 1.
@Oznek: Dans bits tu va stocker tes 4 random (qui vaudront de 1-8), il manque une partie en effet comme je l'ai dis : " Et après tu fill ta string", tu as tes 4 random bits tu les mets dans ta string de 8 bit voilà
Un truc du genre (tapé a la volée) peu etre
unsigned char Choual(char NombreBit)
{
unsigned char Choual[8];
memset(&Choual,0,sizeof(Choual));
char inc=0;
unsigned Choualteub=0;
do{
unsigned char position=rand()%8;
if(Choual[position]==0)
{
Choual[position]=1;
inc++;
}
}while(inc!=NombreBit);
for(inc=0;inc<8;inc++)
{
if(Choual[inc]!=0)Choualteub+=(1<< Choual[inc]);
}
return Choualteub;
}
@JeanKulacek: Je pense qu'il n'aime pas car si c'est un nombre supérieur à 4 ça peut commencer à faire long... De plus si c'est un 8 on sait que ca devrait donner 255 mais on va se taper la galere de la boucle avec if jusqu'à avoir de la chance.
@Oznek: ouai c'est vrai tu as raison alors faire la manip inverse si le chiffre est superieur a 4 au lieu de désigner on retire des positions
@JeanKulacek: Pourquoi pas mais du coup ça rajoute un if :/ ...
Bref je pense toujours que sa 2ème solution n'est pas mal, mais après je ne connais pas bien C il y a peut-être de quoi faire mieux.
@Oznek: C'est pas le plus gros problème, après tout on fout un if hors de la boucle, si on a n=7 on boucle 1 fois et on fait un not(Choualteub) à la fin. Le problème c'est que c'est pas un temps constant mais ça dépends du rand(), si au final je veut généraliser sur 128bits, la boucle risque de tourner inutilement plusieurs fois...
En langage pseudo algorithmique et en temps constant :
NombreDeUn = 0
NombreDeCaracteresRestants = 8
Tant que (NombreDeUn != n)
Si nombreDeCaracteresRestants = n
Remplir toute la chaine avec des 1
Sinon
Si random () < 1/n
Remplir le caractère courant avec un 1
NombreDeUn ++
FinSi
NombreDeCaracteresRestants --
FinSi
FinTantQue
@zeDrik: C'est pas du temps constant.
Je suppose que dans ta boucle, tu boucles également sur tes caractères (en revenant à 0 quand ça arrive à la fin) ? sinon c'est quoi le "caractère courant".
@Oznek: edit sur mon algo (écrit à la vasvite et avec un téléphone mobile) :
NombreDeUn = 0
NombreDeCaracteresRestants = 8
CaractereCourant = 0
Tant que (NombreDeUn != n)
Si nombreDeCaracteresRestants = n
Remplir toute la chaine avec des 1
Retourner la chaine
Sinon
Si random () < 1/n
Remplir le caractère courant avec un 1
NombreDeUn ++
FinSi
FinSi
NombreDeCaracteresRestants --
CaractereCourant ++
FinTantQue
Retourner la chaîne
J'avais mal placé mon second FinSi, effectivement, on risquait une boucle infinie.
Mais là, plus de souci et le premier test assure une ré"solution rapide siu les probabilités n'ont pas été avec nous.
Enfin, c'est en temps linéaire sur la taille de la chaîne supposée fixée à 8 (n variant entre 0 et 8), donc, c'est bien assimilable à du temps constant (O(8)).
@Myosotys: Pas besoin de boucler sur les caractères de la chaîne puisque si le nombre de caractères restant à parcourir vaut le nombre de 1 à insérer dans la chaîne, on remplit la fin de la chaîne et on sort de la fonction.
Tu ne dois accéder à ce site que si tu as au moins 18 ans ou si tu as l'âge légal pour visionner ce type de matériel dans ta juridiction locale, l’âge le plus élevé étant retenu. En outre, tu déclares et garantis que tu ne permettras aucun mineur à d'accéder à ce site ou à ces services.
En accédant à ce site, tu acceptes nos conditions d'utilisation.