# -*- coding: utf-8 -*-
# Created on Sat Sep 31 08:15:00 2024
# @author: mhebding
# TP1 - Revisions



## 1 - Algorithmique

# 1.
def somme(a):
	resultat = 0
	for element in a:
		resultat += element
	return resultat

def somme_bis(a):
	resultat = 0
	for i in range(len(a)):
		resultat += a[i]
	return resultat

# 2.
def moyenne(a):
	return somme(a)/len(a)

# 3.
def is_prime(n):
	if n < 2: 
		return False
	d = 2
	while d * d <= n:
		if n % d == 0:
			return False
		d += 1
	return True

# 4.
def next_prime(n):
	p = n + 1
	while not is_prime(p):
		p += 1
	return p

# 5.
def factorielle(n):
    """Ceci est une fonction recursive qui s'appelle
   elle-meme pour trouver la factorielle du nombre donne"""
    if n == 1:
        return n
    else:
        return n * factorielle(n - 1)

# 6.
def liste_pos(x,L):
	positions = []
	for i in range(len(L)):
		if L[i] == x:
			positions.append(i)
	return positions

#print(liste_pos(3,[1,3,5,2,3])) doit renvoyer [1,4]

# 7. 
# La complexité temporelle de cette fonction est en O(n).



## 2 - Le rendu de monnaie glouton

# 8.
systeme_euro = [500, 200, 100, 50, 20, 10, 5, 2, 1]

def rendu_monnaie(somme, systeme):
    liste_pieces = [] # liste de valeurs retournees
    for valeur in systeme: # pour chaque billet
        while somme >= valeur: # il est utilise tant que cela est possible
            liste_pieces.append(valeur)
            somme = somme - valeur
    return liste_pieces
            
#print(rendu_monnaie(97,systeme_euro)) doit renvoyer [50, 20, 20, 5, 2]

#print(rendu_monnaie(97,systeme_euro)) doit renvoyer [50, 20, 20, 5, 2]



## 3 - Dictionnaires

# 9. 
def nombre_elements_distincts_liste(liste):
    elements_rencontres = []   
    for element in liste:
        if element not in elements_rencontres:
            elements_rencontres.append(element)
    return len(elements_rencontres)
    
# 10. 
def nombre_elements_distincts_dictionnaire(liste):
    elements_rencontres = {}
    for element in liste:
        if element not in elements_rencontres:
            elements_rencontres[element] = True
    return len(elements_rencontres)
    
# 11. 
import random
import time

# Générer une liste aléatoire d'environ 100 000 entiers entre 0 et 10 000
taille_liste = 100000
liste_aleatoire = [random.randint(0, 10000) for _ in range(taille_liste)]

# Comparaison des performances

# Mesurer le temps pour la fonction avec une liste
debut_liste = time.time()
nombre_distincts_liste = nombre_elements_distincts_liste(liste_aleatoire)
fin_liste = time.time()
temps_liste = fin_liste - debut_liste

# Mesurer le temps pour la fonction avec un dictionnaire
debut_dictionnaire = time.time()
nombre_distincts_dictionnaire = nombre_elements_distincts_dictionnaire(liste_aleatoire)
fin_dictionnaire = time.time()
temps_dictionnaire = fin_dictionnaire - debut_dictionnaire

# Affichage des résultats
print(f"Temps avec la méthode utilisant une liste : {temps_liste:.6f} secondes")
print(f"Temps avec la méthode utilisant un dictionnaire : {temps_dictionnaire:.6f} secondes")
print(f"Nombre d'éléments distincts (liste) : {nombre_distincts_liste}")
print(f"Nombre d'éléments distincts (dictionnaire) : {nombre_distincts_dictionnaire}")

# 12. 
def mot_le_plus_frequent(chaine):
    mots = chaine.split() # separer les mots en utilisant espace comme separateur
    compte_mots = {} # initialisation dictionnaire vide
    for mot in mots:
        if mot in compte_mots:
            compte_mots[mot] += 1
        else:
            compte_mots[mot] = 1
    mot_frequent = max(compte_mots, key=compte_mots.get) # trouver le plus frequent
    return mot_frequent
    


## 4 - Graphes

graphe = {"A":("B","D","E"),"B":("A","C"),"C":("B","D"),"D":("A","C","E"),"E":("A","D","F","G"),"F":("E","G"),"G":("E","F","H"),"H":("G")}

# 13.
def parcours_en_largeur(graphe, sommet):
    """
    Parcours d'un graphe en largeur
    :param graphe: une liste d'adajence du graphe étudié (un dictionnaire)
    :param sommet: le sommet de départ du graphe étudié
    :return: la liste des sommets du graphe
    >>> parcours_en_largeur({"A":("B","D","E"),"B":("A","C"),"C":("B","D"),"D":("A","C","E"),"E":("A","D","F","G"),"F":("E","G"),"G":("E","F","H"),"H":("G")},"A")
    ['A', 'B', 'D', 'E', 'C', 'F', 'G', 'H']
    """
    if not(sommet in graphe.keys()):
        return None
    F = [sommet]
    liste_sommets = []
    while len(F) != 0:
        S = F[0]
        for voisin in graphe[S]:
            if not(voisin in liste_sommets) and not(voisin in F):
                F.append(voisin)
        liste_sommets.append(F.pop(0))
    return liste_sommets

for sommet in graphe.keys():
    print(parcours_en_largeur(graphe,sommet))

def parcours_en_profondeur(graphe, sommet):
    """
    Parcours d'un graphe en profondeur
    :param graphe: une liste d'adajence du graphe étudié (un dictionnaire)
    :param sommet: le sommet de départ du graphe étudié
    :return: la liste des sommets du graphe
    >>> parcours_en_profondeur({"A":("B","D","E"),"B":("A","C"),"C":("B","D"),"D":("A","C","E"),"E":("A","D","F","G"),"F":("E","G"),"G":("E","F","H"),"H":("G")},"A")
    ['A', 'E', 'G', 'H', 'F', 'D', 'C', 'B']
    """
    if not(sommet in graphe.keys()):
        return None
    P = [sommet]
    liste_sommets = []
    while len(P) != 0:
        S = P.pop()
        liste_sommets.append(S)
        for voisin in graphe[S]:
            if not(voisin in liste_sommets) and not(voisin in P):
                P.append(voisin)
    return liste_sommets

for sommet in graphe.keys():
    print(sommet,parcours_en_profondeur(graphe,sommet))