Enumerer tous les mots de longueur n à base de 1,2,3

Version imprimable

15/01/2007, 00h13
momeftah

1 pièce(s) jointe(s)

Enumerer tous les mots de longueur n à base de 1,2,3

Bonjour, je veux enumerer tous les mots de longueur N à base de 3 lettres 1, 2, 3 n'ayant jamais 2 lettres successifs identiques
exemple :
N = 1 : 0, 1, 2
N = 2 : 01, 02, 10, 12, 20, 21
N = 3: 010, 012, 020, 021, 101, 102, 120, 121, 201, 202, 210, 212
en fait l'algorithme u(N+1) = 2u(N) et u(1) = 3 ainsi de suite j'ai réussi le programme qui affiche les mots celon un N donné
merci.
15/01/2007, 00h32
khayyam90

Citation:

Envoyé par momeftah

Bonjour, je veux enumerer tous les mots de longueur N à base de 3 lettres 1, 2, 3 n'ayant jamais 2 lettres successifs identiques
[...]
j'ai réussi le programme qui affiche les mots celon un N donné
merci.

Bien le bonsoir,

Et quel est le problème ? si tu as réussi à le programmer, qu'est-ce qui ne va pas ?
15/01/2007, 08h03
momeftah

Bonjour, en fait il y a un bug après l'execution du programme mais il m'affiche pas d'erreur il rend pas le prompt et je ne sais pas ou positionner le printf pour afficher les mots celon le N que je donne comme l'exemple le montre.
Merci.
15/01/2007, 08h59
Thierry Chappuis

Si le programme ne rend pas la main, c'est certainement que tu rentres dans une boucle infinie quelque part.

Thierry

Code:

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;
}

15/01/2007, 11h23
Emmanuel Delahaye
Citation:
Envoyé par momeftah

Code:

1 2 3 4 5 cell * ptr = debut; do { <...> } while(ptr != debut);
Vu que ni ptr, ni debut ne changent dans la boucle, on en sort jamais...

Attention, assert() est mal employé.

http://emmanuel-delahaye.developpez....tes.htm#assert