Discussion :

[juju_juju]

Bonjour,

Je dois obtenir l'ensemble des combinaisons réalisable avec trois valeurs différentes dans un triangle de longueur K.
Par exemple pour K=2, je dois obtenir 27 solutions comme:
00
0

01
0

12
1

...

Pour cela, je dois utiliser un backtrack mais le code ci-dessous ne marche pas. En effet, il y a des redondances et certains triangles ne s'affichent pas.
Pourriez-vous me donner quelques explications?


Le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
int niveau [K][K][K];
int compt = 0;
 
 
void back_track_base (int i){            //appel 1er back_track ligne = 0
    int j, l, m;
 
    if (i == K){                                //Si la ligne = nb lignes
       for (l=0; l<K; l++) {              //Afficher les solutions
           printf("\n");
           for(m=K-l; m>0; m--) {
            printf("%i ",niveau[l][m][K]);
            }
        }
        printf("\n");
 
        compt ++;
 
    }else{                          //Sinon pour chaque colonnes
        for(j=K-i-1; j>=0; j--){
                niveau[i][j][K] = 0;        //SI ROUGE = 0 ==> MARCHE
                back_track_base (i+1);
                niveau[i][j][K] = 1;        //DONC BLEU = 1
                back_track_base (i+1);
                niveau[i][j][K] = 2;        //ET VERT = 2
                back_track_base (i+1);
        }    
    }
}
 
 
 
// Dans le main:
back_track_base(0);
printf("Il ya %i solutions \n",compt);

Merci d'avance

[Matt_Houston]

Je n'ai pas saisi : qu'est-ce qu'un triangle de longueur K ?

Peux-tu placer des balises CODE autour de ton code C indenté ?

[juju_juju]

La longueur du triangle est le nombre de valeur (maximal) de la ligne 1 du triangle.

[stendhal666]

Ton exposé du problème est bien difficile à comprendre.

Si ton but est d'obtenir les combinaisons(3 K), j'ai l'impression que tu te compliques la vie:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
typedef struct Triangle { int a, b, c} Triangle;
 
Triangle* find_combinations(int K) {
  Triangle* solutions = malloc(pow(K,3) * sizeof(Triangle));
  Triangle* resultat = solutions;
  int i, j, k;
  for (i=0; i < K; ++i) // des boucles for imbriquées
    for (j=0; j < K; ++j)  // c'est une sorte de back-tracking aussi
      for (k=0; k < K; ++k)
        *solutions++ = {i, j, k};
  return resultat;

Sinon que veux tu faire exactement?

[Matt_Houston]

Je n'ai toujours rien pigé, je donne ma langue au chat.

[ternel]

*ting*

En fait, quand tu parles de triangles parmi trois valeurs de longueur K, c'est:
une séquence de lignes K lignes, de tailles K à 1, dont chaque élément a sa valeur parmi les trois possibles.
Et tu veux que ton programme les génère toutes.

Supposons que les trois valeurs sont A, B et C, et que K=2.
Regarde ce triangle.

AAA
BC
A

Quel est le triangle suivant?
Est-ce que la méthode que tu as utilisé pour déterminer ce suivant te permettra de générer tous les triangles si tu pars du bon?
Quel est ce bon premier triangle?

Il n'y a plus qu'a coder.