[C] afficher toutes les sous-séquences
Dan
-
fiddy Messages postés 441 Date d'inscription Statut Contributeur Dernière intervention -
fiddy Messages postés 441 Date d'inscription Statut Contributeur Dernière intervention -
Bonjour,
Alors voila, j'aimerais créer un programme qui affiche toutes les sous-séquences possible d'un tableau de nombre. Les nombres doivent rester dans le bon ordre mais ils ne doivent pas nécessairement se suivre:
ex : int tableau[] = {1,2,3,4,5,6,7,8,9}
sous séquence : 2379 ou 1234568 ou encore 4
Si les chiffres devaient se suivre j'aurais fait ça avec 2 variables, une qui fixe le début puis une autre qui, pour un début, parcourrait le reste du tableau en l'affichant. Hélas ici c'est impossible et donc je ne vois vraiment pas comment m'y prendre
Je ne demande pas un code, je demande juste quel méthode je pourrais utiliser.
Alors voila, j'aimerais créer un programme qui affiche toutes les sous-séquences possible d'un tableau de nombre. Les nombres doivent rester dans le bon ordre mais ils ne doivent pas nécessairement se suivre:
ex : int tableau[] = {1,2,3,4,5,6,7,8,9}
sous séquence : 2379 ou 1234568 ou encore 4
Si les chiffres devaient se suivre j'aurais fait ça avec 2 variables, une qui fixe le début puis une autre qui, pour un début, parcourrait le reste du tableau en l'affichant. Hélas ici c'est impossible et donc je ne vois vraiment pas comment m'y prendre
Je ne demande pas un code, je demande juste quel méthode je pourrais utiliser.
2 réponses
-
Bonjour
Tu as 9 éléments, prends un nombre de 9 bits et compte avec.
Autrement dit, compte de 0 à 511.
à chaque bit, associe un élément de ton ensemble
0000000 - {}
0000001 - {1}
0000010 - {2}
0000011 - {1,2}
...
111111100 - {3,4,5,6,7,8,9}
111111101 - {1,3,4,5,6,7,8,9}
111111110 - {2,3,4,5,6,7,8,9}
111111111 - {1,2,3,4,5,6,7,8,9}-
J'ai beau chercher je vois toujours pas comment je pourrait résoudre ce problème, même si il est plus clair et logique que celui de départ. J'imagine que je devrais utiliser une variable qui commencerait à 1 et qui augmenterait à chaque fois qu'on passe au binaire supérieur (0010 -> i=2 0100 ->i=3 1000->i=4) et je vois aussi que je devrai utiliser la récursion, mais je ne parvient toujours pas a imaginer une structure d'algorithme qui modifierait les bon chiffres au bon moment.
-
-
N'oublie pas que les nombres sont en binaire dans ton ordinateur. Quand tu incrémentes un entier (i++), il passe réellement par les valeurs
000000000
000000001
000000010
000000011
etc...
Tu n'as donc pas à chercher d'algorithme pour le faire !
et pour tester les valeurs des bits d'une variable, sers toi d'un masque, c'est à d'un nombre qui a un seul bit à 1. Tu testes les bits successivement en décalant le masque : il y a un opérateur de décalage tout fait en C
ça donnerait à peu près (je n'ai pas testé)
int tableau[] = {1,2,3,4,5,6,7,8,9}; int k,kk,mask; for (k=0; k<(1<<8); k++) { for (kk=0,mask=1; kk<9 ; mask <<=1,kk++) { if (k & msk) printf("%d", tableau[kk]); } printf("/n") } -
-
-
Peu importe qu'on appelle ça un masque ou autrement, ce qui compte, c'est l'opération & ("et" bit à bit) qu'il permet de faire.
<< est l'opérateur de décalage d'un bit à gauche. La notion de bit est fondamentale en informatique. Je ne sais pas si ça vient des profs ou des étudiants, mais j'ai l'impression que les gens oublient que ça existe, ta question en est une belle illustration
1<<8 signifie donc 100000000 en binaire (1 suivi de 8 zéros), c'est à dire 512. J'aurais même dû mettre 1<< (sizeof(tableau)/sizeof(int)-1) pour que ça fasse automatiquement 2,4,8,16 etc selon la taille de tableau
k<(1<<8) signifie donc k inférieur à 512. J'espère que tu savais ce que voulait dire k <-
Je parie que la personne qui demande ça est un élève de l'ULg qui suit le cours de "Structure des données et algorithme" et qui bloque sur son exercice de la recherche du plus grand palindrome non-contigu dans un tableau donné avec une méthode backtracking. En fait pour parcourir toutes les séquences, j'ai trouvé beaucoup plus simple. Je m'en suis sorti avec seulement une fonction récursive de 15 lignes. Il n'y a pas besoin de parler de décalage binaire parce que le prof verra tout de suite que ça ne vient pas d'un élève qui est novice en langage C.
-
-
