[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
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
A voir également:
- [C] afficher toutes les sous-séquences
- Afficher appdata - Guide
- Afficher mot de passe wifi android - Guide
- 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.
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
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 ^^.
Par contre que la méthode récursive soit moins "grillée" par le prof, c'est fort possible ^^.
Modifié par Dan le 15/04/2011 à 18:09
15 avril 2011 à 23:42
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à.
Modifié par le père le 16/04/2011 à 01:35
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é)
16 avril 2011 à 10:14
Et elle signifie quoi cette notation : k<(1<<8) ?