Tableau de chaînes de caractères

Version imprimable

23/10/2012, 16h43
mouradj2006

Tableau de chaînes de caractères

salut;
je pas trouver une solution pour cet exercice je sentait l'odeur de la récursivité mais je pas trouver comment ; merci de m'aider par une solution récursive ou bien itérative .

je veux vérifier si un tableau de chaine de caractère peut être ordonné de façon que chaque chaine commence avec la dernière lettre de la précédente si oui on doit afficher une solution sinon an affiche que ce impossible {on doit utiliser tous les mots }
exmple :
358 123 874 826 638
on doit afficher oui ce possible et la solution est :123 358 826 638 874
alors pour :521 894 189 577 400 on affiche impossible
23/10/2012, 18h57
DrDarko

Bonjour,

En gros le principe est de construire la solution en ajoutant bout à bout les différentes chaines et si la solution n'est pas bonne on essaye une autre chaîne. Si toutes les chaînes disponibles ont été essayé sans succès on revient en arrière en mettant une nouvelle chaîne. C'est peut être pas très clair donc je vais te donner un exemple.

358 123 874 526 638

- tu places 358 en 1er

- tu testes si 123 est compatible non donc tu testes 874 c'est compatible.

- donc la tu as 358 874 tu testes 123, puis 526, puis 638. La t'en as aucun de compatible du coup tu recules, c'est à dire que tu repasses au test juste avec 358.

- tu testes 358 avec 526 puis 638 aucun ne marche donc cela veut dire que tu ne peux pas commencer avec 358.

- tu recules et tu places 123 en premier.

- tu testes 123 avec 358... et ainsi de suite.

Attention ce n'est pas du tout l'algo le plus opti car dans certains cas il va devoir tester toutes les solutions avant de trouver la bonne (voir ne pas en trouver donc bien tourner pour t'annoncer qu'il n'y a pas de possibilité).
23/10/2012, 20h33
mouradj2006

merci ; mais comment implémenter ça ? comment reculer ? dans certain cas il faut reculer même 2 ou 3 fois ou n fois pour trouver le bon chemin
merci de me donne même un pseudo code .
24/10/2012, 13h37
Jerome Briot

Citation:

Envoyé par mouradj2006

123 358 826 638 874

Si j'ai bien compris, tu devrais peut être analyser le nombre de fois qu'apparaissent les caractères en rouge ci-dessus, et les deux extrêmes (1 et 4).
Rien qu'avec ça tu sais si le problème peut être résolu ou non.

Les caractères au milieu des chaînes ne servent à rien, si ce n'est à t’embrouiller.
Le problème serait le même avec :

Citation:

38 13 84 56 68
24/10/2012, 13h55
kwariz

Bonjour,

Il y a plusieurs approches possibles :

* la plus inefficace est sans doute de générer toutes les permutations et de vérifier lesquelles vérifient la propriété souhaitée

* le problème tel que présenté se modélise simplement avec un digraphe :
http://s17.postimage.org/dd4al22tb/chaine.png
Les noeuds contiennent la chaine et deux noeuds u et v sont reliés par une arête si v commence par le caractère par lequel u fini.

Tout algorithme déterminant un chemin hamiltonien dans le graphe convient. Le chemin est en rouge dans l'exemple. C'est en général un problème difficile.
24/10/2012, 13h58
mouradj2006

initialement on a un tableau qui contient n chaine de caractère non ordonné et on veut vérifier sil est possible de l'ordonner comme indiquer dans l’énoncée cad ordonner le de façon que chaque chaine commence par le dernier caractère de la précédente.
si oui (cad possible) alors il faut que le programme affiche une solution
sinon il affiche impossible de l'ordonner .
j’espère que j' était claire cette foi .
merci pour vos aides .

Citation:

Envoyé par kwariz

Bonjour,

Il y a plusieurs approches possibles :

* la plus inefficace est sans doute de générer toutes les permutations et de vérifier lesquelles vérifient la propriété souhaitée

* le problème tel que présenté se modélise simplement avec un digraphe :
http://s17.postimage.org/dd4al22tb/chaine.png
Les noeuds contiennent la chaine et deux noeuds u et v sont reliés par une arête si v commence par le caractère par lequel u fini.

Tout algorithme déterminant un chemin hamiltonien dans le graphe convient. Le chemin est en rouge dans l'exemple. C'est en général un problème difficile.

oui vous avez raison mais je veux une solution pour niveau d'eleve {tableau , boucles, recursivité ,....} les arbres et les graphes son hors programme .
24/10/2012, 14h06
kwariz

* un tableau vide est ok
* un tableau à un élément est ok
* un tableau à deux éléments est facile à résoudre ( soit a[0]a[1] convient, soit a[1]a[0] convient, soit il n'y a pas de solutions) = on essaye d'insérer a[1] dans le sous-tableau a[0] pour construire une solution)
* un tableau à n>2 éléments : pour chaque éléments a[i] de a, on essaye de résoudre le problème "a privé de a[i]" s'il existe une solution alors on essaye d'insérer a[i] quelque part dans cette solution pour en construire une nouvelle(un peu comme pour le tableau à deux éléments).

Cherche du côté backtracking .... tu dois avoir ça dans ton cours.

Voila je sais pas trop faire du pseudo code mais je pense que ça devrait ressembler à ça.

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
Fonction qui retourne un booléen et qui prend en paramètre ton tableau de chaine
{
 
  Tu déclare un tableau de int static qui a un nombre de cases égales au nombre de chaines que tu as et tu initialises toutes ces cases à -1; (Ce tableau va contenir la position de tes chaines de caractères dans l'autre tableau mais dans le bon ordre)
 
  Tu déclares un  int static pos et tu l'initialises à 0;
 
  Tu déclares un int i et tu l'initialises à 0;
 
  boucle while (i != nbr de chaines que tu possèdes)
  {
      if (Tu vérifies que i n'est pas déjà dans ton tableau de int)
      {
           if (Tu vérifies que la chaine peut être placé en dernière)
           {
               Tu places dans ton tableau static à la position pos, la position (= i) de ta chaine dans ton tableau de chaine.
                pos++;
                Tu rappelles ta fonction.
                pos--;
                tab[pos] = -1;
           }
      }
      i++;
  }
  Si tu arrives ici cela veut dire que tu as essayé toutes les solutions sans succès à toi de gérer ce cas la;
}

Plusieurs passages sont incomplets, c'est pour que tu cherches de toi même (notamment sur les valeurs de retour ou encore comment savoir lorsque l'on a pas de bonne réponse ou que faire si on a trouvé une solution).
Le gros de l’algorithme y est si tu as des questions tu peux les poser.

24/10/2012, 16h39
mouradj2006

merci ! le static n'existe pas en pascal ;
merci de m'aider à propos les variables de retours .

si on procède comme ça:
on prend t[1]
on cherche la première case compatible avec t[1] {p}
si p<>0 alors
empiler (p)
on fait la même chose avec t[p]
sinon
r=dépiler()
on fait la même chose avec t[tete de la pile] à partir de la position r

comment je peux organiser ça proprement ?
24/10/2012, 17h54
DrDarko

En gros le principe général c'est que lorsque tu construis ta suite à chaque fois que tu rajoutes un membre tu montes sur la pile et à chaque fois que tu en enlèves un tu redescends dans ta pile.

Après je sais pas à quoi ressemble le pascal je suis encore débutant mais s'il existe quelque chose de similaire aux static tu peux faire comme je t'ai montré précédemment.
24/10/2012, 20h35
Trap D

Ton problème est analogue à celui-ci http://rosettacode.org/wiki/Last_letter-first_letter
29/10/2012, 21h16
I_believe_in_code

Citation:

Envoyé par mouradj2006

oui vous avez raison mais je veux une solution pour niveau d'eleve {tableau , boucles, recursivité ,....}

La solution proposée par DrDarko convient donc tout à fait.

ma proposition en java

salut ; je essayé de implémenter l'algorithme proposé mais toujours il affiche false;

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
 
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package lastfirst;
 
/**
 *
 * @author JABALLAH MOURAD
 */
public class LastFirst {
     public static int sol[] = {-1,-1,-1,-1,-1};
 
       public static int pos=0;
 
public static boolean trouve(int sol[],int j){
    for(int i=0;i<sol.length;i++)
        if(sol[i]==j) return true;
            return false;  
   }
 
     public static boolean ok(String t[],int sol[],int j){ 
         if(sol[sol.length-1]==-1)
             return true;
         else
         {
           String ch1=t[sol[sol.length-1]];
           String ch2=t[j];  
           return ch1.charAt(ch1.length()-1)==ch2.charAt(0); 
         }
 
 
   }
   public static boolean solve(String[]t){
    int i=0;
    if(i==t.length)// la solution est trouvé et tous les  mots sont utilisés 
        return true;
       while(i<t.length)
       {
        if( !trouve(sol,i))// si le mot n'est pas encorre utilisé
            {
                if(ok(t,sol,i))// si le mot et compatible à la solution
                    {
                        sol[pos]=i;// en le place dans le tableau solution 
                        pos++;
                        solve(t);// appel recursive
 
                        pos--;
 
 
                    }
            }
        i++;
 
        }
    return false;// si pas des solution trouvés
      }
 
    public static void main(String[] args) {
        String t[] = {"358", "123", "874" , "826","638"};
        //la solution existe :123 358 826 638 874
        System.out.print(solve(t));
    }
 
 
}

enfin resolu

je poste la solution pour les autres .

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
 
 
package lastfirst;
 
public class LastFirst {
 
    public static int sol[] = {-1, -1, -1, -1, -1};
    public static int pos = 0;
 
    public static boolean trouve(int sol[], int j) {
        for (int i = 0; i < sol.length; i++) {
            if (sol[i] == j) {
                return true;
            }
        }
        return false;
    }
 
    public static void affiche(String[] t, int[] sol) {
        for (int j = 0; j < t.length && sol[j] != -1; j++) {
            System.out.print(t[sol[j]]);
        }
    }
 
    public static boolean ok(String t[], int sol[], int j) {
        if (pos == 0) {
            return true;
        } else {
            String ch1 = t[sol[pos - 1]];
            String ch2 = t[j];
            return ch1.charAt(ch1.length() - 1) == ch2.charAt(0);
        }
 
    }
 
    public static boolean solve(String[] t) {
        int i;
        if (pos == t.length)// la solution est trouvé et tous les  mots sont utilisés 
        {
            return true;
        }
        for (i = 0; i < t.length; i++) {
            if (trouve(sol, i) == false)// si le mot n'est pas encorre utilisé
            {
                if (ok(t, sol, i) == true)// si le mot et compatible avec la solution
                {
                    sol[pos] = i;// en le place dans le tableau solution 
                    affiche(t, sol);
                    System.out.println("");
                    pos++;
                    if (solve(t) == true) {
                        return true;// appel recursive
                    }
                    pos--;
                    sol[pos] = -1;
 
                }
            }
 
        }
        return false;// si pas des solution trouvés
    }
 
    public static void main(String[] args) {
        // String t[] = {"358", "123", "874" , "826","638"};
        String t[] = {"358", "123", "573", "826", "638"};
        //la solution existe :123 358 826 638 874
        System.out.print(solve(t));
    }
 
}