## Mise en place from random import randint from numpy import infty class sommet: def __init__(self, nom = 0, voisins = -1, distance = -1, graph = None, nourriture = -1): self.nom = nom if voisins == -1: #Pour les classes sommet et graphs, on doit initialiser les listes comme ceci et non en les mettant en variable par défaut, sinon, lorsqu'on crée plusieurs sommets/graphes, leurs valeurs seront les mêmes car les adresses mémoires seront générés indépendement de la création des sommets et graphes. self.voisins = [] else : self.voisins = voisins self.tresor = False self.distance = distance self.graph = graph if nourriture == -1 : #-1 si on génère aléatoirement test = randint(0,9) if test: #Si test ne vaut pas 0, on ne génère pas de nourriture self.nourriture = False else: self.nourriture = True else: self.nourriture = nourriture def __repr__(self): """ fonction qui permet, lorsqu'on affiche un sommet de donner son nom, l'existance d'un trésor ou non dessus, sa distance à un trésor et les noms de ses voisins """ if self.distance ==0: print("Il y avait un trésor sur le sommet", self.nom) txt = "" elif self.graph.nb_tresor==0: txt = "sommet :" + str(self.nom) + "\nil n'y a plus de trésor dans ce graphe" else: txt = "sommet : {nom} \ndistance à un trésor : ".format(nom = self.nom ) #utiliser .format permets d'avoir des chaines de caractères plus claires. Ici on remplace {nom} dans le texte par self.nom. (ceci n'était pas demandé dans l'évaluation) if self.distance == infty: txt += "inconnue." else: txt += str(self.distance) txt += "\nSes voisins sont les sommets suivants : " for i in self.voisins: txt += str(i.nom) + ", " txt = txt[:-2]+"\n" return txt class graph: def __init__(self, sommets = -1, nb_tresor = 0): if sommets == -1: self.sommets = [] else : self.sommets = sommets self.nb_tresor = nb_tresor for i in sommets: i.graph = self def genere_tresor(self): """ Ici, on décide que si on essaie de générer un trésor sur une case qui en contient déjà un, il ne se passe rien. On pourrait générer que sur les cases n'en contenant pas pour toujours générer un trésor""" n = len(self.sommets) if n==0: #Si le graphe est vide, on peut pas générer de trésor print("graphe vide") return None i = randint(0,n-1) #On génère un sommet aléatoire if self.sommets[i].tresor == False: #S'il contient pas de trésor self.sommets[i].tresor = True #On en met un et on met a jour la distance et le nombre de trésor self.sommets[i].distance = 0 self.nb_tresor += 1 class explorateur: def __init__(self,position = None,butin = 0, energie = 10): self.position = position self.butin = butin self.energie = energie def deplacement(self, cible): """ Si l'on souhaite ne pas gérer l'énergie, il suffit de commenter toutes les lignes ou la variable énergie intervient""" if self.energie==0: return "Vous n'avez plus d'énergie" calcul_dist(self.position.graph) pos = self.position if cible <= len(pos.voisins): #Si la cible existe self.position = pos.voisins[cible] #On place l'explorateur sur la cible self.energie -=1 if self.position.tresor == True: #S'il y a un trésor self.position.tresor = False self.butin +=1 #On le ramasse self.position.graph.nb_tresor -=1 #On met a jour le nombre de trésor dans le graphe if self.position.nourriture==True: #S'il y a de la nourriture self.position.nourriture = False self.energie +=5 #On augmente l'énergie return "deplacement effectué" else: return "déplacement impossible" ## Graphe exemple #Cycle à n sommets n = 10 V = [sommet(nom = i, voisins = [], distance = -1) for i in range(n)] for i in range(n): V[i].voisins.append(V[(i+1)%n]) V[i].voisins.append(V[(i-1)%n]) C10 = graph(sommets = V, nb_tresor = 0) C10.genere_tresor() ## Recherche de trésor j = explorateur(position = V[0], butin = 0) def recherche_tresor(j): while j.butin == 0: print(j.position) try : cible = int(input("sur quel sommet souhaitez vous aller ?")) except TypeError: #S'il y a une erreur de type, l'utilisateur n'a pas entré un entier print("nom de sommet incorrect") #Donc aucun sommet n'a ce nom mouv = False for i in range(len(j.position.voisins)): if j.position.voisins[i].nom == cible: #On vérifie si le nom entré est dans la liste des voisisn j.deplacement(i) mouv = True break if mouv == False: #Si on a toujours pas bougé, l'entier entré par l'utilisateur n'est pas disponible depuis la position actuelle print("le déplacement demandé est impossible") return "bravo" def calcul_dist(G): som = G.sommets #La distance maximale à un trésor est le nombre de sommet dans le graphe. for v in range(len(som)): #Boucle pour initialiser les distances if som[v].tresor == True: som[v].distance=0 else : som[v].distance = len(som) #L'algorithme utilisé est celui de Dijkstra : à la j-eme étape de la boucles, tous les sommets à distance au plus j d'un trésor ont la bonne valeur de distance for j in range(len(som)): for i in range(len(som)): x = som[i] d = x.distance for vois in x.voisins: #pour aller à un trésor, en d mouvements, il faut aller sur un voisins, pui aller à un trésor en d-1 mouvements d = min(d, 1+ vois.distance) x.distance = d calcul_dist(C10) def recherche_nourriture(j): while j.energie !=0: #Tant qu'on a de l'énergie print("Il vous reste", j.energie, "énergie !") print(j.position) try : #On essaie de se déplacer cible = int(input("sur quel sommet souhaitez vous aller ?")) except TypeError: print("nom de sommet incorrect") mouv = False for i in range(len(j.position.voisins)): #On se déplace sur le voisin s'il existe if j.position.voisins[i].nom == cible: j.deplacement(i) #La méthode déplacement a été modifiée pour gérer l'énergie mouv = True break #On quitte la boucle après avoir fait le déplacement pour gagner du temps if mouv == False: print("le déplacement demandé est impossible") print("Vous n'avez plus d'énergie, vous avez trouvé", j.butin, " trésors !")