zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008
-
24 oct. 2006 à 03:06
zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008
-
28 oct. 2006 à 01:41
Bonjour a tous :-)
je dis pour les experts car cela ne me semble pas evident .
voila le probleme a resoudre ,je souhaiterais generer toutes combinaisons de N parmi K ( en realité N varie de 25 a 90 et K de 4 a 25 et il est la mon probleme)
prenon l'exemple du loto que vous connaissez bien le programme pour generer les combis est tres simple :( sous devcpp)
#include<stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <time.h>
main()
{
int zz=0,a=0,i=0,j=0,k=0,l=0,m=0,n=0,tc[6],touche=0;
int nt=0;
}
printf("nombre de combinaisons %d ",zz);
scanf("%d",&touche);
getchar();
}
maintenant comme mes valeurs contrairement au loto varie je suis obliger de changer le code a chaque fois ,de plus si k = 20 par exemple cela m'oblige a creer 20 boucles imbriquées alors voici ma question :
je sais qu'il est possible d'eviter toutes ses boucles en creant ce qu'on appelle une boucle dynamique donc en theorie avec une seule boucle il est possible de sortir toutes les combinaisons de N parmi K ( ou l'inverse je ne me souviens plus de la formulation mais bon vous aurez compris ;-) )
supposons que je veuille sortir toutes les combinaisons de 15 chiffres parmi 70 cela m'oblige a creer 15 boucles bref et a chaque fois je doit allez dans mon programme pour changer les valeurs bref pas evident ( en tous cas pour moi ;-) )
pouvez vous m'aider ?
cordialement
rrk275
Messages postés540Date d'inscriptionvendredi 25 juin 2004StatutMembreDernière intervention 1 octobre 20072 26 oct. 2006 à 17:08
Sniff tu as masscré ma belle fonction .. c'est pour ca que ca marche pas ^^
for(int i=N-1;i>=0;i--)
// printf("%d ",ch[i]);
// printf("\n");
ch[0]++;
imaginons que les // soit des commentaires , des lignes non interpretée par le compilateur ca donne ceci..
for(int i=N-1;i>=0;i--)
ch[0]++;
et donc a partir de la j'éspere que tu comprend le probleme ..
pour bien commenter ( la ca va pas trop dur ^^ ) il faut aussi commenter ( nan pas la ch[0]++; ) mais le for ^^
Y en a qui ne respectent vraiment rien
Louis
PS , comme tu l'as peut etre remarqué , j'ai mis des arguments par defaut , donc pas la peine de reiterer le 1 ^^
zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008 25 oct. 2006 à 01:34
Bonjour
Joky non ce source ou tu m'envoie ne correspond pas a ce que je cherche ce ne sont pas des arrangements que je veux generer mais des combinaisons.
voici un exemple .
avec le petit programme que j'ai poster plus haut si je donne a "NT" la valeur 8 je vais avoir toutes les combinaisons de 6 chiffres parmi 8
donc
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 5 8
1 2 3 4 6 7
.........
.........
3 4 5 6 7 8
j'ai pris l'exemple du loto car pour les combinaisons c'est ce qui me semblais le plus parlant pour un francais ;-)
mais si par exemple je veux generer toutes les combinaisons de 10 chiffres parmi 50 je suis obliger de changer mon code et faire 10 boucles , voila il est la mon probleme comment generer toutes les combinaisons de X parmi Y quelque soit X et Y sans etre obliger de changer mon code a chaque fois ,je crois qu'il est possible de faire cela avec une seule boucle qu'on nomme boucle dynamique bref pouvez vous m'aider ?
cordialement
ps) je programme en c classique sous devcpp
rrk275
Messages postés540Date d'inscriptionvendredi 25 juin 2004StatutMembreDernière intervention 1 octobre 20072 25 oct. 2006 à 14:20
On apelle ce que tu veux ,en logique combinatoire ( je me la ramene un
peu, je sais.. ) des combianaison de N parmi K sans ordre.
Le fait qu'il y ait sans ordre signifie que 2 3 4 et 4 3 2 sont exactement les memes resultats^^
voici ma fonction, iterative,
void combi(int N = 2,int K=4,int dep=1)
{
int ch[N+1];
for(int i=0;i<=N;i++)
ch[i] = dep;
while(ch[N]==dep)
{
for(int i=N-1;i>=0;i--)
printf("%d ",ch[i]);
printf("\n");
ch[0]++;
for(int i=0;i<N&&ch[i]>K;i++)
{
ch[i+1]++;
ch[i] = -1;
}
int min = K;
for(int i=N-1;i>=0;i--)
{
if(ch[i]!=-1)
min = min<ch[i]?min:ch[i];
else
ch[i] = min;
}
}
}
( l'itération n'apporte que peu à la recursion .. juste un peu de vitesse et de mémoire. )
n'hesite pas à poser des questions sur mon algo.
.
Louis
Vous n’avez pas trouvé la réponse que vous recherchez ?
zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008 25 oct. 2006 à 15:07
Bonjour
cela ne marche pas je viens de l'essayer il ne peut y avoir de doublons hors avec ta fonction il y en a ,une combinaison n'as pas de doublons ( voir mon exemple ) et mon prog qui les genere sans aucun probleme ;-)
cordialement
zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008 26 oct. 2006 à 01:24
Bonjour ,
non cela ne marche pas par exemple si je prends ton exemple j'ai comme resultat
1 1
1 2
1 3
1 4
2 3
2 4
3 4
j'ai 1 1 en doublons et si je change les parametres par exemple si je veux toutes combinaisons de 6 parmi 8 et bien c'est pire j'ai des combinaisons de ce genre 1 4 7 7 7 8 et la derniere est 7 8 8 8 8 8 et je me retrouve avec des centaines de combinaisons alors qu'il y en a que 28 bref ta fonction traite les arrangement et non les combinaisons ;-)
cordialement
zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008 26 oct. 2006 à 02:07
B
cela marche uniquement avec comme valeur 2 et 4 ensuite si je veux par exemple 6 parmi 8 il me sort que 5 combinaisons
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 5 8
1 2 3 4 6 7
1 2 3 4 6 8
zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008 26 oct. 2006 à 02:57
on se raproche ,mais si je prends par exemple 6 et 15 le nombres de combinaisons n'est pas bon il ne les genere pas tous n'oublie pas que dans mon intitulé je doit generer toutes les combinaisons quelque soit N et K , en tout cas le resultat est deja pas mal car c'est pas evident du tout .
pour en venir a ton programme voila ce qu'il fait si je prends par exemple
6 parmi 12 il va me sortir 923 combinaisons ( il y en a 924 )et plus le chiffre est grand plus il en manque ,par exmple pour 6 parmi 12 la derniere combinaisons qu'il trouve est celle la :
6 8 9 10 11 12
hors la derniere en realité c'est celle la :
7 8 9 10 11 12
si a la place de 12 je prends 18 il en manque plusieurs centaines mais en tout cas je pense que ton programme est bon doit manquer un truc quelque part .
en tout merci beaucoup de la peine que tu te donne ;-)
rrk275
Messages postés540Date d'inscriptionvendredi 25 juin 2004StatutMembreDernière intervention 1 octobre 20072 26 oct. 2006 à 11:40
Le probleme c'est que chez moi il me sort bien comme derniere combinaison ,
7 8 9 10 11 12 <- ce qui est logique ^^
et il me donne 924 combinaisons ..
il doit y avoir un probleme quelque part.. (mais où?)
testé sur plusieur compilateur .. avec :
printf("%d",combi(6, 12,1));
pour 6 18 il me donne 18564 combinaisons possibles ..
main()
{
long long NombreNumeros,LongueurCombinaison,depart=1,NombreCombinaisons;
int touche;
printf("\n\nlONGUEUR --> ");
scanf("%d",&LongueurCombinaison);
printf("nombre de numeros --> ");
scanf("%d",&NombreNumeros);
NombreCombinaisons = combi(LongueurCombinaison,NombreNumeros,1);
printf(" nombre de combi %d",NombreCombinaisons);
scanf("%d",&touche);
getchar();
}
zhao77
Messages postés26Date d'inscriptionvendredi 8 septembre 2006StatutMembreDernière intervention 7 août 2008 27 oct. 2006 à 01:32
Bonjour ;-)
desolé d'avoir pas respecter ta jolie fonction ;-) oui ca marche tu avais raison , peut tu m'expliquer le N=2 et le K=4 car si j'ai bien compris dans mes scanf si je veux N=50 et K=10 par exemple "combi(int N = 2,int K=4,int dep=1)" ici je ne touche a rien alors que je croyais que ses valeurs tu l'avais mise comme ca juste pour essayer 2 parmi 4 hors j'ai bien l'impression que c'est pas le cas ,donc je comprends pas ( je debute ;-) ) c'est pour ca que j'avais oter le 2 et le 4 dans ta fonction car je croyais que mes valeurs saisies etaient passer en parametre a ta fonction ;-)
cordialement
rrk275
Messages postés540Date d'inscriptionvendredi 25 juin 2004StatutMembreDernière intervention 1 octobre 20072 27 oct. 2006 à 01:54
Re, pas grave pour ma petite fonction... ^^
dans : int combi(int N = 2,int K=4,int dep=1)
les = qqchose servent d'arguments par defauts mais on peut tout a fait les supprimer ,
int combi(int N,int K,int dep) marcherait , seulement on ne pourrait plus omettre des arguments ( alors que l'on pauvait le faire
avec int combi(int N = 2,int K=4,int dep=1) ( je pense nottament au dernier qui doit etre rarement utilisé...