Ça peut peut-être aider à clarifier les idées, en tout cas ça permet de calculer un stock d'exemples qu'il serait pénible d'obtenir à la main.
Codage :
Pour aller vite, on appelle fourmi droite une fourmi qui va vers la droite et fourmi gauche une fourmi qui va vers la gauche.
Liste D pour les fourmis droites. Fourmis rangées dans l'ordre, avec pour chaque fourmi un couple
dont la première composante est un état : 0 si la fourmi est active, i si la fourmi est zombie après avoir rencontré la fourmi gauche n°i (numérotation commençant à 1 et allant jusqu'à p, nombre de fourmis gauches) et avant de la rencontrer de nouveau.
dont la deuxième composante est le nombre d'épisodes "zombie" vécus par la fourmi.
Liste G pour les fourmis gauches. Fourmis rangées dans l'ordre, avec pour chaque fourmi un couple
dont la première composante est l'indice du trou entre fourmis droites où elle se trouve (indice de la fourmi droite à l'extrémité gauche du trou, les indices de fourmis droites vont de 0 à n-1 où n est leur nombre),
dont la deuxième composante est le caractère "z" (si la fourmi est zombie après avoir rencontré une fourmi droite et avant de la rencontrer de nouveau) ou "a" (si la fourmi est active).
L'état initial est donné par une chaîne de caractères "d" ou "g" (pour fourmi droite ou gauche, respectivement).
- Code: Tout sélectionner
# Procédure qui à partir d'une chaîne contituée de "d" et de "g",
# produit les listes intiales D et G
def Initiale(chaine) :
n = chaine.count("d")
D=[] ; G=[]; trou=n-1
for c in chaine :
if c=="d":
D.append([0,0])
trou = (trou+1)%n
if c=="g":
G.append([trou,"a"])
return D,G
- Code: Tout sélectionner
# Procédure qui fait sauter de trou chaque fourmi gauche
def PasGauche(D,G) :
for i in range(len(G)) :
trou=G[i][0] ; etat=G[i][1]
if (etat=="z" and D[trou][0]==i+1) :
D[trou][0]=0
D[trou][1]+=1
G[i][1]="a"
if (etat=="a" and D[trou][0]==0) :
D[trou][0]=i+1
G[i][1]="z"
G[i][0]=(trou-1)%(len(D))
return D,G
- Code: Tout sélectionner
# Procédure qui fait un demi-tour
def DemiTour(D,G) :
for i in range(len(D)):
D,G=PasGauche(D,G)
return D,G
- Code: Tout sélectionner
# Procédure qui prend en entrée une chaîne de "d" et "g",
# calcule la période en nombre de demi-tours,
# le nombre d'épisodes' "zombie" pour chaque fourmi droite,
# imprime la période en tours
def Periode(chaine) :
D,G=Initiale(chaine)
D,G=DemiTour(D,G)
nb=1
while not(all(d[0]==0 for d in D)):
D,G=DemiTour(D,G)
nb+=1
per=nb//((nb+1)%2+1)
print("Période en tours :",per )
return nb, [d[1] for d in D]
Quelques exemples d'utilisation, d'abord correspondant aux dessins de Vassilia plus haut :
- Code: Tout sélectionner
Periode("ddg")
(3, [1, 1])
- Code: Tout sélectionner
Periode("dddg")
(4, [1, 1, 1])
- Code: Tout sélectionner
Periode("ddgg")
(2, [1, 1])
- Code: Tout sélectionner
Periode("dgdg")
(3, [2, 2])
D'autres exemples plus méchants qui montrent qu'un petit changement peut faire une grande différence.
- Code: Tout sélectionner
Periode("dgdggdgdggdg")
(8, [7, 7, 7, 7, 7])
- Code: Tout sélectionner
Periode("ddgggdgdggdg")
(162, [133, 133, 133, 133, 133])
On voit sur les exemples que le nombre d'épisodes "zombie" est le même pour toutes les fourmis droites. Ce n'est pas évident a priori, montrer ce fait pourrait être une étape dans la compréhension.