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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
| Private Sub CommandButton1_Click()
Dim inn(8) As Integer '====== inn(s) = le nb de flèches rentrantes en s
Dim libre As Integer '====== le nombre de flèches restantes à créer
Dim c(8, 4) As Integer '====== compteur des candidats par sommets:
'==== c(s,0)...,c(s,4) donne les flèches s-->c(s,0) ,...,s-->c(s,4) qu'on va tester
'==== on va chercher à construire les flèches en allant du sommet 1 au sommet 8:
'==== si au sommet 8 les candidats c(8,-) sont OK, c'est gagné!!
Dim pc As Integer '====== pointe le ième sommet en cours de tentative
Dim succes, total As Double
Dim fini, b, bb As Boolean
Dim j, k, l As Integer
fin = False
Dim sol As String
For i = 0 To 8
inn(i) = 0
Next i
'======= ici, on crée 5 flèches issues de 0 vers 4,5,6,7 et 8
'======= (à équivalence près toutes les solutions commencent par ça)
pc = 1
For i = 0 To 4
c(0, i) = 4 + i
inn(4 + i) = 1
Next i
c(1, 0) = 0
For i = 1 To 4
c(1, i) = 1 + i
Next i
c(1, 4) = 4
libre = 40
succes = 0
total = 0
While fini = False
j = 4
c(pc, j) = c(pc, j) + 1 '== on incrémente le 5ième sommet
If c(pc, j) = pc Then c(pc, j) = c(pc, j) + 1 '== ici, c'est pour ne pas créer une flèche pc --> pc (ce test est présent tout le long du code)
While (c(pc, 4) > 8 And j > 0) '=== si le 5ième sommet est >8, on passe au 4ième
'=== et on l'incrémente "lexico" et le 5ième est alors le 4ième+1. Et on redescend tant que.... Au pire, à la fin j=0.
j = j - 1
c(pc, j) = c(pc, j) + 1
If c(pc, j) = pc Then c(pc, j) = c(pc, j) + 1
For k = j + 1 To 4
c(pc, k) = c(pc, k - 1) + 1
If c(pc, k) = pc Then c(pc, k) = c(pc, k) + 1
Next k
Wend
If (c(pc, 4) < 9 And (9 - pc) * 5 >= libre) Then '==== sinon, c(pc,4)=5,6,7,8,9 où il n'y a plus de place suffisante libre pour crée rles 5 flèches, et ON A FINI avec ce sommet, il faut remonter au précédent
b = True
'=== donc ici, les c(pc,-) peuvent être testées pour créer les 5 flèches
j = 0
While (b = True And j < 5)
If inn(c(pc, j)) = 5 Then
'=== le somment c(pc,j) n'a plus de place pour recevoir une flèche!!
b = False
Else
j = j + 1
End If
Wend '=== à la fin b=false si l'une des flèches ne peut pas être construire...
bb = True
j = pc + 1
While (bb = True And j < 9)
'=== ici, on évalue ce que va donner la construction des 5 flèches: peut-être
'=== que cela va amener à une position qui ne marchera pas: par exemple,
'=== si au sommet 6 on construit les 5 flèches mais qu'alors inn(7)=3, on
'=== devra ultérieurement construire 2 flèches allant vers 7: impossible, car
'=== les 2 sommets restant à traiter sont 7 et 8, et on ne fait pas de 7 --> 7.
If (k >= 3 And inn(k) < k - 2) Then
bb = False
Else
j = j + 1
End If
Wend
If (b = True And bb = True) Then
'====== succes sur le sommet pc! Les flèches sont les pc --> c(pc,-)
For j = 0 To 4 '=== on MAJ la disponibilité des sommets
inn(c(pc, j)) = inn(c(pc, j)) + 1
Next j
libre = libre - 5 '=== on réduit le nombre de flèches à créer
If (pc = 8 Or libre = 0) Then '====== graphe trouvé!!!
succes = succes + 1
sol = ""
For k = 0 To 8
sol = sol + " ("
For l = 0 To 4
sol = sol & c(k, l) & " "
Next l
sol = sol + ")"
Next k
Worksheets("Sheet1").Cells(5 + succes, 2) = sol
Worksheets("Sheet1").Cells(4, 2) = succes
'====== ici, on annule la sélection c(pc,-) du graphe trouvé, pour remonter
For j = 0 To 4
libre = libre + 1
inn(c(pc, j)) = inn(c(pc, j)) - 1
Next j
c(pc, 4) = c(pc, 4) + 1
If c(pc, 4) = pc Then c(pc, 4) = c(pc, 4) + 1
Else
pc = pc + 1
For j = 0 To 4
c(pc, j) = j 'c(pc - 1, j)
If c(pc, j) = pc Then c(pc, j) = c(pc, j) + 1
If j > 0 Then
If c(pc, j) <= c(pc, j - 1) Then c(pc, j) = c(pc, j - 1) + 1
End If
Next j
c(pc, 4) = c(pc, 4) - 1
End If
End If
Else '======== échec des candidats c(pc,-)
total = total + 1
Worksheets("Sheet1").Cells(6, 2) = total
pc = pc - 1 '==== on remonte au sommet précédent
If pc = 0 Then
fini = True '========= tout est parsé, car c(1,-) = 45679
Else
For j = 0 To 4 '====== on annule la sélection c(pc,-)
libre = libre + 1
inn(c(pc, j)) = inn(c(pc, j)) - 1
Next j
l = 0
For j = 1 To pc - 2
If c(j, 4) > l Then l = c(j, 4)
Next j
k = 4
While (c(pc, k) > l And k >= pc)
k = k - 1
Wend
c(pc, k) = c(pc, k) + 1
If c(pc, k) = pc Then c(pc, k) = c(pc, k) + 1
For l = k + 1 To 4
c(pc, l) = c(pc, l - 1) + 1
If c(pc, l) = pc Then c(pc, l) = c(pc, l) + 1
Next l
End If
End If
Wend
End Sub |
Partager