Backtrack problème de redondance

Version imprimable

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:

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 :)

12/01/2016, 16h29
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é ?
12/01/2016, 16h50
juju_juju

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

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:

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?

13/01/2016, 11h14
Matt_Houston

Je n'ai toujours rien pigé, je donne ma langue au chat. :roll:
13/01/2016, 11h51
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.