boucles imbriquées

Question

Bonsoir,
je débute en VisualBasic 6 et je souhaiterai avoir une précision sur un problème d'optimisation sur les boucles imbriquées.
Je m'explique
je souhaite faire parcourir aux dix variables (a,b,c,d,e,f,g,h,i,j) les 10 chiffres (0,1,2,3,4,5,6,7,8,9) avec les 10 variables toutes différentes. Je m'en sors avec quelque chose comme :

for a = 1 to 10
for b = 1 to 10
if b = a then next b
for c = 1 to 10if c b or c a then next c
for d = 1 to 10
...
là le calcul que je veux faire avec mes 10 lettres toutes différentes
...
next j
next i
...
next a

Mon problème est que les différents tests (je n'ai pas écris le dernier mais on peut imaginer) prennent du temps et l'exécution de ce programme peut être long. Je voudrais savoir si on peut faire plus rapide en temps d'execution (j'en suis presque sur) mais surtout comment.

J'avais une idée mais je ne vois pas comment la réaliser (et je ne sais si c'est la plus rapide)
Mon idée serait de créer une liste des 10 chiffres.
De prendre un chiffre de cette liste (pour a)
puis enlever ce chiffre de la liste (on obtient alors une liste de 9 chiffres)
De prendre un chiffre de cette liste (pour b)
puis enlever ce chiffre de la liste (on obtient alors une liste de 8 chiffres)
etc...
Est ce faisable et comment ?
Il y a beaucoup d'interrogation mais je débute.
N'hésitez pas à répondre et à me donner plein d'idées..
Merci
Oolivierr

cs_DARKSIDIOUS · Answer

Au lieu de passer par 10 variables, passe par un tableau de 10 lignes ! Ainsi, seul 2 boucles sont nécessaires :

For i = 0 to 10

For j = 0 to 10

if i <> j then
if tableau(i) = tableau(j) then
'les deux sont égaux !
end if
end if

next j
next i

_______________________________________

DarK Sidious

[Responsable API/VB du site www.ProgOtoP.com]
Téléchargez ProgOtoP API Viewer

jrivet · Answer

Salut, 

Pourrais tu reexpliquer ce que tu veux comme resultat avec un exemple concret s il te plait .
(Mais  c est sur que passer par des tableaux c est mieux)
@+
Julien
-----------------------------------------------------------
 :big)  Essai ca sinon on trouvera autre chose  ;) 
-----------------------------------------------------------

cs_oolivierr · Answer

Merci de vos réponses, mais je m'aperçois que je n'ai pas été assez clair. En effet, j'ai bien compris l'utilisation des tableaux mais comment les remplir ? En fait mon souci est le suivant :
Je souhaite creer un programme de résolution de cryptarithmes. Ce sont ces petits problèmes (ROUE+ROUE=VELO) où à chaque lettre correspond un chiffre (celui ci possède trois solutions dont 2673+2673=5346). Pour les trouver par l'informatique (en maths ça va), je teste donc toutes les possibiltés d'où mes 10 boucles (ici, 6 suffisent car on n'a que 6 lettres R, O, U, E, V, L) et puisque à 2 lettres différentes correspondent 2 chiffres différents je mets les différents tests IF... pour éviter de faire dérouler les 10 boucles complètes (sinon il y aurait 10^10 tours de boucles au lieu des 10! permutations possibles.
Je peux fournir le programme complet pour le résoudre  si vous avez besoin de plus de clarté dans mes explications (après tout c'est fort possible car je me comprends mais je ne suis pas sur d'être clair).
Merci
A+
Oolivierr

cs_rene38 · Answer

Bonjour
Je reprends ce que tu as écrit et je modifie :


For a = 1 To 10
  For b = a + 1 To 10
    For c = b + 1 To 10
      For d = c + 1 To 10
...
là le calcul que je veux faire avec mes 10 lettres toutes différentes
...
Next j
Next i
..
Next a

cs_oolivierr · Answer

Bonjour, merci René38, mais cela ne convient pas car dans ce cas on a toujours a<b<c<d<e<... et le j fait donc toujours 10... Où alors il y a un truc que je ne saisi pas...
Je mets ci-dessous le programme tel que je le conçois aujourd'hui :

Voici l'idée du programme pour résoudre le probleme ROUE+ROUE=VELO.

For R = 0 to 9

For O = 0 to 9
IF O=R then Next O

For U = 0 to 9
IF U=R or U = O then Next U

For E = 0 to 9
IF E=R or E = O or E=U   then Next E

For V = 0 to 9
IF V=R or V = O or V=U or V = E  then Next V

For L = 0 to 9
IF L=R or L = O or L=U or L = E or L=V  then Next L

'on teste les additions
n1=1000*R+100*O+10*U+E
n3=1000*V+100*E+10*L+O
If n1+n1=n3 then affiche_réponse 'on a trouvé une solution
Next L
Next V
Next E
Next U
Next O
Next R

Avec 10 lettres cela fait plus long sutout la conditions, mon but serait de trouver une autre manière de résoudre ces petits problèmes (par exemple pour en résoudre une centaine à la seconde)
A+
Oolivierr

Vb Lover · Answer

Alors moi, voilà ce que je pense :

1) les boucles ça marche, mais quoi qu'on fasse, ça prend beaucoup de temps pour rien. Donc même si tu optimises ta manière de faire tes boucles, il y a énormément d'essais infructueux qui pourraient être évités
2) une possibilités est de se créer un arbre de recherche, et de se trouver une heuristique pour optimiser la recherche. A chaque étape, on supprime tous les noeuds incompatibles (par exemple, pour ROUE+ROUE=VELO, il faut que O soit pair, ...). Mais c'est beaucoup de travail pour un résultat pas assuré
3) tu décomposes ton problème pour chaque colonne, et ajoutant comme inconnues les retenues; ça crée un système linéaire d'équations à résoudre, avec des boucles concernant les retenues seulement et non les lettres

Je cogite sur la 3e solution et je te tiens au courant

VB Lover

Gobillot · Answer

trouvé 3 solutions:
0673 + 0673 = 1346
2673 + 2673 = 5346
4653 + 4653 = 9306


Option Explicit
    
Dim T(5) As String
Dim n    As Integer
Dim x(9) As Integer
Dim V(6) As Integer
Dim niv  As Integer
Dim zniv As Integer
Dim i    As Integer
Dim j    As Integer
Dim s1   As Long
Dim s2   As Long
Dim b    As Boolean

Private Sub Command1_Click()

    n = 6    T(0) "R": T(1) "O": T(2) = "U": T(3) = "E"    T(4) "V": T(5) "L"
        b True: zniv 0
    While b = True
       b = False: Call Cherche(zniv)
       Wend
    MsgBox "Terminé"
    
End Sub

Private Sub Cherche(niv As Integer)

    If niv < n Then
       For i = 0 To 9
           If x(i) = 0 Then Exit For
           Next
       If i < 10 Then
          x(i) = 1
          V(niv) = i
          Call Cherche(niv + 1)
          Exit Sub
          Else
          GoTo P10
          End If
       End If

    s1 = 1000 * V(0) + 100 * V(1) + 10 * V(2) + V(3)
    s2 = 1000 * V(4) + 100 * V(3) + 10 * V(5) + V(1)
    s1 = s1 + s1
'   List1.AddItem s1 & " - " & s2

    If s1 = s2 Then
       MsgBox "Trouvé " & V(0) & " " & V(1) & " " & V(2) & " " & V(3) & " " & V(4) & " " & V(5)
'      Exit Sub
       End If

    Call Cherche(niv - 1)
    Exit Sub
    
P10:
    For niv = (n - 1) To 0 Step -1
        i = V(niv)
        x(i) = 0
        If i = 9 Then Exit For
        Next
    niv = niv - 1
    If niv < 0 Then Exit Sub
    j = V(niv)    For i 0 To 9: x(i) 0: Next    For i 0 To (niv - 1): x(V(i)) 1: Next
    For i = 0 To 9
        If x(i) = 0 And i > j Then Exit For
        Next
    If i < 10 Then
       x(i) = 1
       V(niv) = i       b True: zniv niv + 1
       Exit Sub
       End If
    
End Sub


Daniel

cs_oolivierr · Answer

Bonsoir, merci Gobillot. Cela m'a l'air fort intéressant. Je vais essayé de comprendre comment cela marche. J'ai l'impression qu'il s'agit de procédure récurrente pour former une sorte d'arbre. J'y réfléchirai demain car il se fait tard. J'ai cependant remarqué 2 choses :
1. Il y a une solution qui n'apparait pas 2693+2693=5386. Pourquoi ?
2.J'ai essayé d'adapter ton programme à un autre cryptarithme : CHER + LUC = MERCI. Cela ne me paraissait pas compliqué mais : 

a. Là aussi il ne me trouve que 12 des 14 solutions possibles (9603+789=10392) n'apparait pas.
b. J'ai fait le programme dans excel en VBA (je n'ai pas encore remis VB6 après formatage). J'ai modifié les lignes s1et s2... en s1 = 1000 * V(0) + 100 * V(1) + 10 * V(2) + V(3)
s2 = 100 * V(4) + 10 * V(5) + V(0)
s3 = V(6) * 10000 + V(2) * 1000 + 100 * V(3) + 10 * V(0) + V(7)
Et là, une erreur apparait "Dépassement de capacité" au niveau de s3.
Pour y remédier j'ai mis :
Dim V(8) 'As Integer au lieu de Dim V(8) As Integer
Encore plus étrange si je mets 
s3 = V(6) * 40000 + V(2) * 1000 + 100 * V(3) + 10 * V(0) + V(7)
qui n'a plus de sens pour nos calculs) le programme s'execute normalement (si on mets 20000 ou 30000 à la place de 10000 ca coince aussi)

Je vais y reflechir mais si tu peux y regarder toi aussi cela serait sympa car tu as l'air de mieux t'y connaitre que moi.
Merci
A+
Oolivierr

Gobillot · Answer

Bon j'ai corrigé, parce que je cherchais le 9 en remontant et je perdais pas mal de cas, maintenant je passe au niveau supérieur en cherchant le plus grand dans ceux qui reste.
Ce n'est pas la méthode de l'arbre, c'est rien que des boucles avec un peu de récursif, mais comme j'avais des "stacks out of space" j'ai dû sortir de la boucle pour libérer la pile, et après j'y reviens, d'où le booléen et la déclaration des variables en shared et non pas en locale.
pour le "Dépassement de capacité" faut mettre en Long.
J'ai mis le résultat dans une Listbox ...
si on met 20000 ou 30000 on ne trouve que les résultats avec V(6) = 0 (valeur de M)  normal !...


Option Explicit
    
Dim T(7) As String
Dim n    As Integer
Dim x(9) As Integer
Dim V(7) As Long
Dim niv  As Integer
Dim zniv As Integer
Dim i    As Integer
Dim j    As Integer
Dim s1   As Long
Dim s2   As Long
Dim S3   As Long
Dim b    As Boolean
Dim s    As String

Private Sub Command1_Click()
    
'  'ROUE + ROUE = VELO
'   n = 6'   T(0) "R": T(1) "O": T(2) = "U": T(3) = "E"'   T(4) "V": T(5) "L"

   'CHER + LUC = MERCI
    n = 8    T(0) "C": T(1) "H": T(2) = "E": T(3) = "R"    T(4) "L": T(5) "U":    T(6) "M": T(7) "I":
    b True: zniv 0
    While b = True
       b = False: Call Cherche(zniv)
       Wend
    MsgBox "Terminé"
    
End Sub

Private Sub Cherche(niv As Integer)
    If niv < n Then
       For i = 0 To 9
           If x(i) = 0 Then Exit For
           Next
       If i < 10 Then
          x(i) = 1
          V(niv) = i
          Call Cherche(niv + 1)
          Exit Sub
          Else
          GoTo P10
          End If
       End If
   
'   s1 = 1000 * V(0) + 100 * V(1) + 10 * V(2) + V(3)
'   s2 = s1
'   S3 = 1000 * V(4) + 100 * V(3) + 10 * V(5) + V(1)
    
    s1 = 1000 * V(0) + 100 * V(1) + 10 * V(2) + V(3)
    s2 = 100 * V(4) + 10 * V(5) + V(0)
    S3 = 10000 * V(6) + 1000 * V(2) + 100 * V(3) + 10 * V(0) + V(7)
    
    If (s1 + s2) = S3 Then
       s = vbNullString       For i 0 To (n - 1): s s & V(i) & " ": Next
       List1.AddItem s & "  " & s1 & "+" & s2 & "=" & S3
       DoEvents
       End If
    Call Cherche(niv - 1)
    Exit Sub
    
P10:
    niv = niv - 1
    If niv < 0 Then Exit Sub
    j = V(niv)    For i 0 To 9: x(i) 0: Next    For i 0 To (niv - 1): x(V(i)) 1: Next
    For i = 0 To 9
        If x(i) = 0 And i > j Then Exit For
        Next
    If i < 10 Then
       x(i) = 1
       V(niv) = i       b True: zniv niv + 1
       Exit Sub
       Else
       GoTo P10
       End If
    
End Sub

Vb Lover · Answer

Voilà, j'ai cogité un peu et en résumé (je me base sur l'exemple 
ROUE+ROUE=VELO) :

Si on fait des boucles sur toutes les lettres (y'en a 6) jusqu'à trouver une solution, ça fait 10^6 passages dans les boucles.
En fait, on se rend bien compte que les variables sont reliées entre elles et qu'on fait plein d'itérations inutiles.

Maintenant, utilisons la manière suivante :
il y a 4 colonnes dans notre addition. En plus des lettres inconnues, on se rajoute 3 retenues pour les 3 colonnes de gauche (par ex., E+E=10*retenue1+0); les retenues ici valent 0 ou 1. On a donc 9 symboles à trouver.
Ensuite, on traduit les 4 équations des colonnes dans une matrice 4x9, qu'on échelonne. Le résultat de cette opération, c'est que sur les 9 inconnues, seulement 5 sont indépendantes, et que sur ces 5, 2 ont 10 valeurs possibles et les 3 retenues seulement 2 valeurs possibles. Donc il faut 2^3 * 10^2 = 800 boucles.
Finalement, on fait comme les réponses ci-dessus pour résoudre le problème.

Bien sûr, tout ceci peut-être appliqué à n'importe quel crytarithme de manière automatisée.

En conclusion : avec quelques opérations (échelonner-réduire une matrice : très très rapide), on va plus de 1000 fois plus vite !!

VB Lover

Boucles imbriquées

10 réponses

Discussions similaires