Programme harmonie.py
###############################################################################
# questions 1 a 5
###############################################################################
def lit_fichier (nom) :
"""cette fonction lit le contenu d'un fichier
et retourne une liste contenant ses lignes"""
f = open (nom, "r")
li = f.readlines ()
f.close ()
r =[]
for l in li :
s = l.replace ("\n", "")
s = s.replace ("\r", "")
r.append (s)
return r
def genre (prenom, femme, homme) :
"""retourne le genre d'un prenom"""
if prenom in femme : return True
if prenom in homme : return False
return None
def contrainte (table, femme, homme) :
"""cette fonction verifie que la table
obeit aux contrainte d'Harmonie :
il ne peut y avoir trois personnes voisines du meme sexe
qui se suivent"""
ge = [ genre (t,femme, homme) for t in table ]
for i in range (0,len (ge)) :
if ge [i] == ge [ (i+1) % len (ge) ] == ge [(i+2) % len (ge) ] :
return False
return True
def dominique (table, femme, homme) :
"""cette fonction dit si on peut placer dominique,
deux schemas de figures possibles :
1- H F dominique H F
2- F H dominique F H
"""
ge = [ genre (t,femme, homme) for t in table ]
for i in range (0,len (ge)) :
if ge [i] != ge [ (i+1) % len (ge) ] and \
ge [(i+2) % len (ge)] != ge [ (i+3) % len (ge) ] and \
ge [i] == ge [ (i+2) % len (ge) ] :
return True
return False
femme = lit_fichier ("femme.txt")
homme = lit_fichier ("homme.txt")
table = lit_fichier ("table.txt")
r = contrainte (table, femme, homme)
print "la table suit les desirs d'Harmonie : ", r
r = dominique (table, femme, homme)
print "peut-on ajouter Dominique : ", r
###############################################################################
# question 6
###############################################################################
def contrainte_dominique (table, femme, homme) :
"""meme fonction que contrainte mais on tient aussi du fait que
le genre peut etre indetermine (None), toute configuration
incertaine est eliminee"""
ge = [ genre (t,femme, homme) for t in table ]
for i in range (0,len (ge)) :
if ge [i] == ge [ (i+1) % len (ge) ] == ge [(i+2) % len (ge) ] :
return False
if ge [i] == None and ge [ (i+1) % len (ge) ] == ge [(i+2) % len (ge) ] :
return False
if ge [i] == ge [ (i+1) % len (ge) ] and ge [(i+2) % len (ge) ] == None :
return False
if ge [i] == ge [ (i+2) % len (ge) ] and ge [(i+1) % len (ge) ] == None :
return False
if ge [i] == None and ge [ (i+1) % len (ge) ] == None :
return False
if ge [i] == None and ge [ (i+2) % len (ge) ] == None :
return False
if ge [ (i+2) % len (ge) ] == None and ge [ (i+1) % len (ge) ] == None :
return False
return True
def place_dominique (table, femme, homme) :
"""on cherche a inserer autant de dominique que possible"""
nb = len (table)
fin = False
while not fin :
fin = True
for i in range (0, len (table)) :
table.insert (i, "DOMINIQUE")
r = contrainte_dominique (table, femme, homme)
if r :
fin = False
break
else :
del table [i]
return len (table) - nb
print "-----------------------------------------------------------------"
nb = place_dominique (table, femme, homme)
print "nombre de dominique ", nb
for p in table :
print p
###############################################################################
# question 7
###############################################################################
#
# nombre minimal : partie entiere de (n+1)/2
# nombre maximal : 2n
#
###############################################################################
# question 8
###############################################################################
def trois_pareil (table) :
"""table est une suite booleens, on retourne True
s'il n'y en a pas trois consecutifs"""
for i in xrange (len (table)-2) :
if table [i] == table [i+1] == table [i+2] :
return False
return True
def trois_pareil_rond (table) :
"""table est une suite booleens, on retourne True
s'il n'y en a pas trois consecutifs"""
for i in xrange (len (table)) :
if table [i] == table [ (i+1) % len (table)] == table [(i+2) % len (table)] :
return False
return True
def compte (n) :
"""on parcours toutes les tables possibles et on compte les
bonnes configurations"""
table = [ False for i in range (0,n) ]
nb = 0
bon = 0
while table [0] != None :
nb += 1
if trois_pareil_rond (table) : bon += 1
for i in xrange (len (table)-1, -1, -1) :
if not table [i] :
table [i] = True
break
else :
table [i] = False
if i == 0 : table [0] = None
return nb, bon
print "-----------------------------------------------------------------"
print "calcul en parcourant toutes les tables possibles"
print "-----------------------------------------------------------------"
for n in range (3, 15) :
nb, bon = compte (n)
print n, " nb = ", nb, " bon = ", bon,
print " proba = ", float (bon) / float (nb), " \t",
print bon, "/", nb
###############################################################################
# question 8
# markov
###############################################################################
# module pour le calcul matriciel
import numpy
import copy
def construit_matrice () :
"""construit la matrice de transition,
le vecteur des probabilites d'entrees dans chaque etat"""
# construction des etats
etat = []
for i in range (0,2) :
for j in range (0,2) :
for k in range (0,2) :
etat.append ( (i,j,k) )
# construction de la matrice
mat = []
for i in range (0, len (etat)) :
l = []
for j in range (0, len (etat)) :
if etat [i] [1:3] == etat [j] [0:2] :
# (i,j,k) --> (j,k,0) ou (j,k,1)
l.append (1)
else : l.append (0)
# on renormalise sur chaque ligne
s = sum (l)
for j in range (0, len (etat)) : l[j] /= float (s)
mat.append (l)
entree = [ 0.125 for i in range (0,8) ]
return etat, numpy.matrix (mat), numpy.matrix (entree)
def calcul_probabilite_droite (n, etat, mat_, entree) :
"""calcule les probabilites pour une table droite"""
pos = [ etat.index ( (0,0,0) ), etat.index ( (1,1,1) ) ]
temp = copy.deepcopy (entree)
mat = copy.deepcopy (mat_)
for p in pos :
for i in range (0,8) :
mat [ (p,i) ] = 0.0
mat [ (p,p) ] = 1.0
m = mat ** (n-1)
sum = 0.0
for i in range (0,8) :
for j in range (0,8) :
if i not in pos and j not in pos :
sum += m [ (i,j) ] * mat [ (j,i) ]
return sum
print "-----------------------------------------------------------------"
print "calcul avec les chaines de Markov"
print "-----------------------------------------------------------------"
etat,mat,entree = construit_matrice ()
for n in range (3,15) :
proba = calcul_probabilite_droite (n, etat, mat, entree)
print n, " bon ", proba
créé avec py2html version:0.62