Feuille 1 : fonctions

21. Feuille 1 : fonctions#

Rappels

Le symbole \(\blacksquare\) indique les exercices ou questions obligatoires. Commencez par ceux-là.
Les symboles \(\star\) et \(\star\star\) indiquent les exercices ou questions de difficulté relative plus importante.

Focus

Fonctions

Compétences

utiliser une fonction prédéfinie ou existante
définir et écrire la spécification d’une fonction qui réalise un traitement décrit en français, ou qui résout un problème (simple) décrit en français
définir et écrire des appels simples (ou des tests unitaires)
définir, écrire et utiliser des tests unitaires
définir et écrire l’implémentation d’une fonction associée à une spécification

Rappel de quelques consignes

Dans cet ordre et avec les corrections entre 2 étapes si besoin :

écriture de la signature de la fonction docstring compris
écriture d’au moins un appel simple ou un test unitaire
écriture du corps
écriture des tests unitaires
exécution des tests unitaires
écriture des appels voulus
exécution des appels voulus

Se souvenir :

Séparer les entrées-sorties des traitements !
Réduire au minimum l’utilisation des input() (les entrées au clavier) et des print() (les sorties à l’écran).
Utiliser des identifiants différents pour les paramètres formels et effectifs, respectivement dans la définition et les appels.

21.1. Objectif 10#

21.1.1. Exercice. (factorielle)#

La valeur de factorielle (de) \(n\), où \(n\) est un entier positif, est : \(n ! = 1 \times 2 \times \cdots \ \times (n-1) \times n\). On choisit \(0 ! = 1\).

\(\blacksquare\) Écrire la fonction factorielle() qui calcule et retourne \(n!\).

def factorielle(n: int) -> int:
    '''
    calcule n!
    entrée. n : int
    retourne int
    '''
    res = 1  
    if (n==0):
        return res
    for i in range(1, n+1):
        res = res * i
    return res

"""
Tests de la fonction factorielle avec quelques cas de base.
Rmq. Ces tests peuvent être regrouper dans une fonction 
tester_factorielle()
"""
assert factorielle(0) == 1  # Cas spécial
assert factorielle(1) == 1
assert factorielle(5) == 120
assert factorielle(10) == 3628800
print("Tous les tests pour factorielle() sont passés.")    

Tous les tests pour factorielle() sont passés.

La fonction factorial() du module math effectue le même calcul. Utiliser cette fonction pour définir et coder des tests unitaires de votre fonction factorielle().

Des tests avec des valeurs aléatoires sont parfois possibles. Ici en faisant confiance à la fonction factorial() du module math de python.

from math import factorial
from random import randint

# tests aléatoires : attention aux temps de calcul
for i in range(10):
    val = randint(0,100)
    assert factorielle(val) == factorial(val)

Utiliser la fonction factorielle() pour écrire des fonctions qui calculent les quantités suivantes.
1. Le nombre d’arrangements (listes ordonnées) de \(k\) valeurs prises dans un ensemble de \(n\) valeurs est : \(\mathcal{A}_n^k = {n !}/{(n-k)!}, (k \le n)\).
2. Le nombre de combinaisons (listes non ordonnées) de \(k\) valeurs prises dans un ensemble de \(n\) valeurs est : \(\left(_k^n\right) = {\mathcal{A}_n^k}/{k!}\), \((k \le n)\).

def arrangements(n: int, k: int) -> int:
    """
    Calcule le nombre d'arrangements de k valeurs prises dans un ensemble de n valeurs.
    Formellement, A_k^n = n! / (n-k)!.
    """
    if k > n:
        return 0  # Pas d'arrangement possible si k > n
    return factorielle(n) // factorielle(n - k)

def combinaisons(n: int, k: int) -> int:
    """
    Calcule le nombre de combinaisons de k valeurs prises dans un ensemble de n valeurs.
    Formellement, C_k^n = A_k^n / k! = n! / (k! * (n-k)!).
    """
    if k > n:
        return 0  # Pas de combinaison possible si k > n
    return arrangements(n, k) // factorielle(k)

def tester_arrangements_et_combinaisons() -> None:
    """
    Teste les fonctions arrangements() et combinaisons() avec quelques cas de base.
    """
    # Tests pour arrangements
    assert arrangements(5, 2) == 20
    assert arrangements(5, 5) == 120
    assert arrangements(5, 0) == 1
    assert arrangements(5, 6) == 0
    
    # Tests pour combinaisons
    assert combinaisons(5, 2) == 10
    assert combinaisons(5, 5) == 1
    assert combinaisons(5, 0) == 1
    assert combinaisons(5, 6) == 0
    
    print("Tous les tests de base pour arrangements() et combinaisons() sont passés.")

tester_arrangements_et_combinaisons()

Tous les tests de base pour arrangements() et combinaisons() sont passés.

Les tests unitaires peuvent utiliser des fonctions préalablement vérifiées.

n = 10

# tests arrangements(n,p)
for i in range(n):
    assert arrangements(n, 0) == 1
    assert arrangements(n, n) == factorielle(n)

Les tests unitaires peuvent utiliser des propriétés mathématiques constructives. Ici : la construction du triangle de Pascal (qui donne les coefficients du développement de \((a + b)^n\) utilise une propriété importante du nombre de combinaison (voir wikipedia si besoin).

# tests C(n,p)
# première et dernière "colonne" du triangle de Pascal
for i in range(n):
    assert combinaisons(n, 0) == 1
    assert combinaisons(n, n) == 1

# Construction du triangle de Pascal
for i in range(10):
    n = randint(0,100)
    p = randint(0, n+1)
    assert combinaisons(n+1, p+1) == combinaisons(n, p) + combinaisons(n, p+1)

Bonus. Approximation arbitrairement précise de \(e^x\) pour \(x\) proche de 1.

def e_approx(x,n):
    '''calcule une appoximation de e avec son dével. limité à l ordre n
    entrées. x : float, n: int
    '''
    app = 1.0 # on accumule
    for k in range(n,0,-1):
        app = app + 1/factorielle(k)
    return app

from math import exp
# test approx e en x0 arbitraire et comparaison selon évoltuion de n
x0 = 1
e0 = exp(x0)
print("n , approx_e (", e0, "), err_relative (en %)")
for ordre in range(2,10):
    app_e0 = e_approx(x0, ordre)
    diff_rel = abs(e0-app_e0)/e0
    print(ordre, "{:2.8f}".format(app_e0), "{:2.2f}".format(diff_rel*100))

n , approx_e ( 2.718281828459045 ), err_relative (en %)
2.50000000 8.03
2.66666667 1.90
2.70833333 0.37
2.71666667 0.06
2.71805556 0.01
2.71825397 0.00
2.71827877 0.00
2.71828153 0.00

21.1.2. \(\blacksquare\) Exercice#

Écrire une fonction moy() qui calcule et retourne la moyenne de 4 valeurs flottantes de façon adaptée au traitement suivant souhaité.

Ces 4 valeurs sont entrées au clavier et stockées dans un tableau.
La moyenne calculée est affichée à l’écran avec un rappel des 4 valeurs correspondantes.

Accompagner votre développement avec quelques tests unitaires bien choisis.

def moy(a: float, b: float, c: float, d: float) -> float:
    """
    Calcule et retourne la moyenne de quatre valeurs flottantes.
    """
    return (a + b + c + d) / 4

def tester_moy() -> None:
    """
    Teste la fonction moy() avec quelques cas de base.
    """
    assert moy(1.0, 1.0, 1.0, 1.0) == 1.0  # Moyenne uniforme
    assert moy(1.0, 2.0, 3.0, 4.0) == 2.5  
    assert moy(-1.0, -1.0, -1.0, -1.0) == -1.0  # Moyenne avec valeurs négatives
    assert moy(0.0, 0.0, 0.0, 0.0) == 0.0  # Moyenne avec zéros
    print("Tous les tests pour moy() sont passés.")

tester_moy()

Tous les tests pour moy() sont passés.

'''
# Cette cellule qui demande des ES au clavier est commentée pour être intégrée au support de cours.
# La décommenter pour l'exécuter
"""
Lit quatre valeurs flottantes au clavier, calcule leur moyenne à l'aide de la fonction moy(),
et affiche la moyenne ainsi que les valeurs initiales.
"""
# Lecture des quatre valeurs au clavier
valeurs = []
for i in range(4):
    valeur = float(input(f"Entrez la valeur {i + 1} : "))
    valeurs.append(valeur)

# Calcul de la moyenne
moyenne = moy(valeurs[0], valeurs[1], valeurs[2], valeurs[3])

# Affichage des résultats
print("Les valeurs entrées sont : " ,valeurs)
print("La moyenne des valeurs est : " ,moyenne)
'''

'\n# Cette cellule qui demande des ES au clavier est commentée pour être intégrée au support de cours.\n# La décommenter pour l\'exécuter\n"""\nLit quatre valeurs flottantes au clavier, calcule leur moyenne à l\'aide de la fonction moy(),\net affiche la moyenne ainsi que les valeurs initiales.\n"""\n# Lecture des quatre valeurs au clavier\nvaleurs = []\nfor i in range(4):\n    valeur = float(input(f"Entrez la valeur {i + 1} : "))\n    valeurs.append(valeur)\n\n# Calcul de la moyenne\nmoyenne = moy(valeurs[0], valeurs[1], valeurs[2], valeurs[3])\n\n# Affichage des résultats\nprint("Les valeurs entrées sont : " ,valeurs)\nprint("La moyenne des valeurs est : " ,moyenne)\n'

21.1.3. Exercice (codage ASCII)#

L’ASCII est un codage de caractères qui définit 128 codes sur 7 bits. Chaque code correspond à un caractère : chiffres, lettres, symboles mathématiques et de ponctuation.

En Python, la fonction ord() retourne le code ASCII d’un caractère fourni en argument. La fonction chr() retourne le caractère associé à un code donné.

Ecrire un programme qui affiche les 128 codes ASCII selon 16 lignes de 8 colonnes.

Remarque. Etre conscient que cette question nécessite de mélanger des traitements (appels de fonctions) et des entrées-sorties (print()).

for i in range(128):
    if i % 8 != 0:
        print(chr(i), end='')
    else:
        print(chr(i))


	



 
!"#$%&'(
)*+,-./0
12345678
9:;<=>?@
ABCDEFGH
IJKLMNOP
QRSTUVWX
YZ[\]^_`
abcdefgh
ijklmnop
qrstuvwx
yz{|}~

Une autre solution pour illustrer les codes ascii des majuscules de l’alphabet

alphabet = 'ABCDEFGHIJKLMNOPQRST'
for c in alphabet:
    print(c, "->", ord(c))
print()

A -> 65
B -> 66
C -> 67
D -> 68
E -> 69
F -> 70
G -> 71
H -> 72
I -> 73
J -> 74
K -> 75
L -> 76
M -> 77
N -> 78
O -> 79
P -> 80
Q -> 81
R -> 82
S -> 83
T -> 84

Et une dernière avec tous les codes ascii. (\(\star\)) Que constatez-vous ?

for i in range(128):
    if i % 10 != 0:
        print(i, "->", chr(i), end=' ')
    else:
        print(i, ":", chr(i))

0 : 1 ->  2 ->  3 ->  4 ->  5 ->  6 ->  7 ->  8 ->  9 -> 	 10 : 

11 ->  12 ->  13 -> 
 14 ->  15 ->  16 ->  17 ->  18 ->  19 ->  20 : 
21 ->  22 ->  23 ->  24 ->  25 ->  26 ->  27 ->  28 ->  29 ->  30 : 
31 ->  32 ->   33 -> ! 34 -> " 35 -> # 36 -> $ 37 -> % 38 -> & 39 -> ' 40 : (
41 -> ) 42 -> * 43 -> + 44 -> , 45 -> - 46 -> . 47 -> / 48 -> 0 49 -> 1 50 : 2
51 -> 3 52 -> 4 53 -> 5 54 -> 6 55 -> 7 56 -> 8 57 -> 9 58 -> : 59 -> ; 60 : <
61 -> = 62 -> > 63 -> ? 64 -> @ 65 -> A 66 -> B 67 -> C 68 -> D 69 -> E 70 : F
71 -> G 72 -> H 73 -> I 74 -> J 75 -> K 76 -> L 77 -> M 78 -> N 79 -> O 80 : P
81 -> Q 82 -> R 83 -> S 84 -> T 85 -> U 86 -> V 87 -> W 88 -> X 89 -> Y 90 : Z
91 -> [ 92 -> \ 93 -> ] 94 -> ^ 95 -> _ 96 -> ` 97 -> a 98 -> b 99 -> c 100 : d
101 -> e 102 -> f 103 -> g 104 -> h 105 -> i 106 -> j 107 -> k 108 -> l 109 -> m 110 : n
111 -> o 112 -> p 113 -> q 114 -> r 115 -> s 116 -> t 117 -> u 118 -> v 119 -> w 120 : x
121 -> y 122 -> z 123 -> { 124 -> | 125 -> } 126 -> ~ 127 ->

Ecrire une autre solution qui ne mélange pas traitements et entrées-sorties.

def ascii_tab() -> list[str]:
    '''
    On utilise un tableau pour stocker les résultats
    '''
    tab = [' ' for i in range(128)]
    for i in range(128):
        tab[i] = chr(i)
    return tab

def es_tab(t: list[str], n: int) -> None:
    '''
    On regroupe les ES dans une fonction adaptée
    '''
    assert n == len(t)

    for i in range(128):
        if i % 8 != 0:
            print(t[i], end='')
        else:
            print(t[i])

res = ascii_tab()
es_tab(res, len(res))


	



 
!"#$%&'(
)*+,-./0
12345678
9:;<=>?@
ABCDEFGH
IJKLMNOP
QRSTUVWX
YZ[\]^_`
abcdefgh
ijklmnop
qrstuvwx
yz{|}~

(*) Bien comprendre les parenthèses de l’appel suivant qui produit le même traitement que le précédent.

es_tab(ascii_tab() , len(ascii_tab()))


	



 
!"#$%&'(
)*+,-./0
12345678
9:;<=>?@
ABCDEFGH
IJKLMNOP
QRSTUVWX
YZ[\]^_`
abcdefgh
ijklmnop
qrstuvwx
yz{|}~

21.1.4. \(\blacksquare\) Exercice#

On rappelle quelques suites et séries numériques classiques.

La somme des \(n\) premiers entiers : \(s_1(n) = 1 + 2 + \cdots + (n-1) + n = \sum_{k=1}^{n} k\) ;
La suite de Fibonacci : \(u_{n+1} = u_{n}+ u_{n-1}\) et \(u_0=u_1=1\).
Une suite arithmético-géométrique : \(u_{n+1} = u_n/3 + 2\) avec \(u_0=1\).

La somme des \(n\) premiers entiers : \(s_1(n) = 1 + 2 + \cdots + (n-1) + n = \sum_{k=1}^{n} k\) ;

Écrire des fonctions (en-tête, appel, corps) qui calculent et retournent le \(n\)-ième terme de ces suites.
Ecrire des tests unitaires adaptés. Justifier vos choix.
Pour chacune de ces suites et en utilisant ces fonctions, lire une valeur de \(n\) entrée au clavier, calcule le \(n\)-ième terme de la suite puis l’afficher à l’écran.

def somme1(n : int) -> int:
    '''
    Calcule et retourne la somme des n premiers entiers.
    '''
    s = 0
    for i in range(1, n+1):
        s = s + i
    return s

def tester_somme1() -> None:
    """
    Teste les fonctions associées aux suites avec quelques cas de base.
    """
    # Tests pour la somme des n premiers entiers
    assert somme1(0) == 0   
    assert somme1(1) == 1
    assert somme1(5) == 15
    assert somme1(10) == 55
    
tester_somme1()

# Utilisation d'une propriété mathématique bien connue et d'aléa

from math import factorial
from random import randint

# tests aléatoires : attention aux temps de calcul
for i in range(10):
    n = randint(0,100)
    assert  somme1(n) == n*(n+1)//2 

print("Tous les tests pour somme1() sont passés.")

Tous les tests pour somme1() sont passés.

La suite de Fibonacci : \(u_{n+1} = u_{n}+ u_{n-1}\) et \(u_0=u_1=1\).

Écrire des fonctions (en-tête, appel, corps) qui calculent et retournent le \(n\)-ième terme de ces suites.
Ecrire des tests unitaires adaptés. Justifier vos choix.
Pour chacune de ces suites et en utilisant ces fonctions, lire une valeur de \(n\) entrée au clavier, calcule le \(n\)-ième terme de la suite puis l’afficher à l’écran.

def fibo(n: int) -> int:
    '''
    Calcule et retourne le n-ième terme de la suite de Fibonacci.
    '''
    f_0 = 1
    f_1 = 1
    if n == 0:
        res = f_0
    elif n == 1:
        res = f_1
    else:
        for i in range(2, n+1):
            res = f_0 + f_1
            f_0 = f_1
            f_1 = res

    return res

def tester_fibo() -> None:
    """
    Teste fibo() avec quelques cas de base.
    """
    # Tests pour la suite de Fibonacci
    assert fibo(0) == 1
    assert fibo(1) == 1
    assert fibo(5) == 8
    assert fibo(10) == 89

    print("Tous les tests pour fibo() sont passés.")
    
tester_fibo()

Tous les tests pour fibo() sont passés.

'''
# ES commentées

nb = int(input("suite de Fibonacci pour n = "))

F = Fibo(nb)
 
print("la suite Fibonacci : Fibo(", nb, ") = ", F)
'''

'\n# ES commentées\n\nnb = int(input("suite de Fibonacci pour n = "))\n\nF = Fibo(nb)\n \nprint("la suite Fibonacci : Fibo(", nb, ") = ", F)\n'

Une suite arithmético-géométrique : \(u_{n+1} = u_n/3 + 2\) avec \(u_0=1\).

Écrire des fonctions (en-tête, appel, corps) qui calculent et retournent le \(n\)-ième terme de ces suites.
Ecrire des tests unitaires adaptés. Justifier vos choix.
Pour chacune de ces suites et en utilisant ces fonctions, lire une valeur de \(n\) entrée au clavier, calcule le \(n\)-ième terme de la suite puis l’afficher à l’écran.

def suiteArithmeticoGeometrique(n: int) -> int:
    '''
    calcule u_n = (u_n-1)/3+2
    entrée. n : int
    retourne float
    '''
    u = 1.0
    for i in range(1, n+1):
        u = u/3.0 + 2.0
    return u

'''
# ES commentéesnb = int(input("n = "))

# appel
res = suiteArithmeticoGeometrique(nb)

print("u(", nb, ") = ", res)
'''

'\n# ES commentéesnb = int(input("n = "))\n\n# appel\nres = suiteArithmeticoGeometrique(nb)\n\nprint("u(", nb, ") = ", res)\n'

21.1.5. Exercice#

\(\blacksquare\) Définir et écrire une fonction est_rectangle() qui vérifie si un triangle est rectangle. Aucune hypothèse est effectuée sur les paramètres de ce traitement.

def est_rectangle(a: float, b: float, c: float) -> bool:
    '''vérifie si le triangle de c^tés (a,b,c) est triangle grâce au théorème de Pythagore''' 
    assert a * b * c != 0 # pas de coté de longuer nulle dans un triangle (non plat)
    
    if a*a + b*b == c*c:
        return True
    if b*b + c*c == a*a:
        return True
    if a*a + c*c == b*b:
        return True
    return False

Ecrire des tests unitaires adaptés. Justifier vos choix.

assert est_rectangle(3, 4, 5)
assert est_rectangle(3.0, 4.0, 5.0)

# tester des égalités en des valeurs flottantes est compliqué
# décommenter le premier assert et conclure sur l'intérêt du second
from math import sqrt
#assert sqrt(2.0) * sqrt(2.0) == 2.0
#assert est_rectangle(1.0, 1.0, sqrt(2.0))

# pourquoi ?
print(sqrt(2.0) * sqrt(2.0))

2.0000000000000004

# une piste ? 
epsilon = float(10**(-16)) # une valeur petite
assert (sqrt(2.0) * sqrt(2.0) <= 2.0 - epsilon) or (sqrt(2.0) * sqrt(2.0) >= 2.0 - epsilon) 

Hélas ça reste compliqué pour est_rectangle() :

# OK pour sqrt(2.0) mais est_rectangle() demande une égalité ... 
# Le test suivant ne peut pas passer
#assert est_rectangle(1.0, 1.0, sqrt(2.0) - epsilon) or est_rectangle(1.0, 1.0, sqrt(2.0) + epsilon) 

Conclusion :

solution 1 : limiter est_rectangle() aux int
solution 2 : modifier la version float en remplaçant l’égalité de façon similaire au test “d’égalité” sur sqrt(2.0).

21.1.6. \(\blacksquare\) Exercice#

Ecrire une fonctions tabup() qui vérifie si les n valeurs d’un tableau sont rangées par ordre croissant. Ces valeurs sont des entiers.

Accompagner votre développement avec quelques tests unitaires bien choisis.

def tabup(tab: list, n: int) -> bool:
    """
    Vérifie si les valeurs du tableau sont rangées en ordre croissant.
    Utilise une boucle for.
    """
    assert n == len(tab)
    
    for i in range(len(tab) - 1):  # Parcourt le tableau jusqu'à l'avant-dernier élément
        if tab[i] > tab[i + 1]:  # Vérifie si un élément est plus grand que le suivant
            return False
    return True

def tabup_while(tab: list, n: int) -> bool:
    """
    Vérifie si les valeurs du tableau sont rangées en ordre croissant.
    Utilise une boucle while.
    """
    assert n == len(tab)
    
    i = 0
    while i < len(tab) - 1:  # Tant qu'on n'a pas atteint l'avant-dernier élément
        if tab[i] > tab[i + 1]:  # Si un élément est plus grand que le suivant
            return False
        i = i + 1  # Passage à l'élément suivant
    return True

def tester_tabup() -> None:
    """
    Teste les fonctions tabup() et tabup_while() avec plusieurs cas.
    """
    # Cas où le tableau est trié
    assert tabup([1, 2, 3, 4, 5], 5) == True
    assert tabup_while([1, 2, 3, 4, 5], 5) == True

    # Cas où le tableau n'est pas trié
    assert tabup([1, 3, 2, 4, 5], 5) == False
    assert tabup_while([1, 3, 2, 4, 5], 5) == False

    # Cas avec un seul élément
    assert tabup([10], 1) == True
    assert tabup_while([10], 1) == True

    # Cas avec un tableau vide
    assert tabup([], 0) == True
    assert tabup_while([], 0) == True

    # Cas où tous les éléments sont identiques
    assert tabup([5, 5, 5, 5], 4) == True
    assert tabup_while([5, 5, 5, 5], 4) == True

    print("Tous les tests pour tabup() et tabup_while() sont passés.")

tester_tabup()

Tous les tests pour tabup() et tabup_while() sont passés.

Compléments.

assert peut afficher un message d’erreur “personnalisé” après AssertionErrror

Dé-commenter les cellules suivantes pour observer.

#assert True == False

#assert True == False, "Pff tu es sûr ?"

# Tests unitaires
def test_tabup():
    # Cas où le tableau est vide
    assert tabup([], 0) == True
    
    # Cas où le tableau contient un seul élément
    assert tabup([1], 1) == True, "Échec: tableau avec un seul élément doit retourner True"
    
    # Cas où le tableau est trié par ordre croissant
    assert tabup([1, 2, 3, 4, 5], 5) == True, "Échec: tableau trié doit retourner True"
    
    # Cas où le tableau n'est pas trié
    assert tabup([5, 3, 2, 1], 4) == False, "Échec: tableau non trié doit retourner False"
    
    # Cas où le tableau contient des éléments égaux
    assert tabup([1, 2, 2, 3], 4) == True, "Échec: tableau avec éléments égaux triés doit retourner True"
    
    # Cas où le tableau contient des valeurs décroissantes
    assert tabup([5, 4, 3, 2, 1], 5) == False, "Échec: tableau décroissant doit retourner False"

# Exécuter les tests
test_tabup()
print("Tous les tests avec message ont réussi.")

Tous les tests avec message ont réussi.

21.1.7. \(\blacksquare\) Exercice (tableaux 1D)#

Soit t un tableau 1D d’entiers de taille n arbitraire. Voici quelques traitements classiques de ces tableaux et les fonctions associées.

max_tab() qui calcule et retourne la valeur maximale d’un tableau 1D.
max_ind_max() qui calcule et retourne le plus grand indice de la valeur maximale d’un tableau 1D.
min_ind_max() : une modification de la fonction précédente qui calcule et retourne le plus petit indice de la valeur maximale d’un tableau 1D.

Pour chacune de ces fonctions, deux questions.

Proposer des solutions itératives alternatives (for vs. while) lorsque qu’elles conduisent à des traitements différents.
Tests unitaires : expliciter différents tableaux t qui correspondent, le cas échéant, à des cas particuliers de traitement. Les tester pour valider vos solutions.

def max_tab_for(t: list[int], n: int)-> int:
    '''
    calcule et retourne la valeur maximale de t
    '''
    assert n == len(t)
    assert n > 0 # pas de tableau vide
    
    max_val = t[0]
    max_val = t[0]
    for num in t:
        if num > max_val:
            max_val = num
    return max_val

def max_tab_while(t: list[int], n: int)-> int:
    '''
    calcule et retourne la valeur maximale de t
    '''
    assert n == len(t)
    assert n > 0 # pas de tableau vide    
        
    max_val = t[0]
    max_val = t[0]
    i = 0
    while i < len(t):
        if t[i] > max_val:
            max_val = t[i]
        i += 1
    return max_val

def max_ind_max_for(t: list[int], n: int)-> int:
    '''
    calcule et retourne le plus grand indice de la
    valeur maximale de t
    '''
    assert n == len(t)
    assert n > 0 # pas de tableau vide
    
    max_val = t[0]
    max_val = t[0]
    max_index = 0
    for i in range(len(t)):
        if t[i] >= max_val:  # Using >= to find the largest index
            max_val = t[i]
            max_index = i
    return max_index

def max_ind_max_while(t: list[int], n: int)-> int:
    '''
    calcule et retourne le plus grand indice de la
    valeur maximale de t
    '''
    assert n == len(t)
    assert n > 0 # pas de tableau vide
    
    max_val = t[0]
    max_val = t[0]
    max_index = 0
    i = 0
    while i < len(t):
        if t[i] >= max_val:  # Using >= to find the largest index
            max_val = t[i]
            max_index = i
        i += 1
    return max_index

def min_ind_max_for(t: list[int], n: int)-> int:
    '''
    calcule et retourne le plus petit indice de la valeur maximale de t
    '''
    assert n == len(t)
    assert n > 0 # pas de tableau vide
    
    max_val = t[0]
    min_index = 0
    for i in range(len(t)):
        if t[i] > max_val or (t[i] == max_val and i < min_index):
            max_val = t[i]
            min_index = i
    return min_index

def min_ind_max_while(t: list[int], n: int)-> int:
    '''
    calcule et retourne le plus petit indice de la valeur maximale de t
    '''
    assert n == len(t)
    assert n > 0 # pas de tableau vide
    
    max_val = t[0]
    min_index = 0
    i = 0
    while i < len(t):
        if t[i] > max_val or (t[i] == max_val and i < min_index):
            max_val = t[i]
            min_index = i
        i += 1
    return min_index

def tester_fonctions() -> None:
    """
    Teste les fonctions max_tab(), max_ind_max() et min_ind_max() avec différents cas.
    """
    # Cas normal avec des valeurs différentes
    t1 = [1, 3, 7, 2, 7, 5]
    assert max_tab_for(t1, len(t1)) == 7
    assert max_ind_max_for(t1, len(t1)) == 4  # Dernier 7
    assert min_ind_max_for(t1, len(t1)) == 2  # Premier 7

    # Cas où tous les éléments sont identiques
    t2 = [4, 4, 4, 4]
    assert max_tab_for(t2, len(t2)) == 4
    assert max_ind_max_for(t2, len(t2)) == 3  # Dernier 4
    assert min_ind_max_for(t2, len(t2)) == 0  # Premier 4

    # Cas avec un seul élément
    t3 = [10]
    assert max_tab_for(t3, len(t3)) == 10
    assert max_ind_max_for(t3, len(t3)) == 0
    assert min_ind_max_for(t3, len(t3)) == 0

    

    print("Tous les tests sur les versions for sont passés avec succès.")

tester_fonctions()

Tous les tests sur les versions for sont passés avec succès.

On teste maintenant sur d’autres cas la validité des versions for et while.

test_cases = [
    [1, 3, 7, 7, 2],       # Cas normal avec des valeurs max répétées
    [10, 20, 30, 40, 50],  # Ordre croissant
    [50, 40, 30, 20, 10],  # Ordre décroissant
    [7],                   # Tableau avec un seul élément
    [3, 3, 3, 3],          # Tous les éléments identiques
]

for test in test_cases:
    assert max_tab_for(test, len(test)) == max_tab_while(test, len(test))
    assert max_ind_max_for(test, len(test)) == max_ind_max_while(test, len(test))
    assert min_ind_max_for(test, len(test)) == min_ind_max_while(test, len(test))

21.1.8. \(\blacksquare\) Exercice (extrait d’examen 2017 sans machine)#

Que calcule la fonction m suivante ?

    def m(s : str, n : int, c : str ) -> int: 
        ''' role : à vous de deviner :) '''
        res = 0
        for i in range(n): 
            if s[i] == c: 
                res = res + 1 
        return res

La fonction m calcule le nombre d’occurrences d’un caractère donné c dans les n premiers caractères de la chaîne s

Quel résultat produit l’exécution du code suivant ?

    t = "anticonstitutionnellement" 
    nba = m(t, len(t), 'a') 
    nbe = m(t, len(t), 'e') 
    nbl = m(t, len(t), 'l') 
    print(len(t), nba, nbe, nbl)

def m(s : str, n : int, c : str ) -> int: 
        ''' role : à vous de deviner :) '''
        res = 0
        for i in range(n): 
            if s[i] == c: 
                res = res + 1 
        return res

25 1 3 2

Utiliser la fonction m pour écrire une fonction mm qui identifie et retourne la lettre ayant le maximum d’occurrences dans une chaîne de caractères de longueur n. Si plusieurs lettres conviennent, l’algorithme identifiera celle dont l’occurrence est la plus tardive dans s. Par exemple 'o' dans 'toto'.

Accompagner cette fonction de quelques tests unitaires pertinents.

def mm(s: str, n: int) -> str:
    '''
    - identifie et retourne la lettre ayant le maximum d'occurrences dans une chaîne
    de caractères de longueur `n`
    - si plusieurs lettres conviennent, retiourne celle dont l'occurrence est la plus tardive
    '''
    assert n == len(s)
    
    max_occ = 0
    max_char = ""
    for i in range(n):
        nbOcc = m(s,n,s[i])
        if nbOcc >= max_occ:
            max_occ = nbOcc
            max_char = s[i]

    return max_char

def tester_mm() -> None:
    """
    Teste la fonction mm() avec plusieurs cas.
    """
    assert mm("toto", 4) == "o"  # 'o' et 't' apparaissent 2 fois, mais 'o' est plus tardif
    assert mm("banana", 6) == "a"  # 'a' apparaît 3 fois (plus que 'n' et 'b')
    assert mm("hello", 5) == "l"  # 'l' apparaît 2 fois, et sa dernière apparition est tardive
    assert mm("mississippi", 11) == "i"  # 'i' est le plus fréquent et le plus tardif
    assert mm("", 0) == ""  # Cas vide

    print("Tous les tests pour mm() sont passés.")

tester_mm()

Tous les tests pour mm() sont passés.

Écrire le code qui utilise mm et fournit l’affichage suivant.

t est la lettre qui apparaît le plus ( 5 fois) dans anticonstitutionnellement
o est la lettre qui apparaît le plus ( 2 fois) dans toto

t1 = "anticonstitutionnellement"
t2 = "toto"

lettre1 = mm(t1, len(t1))
lettre2 = mm(t2, len(t2))

print(lettre1 ,"est la lettre qui apparaît le plus (",m(t1, len(t1), lettre1)," fois) dans", t1)
print(lettre2 ,"est la lettre qui apparaît le plus (",m(t2, len(t2), lettre2)," fois) dans", t2)

t est la lettre qui apparaît le plus ( 5  fois) dans anticonstitutionnellement
o est la lettre qui apparaît le plus ( 2  fois) dans toto

Modifier mm pour que dans le cas d’une occurrence maximale multiple, l’algorithme identifie la lettre de première occurrence. Par exemple, 't' dans 'toto'.

def mm(s: str, n: int) -> str:
    """
    Identifie et retourne la lettre ayant le maximum d'occurrences dans une chaîne de longueur n.
    Si plusieurs lettres ont le même nombre d'occurrences, retourne celle qui apparaît en premier.
    """
    assert n == len(s)

    max_occ = 0  # Nombre maximum d'occurrences trouvées
    max_char = ""  # Lettre ayant le maximum d'occurrences

    for i in range(n):  # Parcours chaque lettre de la chaîne en partant de la fin
        nbOcc = m(s, n, s[i])  # Nombre d'occurrences de la lettre s[i]
        if nbOcc > max_occ: # la première occurence maximale est conservée
            max_occ = nbOcc
            max_char = s[i]
                

    return max_char

def tester_mm() -> None:
    """
    Teste la fonction mm() avec plusieurs cas.
    """
    assert mm("toto", 4) == "t"  # 't' et 'o' apparaissent 2 fois, mais 't' est le premier
    assert mm("banana", 6) == "a"  # 'a' apparaît 3 fois
    assert mm("hello", 5) == "l"  # 'l' apparaît 2 fois, et le premier 'l' est à l'indice 2
    assert mm("abcabcabc", 9) == "a"  # 'a', 'b', 'c' sont égaux mais 'a' est le premier
    assert mm("aaaaa", 5) == "a"  # Seul 'a' existe
    assert mm("abcdef", 6) == "a"  # Tous uniques, premier caractère choisi
    assert mm("mississippi", 11) == "i"  # 'i' est le plus fréquent et son premier 'i' est à l'indice 1
    assert mm("", 0) == ""  # Cas vide

    print("Tous les tests pour mm() sont passés.")

tester_mm()

Tous les tests pour mm() sont passés.

Réécrire la fonction mm de la question que:mmavecm sans utiliser la fonction m. Vérifier que les tests unitaires écrits plus haut valident cette version.

(exo:palindromeiter)

21.1.9. \(\blacksquare\) Exercice (palindrome)#

Un palindrome est un mot, ou un groupe de mots, dont l’ordre des lettres reste le même qu’on le lise de la droite vers la gauche ou inversement. Des exemples bien connus sont “été”, “kayak”, “mon nom”, “élu par cette crapule”. Ce dernier permet d’illustrer qu’on ne tient pas compte en général des accents, trémas, cédilles, ni des espaces. Dans cet exercice :

un mot ou un groupe de mots est représenté par une chaîne de caractères (str),
ces caractères sont sans accent, tréma, ni cédille : “ete”
les espaces sont considérés comme des caractères : ainsi “elu par cette crapule” n’est pas un palindrome ici.

Ecrire une fonction qui teste si un argument est ou non un palindrome et retourne le booléen correspondant.
Valider votre fonction avec des tests unitaires.

def est_palindrome(s: str, n: int) -> bool:
    """
    Vérifie si une chaîne de caractères est un palindrome.
    La comparaison prend en compte les espaces et la casse.
    """
    assert n == len(s)
    
    for i in range(n // 2):  # On compare les caractères symétriques
        if s[i] != s[n - 1 - i]:  # Vérifie si le premier != dernier, deuxième != avant-dernier...
            return False
    return True

def tester_est_palindrome() -> None:
    """
    Teste la fonction est_palindrome() avec plusieurs cas.
    """
    assert est_palindrome("ete", 3) == True  # Mot palindrome
    assert est_palindrome("kayak", 5) == True  # Mot palindrome
    assert est_palindrome("mon nom", 7) == True  # Prend en compte l'espace
    assert est_palindrome("hello", 5) == False  # Pas un palindrome
    assert est_palindrome("aa", 2) == True  # Deux lettres identiques
    assert est_palindrome("a", 1) == True  # Une seule lettre
    assert est_palindrome("", 0) == True  # Chaîne vide est un palindrome

    print("Tous les tests pour est_palindrome() sont passés.")

tester_est_palindrome()

Tous les tests pour est_palindrome() sont passés.

21.1.10. Exercice (produit scalaire)#

Rappel : le produit scalaire deux vecteurs orthogonaux est nul.

Ecrire les fonctions qui vérifie l’orthogonalité ou non de vecteurs

de taille 3,
de taille arbitraire \(n\).

def produit_scalaire_3D(v1: list, n1: int, v2: list, n2 : int) -> int:
    """
    Calcule le produit scalaire de deux vecteurs de dimension 3.
    """
    assert len(v1) == 3
    assert len(v2) == 3
    
    return v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2]

def sont_orthogonaux_3D(v1: list, n1: int, v2: list, n2 : int) -> bool:
    """
    Vérifie si deux vecteurs de dimension 3 sont orthogonaux (produit scalaire nul).
    """
    assert len(v1) == 3
    assert len(v2) == 3

    
    return produit_scalaire_3D(v1, 3, v2, 3) == 0

def produit_scalaire_nD(v1: list, n1: int, v2: list, n2 : int) -> int:
    """
    Calcule le produit scalaire de deux vecteurs de dimension n.
    """
    assert len(v1) == n1
    assert len(v1) == n2
    assert len(v1) == len(v2)
    
    produit = 0
    for i in range(len(v1)):
        produit += v1[i] * v2[i]
    
    return produit

def sont_orthogonaux_nD(v1: list, n1: int, v2: list, n2 : int) -> bool:
    """
    Vérifie si deux vecteurs de dimension n sont orthogonaux.
    """
    assert len(v1) == n1
    assert len(v1) == n2
    assert len(v1) == len(v2)

    
    return produit_scalaire_nD(v1, n1, v2, n2) == 0

def tester_orthogonalite() -> None:
    """
    Teste les fonctions de produit scalaire et d'orthogonalité.
    """
    # Tests en 3D
    assert sont_orthogonaux_3D([1, 0, 0], 3, [0, 1, 0], 3) == True  # Orthogonaux
    assert sont_orthogonaux_3D([1, 2, 3], 3, [-2, 1, 0], 3) == True  # Non orthogonaux
    assert sont_orthogonaux_3D([1, 1, 1], 3,[-1, -1, -1], 3) == False  # Pas orthogonaux

    # Tests en nD
    assert sont_orthogonaux_nD([1, 2, 3, 4], 4, [-4, -3, -2, -1], 4) == False  # Pas orthogonaux
    assert sont_orthogonaux_nD([1, 5, 2, 0], 4, [0, 2, -5, 1], 4) == True  # Orthogonaux
    assert sont_orthogonaux_nD([1, 1, 1, 1], 4, [-1, -1, -1, -1], 4) == False  # Pas orthogonaux

    print("Tous les tests pour l'orthogonalité sont passés.")

tester_orthogonalite()

Tous les tests pour l'orthogonalité sont passés.

21.1.11. \(\blacksquare\) Exercice (tableau 2D)#

Écrire une fonction qui, pour les deux paramètres entiers a et b (\(a \le b\)), calcule la table de multiplication entre les entiers compris entre a et b inclus. Le résultat attendu est un tableau 2D : la case \((i,j)\) du tableau contient le résultat de \(i \times j\). La table des multiplications entre 1 et 10 est obtenue pour \(a = 1\) et \(b= 10\).
Utiliser cette fonction pour afficher cette table pour des valeurs de a et b entrées au clavier.

21.1.12. \(\blacksquare\) Exercice (matrices)#

Ecrire les algorithmes de vérification suivants pour une matrice \(M\) donnée, carrée de taille \(n\) et à valeurs flottantes.

\(M\) est diagonale ?
\(M\) est symétrique ?
\(M\) est égale à l’identité ?
\(M\) est l’inverse d’une autre matrice donnée \(N\) ?

def est_diagonale(m: list[list[float]], n: int) -> bool:
    assert n == len(m)  # nb lignes
    for i in range(n): # chaque colonne
        assert len(m[i]) == n
            
    for i in range(n):
        for j in range(n):
            if i != j and m[i][j] != 0:  # Vérifie les éléments hors diagonale
                return False
    return True

def est_symetrique(m: list[list[float]], n: int) -> bool:
    assert n == len(m)  # nb lignes
    for i in range(n): # chaque colonne
        assert len(m[i]) == n

    for i in range(n):
        for j in range(i, n):  # Parcourt uniquement la moitié supérieure
            if m[i][j] != m[j][i]:
                return False
    return True

def est_identite(m: list[list[float]], n: int) -> bool:
    assert n == len(m)  # nb lignes
    for i in range(n): # chaque colonne
        assert len(m[i]) == n

    for i in range(n):
        for j in range(n):
            if (i == j and m[i][j] != 1) or (i != j and m[i][j] != 0):
                return False
    return True

def sont_inverse(m1: list[list[float]], n1: int, m2: list[list[float]], n2: int) -> bool:
    assert n1 == n2
    assert n1 == len(m1)  # nb lignes
    for i in range(n1): # chaque colonne
        assert len(m1[i]) == n1
    assert n2 == len(m2)  # nb lignes
    for i in range(n2): # chaque colonne
        assert len(m2[i]) == n2
    
    n = n1
    for i in range(n):
        for j in range(n):
            res = 0.0
            for k in range(n):
                res = res + m1[i][k] * m2[k][j] # (m1*m2)[i][j]
                
            if (i == j and res != 1.) or (i != j and res != 0.):
                return False
    return True

# Exemple de matrices
M1 = [[1, 0, 0], [0, 2, 0], [0, 0, 3]]  # Matrice diagonale
M2 = [[1, 2, 3], [2, 4, 5], [3, 5, 6]]  # Matrice symétrique
M3 = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]  # Matrice identité
M4 = [[0.5, 0], [0, 0.5]]               # Inverse d'une matrice donnée
N4 = [[2, 0], [0, 2]]                   # Matrice donnée

assert est_diagonale(M1, 3)
assert est_symetrique(M2, 3)
assert est_identite(M3, 3)
assert sont_inverse(M4, 2, N4, 2)