## TP11 -- Dictionnaires



## Exercise 11.2

## question 5) c)

def monDico(n):
    d = {}
    for i in range(n+1):
        L = []
        for k in range(i):
            L.append(k+1)
        d[i] = L
    return d

def monDico2(n):
    d = {}
    for i in range(n+1):
        L = [ k+1 for k in range(i) ]
        d[i] = L
    return d

def monDico3(n):
    return { i : [k+1 for k in range(i)] for i in range(n+1) }



## Exercise 11.4 -- Compter les lettres

## question 1) c)


def dicoDesLettres(texte):
    d = {}
    for x in texte:
        if not x in d:
            d[x] = 1
        else:
            d[x] = d[x] + 1
    return d


## question 2) c)


def lettresMajoritaires(texte):
    nbRecord = 0
    lettresRecord = []
    d = dicoDesLettres(texte)
    for x in d:
        if d[x] > nbRecord:
            nbRecord = d[x]
            lettresRecord = [x]
        elif d[x] == nbRecord:
            lettresRecord.append(x)
    return lettresRecord




## Exercise 11.6 -- Le triangle de Pascal : programmation naïve

## question 1) c)


def binomNaif(n, p):
    if p == 0 or p == n:
    	return 1
	else:
		return binomNaif(n-1, p) + binomNaif(n-1, p-1)




## Exercise 11.7 -- Accélération du temps de calcul par mémoïsation

## question 1) c)


memoire = {}

def binomeAvecMemo(n, p):
	# La valeur a-t-elle été déjà calculée ?
	if (n, p) in memoire:
		return memoire[(n, p)]
	
	# Cas limites
	if p == 0:
		memoire[(n, 0)] = 1
		return 1
	if p > n:
		memoire[(n, p)] = 0
		return 0
	
	# Cas général avec la relation de Pascal
	nb1 = binomeAvecMemo(n-1, p)
	nb2 = binomeAvecMemo(n-1, p-1)
	nb3 = nb1 + nb2
	
	# On stocke le résultat trouvé dans la mémoire
	memoire[(n, p)] = nb3
	return nb3
	

## question 2) c)


def binomeAux(n, p, memo):
	if (n, p) in memo:
		return memo[(n, p)]
	if p == 0 or p == n:
		return 1
	nb1 = binomeAux(n-1, p, memo)
	nb2 = binomeAux(n-1, p-1, memo)
	nb3 = nb1 + nb2
	memo[(n, p]) = nb3
	return nb3

def binome(n, p):
	memo = {}
	return binomeAux(n, p, memo)
		



## Exercise 11.8 -- Étude expérimentale de la complexité de l'algorithme naïf

## question 2) c)


def binomNaifBIS(n, p):
    N = 0

    def valeurBinome(n, p):
        nonlocal N
        N = N+1
        if p == 0 or p == n:
            return 1
        else:
            return valeurBinome(n-1, p) + valeurBinome(n-1, p-1)

    return valeurBinome(n, p), N




## Exercise 11.9

## question 2) c)


def valeurA(n, p):
   	
    def calculeValeur(n, p, memo):
        if (n, p) in memo:
        	return memo[(n, p)]
		else:
			if p == 0:
				memo[(n, p)] = 2**n
				return memo[(n, p)]
			elif n == 0:
				memo[(n, p)] = 3**p
				return memo[(n, p)]
			else:
				S = 0
				for k in range(n):
					for l in range(p):
						S = S + calculeValeur(k, l, memo) * (k**l)
				memo[(n, p)] = S
				return memo[(n, p)]

	memo = {}
	
    return calculeValeur(n, p, memo)




## Exercise 11.10 -- D'un dictionnaire à une liste

## question 1) c)


def dictToList(dico, listeCles):
	return [ dico[x] for x in listeCles ]


## question 2) c)


def dictToListBIS(dico, liste):
	return [ dico[x] for x in liste if x in dico ]




## Exercise 11.11 -- D'une liste à un dictionnaire

## question 2) c)


def listToDict(L, listeCles):
	return { listeCles[i]:L[i] for i in range(L) }




## Exercise 11.12 -- Compter et trier avec un dictionnaire

## question 1) c)


def occurences(texte):
	L = texte.split()
	d = {}
	for mot in L:
		if not mot in d:
			d[mot] = texte.count(mot)
	return d


## question 2) c)


def triRapide(L):
	if len(L) <= 1:
		return L[:]
	else:
		n = len(L)
		a = L[n//2][1]
		L_petit = [x for x in L if x[1] < a]
		L_grand = [x for x in L if x[1] > a]
		L_egal = [x for x in L if x[1] == a]
		
		return triRapide(L_petit) + L_egal + triRapide(L_grand)
		

## question 3) c)


def occurencesTriees(texte):
	d = occurences(texte)
	L = [ (x, d[x]) for x in d ]
	return triRapide(L)
	

## question 4) c)


def plusOccurent(texte):
	L = occurencesTriees(texte)
	n = len(L)
	occurrenceMax = L[n-1][1]
		
	return [x for x in L if x[1] == occurrenceMax]
		



## Exercise 11.13 -- Le triangle de Pascal : programmation exhaustive

## question 1) c)


def ligneSuivante(L):
	n = len(L)
	resultat = [1]
	for i in range(n-1):
		resultat.append(L[i] + L[i+1])
	resultat.append(1)
	return resultat
		

## question 2) c)


def trianglePascal(n):
	L = [ [1] ]
	for i in range(n):
		ligne = L[-1]
		suivante = ligneSuivante(ligne)
		L.append(suivante)

	return L