probleme Train de domino !Résolu

Question

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

Utilisateur anonyme · Accepted Answer

Ha ok, j'avais pas vu qu'il fallait les ordonner
Une solution, par forcement la plus optimisé, mais on peut facilement optimiser la fonction de test et limiter les arrangements impossibles


Sub Main()
  Dim str As String = "358 123 874 826 638"
  If TestDomino(str) Then
    Console.WriteLine("possible")
    Console.WriteLine(str)
  Else
    Console.WriteLine("impossible ")
  End If
End Sub

Function TestDomino(ByRef str As String) As Boolean
  Dim values() As String = str.Split(New Char() {" "c}, StringSplitOptions.RemoveEmptyEntries)
  Dim ok As Boolean = TestDomino(values, 0, values.GetUpperBound(0))
  If ok Then
    str = String.Join(" "c, values)
  End If
  Return ok
End Function

Function TestDomino(ByRef values() As String, ByVal startpos As Integer, ByVal endpos As Integer) As Boolean
  Dim tmp As String
  Dim ok As Boolean = CheckDomino(values)
  Dim i, j As Integer
  i = startpos
  While Not ok AndAlso i <= endpos
    j = i + 1
    While Not ok AndAlso j <= endpos
      tmp = values(i)
      values(i) = values(j)
      values(j) = tmp
      ok = TestDomino(values, i + 1, endpos)
      If Not ok Then
        values(j) = values(i)
        values(i) = tmp
        j += 1
      End If
    End While
    i += 1
  End While
  Return ok
End Function

Function CheckDomino(ByRef values() As String) As Boolean
  Dim ok As Boolean = True
  Dim i As Integer = 0
  While ok AndAlso i < values.Length - 1
    Dim a As String = values(i).Substring(values(i).Length - 1)
    Dim b As String = values(i + 1).Substring(0, 1)
    ok a b
    i += 1
  End While
  Return ok
End Function


Voilà, à arranger comme tu veux.

_____________
Kenji

Utilisateur anonyme · Answer

Bonjour,

Pas besoins de récursivité, c'est juste une comparaison de bloc 2 par 2


Function MonDeLaFonction(str As String) As Boolean
  Dim groups() As String = str.Split(New Char() {" "c}, StringSplitOptions.RemoveEmptyEntries)
  Dim ok As Boolean = True
  Dim i As Integer = 0
  While ok AndAlso i < groups.Length - 1
    Dim a As String = groups(i).Substring(groups(i).Length - 1)
    Dim b As String = groups(i + 1).Substring(0, 1)
    ok a b
    i += 1
  End While
  Return ok
End Function



_____________
Kenji

mouradj2006 · Answer

merci pour la réponse mais je cherche pas à vérifier une  propriété , je veux l'ordonner de la manière indiqué dans l&#8217;énoncée si possible sinon le programme affiche que ce  impossible de l&#8217;ordonnée .
merci

ucfoutu · Answer

Bonjour,
Je te propose de mettre en place un mécanisme bourrin, mais efficace :
1) tu as donc 5 éléments
2) tu fais la liste de tous les arrangements de 5 possibles de ces 5 éléments, . Leur nombre, égal à 5! (factorielle 5) n'est que 120 (soit très peu)
3) tu parcours chacun des membres de cette liste. Tu abandonnes un membre dès "cassure" (facile).
Tu abandonnes la boucle si un membre est sans "cassure" et met ce membre (dont une chaîne) dans une variable toto
4) si toto <> "" tu affiches toto, sinon tu affiches "impossible".

120 chaînes de caractères à traiter, c'est du gâteau en matière de durée de traitement. Et ce : d'autant que la plupart des "chaînes"/membres seront éliminées bien avant d'en avoir parcouru tous le groupes.


________________________
Réponse exacte ? => "REPONSE ACCEPTEE" pour faciliter les recherches.
Pas d'aide en ligne installée ? => ne comptez pas sur moi pour simplement vous dire ce qu'elle contient. Je n'interviendrai qu'en cas de nécessité de développ

ucfoutu · Answer

Bon...
Je ne vais pas traiter la première partie (tous les arrangements, 5 à 5, de 5 éléments). Tu trouveras sur le web des quantités d'algos et de codes pour parvenir à en dresser la liste.
Nous n'allons voir ensemble que la manière de déterminer si une chaîne (parmi celles à parcourir en boucle dans la liste ainsi obtenue, est ou non valable (sans "cassure").
Je ne sais pas écrire en VB.Net, mais voilà un code VB6 que tu ne devrais avoir aucune difficulté à transposer :
  ch = "123 358 826 638 874"
  For i = 5 To Len(ch) Step 4
    If Left(Mid(ch, i, 3), 1) <> Right(Mid(ch, i - 2, 1), 1) Then Exit For
  Next
  If i >= Len(ch) Then MsgBox "bon" Else MsgBox "mauvais"

Tu as pour moi maintenant tout ce qu'il faut à un développeur, même débutant, pour parvenir à tes fins avec un tout petit peu de travail (vraiment très peu)
Bonne chance
________________________
Réponse exacte ? => "REPONSE ACCEPTEE" pour faciliter les recherches.
Pas d'aide en ligne installée ? => ne comptez pas sur moi pour simplement vous dire ce qu'elle contient. Je n'interviendrai qu'en cas de nécessité de développ

4u4me4us · Answer

Je te propose l'algo. suivant

tableau wagon = splite de la chaine "358 123 874 826 638" 

indice1 = 0
indice2 = 1
temporaire = vide
réponse = vrai

TANT QUE réponse = vrai et que indice 2 < que le nombre de cases de tableau wagon

SI le dernier caractère du tableau wagon case indice1 n'est pas égale au premier caractère du tableau wagon case indice2
  VRAI: 
    réponse = non
  FAUX:
   temporaire = tableau wagon case indice1
   tableau wagon case indice1 = tableau wagon case indice2
   tableau wagon case indice2 = temporaire 
FIN DU SI  
incrémenter indice1 et indice2 
RÉPÉTÉ 
SI réponse = vrai 
   VRAI:
    afficher les cases du tableau wagon
   FAUX:
    afficher "impossible"
FIN DU SI


Voila le l'idée que j'ai.

NOTE : Je me suis dis que c t plus rapide de te l'explique ainsi plus tôt que de le programmer.Quand j'ai vu mon erreur  j'étais à plus de la moité donc sorry

ucfoutu · Answer

Ouille !
Je viens de relire mon bout de code précédent et je vois bien que, bien que juste, il est inutilement tortueux !
Il est vrai que je n'avais pas encore bu mon vin !!!
Allez ! ===>>
  ch = "123 358 826 638 874"
  For i = 5 To Len(ch) Step 4
    If Mid(ch, i, 1) <> Mid(ch, i - 2, 1) Then Exit For
  Next
  If i >= Len(ch) Then MsgBox "bon" Else MsgBox "mauvais"

Encore plus facile à transposer en VB.Net, selon ce que je comprends de ce "langage"-là ! 

________________________
Réponse exacte ? => "REPONSE ACCEPTEE" pour faciliter les recherches.
Pas d'aide en ligne installée ? => ne comptez pas sur moi pour simplement vous dire ce qu'elle contient. Je n'interviendrai qu'en cas de nécessité de développ

mouradj2006 · Answer

pour la solution de 4u4me4us est totalement fausse il se bloque de la deuxième case  pour dire que c'est impossible alors la vérité que c'est possible

4u4me4us · Answer

Oui mouradj2006 je me suis planté sur le if. J'aurais du écrire :

SI le PREMIER caractère du tableau wagon case indice1 n'est pas égale au DERNIER caractère du tableau wagon case indice2

probleme Train de domino !

9 réponses

Votre réponse

Discussions similaires