#### Par Pierre Béaur. 10/09/2026.
#### Séance 02

### Exercice 1
## 3.

def somme_inverse(n):
    s = 0
    for i in range(1,n+1):
        s = s + 1/i
    return s

### Exercice 2.

def factorielle(n):
    p = 1
    # problème aux bornes du range
    for i in range(1,n+1):
        p = p * i
    return p

def somme_alternee(n):
    s = 0
    # il manque un n à "range"
    for k in range (n+1):
        s += ((-1)**k)*k
        # mauvaise indentation
    return s

# pas de majuscule à def !

def binaire(n):
    k = n
    # manque le deux-points
    for i in range(n):
        # mauvaises formules pour
        # obtenir le codage binaire
        print(k%2)
        k = n//2

### Exercice 5.

x = 3
i = 0
while i < 16:
    x += 3
    i += 1
print(x)

t = ""
x = 0
while x < 10:
    t += str(x)
    x += 1
print(t)

### Exercice 8.
## 4.

def premiers_nombres(n):
    t = []
    for i in range(n):
        t += [i]
    return t

## 5.

def puissances_de_2(n):
    t = []
    for i in range(n):
        t += [2**i]
    return t
    # remarque : on peut faire une version
    # un peu moins coûteuse en maintenant
    # un accumulateur qu'on double à chaque
    # passage de boucle.

## 6.

def premiers_fibo(n):
    t = []
    a = 0
    b = 1
    for i in range(n):
        t += [a]
        a,b = b,a+b
    return t

### Exercice 9.
## 1.

def affiche(tab):
    for i in range(len(tab)):
        print(tab[i])

## 2.

def est_dedans(elem,tab):
    for i in range(len(tab)):
        if tab[i] == elem:
            return True
    return False

## 3.

def nb_occurrences(x,t):
    c = 0
    for i in range(len(t)):
        if t[i] == x:
            c += 1
    return c

### Exercice 10.
## 1.

def element_en_commun(tab1,tab2):
    for i in range(len(tab1)):
        if est_dedans(tab1[i],tab2):
            return True
    return False

## 2.

def element_en_commun_v2(tab1,tab2):
    for i in range(len(tab1)):
        for j in range(len(tab2)):
            if tab1[i] == tab2[j]:
                return True
    return False
# intérêt : la complexité temporelle se
# lit en un coup d'oeil (deux boucles
# imbriquées).

### Exercice 12.
## 1.

def maximum(tab):
    m = tab[0] # attention, ce n'est
    # pas forcément un tableau d'entiers !
    for i in range(len(tab)):
        if tab[i] > m :
            m = tab[i]
    return m

## 2.

def indice_max(tab):
    ind = 0
    for i in range(len(tab)):
        if tab[ind] < tab[i]:
            ind = i
    return ind

## 3.

# On propose deux méthodes :
# - la 1ère est moins intuitive, mais
#   facile à faire avec les outils actuels
# - la 2ème est plus intuitive, mais
#   utilise une syntaxe pas encore vue

# Version 1 : on crée un nouveau tableau
# sans la valeur maximale.
def sousmaximum1(tab):
    m = maximum(tab)
    tab2 = []
    for i in range(len(tab)):
        if tab[i] != m :
            tab2 += [tab[i]]
    return maximum(tab2)

# Version 2 : on fait un simple passage.
def sousmaximum2(tab):
    m = maximum(tab)
    m2 = None
    for i in range(len(tab)):
        if tab[i] != m and (m2 == None or tab[i] > m2):
            m2 = tab[i]
    return m2

## 4.

def somme(tab):
    s = 0
    for i in range(len(tab)):
        s += tab[i]
    return s

## 5.

def moyenne(tab):
    return somme(tab)/len(tab)

### Exercice 13.
## 1.

def begayant(tab):
    tab2 = []
    for i in range(len(tab)):
        tab2 += [tab[i],tab[i]]
    return tab2

## 2.

def positifs(tab):
    tab2 = []
    for i in range(len(tab)):
        if tab[i] > 0:
            tab2 += [tab[i]]
    return tab2

#### Bonus 02.
### Exercice 3.
##1.

def variance(tab):
    m = moyenne(tab)
    v = 0
    for i in range(len(tab)):
        v += (tab[i]-m)**2
    return v

##2.

def ecart_type(tab):
    # J'ai la flemme de faire l'import.
    return variance(tab)**(1/2)

## 3.

def mediane(tab):
    return sorted(tab)[len(tab)//2]

### Exercice 4.
## 2.
# Techniquement, on n'a pas encore vu
# les tableaux par compréhension.
# Il est tout à fait possible de faire sans.

def est_permutation(tab):
    vu = [False for i in range(len(tab))]
    for i in range(len(tab)):
        if tab[i]<0 or tab[i] > len(tab) or vu[tab[i]]:
            return False
        vu[tab[i]] = True
    return True

## 3.

def nb_inversions(tab):
    c = 0
    for i in range(len(tab)):
        for j in range(i+1,len(tab)):
            if tab[i] > tab[j]:
                c += 1
    return c

## 4.

def signature(tab):
    return (-1)**(nb_inversions(tab))

## 5.

def composition(tab1,tab2):
    tab3 = [-1 for i in range(len(tab))]
    for i in range(len(tab1)):
        tab3[i] = tab1[tab2[i]]
    return tab3

### Exercice 5.
## 1.

def factorielle(k):
    p = 1
    for i in range(k):
        p *= (i+1)
    return p

def binom(n,k):
    return factorielle(n)//(factorielle(k)*factorielle(n-k))

## 3.

def binom2(n,k):
    ligne0 = [1]+[0]*(n)
    coef = [ligne0]
    for m in range(1,n+1):
        nv_ligne = [1]
        for j in range(1,m+1):
            nv_ligne += [coef[m-1][j]+coef[m-1][j-1]]
        coef += [nv_ligne+[0]*(n-m)]

    return coef[n][k]