##TP - Structure de données : Listes

##1-Listes unidimensionnelles

##Premières manipulations
"""
Question 1 :
"""
L=[1,2,3,4,5] #Création de la liste L
print(L[4]) #Accès au terme d'indice 4
"""
Le terme d'indice 4 dans la liste est le cinquième élément. L'indexation des éléments de la liste commence à 0.
"""

"""
Question 2 :
"""
L[4]=L[3]+L[2]
print(L)

"""
Question 3 :
"""
print(L+L) #concatène les deux listes.
#L*L n'est pas défini.
#L+4 n'est pas défini.
print(L*4) #duplique 4 fois la liste L.

"""
Question 4 :
"""
print(L[-1]) #Accès au dernier terme de la liste.
"""
La liste est aussi indexée par des entiers négatifs en partant de la fin de la liste.
"""

"""
Question 5 :
"""
x=L.pop(4) #stocke dans x le dernier élément de L1 et le supprime de cette dernière

"""
Question 6 :
"""
L1 =[0,1,2,3]
L2=L1
print(L2)
L1[1]=4
print(L2)
"""
La modification de L1 a entraîné une modification de L2. On a deux noms différents pour le même ojet informatique, nous n'avons pas crée de copie seulement un alias.
"""

"""
Question 7 :
Générer une liste alétoire :
L=[random.randint(intervalle pour les valeurs de la liste) for i in range(taille de la liste)]
"""
import random

L=[random.randint(1,9) for i in range(10)]
print(L)

#Liste aléatoire de taille 15 composée d'entiers entre 0 et 7.
L=[random.randint(1,5) for i in range(15)]
print(L)



##Algorithmes fondamentaux
"""
Question 8 :
Fonction index
Entrées : une liste L et un élement e
Sortie : l'indice de la première occurrence de e dans L
"""
def index(L,e):
    n=len(L) #longueur de la liste
    i=0 #Indice de parcours de L
    while i<n and L[i]!=e : #Tant qu'on n'a pas fini le parcours de L et qu'on n'a pas trouvé e
        i += 1 #On passe à l'indice suivant
    if i<n :
        return i #Si i<n, on n'a pas parcouru L en entier donc on a trouvé e à la position i
    else :
        return False

L8=[7,4,9,-3,5,-3]
print(index(L8,-3))

#La boucle while effectue au pire n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

def index_2(L,e):
    n=len(L)
    for i in range(n):
        if L[i]==e :
            return i
    return False

#Est également une réponse acceptable.

"""
Question 9 :
Fonction somme
Entrée : une liste d'entiers L
Sortie : l'entier égale à la somme des éléments de la liste.
"""
def somme(L):
    n=len(L) #longueur de la liste
    som=0 #variable contenant la somme
    for i in range(n): #on parcourt la liste L
        som += L[i] #on ajoute le terme d'indice i à som
    return som #On retourne som

L9=[1,2,3,2,1]
print(somme(L9))

#La boucle for effectue n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

"""
Question 10 :
Fonction present
Entrées : une liste L et e un élément du même type que les éléments de L
Sortie : booléen True si e appartient à L
         booléen False sinon.
"""
def present(L,e):
    n=len(L) #longueur de la liste
    i = 0 #Indice de parcours de la liste L
    while i<n and (not e==L[i]): #Tant qu'on n'a pas fini le parcours de L et qu'on n'a pas trouvé e
        i += 1 #On passe à l'indice suivant
    return i<n #Si i<n, on n'a pas parcouru L en entier donc on a trouvé e

print(present(L9,1))
print(present(L9,4))

#La boucle while effectue au pire n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

def present_2(L,e):
    for elem in L:
        if elem==e :
            return True
    return False

#Est également une réponse acceptable.

"""
Question 11 :
Fonction compter
Entrées : une liste L et e un élément du même type que les éléments de L
Sortie : l'entier égale au nombre d'occurences de e dans L.
"""
def compter(L,e):
    n=len(L) #longueur de la liste
    cpt=0 #compteur comptant les occurrences de e dans L
    for i in range(n): #On parcourt la liste L
        if e==L[i]: #Si on trouve l'élément e
            cpt += 1 #On incrémente le compteur
    return cpt #On renvoie le compteur

L11=[4,7,2,7]
print(compter(L11,1))
print(compter(L11,4))
print(compter(L11,7))

#La boucle for effectue n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

"""
Question 12 :
Fonction minimum
Entrée : une liste d'entiers L non vide
Sortie : l'entier minimal contenu dans L.
"""
def minimum(L):
    n=len(L) #longueur de la liste
    min=L[0]  #Minimum courant, initialisé au premier terme
    for i in range(1,n): #On parcourt le reste de L
        if min>L[i]: #Si le terme d'indice i est inférieur au minnimum courant
            min=L[i]  #On actualise la valeur de min
    return min #On renvoie min

L12=[7,4,9,-3,5,-3]
print(minimum(L12))
print(minimum([4,0,1,2,3,]))
print(minimum([4,3,2,1,0]))

#La boucle for effectue n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

"""
Question 13 :
1. Fonction indiceMin
Entrée : une liste d'entiers L non vide
Sortie : l'entier égal à l'indice du dernier minimum rencontré dans L.
"""
def indiceMin(L):
    n=len(L)  #longueur de la liste
    indmin=0 #Indice du minimum courant, initialisé à 0
    for i in range(1,n): #On parcourt le reste de la liste L
        if L[indmin]>=L[i]: #Si le terme d'indice i est inférieur au minnimum courant (terme d'indice indmin)
            indmin=i #On actualise la valeur de indmin
    return indmin #On renvoie indmin

print(indiceMin(L12))
print(indiceMin([4,0,1,2,3,]))
print(indiceMin([4,3,2,1,0]))

#La boucle for effectue n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

"""
2. Fonction listeIndMin
Entrée : une liste d'entiers L non vide
Sortie : la liste d'entiers composée des indices des positions des occurences du minimum dans L.
"""
def listeIndMin(L):
    n=len(L) #longueur de la liste
    lmin=[0] #Liste des indices du minimum courant, initialisé à [0]
    for i in range(1,n): #On parcourt le reste de la liste L
        if L[lmin[0]]>L[i]: #Si le terme d'indice i est inférieur au minimum courant (terme d'indice lmin[0])
            lmin=[i] #On a trouvé un nouveau minimum, on actualise la valeur de lmin
        elif L[lmin[0]]==L[i] : #Si le terme d'indice i est égale au minimum courant (terme d'indice lmin[0])
            lmin.append(i) #On a trouvé un autre minimum, on ajoute son indice à lmin
    return lmin

print(listeIndMin(L12))
print(listeIndMin([4,0,1,2,3,]))
print(listeIndMin([4,3,2,1,0]))

#La boucle for effectue n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

##Autres exercices
"""
Question 14 :
Fonction supprimer
Entrées : une liste L et un élément e
Sortie : la liste L de laquelle on a supprimé e
"""
def supprimer(L,e):
    n=len(L) #longueur de la liste
    i=0 #Indice de parcours de L
    while i<n and L[i]!=e : #Tant qu'on n'a pas fini le parcours de L et qu'on n'a pas trouvé e
        i += 1 #On passe à l'indice suivant
    L[i],L[-1]=L[-1],L[i] #On échange l'élément e avec le dernier
    L.pop() #On supprime le dernier élément de L
    return L

print(supprimer(L12,-3))

#La boucle while effectue au pire n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

"""
Question 15 :
Fonction miroir
Entrées : une liste L
Sortie : une nouvelle liste miroir
"""
def miroir(L):
    n=len(L) #longueur de la liste
    res=[] #Liste miroir
    for i in range(n): #On parcours la liste L à l'envers
        res.append(L[-1-i])
    return res

print(miroir(L12))

#La boucle for effectue n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

#On peut utiliser une boucle for décroissante
def miroir(L):
    n=len(L) #longueur de la liste
    res=[] #Liste miroir
    for i in range(-1,-n-1,-1): #On parcours la liste L à l'envers
        res.append(L[i])
    return res

print(miroir(L12))

#La boucle for effectue n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

"""
Question 16 :
Fonction inserer
Entrées : une liste L triée dans l'ordre croissant et un élément e
Sortie : une nouvelle liste triée dans l'ordre croissant contenant les élément de L plus e
"""
def inserer(L,e):
    n=len(L) #longueur de la liste
    res = [] #Liste résultat
    if e<L[0] :
        res.append(e)
    for i in range(n-1) :
        if L[i]<e<=L[i+1] :
            res.append(L[i])
            res.append(e)
        elif L[i]<e :
            res.append(L[i])
        else :
            res.append(L[i])
    res.append(L[-1])
    if e>L[-1] :
        res.append(e)
    return res

L16=[1,2,4,5]
print(inserer(L16,3))

#La boucle for effectue n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

"""
Question 17 :
Fonction croissant
Entrée : une liste de nombres L
Sortie : booléen True si la liste est rangée en ordre croissant
         booléen False sinon.
"""
def croissant(L):
    n=len(L) #longueur de la liste
    i=0 #Indice de parcours de la liste
    while i<n-1 and not(L[i]> L[i+1]): #Tant qu'on n'a pas fini le parcours de L et que le terme d'indice i est inférieur ou égale à celui d'indice i+1
        i += 1 #On passe à l'indice suivant
    return i==n-1 #Si i=n-1, on a parcouru L en entier donc tout les éléments sont bien ordonnés

L17a=[1,2,4,5,6]
L17b=[5,4,3,1]
L17c=[1,2,4,3]

print(croissant(L17a))
print(croissant(L17b))
print(croissant(L17c))

#La boucle while effectue au pire (n-1) itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

def croissant_2(L):
    n=len(L)
    for i in range(n-1):
        if L[i] > L[i+1] :
            return False
    return True

#Est également une réponse acceptable.

"""
Question 18 :
Fonction getListeSuite
Entrée : un entier n
Sortie : une liste res composée des n premiers termes de la suite u.
"""
def getListeSuite(n):
    u=3 #terme u0
    res=[3] #liste résultat
    for i in range(1,n): #On calcule les n-1 termes suivants
        u=2*u+1 #Calcul de u(i)
        res.append(u) #On l'ajoute à res
    return res

print(getListeSuite(5))

#La boucle for effectue n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

"""
Question 19 :
1. Fonction rearrange
Entrée : une liste d'entiers L contenant des entiers n <len(n)
Sortie : une liste d'entiers newL telle que newL[i]=i si i est présent dans L et -1 sinon.
"""
def rearrange(L):
    n=len(L) #longueur de la liste
    newL=[-1 for i in range(n)] #la nouvelle liste à renvoyer
    for i in range(n): #On parcourt la liste L
        if L[i] != -1 : #Si ce n'est pas un -1
            newL[L[i]]=L[i] #on met L[i] dans la case d'indice L[i] de newL
    return newL

L19=[-1,-1,6,1,9,3,2,-1,4,-1]
print(rearrange(L19))

#La boucle for effectue n itérations, toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

"""
2.Version en place : on utilise une espace mémoire de taille 1 pour stocker ind indépendamment de la taille de la liste d'entrée.
"""
def rearrange2(L):
    n=len(L) #longueur de la liste
    for i in range(n): #On parcourt la liste L
        if L[i] != -1 : #Si ce n'est pas un -1
            ind=L[i] #On stocke l'entier L[i]
            L[i],L[ind]=L[ind],L[i] #on échange les contenus des cases i et L[i] comme ça la case d'indice L[i] contient L[i]
    return L

print(rearrange2(L19))

#La boucle for effectue n itérations et toutes les instructions sont élémentaires. L'algorithme a une complexité linéaire O(n) où n est la taille de la liste.

"""
Question 20 :
Fonction lesDeuxPlusProches
Entrée : une liste d'entiers L
Sortie : une nouvelle liste contenant les deux entiers de la liste L les plus proches.
"""
def lesDeuxPlusProches(L):
    n=len(L) #longueur de la liste
    DPP=[L[n-1],L[n-2]]  #liste des deux entiers les plus proches, intialisée avec les deux derniers
    dist=abs(L[n-1]-L[n-2]) #distance entre ces deux entiers, abs renvoie la valeur absolue d'un nombre
    for i in range(n-1): #On parcourt la liste L avec un indice i
        for j in range(i+1,n): #On parcourt les éléments situés à gauche de celui d'indice i
            d = abs(L[i]-L[j]) #On stocke la distance de L[i] à L[j]
            if d < dist: #Si cette distance est inférieur à dist
                dist=d #On actualise dist
                DPP=[L[i],L[j]] #On actualise DPP
    return DPP #On renvoie DPP

L20=[39,28,41,13,23,29,10,14,0,46]
print(lesDeuxPlusProches(L20))

#On suppose que la fonction abs est en temps constant.
#La boucle for sur j effectue n-i itérations et chaque itération effectue au maximum une dizaine d'opérations. La boucle for sur i effectue donc somme sur i allant de 0 à n-2 de 10(n-i) opérations. Ce qui donne un total de O(n^2) opérations dans la boucle for sur i. Le reste de l'algorithme est constitué d'instructions élémentaires. L'algorithme a une complexité quadratique O(n^2) où n est la taille de la liste.

"""
Question 21 :
Fonction supprimeDoublons
Entrée : une liste d'entiers L
Sortie : une nouvelle liste sans entiers dupliqués.
"""
def supprimeDoublons(L):
    n=len(L) #longueur de la liste
    res=[L[0]] #liste sans doublons, contenant L[0]
    for i in range(1,n): #On le reste de L
        if not present(res,L[i]): #si L[i] n'appartient pas déjà à res (Q9)
            res.append(L[i]) #On l'y ajoute
    return res #On renvoie res

L21 = [6,1,0,6,7,9,1,8,8,5]
print(supprimeDoublons(L21))

#La boucle for effectue n itérations, toutes les instructions sont élémentaires sauf l'appel à la fonction present effectuée dans la boucle qui est en O(n). L'algorithme a donc une complexité quadratique O(n^2) où n est la taille de la liste.

"""
Question 22 :
Fonction majorityElement
Entrée : une liste L d'entiers
Sortie : l'entier majoritaire dans L c'est-à-dire l'entier ayant le plus grand nombre d'occurences dans L.
"""
def majorityElement(L):
    n=len(L) #longueur de la liste
    maj=L[0] #Element majoritaire, initialisé à L[0]
    count=compter(L,maj) #nombre d'occurrences de maj dans L (stocké pour ne pas le recalculer plusieurs fois) (Q10)
    for i in range(1,n): #on parcourt le reste de L
        if L[i]!=maj : #Si L[i] est différent de maj
            counti=compter(L,L[i]) #On compte le nombre d'occurrences de L[i]
            if count<counti: #Si L[i] est plus présent que maj
                maj=L[i] #On actualise maj
                count=counti #On actualise count
    return maj #On renvoie maj

L22=[0,3,1,5,3,1,2,1,2,2]
print(majorityElement(L22))

#La boucle for effectue n itérations, toutes les instructions sont élémentaires sauf l'appel à la fonction compter effectuée avant la boucle puis dans la boucle qui est en O(n). L'algorithme a donc une complexité quadratique O(n^2) où n est la taille de la liste.

"""
Question 23 :
Fonction maxSubArray
Entrée : une liste L d'entiers relatifs
Sortie : la sous-liste de L contenant la plus grande somme.
"""
def maxSubArray(L):
    n=len(L) #longueur de la liste
    som=L[0] #somme maximale
    Lmax=[L[0]] #liste des éléments réalisant som
    for i in range(n): #On parcourt L
        if L[i]>som : #Si L[i] est plus grand que som
            som = L[i] #On actualise L[i]
            Lmax = [L[i]] #On actualise Lmax
        for j in range(i+1,n): #On parcourt les éléments de L situés à gauche de L[i]
            ssliste = L[i:j+1] #sous-liste contenant les éléments d'indice i à j
            nvsom = somme(ssliste) #Somme de ssliste (Q8)
            if nvsom>som: #Si la somme de la sous-list est supérieur à som
                som = nvsom #On actualise som
                Lmax = ssliste #On actualise ssliste
    return Lmax #Onr envoie Lmax

L23a=[-2,1,-3,4,-1,2,1,-5,4]
print(maxSubArray(L24a))

L23b=[3,7,1]
print((maxSubArray(L24b)))

#La boucle for sur j effectue n-1-i itérations, toutes les instructions y sont élémentaires sauf la création de liste en slicing qui coûte j-i+1 opérations et l'appel à somme qui est en O(n) donc la boucle sur j est quadratique.
#La boucle sur i effectue n itérations d'opérations élémentaires et de la boucle sur j, toutes les autres instructions sont élémentaires. L'algorithme a une compleixté cubique O(n^3) où n est la taille de la liste.


##2-Listes à deux dimensions
"""
Question 24 :
"""
L=[[1,0,6],[6,1,1],[0,4,9],[8,7,6]] #Création de la liste L

"""
Question 25 :
La liste L est composée de 4 lignes et 3 colonnes. Autrement dit, 4 listes de taille 3.
"""

"""
Question 26 :
"""
print(L[2]) #sous-liste d'indice 2 i.e. troisième sous-liste : [0,4,9]
print(L[0][1]) #teme d'indice 1 de la sous-liste d'indice 0 : 0
print(L[2][0]) #terme d'indice 0 de la sous-liste d'indice 2 : 0
print(L[3][2]) #terme d'indice 2 de la sous-liste d'indice 3 : 6
print(L[1][5]) #terme d'indice 5 de la sous-liste d'indice 1 : erreur car n'existe pas

"""
Question 27 :
"""
L.append([2,3,7])
"""
La nouvelle matrice contient une ligne supplémentaire, soit 5 lignes.
"""

"""
Question 28 :
On ajoute un 1 à la fin de chaque ligne.
"""
n=len(L) #Longueur de L
for i in range(n) : #On parcourt L
    L[i].append(1) #On coimplète la sous-liste d'indice i en ajoutant un 1
print(L)

"""
Question 29 :
"""
L=[[0,1],[2,3]]
print(L)
print(L[0])
print(L[1])
print(L[0][1])
print(L[1][0])

"""
Question 30 :
"""
print(L[1][1]) #terme d'indice 1 de la sous-liste d'indice 1 : 3

"""
Question 31 :
Incrémenter les valeurs de 1.
"""
n=len(L) #longueur de L : nombre de lignes
for i in range(n) : #On parours L
    for j in range(len(L[i])) : #On parcourt le liste L[i]
        L[i][j] += 1 #On incrémente le coefficient (i,j) de L de 1
print(L)

"""
Question 32 :
Générer une liste alétoire :
L=[[random.randint(intervalle pour les valeurs de la liste) for j in range(nb de sous listes)] for i in range(taille de la liste)]
"""
import random as rd

L=[[rd.randint(1,9) for j in range(10)] for i in range(15)]
print(L)

#Liste aléatoire de taille 3 composée de listes de taille 5 contenant des entiers compris entre 0 et 5.
L=[[rd.randint(0,5) for j in range(5)] for i in range(3)]
print(L)


##Reprise des algorithmes fondamentaux
"""
Question 33 :
Fonction somme2
Entrée : une liste L de listes d'entiers
Sortie : l'entier est égale à la somme des éléments de L.
"""
def somme2(L):
    n=len(L) #longueur de L, nombre de sous-listes
    som=0 #variable contenant la somme
    for i in range(n): #On parcourt L
        m=len(L[i]) #longueur de la sous-liste L[i]
        for j in range(m): #On parcourt L[i]
            som += L[i][j] #On ajoute le terme j de L[i] à som
    return som #On renvoie som

L33=[[1,0,6],[6,1,1],[0,4,9],[8,7,6]]
print(somme2(L29))

#La boucle for sur j effectue m itérations et les instructions sont élémentaires, elle est en O(m).
#La boucle for sur i effectue n itérations d'opérations élémentaires et de la boucle sur j, elle est en O(nm).
#Les autres des oéprations sont élémentaires, l'algorithme a une complexité en O(nm) où nxm est la taille de la liste de listes d'entrée.

#Ou bien, on utilise la fonction somme de la question 8
def somme2(L):
    n=len(L) #longueur de L, nombre de sous-listes
    som=0 #variable contenant la somme
    for i in range(n): #On parcourt L
        som += somme(L[i]) #On ajoute la somme de éléments de L[i] à som
    return som #On renvoie som

print(somme2(L29))

#La boucle for sur i effectue n itérations d'opérations élémentaires et d'appel à la fonction somme qui est en O(m). Le reste des oéprations sont élémentaires, l'algorithme a une complexité en O(nm) où nxm est la taille de la liste de listes d'entrée.

"""
Question 34 :
Fonction present2
Entrées : une liste de listes L et e un élément de même type que les éléments de L
Sortie : booléen True si e appartient à L
         booléen False sinon.
"""
def present2(L,e):
    n=len(L) #longueur de la liste
    i=0 #Indice de parcours de la liste L
    m=len(L[i]) #longueur de la sous-liste L[i]
    j=0 #Indice de parcours de L[i]
    while i<n and (not L[i][j]==e) : #Tant qu'on n'a pas fini les parcours et qu'on n'a pas trouvé e
            j += 1  #On passe à l'indice suivant dans L[i]
            if j==m : #Si on a fini L[i]
                i += 1 #On passe à la sous-liste suivante
                j = 0 #et on commence son parcours à l'indice 0
    return i<n #Si on n'a pas parcourue toute les sous-listes alors on a trouvé e et réciproquement

print(present2(L29,1))
print(present2(L29,11))

#La boucle while effectue au pire nm itérations et les opérations sont élémentaires. L'algorithme a une complexité en O(nm) où nxm est la taille de la liste de listes d'entrée.

#Ou bien, en utilisant prenset de la Q9
def present2(L,e):
    n=len(L) #longueur de la liste
    i=0 #Indice de parcours de la liste L
    while i<n and not(present(L[i],e)) : #Tant qu'on n'a pas fini les parcours et qu'on n'a pas trouvé e
        i+= 1 #On passe à la sous-liste suivante
    return i<n #Si on n'a pas parcourue toute les sous-listes alors on a trouvé e et réciproquement

print(present2(L33,1))
print(present2(L33,11))

#La boucle while effectue au pire n itérations, les opérations sont élémentaires sauf l'appel à present qui est en O(m) et qui est effectué à chaque itération de la boucle. L'algorithme a une complexité en O(nm) où nxm est la taille de la liste de listes d'entrée.

"""
Question 35 :
Fonction compter2
Entrées : une liste de listes L et un élément e de même type que les éléments de L
Sortie : l'entier égale aux nombres d'occurences de e dans L.
"""
def compter2(L,e):
    n=len(L) #longueur de la liste
    count=0 #compteur des occurrences de e dans L
    for i in range(n): #On parcourt L
        m=len(L[i]) #longueur de la sous-liste L[i]
        for j in range(m): #On parcourt L[i]
            if L[i][j]==e: #Si on a trouvé e
                count += 1 #On incrémente le compteur
    return count #On renvoie le compteur

L35=[[0,2,2,9],[1,4,4,1],[2,4,5,6]]

print(compter2(L35,2))
print(compter2(L35,9))
print(compter2(L35,7))

#La boucle for sur j effectue m itérations et les instructions sont élémentaires, elle est en O(m).
#La boucle for sur i effectue n itérations d'opérations élémentaires et de la boucle sur j, elle est en O(nm).
#Les autres des oéprations sont élémentaires, l'algorithme a une complexité en O(nm) où nxm est la taille de la liste de listes d'entrée.

#Ou bien en utilisant compter de la Q10
def compter2(L,e):
    n=len(L) #longueur de la liste
    count=0 #compteur des occurrences de e dans L
    for i in range(n): #On parcourt L
        count += compter(L[i],e) #On incrémente le compteur du nombre d'occurrence de e dans L[i]
    return count #On renvoie le compteur

print(compter2(L35,2))
print(compter2(L35,9))
print(compter2(L35,7))

#La boucle for sur i effectue n itérations d'opérations élémentaires et d'appel à la fonction compter qui est en O(m). Le reste des oéprations sont élémentaires, l'algorithme a une complexité en O(nm) où nxm est la taille de la liste de listes d'entrée.


"""
Question 36 :
Fonction minimum2
Entrée : une liste de listes d'entiers L
Sortie : l'entier égale au minimum de la liste L.
"""
def minimum2(L):
    n=len(L) #longueur de la liste
    min=L[0][0] #minimum courant, itialisée au premier terme de la première sous-liste
    for i in range(n): #On parcourt L
        m=len(L[i]) #longueur de la sous-liste L[i]
        for j in range(m): #On parcourt L[i]
            if L[i][j]< min: #Si le terme d'indice j de L[i] est inférieur à min
                min=L[i][j] #On actualise min
    return min #On renvoie min

L36=[[-7,-1,0,-9],[4,-3,-4,-6],[5,8,-8,-2]]
print(minimum2(L36))

#La boucle for sur j effectue m itérations et les instructions sont élémentaires, elle est en O(m).
#La boucle for sur i effectue n itérations d'opérations élémentaires et de la boucle sur j, elle est en O(nm).
#Les autres des oéprations sont élémentaires, l'algorithme a une complexité en O(nm) où nxm est la taille de la liste de listes d'entrée.

#Ou bien, en utilisant minimum de la Q11
def minimum2(L):
    n=len(L) #longueur de la liste
    min=minimum(L[0]) #minimum courant, itialisée comme minimum de la première sous-liste
    for i in range(1,n): #On parcourt le reste de L
        min_i = minimum(L[i]) #minimum de la sous-liste L[i]
        if min_i< min: #Si min_i est inférieur à min
            min=min_i#On actualise min
    return min #On renvoie min

L36=[[-7,-1,0,-9],[4,-3,-4,-6],[5,8,-8,-2]]
print(minimum2(L36))

#La boucle for sur i effectue n itérations d'opérations élémentaires et d'appel à la fonction minimum qui est en O(m). Le reste des oéprations sont élémentaires, l'algorithme a une complexité en O(nm) où nxm est la taille de la liste de listes d'entrée.


##Autres exercices
"""
Question 37 :
Fonction someMatrices
Entrées : deux matrices de même taille i.e. listes de listes de même taille
Sortie : une matrice, i.e. une liste de liste, de même taille que les entrées dont l'élément (i,j) est la somme des éléments (i,j) des deux listes d'entrées.
"""
def sommeMatrices(M1,M2):
    n=len(M1) #longueur de M1 i.e. nombre de lignes de M1
    m=len(M1[0]) #longueur de la première sous-liste de M1 i.e. nombre de colonnes de M1
    Msom=[[0 for j in range(m)] for i in range(n)] #Matrice somme de même taille (n,m)
    for i in range(n): #On parcourt les lignes des matrices
        for j in range(m): #On parcourt les colonnes des matrices
            Msom[i][j] = M1[i][j]+M2[i][j] #On met la somme des coefficients (i,j) des matrices dans la matrice somme
    return Msom #On renvoie la matrice somme

M1=[[8,3,1],[9,4,2]]
M2=[[4,5,1],[5,2,4]]
print(sommeMatrices(M1,M2))

#La boucle for sur j effectue m itérations et les instructions sont élémentaires, elle est en O(m).
#La boucle for sur i effectue n itérations d'opérations élémentaires et de la boucle sur j, elle est en O(nm).
#Les autres des oéprations sont élémentaires, l'algorithme a une complexité en O(nm) où nxm est la taille de la liste de listes d'entrée.

"""
Question 38 :
Fonction triangleDePascal
Entrée : un entier n
Sortie : une liste de liste telle que la sous-liste numéro i corresponde à la ligne i du triangle de Pascal.
"""
def triangleDePascal(n):
    if n==0: #Cas de base n=0
        return [1]
    elif n==1: #Cas de base n=1
        return [1,1]
    else : #Cas général n>1
        triangle=[[1],[1,1]] #on initialise les deux premières lignes du triangle
        for i in range(2,n): #On crée les lignes 2 à n
            binom=[1] #La ligne commence par un 1 (coefi binomial 0 parmi i)
            for j in range(1,i): #On complète la ligne par les coefficients binomiaux de j parmi i pour j allant de 1 à i-1
                binom.append(triangle[i-1][j-1]+triangle[i-1][j])
            binom.append(1) #on ajoute le 1 de la fin de la ligne (coeff binomial i parmi i)
            triangle.append(binom) #On ajoute la nouvelle ligne au triangle
    return triangle #On renvoie le triangle

print(triangleDePascal(4))
print(triangleDePascal(10))

#La boucle for sur j effectue i-1 itérations de 4 oéprations.
#La boucle for sur i effectue somme de i allant de 0 à n des 4(i-1) opérations don est quadratique O(n^2).
#Les autres oéprations sont élémentaires, l'algorithme a une complexité en O(n^2).