Aller au contenu

Ep 11

‚Ė∂ T√©l√©charger le sujet en pdf.

EXERCICE 1‚öďÔłé

On modélise la représentation binaire d'un entier non signé par un tableau d'entiers dont les éléments sont 0 ou 1. Par exemple, le tableau [1, 0, 1, 0, 0, 1, 1] représente l'écriture binaire de l'entier dont l'écriture décimale est 2**6 + 2**4 + 2**1 + 2**0 = 83.

À l'aide d'un parcours séquentiel, écrire la fonction convertir répondant aux spécifications suivantes :

Réponse

Complétez le code ci-dessous

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



Solution

###
def convertir(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-nl



Exemple :

ūüźć Script Python
    >>> convertir([1, 0, 1, 0, 0, 1, 1])
    83
    >>> convertir([1, 0, 0, 0, 0, 0, 1, 0])
    130

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.

Exemple :

ūüźć Script Python
    >>> liste = [9, 5, 8, 4, 0, 2, 7, 1, 10, 3, 6]
    >>> tri_insertion(liste)
    >>> liste
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Réponse

Complétez le code ci-dessous

###
def tripy-undinsertion(tab):bksl-nl n = len(tab)bksl-nl for i in range(1, n):bksl-nl valeurpy-undinsertion = tab[...]bksl-nl # la variable j sert √† d√©terminer o√Ļ placer la valeur √† rangerbksl-nl j = ...bksl-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 > ... and valeurpy-undinsertion < tab[...]:bksl-nl tab[j] = tab[j-1]bksl-nl j = ...bksl-nl tab[j] = ...bksl-nlbksl-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-nl