Aller au contenu

Ep 07

le document

l'algorithme

Issue de : 23-NSI-11⚓

EXERCICE 1⚓

On considĂšre dans cet exercice une reprĂ©sentation binaire d’un entier non signĂ© en tant que tableau de boolĂ©ens. Si tab = [True, False, True, False, False, True, True] est un tel tableau, alors l’entier qu’il reprĂ©sente est 26 + 24 + 21 + 20 = 83. Cette reprĂ©sentation consistant Ă  placer en premier le boolĂ©en indiquant la puissance la plus Ă©levĂ©e de 2 est dite big-endian ou grand-boutiste.

Écrire une fonction gb_vers_entier qui prend en paramĂštre un tel tableau et renvoie l’entier qu’il reprĂ©sente.

Exemple :

🐍 Script Python
>>> gb_vers_entier([])
0
>>> gb_vers_entier([True])
1
>>> gb_vers_entier([True, False, True,
False, False, True, True])
83
>>> gb_vers_entier([True, False, False, False,
False, False, True, False])
130

RĂ©ponse

Complétez le code ci-dessous

###
#Mettre votre code icibksl-nlbksl-nl

Solution

###
def gbpy-undverspy-undentier(tab):bksl-nl puissance = 0bksl-nl total = 0bksl-nl for i in range(len(tab)-1, -1, -1):bksl-nl total += tab[i]py-str(2py-strpy-strpuissance)bksl-nl puissance += 1bksl-nl return totalbksl-nlbksl-nltry:bksl-nl assert gbpy-undverspy-undentier([]) == 0bksl-nl assert gbpy-undverspy-undentier([True]) == 1bksl-nl assert gbpy-undverspy-undentier([True, False, True, False, False, True, True]) == 83bksl-nl assert gbpy-undverspy-undentier([True, False, False, False, False, False, True, False]) == 130bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le rĂ©sultat de votre fonction n\'est pas conforme đŸ€”')bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl

EXERCICE 2⚓

La fonction tri_insertion suivante prend en argument une liste tab et trie cette liste en utilisant la méthode du tri par insertion. Compléter cette fonction pour qu'elle réponde à la spécification demandée.

On rappelle le principe du tri par insertion : on considÚre les éléments à trier un par un, le premier élément constituant, à lui tout seul, une liste triée de longueur 1. On range ensuite le second élément pour constituer une liste triée de longueur 2, puis on range le troisiÚme élément pour avoir une liste triée de longueur 3 et ainsi de suite


A chaque étape, le premier élément de la sous-liste non triée est placé dans la sous-liste des éléments déjà triés de sorte que cette sous-liste demeure triée.

Le principe du tri par insertion est donc d'insérer à la n-iÚme itération, le n-iÚme élément à la bonne place.

🐍 Script Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def tri_insertion(tab):
    '''Trie le tableau tab par ordre croissant
    en appliquant l'algorithme de tri par insertion'''
    n = len(tab)
    for i in range(1, n):
        valeur_insertion = ... 
        # la variable j sert à déterminer 
        # oĂč placer la valeur Ă  ranger
        j = ... 
        # tant qu'on n'a pas trouvé la place de l'élément à
        # insérer on décale les valeurs du tableau vers la droite
        while j > ... and valeur_insertion < tab[...]: 
            tab[j] = tab[j-1]
            j = ... 
        tab[j] = ...
Exemple :
🐍 Script Python
>>> tab = [98, 12, 104, 23, 131, 9]
>>> tri_insertion(tab)
>>> tab
[9, 12, 23, 98, 104, 131]

RĂ©ponse

Complétez le code ci-dessous

###
def tripy-undinsertion(tab):bksl-nl '''Trie le tableau tab par ordre croissantbksl-nl en appliquant l'algorithme de tri par insertion'''bksl-nl n = len(tab)bksl-nl for i in range(1, n):bksl-nl valeurpy-undinsertion = ... bksl-nl # la variable j sert Ă  dĂ©terminer bksl-nl # oĂč placer la valeur Ă  rangerbksl-nl j = ... bksl-nl # tant qu'on n'a pas trouvĂ© la place de l'Ă©lĂ©ment Ă bksl-nl # insĂ©rer on dĂ©cale les valeurs du tableau vers la droitebksl-nl while j > ... and valeurpy-undinsertion < tab[...]: bksl-nl tab[j] = tab[j-1]bksl-nl j = ... bksl-nl tab[j] = ... bksl-nl

Solution

###
def tripy-undinsertion(tab):bksl-nl n = len(tab)bksl-nl for i in range(1, n):bksl-nl valeurpy-undinsertion = tab[i]bksl-nl # la variable j sert Ă  dĂ©terminer oĂč placer la valeur Ă  rangerbksl-nl j = ibksl-nl # tant qu'on a pas trouvĂ© la place de l'Ă©lĂ©ment Ă  insĂ©rerbksl-nl # on dĂ©cale les valeurs du tableau vers la droitebksl-nl while j > 0 and valeurpy-undinsertion < tab[j-1]:bksl-nl tab[j] = tab[j-1]bksl-nl j = j - 1bksl-nl tab[j] = valeurpy-undinsertionbksl-nlbksl-nltry:bksl-nl tab = [98, 12, 104, 23, 131, 9]bksl-nl tripy-undinsertion(tab)bksl-nl assert tab == [9, 12, 23, 98, 104, 131] bksl-nl print('Tout semble correct 👍')bksl-nlbksl-nlexcept AssertionError as asser:bksl-nl print('Le rĂ©sultat de votre fonction n\'est pas conforme đŸ€”')bksl-nlbksl-nl