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