[C] afficher toutes les sous-séquences
Dan
-
fiddy Messages postés 11069 Date d'inscription Statut Contributeur Dernière intervention -
fiddy Messages postés 11069 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.
A voir également:
- [C] afficher toutes les sous-séquences
- Afficher appdata - Guide
- Afficher toutes les lignes masquées excel ✓ - Forum Excel
- Afficher les commentaires word - Guide
- Afficher les modifications word - Guide
- Afficher taille dossier windows - Guide
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}
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}
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 <
<< 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.
Non pas besoin de récursion.
Une simple boucle for de 0 à 511.
Une autre boucle for de 0 à 8 : k.
Ensuite, tu fais de la logique boolèenne. Si i & 2 puissance(k) > 0; alors afficher k+1.
Et voilà.
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") }Et elle signifie quoi cette notation : k<(1<<8) ?