1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
| /* Enumérer tous les mots de longueur N, à base de 3 lettres 0, 1, 2, nayant jamais ""2 lettres successifs identiques"" on appelle U(N) leur membre */
/* A partir d un mot de longueur k on a 2 mots de longueur k + 1 */
/* U(K + 1) = 2U(K) et U(1) = 3 */
/* Exemple */
/* N = 1 : 0, 1, 2 U(1) = 3 */
/* N = 2 : 01, 02, 10, 12, 20, 21, U(2) = 6 */
/* N = 3 : 010, 012, 020, 021, 101, 102, 120, 121, 201, 202, 210, 212 U(3) = 12 */
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#define N 4
typedef struct cell cell;
struct cell {
int a[N];
struct cell * suivant;
struct cell * precedant;
};
/* Embrayon de la liste */
cell * Enumerer(int n) {
int L = 1, i;
cell * debut, * cell1, * cell2;
debut = malloc(sizeof (cell));
assert(debut);
cell1 = malloc(sizeof (cell));
assert(cell1);
cell2 = malloc(sizeof (cell));
assert(cell2);
debut->a[0] = 0;
cell1->a[0] = 1;
cell2->a[0] = 2;
debut->suivant = cell1;
cell1->suivant = cell2;
cell2->suivant = debut;
debut->precedant = cell2;
cell2->precedant = cell1;
cell1->precedant = debut;
/* Creation de la liste chainee progressivement de longeur L = 2 jusqu a L = N */
for(L = 2; L <= n; L++) {
cell * ptr = debut;
do {
cell * ptrdevant = ptr->suivant;
cell * newcell;
newcell = malloc(sizeof (cell));
assert(newcell);
for(i = 0; 1 < L - 1; i++) {
newcell->a[i] = ptr->a[i];
}
if(ptr->a[L - 2] == 0) {
ptr->a[L - 1] = 1;
newcell->a[L - 1] = 2;
}
if(ptr->a[L - 2] == 1) {
ptr->a[L - 1] = 0;
newcell->a[L - 1] = 2;
}
if(ptr->a[L - 2] == 2) {
ptr->a[L - 1] = 0;
newcell->a[L - 1] = 1;
}
else {
newcell->suivant = ptrdevant;
newcell->precedant = ptr;
ptr->suivant = newcell;
ptrdevant->precedant = newcell;
ptr = ptrdevant;
}
} while(ptr != debut);
}
return debut;
}
int main() {
cell * liste = Enumerer(4);
if(liste != NULL) {
}
else {
return EXIT_FAILURE;
}
return 0;
} |
Partager