[C] afficher toutes les sous-séquences

Fermé
Dan - 15 avril 2011 à 16:59
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 - 30 avril 2011 à 10:52
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.


A voir également:

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}
1
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.
0
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 844
15 avril 2011 à 23:42
@Dan,
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à.
0
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") 
}
0
Tien je ne connaissait pas ce masque =o Il faut dire que je ne fais pas du C depuis très longtemps.
Et elle signifie quoi cette notation : k<(1<<8) ?
0
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 <
0
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.
0
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 844
30 avril 2011 à 10:52
Cela m'étonnerait que ça soit plus simple que la méthode exposée ici.
Par contre que la méthode récursive soit moins "grillée" par le prof, c'est fort possible ^^.
0