remplir un tableau sans doublons ...

Version imprimable

bonjour,

je suis en plein apprentissage mais je patauge : lors de mon cours (algorithmie) l'on nous a demandé de remplir un tableau de facon aleatoire (jusque-la ok ) mais sans aucun doublons, alors la ... 8O .
je viens d' y passer 5 heures mais je n'ai pas encore les connaissances necessaires.ceci dit j'ai horreur de ne pas comprendre donc si vous pouviez m'aiguiller ou m'expliquer svp.
voila ce que j'ai fait pour l'instant :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 # include <stdio.h> # include <stdlib.h> int tab[9]; int i=0; main() { do { tab[i] = rand()%10; printf ("\nvaleur %d : %d", i, tab[i]) ; i++; } while ( i<10 ); printf("\n\n"); }
autre chose , j'avais commencé par une boucle for mais je declare un tableau avec 10 emplacements et cela s'arrete au 9 ieme :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 # include <stdio.h> # include <stdlib.h> int tab[9]; int i; main() { for (i=0; i<9; i++){ tab[i]=rand()%10; printf("\nLigne %d : %d", i, tab[i]); } printf("\n"); }
la sortie du premier :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 ryo@LFS ~ $ ./test valeur 0 : 3 valeur 1 : 6 valeur 2 : 7 valeur 3 : 5 valeur 4 : 3 valeur 5 : 5 valeur 6 : 6 valeur 7 : 2 valeur 8 : 9 valeur 9 : 1
celui du deuxieme :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 ryo@LFS ~ $ ./test2 Ligne 0 : 3 Ligne 1 : 6 Ligne 2 : 7 Ligne 3 : 5 Ligne 4 : 3 Ligne 5 : 5 Ligne 6 : 6 Ligne 7 : 2 Ligne 8 : 9
desole si cela a deja poste , j'ai bien chercher une dizaine de pages et via le moteur mais je n'ai rien trouve.
merci par avance.

ps : ah oui , je ne retourne pas en cours avant deux semaines, c'est pour eviter ma desiocialisation que je poste :D

09/11/2005, 04h49
afrikha

Re: remplir un tableau sans doublons ...

tout d'abord bienvenu à toi sur le forum de developpez :)

Citation:

Envoyé par ryo-san

bonjour,

je suis en plein apprentissage mais je patauge : lors de mon cours (algorithmie) l'on nous a demandé de remplir un tableau de facon aleatoire (jusque-la ok ) mais sans aucun doublons, alors la ... 8O .
je viens d' y passer 5 heures mais je n'ai pas encore les connaissances necessaires.ceci dit j'ai horreur de ne pas comprendre

je connais ça :wink:

Citation:

donc si vous pouviez m'aiguiller ou m'expliquer svp.

si c'est demandé aussi poliment....

alors en fait je pense que à chaque fois que tu tire un nombre au hasard,tu dois d'abord t'assurer qu'il ne figure pas déja dans le tableau avant de l'y inserer(tu parcours ton tableau en comparant chaque elemnt avec ton nombre),si il n'y figure pas alors tu l'insere dans le tableau,si non tu tire un autre nombre aleatoire et tu refait la meme chose.
voilà pour la partie algorithmie,MAIS il y a tout de mème un petit problème c'est que en theorie,cet algorithme peut tourner indefiniment vu que rand() peut donner un nombre dejà present dans le tableau une infinité de fois.En pratique je sais pas mais je pense que ça ira.

voilà,je te laisse le soin d'implementer tout ça.
Si tu n'y arrive pas n'hesite pas à poster :wink:
09/11/2005, 04h49
khayyam90

bien le bonjour,

Citation:

Envoyé par ryo-san

je suis en plein apprentissage mais je patauge : lors de mon cours (algorithmie) l'on nous a demandé de remplir un tableau de facon aleatoire (jusque-la ok ) mais sans aucun doublons [...] mais je n'ai pas encore les connaissances necessaires.[...]si vous pouviez m'aiguiller ou m'expliquer svp.

la methode a suivre est la suivante :
tu crees une boucle qui tourne autant de fois que tu veux de nombres dans ton tableau. Et a chaque tour de boucle tu generes un nombre tant qu'il est deja present dans le tableau.

pour ce qui est de ton probleme de tableau a neuf cases, il faut faire

Code:

for (i=0; i<10; i++)

ou

Code:

for (i=0; i<=9; i++)

pour obtenir 10 tours de boucle

autre chose, le main doit renvoyer int.
On pourrait aussi chipoter sur ta methode pour obtenir un nombre aleatoire avec un simple rand()%10 qui peut etre ameliore en suivant le code present dans la faq (ou dans le nouveau cours sur les nombres aleatoires, ecrit par gege, paru tres recemment) ; mais c'est vraiment du chipotage :D
09/11/2005, 07h07
Médinoc

ben, pour remplir ton tableau, si tu as assez peu de valeurs possibles , je puis te conseiller ceci:

(on va dire X valeurs possibles, pour un tableau de Y cases. Naturellement, X>=Y sinon il y aura forcément des doublons)

1) Tu vais un tableau de toutes les X valeurs possibles
2) Tu les mélanges
3) Tu copies les Y premières valeurs dans ton tableau de destination
09/11/2005, 09h36
Le Furet

Re: remplir un tableau sans doublons ...

Citation:

Envoyé par afrikha

MAIS il y a tout de mème un petit problème c'est que en theorie,cet algorithme peut tourner indefiniment vu que rand() peut donner un nombre dejà present dans le tableau une infinité de fois.En pratique je sais pas mais je pense que ça ira.

Ca peut arriver mais la probabilité est nulle (autrement dit, tu as beaucoup plus de chances de gagner 1000 fois de suite au loto que de voir ça se produire).

A part ça, je rejoins Afrikha en tous points.

Médinoc : en l'occurence, X = Y = 10. Comment mélanges-tu tes tableaux (étape 2), à part en refaisant ce qu'Afrikha a dit (ou équivalent) ?
09/11/2005, 09h42
Médinoc

Moi, j'avais trouvé une technique en temps garanti fini pour cela:

En fait de tableau simple, tu utilise un tableau de structures avec deux valeurs, dont l'une est celle que tu veux mettre.

Pour mélanger le tableau, tu remplis la seconde valeur de chaque structure avec des nombres aléatoires, et tu fais un tri du tableau (avec les fonctions de tri standard) selon cette valeur: Le tableau sera donc trié selon un ordre aléatoire --> aucun problème d'emplacement de rand().

Pour les amateurs d'algorithmique, la complexité du remplissage est O(n), et celle du tri O(n²) ou O(n log(n)) ---> complexité du tout O(n²) ou O(n log(n)) selon l'algo de tri utilisé.
09/11/2005, 09h47
Le Furet

[HS]
Mais tu dois quand même vérifier que chaque nombre aléatoire n'est pas déjà apparu avant, non ? Et cela peut arriver quel que soit l'intervalle dans lequel tu prends ton nombre aléatoire (même si je reconnais que c'est négligeable si tu prends un intervalle beaucoup plus grand que le nombre de données).
[/HS]
09/11/2005, 09h49
Médinoc

ben non, tu vérifies pas. pas la peine de vérifier, c'est tout l'intéret.

Simplement, deux valeurs ayant le même nombre aléatoire seront cote-à-cote après le tri.
09/11/2005, 09h51
Le Furet

Ca dépend de ton algorithme de tri. Et je serai pas étonné que ça introduise un biais dans ton ordre, mais j'ai la flemme de vérfier :)
09/11/2005, 09h55
Emmanuel Delahaye

Citation:

Envoyé par Le Furet

Ca dépend de ton algorithme de tri. Et je serai pas étonné que ça introduise un biais dans ton ordre, mais j'ai la flemme de vérfier :)

En effet, le risque est d'avoir 1,2,2,3 au lieu de 1,2,2,3 :-)
09/11/2005, 12h07
Le Furet

Non :)

Je pensais aux résultats finals. Toutes les permutations ne seraient pas équiprobables. Par exemple, imagine qu'on ait :

(1,3) (2,2) (3,2) (4,1) (5,3)

Si je classe par valeurs du 2ème terme, en balayant de gauche à droite et en prenant en cas d'ex aequo le premier qui me tombe sous la main (algorithme stupide, mais c'est pour l'exemple), j'ai :

(4,1) (2,2) (3,2) (1,3) (5,3)

Et comme résultat final : 4 2 3 1 5.

Je privilégie donc les séquences dans lesquelles on trouve des couples de nombres (i,j) avec i<j. Toutes les permutations de (1,2,3,4,5) ne seront pas équiprobables à l'arrivée.

Bien sûr, ça dépend de l'algorithme de tri, mais tous doivent avoir un biais.

Je pense que tout celà dépasse ce qui est demandé par ryo-san.

Je pense que ce qu'il cherche c'est un truc du genre

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
tab est le tableau où ranger les nombres
n est le nombre d'elements du tableau
i est un compteur
k est un compteur
pour i <- 1 jusqu'à n faire
  faire
     val <- une valeur aléatoire
     k <- 1
     tant que k < i et val != tab[k] faire
         k <- k + 1
     fin tant que
  tant que k < i
  tab[i] <- val
fin pour

09/11/2005, 18h14
afrikha

Le Furet a écrit:

Citation:

Ca peut arriver mais la probabilité est nulle (autrement dit, tu as beaucoup plus de chances de gagner 1000 fois de suite au loto que de voir ça se produire).

ceci serait vrai si rand() generait des nombres aléatoires,or celle-ci genere des nombres pseudo-aleatoires.
Pour trancher donc la question de savoir si l'algorithme a une durée finie ou pas ,il faut se pencher sur le fonctionnement de rand()

P.S:ça reste quand mème du chipotage,d'où ma phrase dans mon precedent poste

Citation:

En pratique je pense que ça ira
09/11/2005, 21h39
Le Furet

Citation:

Envoyé par afrikha

ceci serait vrai si rand() generait des nombres aléatoires,or celle-ci genere des nombres pseudo-aleatoires.
Pour trancher donc la question de savoir si l'algorithme a une durée finie ou pas ,il faut se pencher sur le fonctionnement de rand()

Un générateur de nombres qui renverrait un nombre infini de fois la même chose aurait du mal à être qualifié de pseudo-aléatoire. Franchement, ce problème n'en est pas un.
10/11/2005, 02h52
ryo-san

lol

tout d'abord merci a tous pour les conseils et pour votre acceuil.
comme la bien remarqué trapd, je voudrais un truc tout simple mais d'apres ce qu'il y a dans ce post , je devrais y arriver, le probleme initial est lié a rand()%10 meme si c'est discutable, le probleme m'a ete expose comme ca.
pour l'instant j'apprends a manipuler , je vais pas tarder avec les pointeurs donc il y a beaucoup de choses que je n'ai pas saisies mais ce n'est que partie remise.
je vais creuser un peu tout ca et vous dirais ce que j'ai pu faire ...
encore merci.

ps : z'auriez pas une certaine tendance a squatter les posts :lol: ?
10/11/2005, 04h26
Jack_serious

Citation:

Envoyé par ryo-san

lol

ps : z'auriez pas une certaine tendance a squatter les posts :lol: ?

Meme pas vrai d'abord.

1_ Toute discussion ou debat est enrichissant(e). (Sauf de type trollesque, ca va sans dire)
2_ Tout est sujet a discussion ou a debat.

CQFD...

je vais devenir fou !

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
# include <stdio.h>
# include <stdlib.h>
 
int tab[9];
int i;
int x;
 
 
int main() {
	for (i=0; i<10; i++){ 
 
		x = rand()%10;
 
	printf ("\nvaleur %d : %d", i, x) ;	
	}
	printf("\n");
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
 
ryo@LFS ~ $ ./test2
 
valeur 0 : 3
valeur 1 : 6
valeur 2 : 7
valeur 3 : 5
valeur 4 : 3
valeur 5 : 5
valeur 6 : 6
valeur 7 : 2
valeur 8 : 9
valeur 9 : 1

mais

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# include <stdio.h>
# include <stdlib.h>
 
int tab[9];
int i;
int x;
 
 
int main() {
	for (i=0; i<10; i++) { 
 
		x = rand()%10;
		tab[i] = x;	
                printf ("\nvaleur %d : %d", i,tab[i]) ;	
	}
	printf("\n");
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
ryo@LFS ~ $ ./test2
 
valeur 0 : 3
valeur 1 : 6
valeur 2 : 7
valeur 3 : 5
valeur 4 : 3
valeur 5 : 5
valeur 6 : 6
valeur 7 : 2
valeur 8 : 9
valeur 1 : 6
valeur 2 : 2
valeur 3 : 7
valeur 4 : 0
valeur 5 : 9
valeur 6 : 3
valeur 7 : 6
valeur 8 : 0
valeur 6 : 3
valeur 7 : 2
valeur 8 : 6
valeur 1 : 6
valeur 2 : 8
valeur 3 : 7
valeur 4 : 9
valeur 5 : 2
valeur 6 : 0
valeur 7 : 2
valeur 8 : 3
valeur 7 : 2
valeur 8 : 5
valeur 9 : 9

pourquoi ????

10/11/2005, 05h28
ryo-san

ok tab [10] et non tab [9] grrr..

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
# include <stdio.h>
# include <stdlib.h>
 
int tab[10];
int i;
int x;
int k;
 
 
int main() {
	for (i=0; i<10; i++){ 
 
		x=rand()%10;
		if (i < 1){
			tab[i] = rand()%10;
		}	
		else{	
			for (k=0; k<i; k++) {	
 
				if ( x != tab[k]){
 
				}
				else{
					x=rand()%10;
					k=-1;
 
				}	
			} 
		tab[i]=x;
		printf("\nvaleur tab[%d] : %d",i,tab[i]);
		}
	}
printf("\n");
}

et voila la bete !
j'en suis fier comme un turc , vous raconte pas :D
merci a vous tous.

Citation:

Envoyé par ryo-san

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
# include <stdio.h>
# include <stdlib.h>
 
int tab[9];
int i;
int x;
 
 
int main() {
	for (i=0; i<10; i++){ 
 
		x = rand()%10;
 
	printf ("\nvaleur %d : %d", i, x) ;	
	}
	printf("\n");
}

http://jmduhen.chez-alice.fr/Shadocks/Shadoc4.jpg

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <stdio.h>
#include <stdlib.h>
 
int main (void)
{
   int i;
 
   for (i = 0; i < 10; i++)
   {
      int x = rand () % 10;
 
      printf ("valeur %d : %d\n", i, x);
   }
}

Citation:

mais

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# include <stdio.h>
# include <stdlib.h>
 
int tab[9];
int i;
int x;
 
 
int main() {
	for (i=0; i<10; i++) { 
 
		x = rand()%10;
		tab[i] = x;	
                printf ("\nvaleur %d : %d", i,tab[i]) ;	
	}
	printf("\n");
}

Comportement indéfini. 9 cases dans le tableau, 10 valeurs (0-9)
Codage atroce et non significatif...

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
#include <stdio.h>
#include <stdlib.h>
 
int main (void)
{
   int tab[9];
   size_t i;
 
   for (i = 0; i < sizeof tab / sizeof *tab; i++)
   {
      int x = rand () % 10;
      tab[i] = x;
   }
 
   for (i = 0; i < sizeof tab / sizeof *tab; i++)
   {
      printf ("valeur %d : %d\n", i, tab[i]);
   }
   return 0;
}

10/11/2005, 11h04
ryo-san

Citation:

Envoyé par Emmanuel Delahaye

comportement indéfini. 9 cases dans le tableau, 10 valeurs (0-9)
Codage atroce et non significatif...

merci :D .
ceci dit , je m'etais un peu embrouillé avec l'initialisation des tableaux.
mais tu cites l'avant dernier post, le dernier est-il un peu mieux ?

Citation:

Envoyé par ryo-san

Citation:

Envoyé par Emmanuel Delahaye

comportement indéfini. 9 cases dans le tableau, 10 valeurs (0-9)
Codage atroce et non significatif...

merci :D .
ceci dit , je m'etais un peu embrouillé avec l'initialisation des tableaux.
mais tu cites l'avant dernier post, le dernier est-il un peu mieux ?

L'exécution est correcte, mais le codage est toujours aussi compliqué... J'ajoute srand() pour que le tirage change...
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <stdio.h> #include <stdlib.h> #include <time.h> int main (void) { int tab[10]; int i; srand ((unsigned) time (NULL)); for (i = 0; i < 10; i++) { int x = rand () % 10; if (i < 1) { tab[i] = rand () % 10; } else { int k; for (k = 0; k < i; k++) { if (x == tab[k]) { x = rand () % 10; k = -1; } } tab[i] = x; printf ("valeur tab[%d] : %d\n", i, tab[i]); } } return 0; }

10/11/2005, 12h43
ryo-san

bon merci.je ne doute pas qu'il existe de bien meilleure facon,mais c'etais mon tout premier.
faut que je bosse.
z'etes sympa ici j'reviendra :P .