Automatismes

L’image gif ci-dessous présente différentes étapes du déroulement d’un algorithme de rotation d’images inspiré d’un travail présenté par Laurent Abbal du lycée français de Tokyo. Le programme assez court peut être réalisé par un élève de terminale (récursivité, approche diviser pour régner). L’image source représente l’oeuvre Matsuri Yatai Dragon du peintre japonais Hokusai. Elle est dans le domaine public et disponible sur https://commons.wikimedia.org.

Dragon

Corrigé des automatismes

Automatisme 1

Programmer la fonction dont on donne la spécification :

def index_min(t):
    """
    Paramètre : t un tableau de nombres (int ou float)
    Précondition : t non vide
    Valeur renvoyée : un tableau contenant les positions (index) où le minimum de t est atteint
    """

Automatisme 2

Programmer la fonction dont on donne la spécification :

def au_moins_un_zero(t):
    """
    Paramètre : t un tableau de nombres (int ou float)
    Précondition : t non vide
    Valeur renvoyée : un booléen indiquant si t contient au moins un zéro
    """

Automatisme 3

Représenter en binaire le nombre d’écriture décimale 49.

Automatisme 4

Représenter en base dix, le nombre dont l’écriture en base deux est 1010110 puis le nombre dont l’écriture en base 16 est A4.

Automatisme 5

Déterminer le successeur des entiers dont l’écriture en base deux est :

Automatisme 6

Pour déterminer la liste des chiffres en base dix d’un entier naturel, un élève a écrit la fonction ci-dessous :

def liste_chiffres(n):
    L = [n % 10]
    while n > 0:
        n = n // 10
        L.insert(0, n % 10)
    return L

Malheureusement sa fonction ne retourne pas le résultat attendu pour l’entier 730 :

>>> liste_chiffres(730)
[0, 7, 3, 0]

Proposer une version corrigée de la fonction liste_chiffres.

Automatisme 7

On travaille sur des tableaux à deux dimensions qui représentent des images binaires : un pixel a pour valeur un entier : 0 pour un pixel noir et 1 pour un pixel blanc.

Compléter les fonctions ci-dessous en respectant leurs spécifications, les postconditions doivent être vérifiées.

Lien vers Basthon pour tester en ligne.

def image_noire(largeur, hauteur):
    """
    Paramètre : 
        largeur et hauteur deux entiers non nuls
    Valeur renvoyée :
        un tableau à 2 dimensions représentant une image
        binaire de dimensions (largeur, hauteur)
        rempli de 0
    """
    # à compléter avec un tableau en compréhension
    
def dimensions(tab):
    """
    Paramètre : 
        tab un tableau à deux dimensions d'entiers
        représentant une image binaire rectangulaire
    Valeur renvoyée :
        un tableau de deux entiers [largeur, hauteur]
        représentant les dimensions de l'image
    """
    # à compléter
    
def nombre_blancs(tab):
    """
    Paramètre : 
        tab un tableau à deux dimensions d'entiers
        représentant une image binaire rectangulaire
    Valeur renvoyée :
        un entier représentant le nombre de pixels 
        blancs (valeur 1)
    """
    # à compléter

#postconditions pour la fonction image_noire 
assert image_noire(2,1) == [[0,0]]
assert image_noire(1,2) == [[0], [0]]
assert image_noire(3,2) == [[0,0,0], [0,0,0]]


#postconditions pour la fonction dimensions 
assert dimensions([[], []]) == [2,0]
assert dimensions([[0,1,2], [3,4,5]]) == [2,3]

#postconditions pour la fonction nombre_blancs
assert nombre_blancs([[0,0], [0,0]]) == 0
assert dimensions([[0,1,1], [0,1,0]]) == 3
assert dimensions([[], []]) == 0

Automatisme 8

Modifier les expressions “à modifier” dans la fonction Python ci-dessous pour que la spécification soit vérifiée.

Tester le code dans Basthon

Décommenter #test_indice_maximum(indice_maximum) en ligne 63 pour soumettre votre fonction au test unitaire.

def indice_maximum(tab, debut, fin):
    """
    Paramètres : 
        tab un tableau d'entiers
        debut un entier indice du début de la plage
        fin un entier indice de la fin de la plage (inclus)
    Valeur renvoyée : l'indice de la première occurence du maximum de tab 
    dans la plage  de valeurs entre les indice et debut et fin (inclus)
    """
    imax = "à modifier"
    for i in range(imax + 1, fin + 1):
        if "à modifier":
            imax = "à modifier"
    return imax

Automatisme 9

Modifier les expressions “à modifier” dans la fonction tri_selection ci-dessous pour que la spécification et l’assertion placée à la fin de la boucle externe soient vérifiés.

def tri_selection(tab):
    """
    Paramètre : tab un tableau de nombres
    Valeur renvoyée : tab
    Postcondition : valeur renvoyée de tab triée dans l'ordre croissant
    """
    i = len(tab) - 1
    while i >= 1:
        imax = indice_maximum(tab, "à modifier", "à modifier")
        tab[i], tab[imax] =  "à modifier"
        # assertion qui doit être vérifiée
        assert max(tab[:i+1]) == tab[i]
        i = "à modifier"
    return tab 

Décommenter #test_tri(tri_selection) en ligne 64 pour soumettre votre fonction au test unitaire.

Automatisme 10

Un algorithme de tri d’une liste d’entiers est implémenté de la façon suivante :

def trier(L) : 
    for i in range(len(L)): 
        indice_min = i 
        for j in range(i+1, len(L)): 
            if L[j] < L[indice_min] : 
                indice_min = j 
        L[i], L[indice_min] = L[indice_min], L[i] 
        # assertion vraie à cet endroit 
    return L 

Parmi les assertions suivantes laquelle reste vraie à chaque itération de la boucle, à l’endroit indiqué ci-dessus ?

Automatisme 11

def un_doublon(t):
    """
    Paramètre : t un tableau de nombres
    Valeur renvoyée : un booléen 
        True si t comporte au moins un doublon
        False sinon
    """
    #à compléter

assert un_doublon([1, 2, 3]) == False
assert un_doublon([1, 2, 2]) == True
assert un_doublon([1, 2, 4, 2]) == True
assert un_doublon([]) == False

Automatisme 12

def index_premiere_occurence_dicho(x, t):
    """
    Paramètre : 
        t un tableau de nombres trié dans l'ordre croissant
        x un nombre 
    Valeur renvoyée : 
        l'index de la première de x dans t si x est dans t
        -1 sinon
    """
    a = 0
    b = len(t) - 1
    while a <= b:
        m = (a + b) // 2
        if t[m] < x:
            "à compléter"
        elif t[m] > x:
            "à compléter"
        else:
            "à compléter"
            return "à compléter"
    return -1

assert index_premiere_occurence_dicho(10, [10, 10, 11, 12, 13]) == 1
assert index_premiere_occurence_dicho(10, [9, 10, 11, 12, 13]) == 1
assert index_premiere_occurence_dicho(10, [9, 9, 11, 12, 13]) == -1
assert index_premiere_occurence_dicho(10, [7, 8, 9, 10]) == 3 
assert index_premiere_occurence_dicho(10, [7, 10, 10,  10, 10]) == 1 
assert index_premiere_occurence_dicho(10, []) == -1

Automatisme 13

def est_decroissant(t):
    """
    Paramètre : 
        t un tableau de nombres 
    Valeur renvoyée : 
        booléen indiquant si t dans l'ordre décroissant
    """
    "à compléter"


def recherche_dicho_decroissant(x, t):
    """
    Paramètre : 
        t un tableau de nombres trié dans l'ordre décroissant
        x un nombre 
    Valeur renvoyée : 
        index de x dans t si x dans t
        None si x pas dans t
    """
    a = 0
    b = len(t) - 1
    while a <= b:
        m = (a + b) // 2
        "à compléter"
    return None

assert est_decroissant([k ** 2 for k in range(10)]) == False
assert est_decroissant([]) == True
t1 = list(range(10, -1, -1))
assert est_decroissant(t1) == True
assert recherche_dicho_decroissant(8, t1) == 2
assert recherche_dicho_decroissant(10, t1) == 0
assert recherche_dicho_decroissant(0, t1) == 10
assert recherche_dicho_decroissant(4.5, t1) == None
print("Test unitaires réussis pour l'automatisme 13 : recherche_dicho_decroissant et est_decroissant")

Automatisme 14

def decimal_vers_IEE754(x, taille_exposant, taille_mantisse):
    #print("détermination du signe")
    if x > 0:
        print("Bit de signe  : 0")
    elif x <0:
        print("Bit de signe : 1")
    else:
        print("O valeur particulière")
    if x != 0:
        #print("détermination de l'exposant")
        exposant = 0
        while int(x) >= 1:
            x = x / 2
            exposant = exposant + 1
        while int(x) == 0:
            x = x * 2
            exposant = exposant - 1           
        decalage = 2 ** (taille_exposant - 1) - 1
        print("Exposant en décimal : ", exposant)
        print(f"Exposant décalé  de  + {decalage} : ", exposant + decalage)
        print(f"Exposant décalé de + {decalage}  : codage binaire sur 11 bits : ", bin(exposant + decalage).lstrip('0b').zfill(taille_exposant))
        #print("détermination des bits de mantisse")
        x = x - 1
        nbits = 0
        mantisse = []
        while nbits < taille_mantisse:
            x = x * 2
            partie_entiere = int(x)
            mantisse.append(str(partie_entiere))
            if partie_entiere == 1:
                x = x - partie_entiere
            nbits = nbits + 1
        print("Mantisse : ", ''.join(mantisse))

Automatisme 15

On considère une formule booléenne form des variables booléennes a et b dont voici la table de vérité.

a b form
True True False
False True True
True False True
False False False

Quelle est cette formule booléenne ?

Automatisme 16

Pouvez-vous deviner ce qui va se passer si on exécute le code ci-dessous ? Vérifiez. Explication ?

def boucle1():
    x = 1
    h = 1
    c = 0
    while x < 2:
        h = h / 2
        x = x + h
        c = c + 1
    return x == 2, c

boucle1()

Automatisme 17 (banque d’épreuve pratique 2021)

Écrire une fonction recherche qui prend en paramètres elt un nombre entier et tab un tableau de nombres entiers, et qui renvoie l’indice de la première occurrence de elt dans tab si elt est dans tab et -1 sinon.

Exemples :

>>> recherche(1, [2, 3, 4])
-1
>>> recherche(1, [10, 12, 1, 56])
2
>>> recherche(50, [1, 50, 1])
1
>>> recherche(15, [8, 9, 10, 15])
3

Automatisme 18 (banque d’épreuve pratique 2021)

Écrire une fonction maxi qui prend en paramètre une liste tab de nombres entiers et renvoie un couple donnant le plus grand élément de cette liste, ainsi que l’indice de la première apparition de ce maximum dans la liste.

Exemple :

>>> maxi([1,5,6,9,1,2,3,7,9,8])
(9,3)

Automatisme 19 (banque d’épreuve pratique 2021)

On considère la fonction insere ci-dessous qui prend en argument un entier a et un tableau tab d’entiers triés par ordre croissant. Cette fonction insère la valeur a dans le tableau et renvoie le nouveau tableau. Les tableaux seront représentés sous la forme de listes python.

Compléter la fonction insere ci-dessous.

def insere(a, tab):
    l = list(tab) #l contient les mêmes éléments que tab
    l.append(a)
    i = "à compléter"
    while i >= 0 and a < "à compléter" : 
      l[i+1] = "à compléter"
      l[i] = a
      i = "à compléter"
    return l

assert insere(3,[1,2,4,5]) == [1, 2, 3, 4, 5]
assert insere(10,[1,2,7,12,14,25]) == [1, 2, 7, 10, 12, 14, 25]
assert insere(1,[2,3,4]) == [1,2,3,4]
print('Tests réussis')

Automatisme 20 (banque d’épreuve pratique 2021)

Compléter sous Python la fonction suivante en respectant la spécification.

def dichotomie(tab, x):
    """
        tab : tableau d’entiers trié dans l’ordre croissant
        x : nombre entier
        La fonction renvoie True si tab contient x et False sinon
    """

    debut = 0 
    fin = len(tab) - 1
    while debut <= fin:
        m = "à compléter"
        if x == tab[m]:
            return "à compléter"
        if x > tab[m]:
            debut = m + 1
        else:
             fin = "à compléter"			
    return "à compléter"

assert dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28) == True
assert dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27) == False
print('Tests réussis')

Automatisme 21 (banque d’épreuve pratique 2021)

Écrire une fonction tri_selection qui prend en paramètre un tableau tab de nombres entiers et qui renvoie le tableau trié par ordre croissant.

On utilisera l’algorithme suivant :

Exemples de postconditions :

>>> assert tri_selection([1,52,6,-9,12]) == [-9, 1, 6, 12, 52]
>>> assert tri_selection([]) == []
>>> assert tri_selection([1, 4, 8]) == [1, 4, 8]
>>> assert tri_selection([8, 4, 1]) == [1, 4, 8]

Automatisme 22 (banque d’épreuve pratique 2021)

Un mot palindrome peut se lire de la même façon de gauche à droite ou de droite à gauche : bob, radar, et non sont des mots palindromes.

De même certains nombres sont eux aussi des palindromes : 33, 121, 345543.

L’objectif de cet exercice est d’obtenir un programme Python permettant de tester si un nombre est un nombre palindrome.

Pour remplir cette tâche, on vous demande de compléter le code des trois fonctions ci- dessous sachant que la fonction est_nbre_palindrome s’appuiera sur la fonction est_palindrome qui elle-même s’appuiera sur la fonction inverse_chaine.

La fonction inverse_chaine inverse l’ordre des caractères d’une chaîne de caractères chaine et renvoie la chaîne inversée. La fonction est_palindrome teste si une chaine de caractères chaine est un palindrome. Elle renvoie True si c’est le cas et False sinon. Cette fonction s’appuie sur la fonction précédente. La fonction est_nbre_palindrome teste si un nombre nbre est un palindrome. Elle renvoie True si c’est le cas et False sinon. Cette fonction s’appuie sur la fonction précédente.

Compléter le code des trois fonctions ci-dessous.

def inverse_chaine(chaine):
    result = "à compléter"
    for caractere in chaine:
       result = "à compléter"
    return result

def est_palindrome(chaine):
    inverse = inverse_chaine(chaine)
    return "à compléter"
    
def est_nbre_palindrome(nbre):
    chaine = "à compléter"
    return est_palindrome(chaine)

assert inverse_chaine('bac') == 'cab'
assert est_palindrome('NSI') == False
assert est_palindrome('ISN-NSI') == True
assert est_nbre_palindrome(214312) == False
assert est_nbre_palindrome(213312) == True
print("Tests réussis")

Automatisme 23 (banque d’épreuve pratique 2021)

Compléter la fonction separe ci-dessous qui prend en argument un tableau tab dont les éléments sont des 0 et des 1 et qui sépare les 0 des 1 en plaçant les 0 en début de tableau et les 1 à la suite.

def separe(tab):
    i = 0
    j = "à compléter"
    while i < j :
        if tab[i] == 0 :
            i = "à compléter"
        else :
            tab[i], tab[j] = "à compléter"
            j = "à compléter"
    return tab

assert separe([1, 0, 1, 0, 1, 0, 1, 0]) == [0, 0, 0, 0, 1, 1, 1, 1]
assert separe([1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0]) == [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
print("Tests réussis")

Automatisme 24 (banque d’épreuve pratique 2021)

Écrire une fonction indice_du_min qui prend en paramètre un tableau de nombres non trié tab, et qui renvoie l’indice de la première occurrence du minimum de ce tableau. Les tableaux seront représentés sous forme de liste Python.

Exemples :

>>> indice_du_min([5])
0
>>> indice_du_min([2, 4, 1])
2
>>> indice_du_min([5, 3, 2, 2, 4])
2

Automatisme 25 : traitement de données en tables

Télécharger l’archive avec le code source à compléter et le fichier eleves.csv. Un corrigé est ici.

#!/usr/bin/env python

"""Consigne : compléter au niveau des  à "compléter"
les fonctions :
    
    1)  moyenne_table
    2) enreg_avec_recompense
    3)  generer_table_recompenses
    4) decompte_recompenses
    5) clef_tri_moyenne_decroissant
    6) clef_tri_alphabetique_croissant_moyenne_decroissant
    
    Chaque fonction est accompagné d'un test unitaire => pour tester, 
    désactiver les commentaires dans le programme principal à partir de la ligne 151
    Pour les tris il faut aussi compléter le programme principal en lignes 167 et 171
"""

import csv

#Import / Export d'un tel fichier CSV ver la représentation d'une tble en Python (tableau de dictionnaires)
def lecture_csv(fichier, delimiteur):
    """
    Paramètre : un chemin vers un fichier CSV
    Valeur renvoyée : un tableau de dictionnaires, extraction de la table contenue dans le fichier
    """
    f = open(fichier, mode = 'r', encoding = 'utf8', newline='')
    reader = csv.DictReader(f, delimiter = delimiteur)  #création de l'objet reader
    table = [dict(enregistrement) for enregistrement in reader]
    f.close()
    return table

def ecriture_csv(table, fichier, delimiteur):
    """
    Paramètre : 
        un chemin vers un fichier CSV
        une table comme tableau de dictionnaires partageant les mêmes clefs, de valeurs str
    Valeur renvoyée :
        None, écrit table dans fichier avec Dictriter du  module CSV 
    """
    g = open(fichier, mode = 'w', encoding = 'utf8', newline='')
    attributs = list(table[0].keys())
    writer = csv.DictWriter(g, delimiter = delimiteur, fieldnames = attributs) #création de l'objet writer
    writer.writeheader()   #écriture des attibuts
    for enregistrement in table:
        writer.writerow(enregistrement)  #écriture des enregistrements
    g.close()
    
def moyenne_table(table_eleves) :
    """Paramètre : table_eleves est une représentation de la table extraite de eleves.csv
        sous forme de tableau de dictionnaires. Attention les attributs 'moyenne' sont de 
        type 'str'
    Valeur renvoyée : un flottant représentant la moyenne de tous les élèves
    de la table arrondie à 2 chiffres après la virgule
    """
    somme = 0
    compteur = 0
    for enreg in table_eleves:
        "à compléter"
        "à compléter"
    return round(somme / compteur, 2)

def test_moyenne_table():
    assert moyenne_table(table_eleves) == 11.46
    print("Test unitaire de moyenne_table réussi")
    
def enreg_avec_recompense(enreg):
    """
    Paramètre : enreg un dictionnaire de clefs 'prénom', 'nom', 'moyenne' 
                Attention toutes les clefs ont des valeurs de type str
    Valeur renvoyée : extension du dictionnaire avec une nouvelle clef
    'récompense' de valeurs s :
            'insuffisant' si moyenne < 8
            'médiocre' si 8 <= moyenne < 10
            'passable' si 10 <= moyenne < 12
            'encouragements' si  12 <= moyenne < 14
            'compliments' si   14 <= moyenne < 16
            'félicitations' si moyenne > 16
    """
    copie = { clef : valeur for clef, valeur in enreg.items() }
    m = "à compléter"
    if m < 8:
        copie['récompense'] = 'insuffisant'
    elif "à compléter":
        copie['récompense'] = 'médiocre'
    elif "à compléter":
        copie['récompense'] = 'passable'
    elif "à compléter":
        copie['récompense'] = 'encouragements'
    elif "à compléter":
        copie['récompense'] = 'compliments'
    else:
        copie['récompense'] = 'félicitations'
    return copie


def generer_table_recompenses(table_eleves):
    """Paramètre : table_eleves est une représentation de la table extraite de eleves.csv
        sous forme de tableau de dictionnaires
    Valeur renvoyée : une extension de table_eleves avec un nouvel attribut 'récompense'
    chaque nouvel enregistrement est généré par enreg_avec_recompense
    """
    table_recompenses = "à compléter"  
    return table_recompenses

def test_generer_table_recompenses():
    """Test unitaires de generer_table_recompenses"""
    table_recompenses = generer_table_recompenses(table_eleves)
    assert table_recompenses[0] == {'prénom': 'Zoé', 'nom': 'Collin',
                                    'moyenne': '19', 'récompense': 'félicitations'}
    assert table_recompenses[8] == {'prénom': 'Roland', 'nom': 'Joly', 
                                    'moyenne': '8', 'récompense': 'médiocre'}
    print("Test unitaires de generer_table_recompenses réussis")
    
def decompte_recompenses(table_recompenses):
    """Paramètre : table_recompenses  est une représentation de la table renvoyée 
                    par generer_table_recompenses. 
    Valeur renvoyée : un dictionnaire avec le décompte de chaque récompense
    """
    decompte = dict()
    for enreg in table_recompenses:
        "à compléter"
        "à compléter"
        "à compléter"
        "à compléter"
    return decompte

def test_decompte_recompenses():
    """Test unitaires de decompte_recompenses"""
    decompte = decompte_recompenses(table_recompenses)
    assert decompte == {'félicitations': 89,
                         'médiocre': 77,
                         'compliments': 95,
                         'insuffisant': 86,
                         'passable': 81,
                         'encouragements': 72}
    print("Test unitaires de decompte_recompenses réussis")
    
    
     
def clef_tri_moyenne_decroissant(enreg):
    """Clef de tri par moyenne décroissante
    Attention la valeur de l'attribut 'moyenne' de enreg est de type str"""
    return "à compléter"

def clef_tri_alphabetique_croissant_moyenne_decroissant(enreg):
    """Clef de tri par moyenne décroissante
    Attention la valeur de l'attribut 'moyenne' de enreg est de type str"""
    return "à compléter"
    

#Programme principal
table_eleves = lecture_csv('eleves.csv', ',')
#Décommenter lorsque moyenne_table est complétée
#test_moyenne_table()

#Décommenter lorsque generer_table_recompenses est complétée
#table_recompenses = generer_table_recompenses(table_eleves)
#test_generer_table_recompenses()

#Décommenter lorsque decompte_recompenses est complétée
#test_decompte_recompenses()

#Décommenter e lorsque clef_tri_moyenne_decroissant terminée
#table_recompenses = generer_table_recompenses(table_eleves)

#Ecrire une instruction qui permet de trier  table_recompenses dans l'ordre décroissant des moyennes
#table_tri1 = "à compléter"

#Ecrire une instruction qui permet de trier  table_recompenses :
#d'abord dans l'ordre alphabétique croissant puis dans l'ordre décroissant des moyennes
#table_tri2 = "à compléter"