TP 4 (fonctions) : éléments de correction

1. Définir une fonction¶

Exercice 1 : occurences

In [1]:

def Occurrences(a, L):
    """
    Renvoie le nombre d'occurences (i.e. d'apparitions)
    de l'élément a dans la liste L
    """
    n = 0  # initialisation du compteur
    for k in range(len(L)):
        if a == L[k]:  # test d'égalité + confusion entre k et L[k] + oubli des ":"
            n = n + 1
    return n  # mauvaise indentation

In [2]:

# test avec la liste vide
Occurrences(1, [])

In [3]:

# test avec plusieurs occurences
Occurrences(1, [1, 2, 3, 4, 1, 2, 3, 4, 1])

In [4]:

# test sans occurrence
Occurrences(1, [2, 3, 4, 5])

On pourrait également utiliser un autre type de parcours de liste, qui se fait élément par élément :

In [5]:

def Occurrences(a, L):
    """
    Renvoie le nombre d'occurences (i.e. d'apparitions)
    de l'élément a dans la liste L
    """
    n = 0
    for elt in L:
        if a == elt:
            n = n + 1
    return n  

Exercice 2 : premières fonctions

Question 1¶

On va utiliser une liste par compréhension :

In [6]:

import random as rd

In [7]:

def listealeatoire(n, a, b):
    """
    Renvoie une liste de n entiers aleatoires compris entre a et b.
    """
    return [rd.randint(a, b) for i in range(n)]

In [8]:

listealeatoire(4, 1, 5)

Out[8]:

[5, 1, 1, 2]

In [9]:

listealeatoire(0, 1, 10)

Out[9]:

[]

In [10]:

listealeatoire(3, 2, 2)

Out[10]:

[2, 2, 2]

Question 2¶

On adapte un script du TP précédent pour le transformer en fonction :

In [11]:

def maxi(L):
    """
    Renvoie le maximum des elements d’une liste de nombres L.
    """
    M = L[0]
    for k in range(len(L)):
        if L[k] > M:
            M = L[k]
    return M

In [12]:

maxi([])

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-12-412a906834f3> in <module>
----> 1 maxi([])

<ipython-input-11-0d975cc57ff3> in maxi(L)
      3     Renvoie le maximum des elements d’une liste de nombres L.
      4     """
----> 5     M = L[0]
      6     for k in range(len(L)):
      7         if L[k] > M:

IndexError: list index out of range

Notre fonction ne fonctionne pas avec une liste vide...

In [13]:

def maxi(L):
    """
    Renvoie le maximum des elements d’une liste de nombres L.
    """
    if len(L) == 0:
        return None
    else:
        M = L[0]
        for k in range(len(L)):
            if L[k] > M:
                M = L[k]
        return M

In [14]:

maxi([])

In [15]:

maxi([1, 2, 3, 4, 5, 4, 3, 2, 1])

Out[15]:

In [16]:

maxi([5, 4, 3, 2, 1])

Out[16]:

Remarque :

on peut également utiliser un parcours des éléments de la liste L de la façon suivante :

In [17]:

def maxi(L):
    """
    Renvoie le maximum des elements d’une liste de nombres L.
    """
    if len(L) == 0:
        return None
    else:
        M = L[0]
        for elt in L:
            if elt > M:
                M = elt
        return M

Question 3¶

In [70]:

def mini(L):
    """
    Renvoie le minimum des elements d’une liste de nombres L.
    """
    if len(L) == 0:
        return None
    else:
        M = L[0]
        for elt in L:
            if elt < M:
                M = elt
        return M

In [77]:

def minmax(N, n, a, b):
    """
    genere N listes de n entiers aleatoires compris entre a et b,
    determine le maximum des elements de chacune de ces listes
    et renvoie le minimum de ces maximums.
    """
    if n==0:
        return None
    else:
        Lmax=[]
        for k in range(N):
            L=listealeatoire(n,a,b)
            M=maxi(L)
            Lmax.append(M)
        return mini(Lmax)

In [78]:

minmax(0, 10, 2, 3)

In [79]:

minmax(10, 0, 2, 3)

In [80]:

minmax(10,12,1,5)

Out[80]:

In [ ]:

In [18]:

def minmax(N, n, a, b):
    """
    genere N listes de n entiers aleatoires compris entre a et b,
    determine le maximum des elements de chacune de ces listes
    et renvoie le minimum de ces maximums.
    """
    if N == 0 or n == 0:
        return None
    else:
        L = listealeatoire(n, a, b)
        M = maxi(L)
        m = M
        for k in range(N - 1):
            L = listealeatoire(n, a, b)
            M = maxi(L)
            if M < m:
                m = M
        return m

In [19]:

minmax(0, 10, 2, 3)

In [20]:

minmax(10, 0, 2, 3)

In [21]:

minmax(10,12,1,5)

Out[21]:

Exercice 3 : coefficients binomiaux

In [22]:

def factorielle(n):
    """
    Renvoie la factorielle de n.
    """
    f = 1
    for k in range(1, n + 1):
        f = f * k
    return f

Question 1¶

In [23]:

def coeff(n, k):
    """
    Renvoie le coefficient binomial "k parmi n"
    """
    return factorielle(n) // factorielle(k) // factorielle(n - k)

In [24]:

coeff(0, 0)

Out[24]:

In [25]:

coeff(3, 1)

Out[25]:

In [26]:

coeff(9, 6)

Out[26]:

In [27]:

[coeff(4, k) for k in range(5)]

Out[27]:

[1, 4, 6, 4, 1]

In [28]:

coeff(50, 13)

Out[28]:

354860518600

In [29]:

coeff(10000, 9997)

Out[29]:

166616670000

On peut même afficher le début du triangle de Pascal :

In [30]:

for n in range(6):
    print([coeff(n, k) for k in range(n + 1)])

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]

Question 2¶

In [31]:

def LigneSuivante(L):
    """
    Reçoit une liste de nombres L
    et renvoie la liste M définie comme dans l'énoncé
    """
    M = [L[0]]
    for k in range(1, len(L)):
        M.append(L[k - 1] + L[k])
    M.append(L[len(L) - 1])
    return M

In [32]:

LigneSuivante([1, 5, 10, 10, 5, 1])

Out[32]:

[1, 6, 15, 20, 15, 6, 1]

Une variante, avec une liste par compréhension :

In [33]:

def LigneSuivante(L):
    """
    Reçoit une liste de nombres L
    et renvoie la liste M définie comme dans l'énoncé
    """
    M = [L[0]] + [L[k - 1] + L[k] for k in range(1, len(L))] + [L[len(L) - 1]]
    return M

In [34]:

LigneSuivante([1, 5, 10, 10, 5, 1])

Out[34]:

[1, 6, 15, 20, 15, 6, 1]

In [35]:

LigneSuivante([1])

Out[35]:

[1, 1]

Question 3¶

In [36]:

def Pascal(N):
    """
    Affiche les N premieres lignes du triangle de Pascal.
    """
    L = [1]
    print(L)
    for k in range(N):
        L = LigneSuivante(L)
        print(L)
    return None

In [37]:

Pascal(5)

[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]

On pourrait chronométrer les 2 façons de faire pour voir que la 2ème est plus efficace : vous pouvez vous inspirer de l'exercice 6 pour faire des tests chez vous !

2. Nombres premiers¶

Exercice 4 : algorithme naïf

Questions 1 et 2¶

In [38]:

from math import sqrt

In [39]:

def estpremier(n):
    """
    Teste si un nombre entier naturel est premier.
    """
    if n == 0 or n == 1:
        return False
    for k in range(2, int(sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

In [40]:

for n in range(21):
    if estpremier(n):
        print(n, end=' ')
print()  # pour le retour a la ligne

2 3 5 7 11 13 17 19

Question 3¶

On peut utiliser un compteur pour chaque nombre premier :

In [41]:

cpt = 0
for n in range(1001):
    if estpremier(n):
        cpt += 1
print("Il y a {} nombres premiers inférieurs (ou égaux) à 1000.".format(cpt))

Il y a 168 nombres premiers inférieurs (ou égaux) à 1000.

Python est assez souple en ce qui concerne les sommes : il peut sommer des booléens (True vaut alors 1 et False vaut 0). On peut donc également proposer la version suivante :

In [42]:

S = sum([estpremier(n) for n in range(1001)])

In [43]:

print("Il y a {} nombres premiers inférieurs (ou égaux) à 1000.".format(S))

Il y a 168 nombres premiers inférieurs (ou égaux) à 1000.

Question 4¶

On va utiliser une boucle while, jusqu'à obtenir un nombre premier :

In [44]:

n = 10**10
while not (estpremier(n)):
    n = n + 1
print("Le plus petit nombre premier supérieur à 10**10 est {}.".format(n))

Le plus petit nombre premier supérieur à 10**10 est 10000000019.

Exercice 5 : crible d'Ératosthène

In [45]:

def Crible(N):
    """
    Implémente le crible d'Eratosthene
    """
    C = [True for k in range(N)]
    C[0] = False
    C[1] = False
    for k in range(2, N):
        if C[k]:
            for i in range(2*k,N,k):
                C[i] = False
    return (C)

In [46]:

C1 = Crible(20)
for n in range(20):
    if C1[n]:  # Test : n est-il premier ?
        print(n, end=' ')
print()

2 3 5 7 11 13 17 19

On peut également utiliser une liste définie par compréhension (avec une condition) :

In [47]:

[n for n in range(20) if C1[n]]

Out[47]:

[2, 3, 5, 7, 11, 13, 17, 19]

On retrouve également le résultat de la question 3 de l'exercice précédent :

In [48]:

C2 = Crible(1000)
c = 0
for n in range(1000):
    if C2[n]:
        c += 1
print(c)

ou bien également :

In [49]:

sum(C2)

Out[49]:

Exercice 6 : comparaison des algorithmes

In [50]:

from time import time

In [51]:

N = 100

t1 = time()
C = [estpremier(n) for n in range(N + 1)]
t2 = time()
print("Temps avec la version naïve :", t2 - t1)

t1 = time()
C = Crible(N + 1)
t2 = time()
print("Temps avec le crible d'Eratosthene  :", t2 - t1)

Temps avec la version naïve : 0.0002818107604980469
Temps avec le crible d'Eratosthene  : 0.00014901161193847656

In [52]:

N = 10**4

t1 = time()
C = [estpremier(n) for n in range(N + 1)]
t2 = time()
print("Temps avec la version naïve :", t2 - t1)

t1 = time()
C = Crible(N + 1)
t2 = time()
print("Temps avec le crible d'Eratosthene  :", t2 - t1)

Temps avec la version naïve : 0.02549600601196289
Temps avec le crible d'Eratosthene  : 0.004354000091552734

In [53]:

N = 10**5

t1 = time()
C = [estpremier(n) for n in range(N + 1)]
t2 = time()
print("Temps avec la version naïve :", t2 - t1)

t1 = time()
C = Crible(N + 1)
t2 = time()
print("Temps avec le crible d'Eratosthene  :", t2 - t1)

Temps avec la version naïve : 0.1811509132385254
Temps avec le crible d'Eratosthene  : 0.018087148666381836

3. Compléments¶

Exercice 7 : nombres parfaits et amis

Question 1¶

Dès qu'on le peut, on utilise une liste par compréhension :

In [54]:

def diviseurs(n):
    """
    reçoit un entier n positif,
    et renvoie la liste de ses diviseurs autres que lui-meme.
    """
    D = [k for k in range(1, n) if n % k == 0]
    return D

In [55]:

diviseurs(12)

Out[55]:

[1, 2, 3, 4, 6]

On peut bien sûr quand même construire la liste élément par élément :

In [56]:

def diviseurs(n):
    """
    Reçoit un entier n positif,
    et renvoie la liste de ses diviseurs autres que lui-meme.
    """
    D = []
    for k in range(1, n):
        if n % k == 0:
            D.append(k)
    return D

In [57]:

diviseurs(30)

Out[57]:

[1, 2, 3, 5, 6, 10, 15]

Question 2 : nombres parfaits¶

On dresse la liste de tous les nombres parfaits strictement inférieurs à $10^4$ :

In [58]:

P = []
N = 10**4
for n in range(N):
    D = diviseurs(n)
    if n == sum(D):
        P.append(n)
print(P)

[0, 6, 28, 496, 8128]

Question 3 : Nombres amis¶

Une première version, naïve et peu efficace :

In [59]:

A = []
N = 10**3
for a in range(N):
    for b in range(a + 1, N):  # pour éviter les doublons
        if a == sum(diviseurs(b)) and b == sum(diviseurs(a)):
            A.append((a, b))
print(A)

[(220, 284)]

Pour éviter de refaire trop de fois les mêmes calculs, on peut proposer la variante suivante :

In [60]:

A = []
N = 10**4
for a in range(N):
    Da = sum(diviseurs(a))
    for b in range(a + 1, N):  # pour éviter les doublons
        if b == Da:
            Db = sum(diviseurs(b))
            if a == Db:
                A.append((a, b))
print(A)

[(220, 284), (1184, 1210), (2620, 2924), (5020, 5564), (6232, 6368)]

Remarque :

On pourrait même faire encore moins de calculs en enregistrant chaque calcul de somme des diviseurs dans une variable : ce sera possible avec ce que l'on appelle un "dictionnaire", que nous étudierons dans le prochain TP.

Exercice 8 : nombres premiers jumeaux

In [61]:

def jumeaux(n):
    """
    Teste si n et n+2 sont premiers
    """
    C = Crible(n + 3)
    if C[n] and C[n + 2]:
        return True
    else:
        return False

On peut simplifier la syntaxe pour le return :

In [62]:

def jumeaux(n):
    """
    Teste si n et n+2 sont premiers
    """
    C = Crible(n + 3)
    return C[n] and C[n + 2]

In [63]:

jumeaux(3)

Out[63]:

True

In [64]:

jumeaux(7)

Out[64]:

False

In [65]:

N = 2**20
cpt = 0  # compteur
C = Crible(N + 1)
for n in range(N - 2):
    if C[n] and C[n + 2]:
        # print((n,n+2)) # ça prend trop de place à l'affichage
        cpt = cpt + 1
print("Il y a {} couples de nombres premiers jumeaux inférieurs à 2**20.".format(cpt))

Il y a 8535 couples de nombres premiers jumeaux inférieurs à 2**20.

Remarque :

on n'a pas utilisé la fonction jumeaux pour ne pas recalculer le crible à chaque fois...

Exercice 9 : conjecture de Goldbach

In [66]:

C = Crible(101)  # c'est une variable globale


def sommepremier(n):
    """
    Teste si n peut s'écrire comme somme de 2 nombres premiers
    Affiche le premier couple possible le cas échéant
    """
    assert (n % 2 == 0)
    for k in range(2, n // 2 + 2):
        if C[k] and C[n - k]:
            print("{0} = {1} + {2}".format(n, k, n - k))
            return True
    return False

In [67]:

for n in range(2, 101, 2):
    sommepremier(n)

4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7
12 = 5 + 7
14 = 3 + 11
16 = 3 + 13
18 = 5 + 13
20 = 3 + 17
22 = 3 + 19
24 = 5 + 19
26 = 3 + 23
28 = 5 + 23
30 = 7 + 23
32 = 3 + 29
34 = 3 + 31
36 = 5 + 31
38 = 7 + 31
40 = 3 + 37
42 = 5 + 37
44 = 3 + 41
46 = 3 + 43
48 = 5 + 43
50 = 3 + 47
52 = 5 + 47
54 = 7 + 47
56 = 3 + 53
58 = 5 + 53
60 = 7 + 53
62 = 3 + 59
64 = 3 + 61
66 = 5 + 61
68 = 7 + 61
70 = 3 + 67
72 = 5 + 67
74 = 3 + 71
76 = 3 + 73
78 = 5 + 73
80 = 7 + 73
82 = 3 + 79
84 = 5 + 79
86 = 3 + 83
88 = 5 + 83
90 = 7 + 83
92 = 3 + 89
94 = 5 + 89
96 = 7 + 89
98 = 19 + 79
100 = 3 + 97

In [68]:

def goldbach(n):
    """
    Teste si n peut s'écrire comme somme de 2 nombres premiers
    """
    assert (n % 2 == 0)
    for k in range(2, n // 2 + 2):
        if C[k] and C[n - k]:
            return True
    return False

Ici encore, C est une variable globale. Si on ne souhaite pas utiliser de variable globale, on pourrait la passer en paramètre de la fonction goldbach.

In [69]:

N = 2**20
C = Crible(N + 2)  # c'est une variable globale
k = 4
conjecture = goldbach(k)
while conjecture and k <= N:
    k += 2
    conjecture = goldbach(k)
print("La conjecture de Goldbach est-elle vérifiée jusqu'au rang N ?",conjecture)

La conjecture de Goldbach est-elle vérifiée jusqu'au rang N ? True