Révisions

Écriture binaire¶

Dans la mémoire de l'ordinateur, toutes les données (nombres, chaînes de caractères, mais aussi images, son…) sont stockées en utilisant uniquement des \(0\) et des \(1\). Pour représenter un nombre dans la mémoire de l'ordinateur, on utilise donc son écriture dans la base 2.

On rappelle que si un nombre \(n\) s'écrit \(\overline{10110001}^2\) en base 2, alors cela veut dire que \(n = 177\). On peut utiliser le tableau ci-dessous pour présenter le calcul.

Écriture en base 2	1	0	1	1	0	0	0	1
Puissances de 2	2⁷	2⁶	2⁵	2⁴	2³	2²	2¹	2⁰	Total
Termes à ajouter	128	0	32	16	0	0	0	1	177

On remarquera que dans cette convention d'écriture, le bit de poids fort (associé à \(2^7\)) est le bit le plus à gauche dans l'écriture du nombre et que le bit de poids faible (aussi appelé bit de parité) est le bit le plus à droite dans l'écriture du nombre. On utilisera cette convention dans tous les exercices.

Déterminer l'écriture en base 2 des entiers compris entre 0 (inclus) et 17 (exclu).

Parité d'un nombre écrit en base 2¶

Écrire une fonction est_pair qui étant donné un tableau bits non vide dont les éléments appartiennent à \(\{0 ; 1\}\) détermine si le nombre dont l'écriture en base 2 est donnée par le tableau bits est un nombre pair. La fonction est_pair renverra True si c'est le cas, et False sinon.

###

def testpy-undestpy-undpair():bksl-nl # Tests pour la fonction estpy-undpairbksl-nl for i in range(128):bksl-nl bits = list(map(int, list(bin(i)[2:])))bksl-nl expected = (i%2) == 0bksl-nl assert estpy-undpair(bits) == expected, f"Le test suivant n'a pas été validé.\nEntrée : {bits}\nSortie : {estpy-undpair(bits)}\nAttendu : {expected}"bksl-nl return Truebksl-nlbksl-nl# from tp import estpy-undpairbksl-nltestpy-undestpy-undpair()bksl-nlbksl-nl 5/5

def estpy-undpair(bits):bksl-nl """ [int] -> boolbksl-nl len(bits) > 0bksl-nl Détermine si le nombre dont l'écriture en base 2 est donnée par le tableau bits est pair. """bksl-nl passbksl-nlbksl-nl

Entier maximal à nombre de bits fixés¶

Écrire une fonction est_plus_grand_kbits qui prend en entrée un tableau bits non vide de taille k dont les éléments appartiennent à \(\{0 ; 1\}\) et qui détermine si le tableau correspond au plus grand nombre entier que l'on puisse écrire en base 2 sur k bits.

###

def testpy-undestpy-undpluspy-undgrandpy-undkbits():bksl-nl # Tests pour la fonction estpy-undpluspy-undgrandpy-undkbitsbksl-nl for i in range(1024):bksl-nl bits = list(map(int, list(bin(i)[2:])))bksl-nl reponse = estpy-undpluspy-undgrandpy-undkbits(bits) bksl-nl expected = all(bits)bksl-nl assert reponse == expected, f"Le test suivant n'a pas été validé.\nEntrée : {bits}\nSortie : {reponse}\nAttendu : {expected}"bksl-nl return Truebksl-nlbksl-nltestpy-undestpy-undpluspy-undgrandpy-undkbits()bksl-nlbksl-nl 5/5

def estpy-undpluspy-undgrandpy-undkbits(bits):bksl-nl """ [int] -> boolbksl-nl k = len(bits) > 0bksl-nl Détermine si le tableau bits correspond au plus grand entier que l'on puisse écrire sur k bits. """bksl-nl passbksl-nlbksl-nl

Base 2 vers base 10¶

Écrire une fonction base2_vers_base10 qui étant donné un tableau bits non vide dont les éléments appartiennent à \(\{0 ; 1\}\) renvoie le nombre dont l'écriture en base 2 est donnée par le tableau bits.

###

def testpy-undbase2py-undverspy-undbase10():bksl-nl # Tests pour la fonction base2py-undverspy-undbase10bksl-nl for i in range(128):bksl-nl bits = list(map(int, list(bin(i)[2:])))bksl-nl réponse = base2py-undverspy-undbase10(bits)bksl-nl assert réponse == i, message(bits, réponse, i)bksl-nl return Truebksl-nlbksl-nl# from tp import base2py-undverspy-undbase10bksl-nltestpy-undbase2py-undverspy-undbase10()bksl-nlbksl-nl 5/5

def base2py-undverspy-undbase10(bits):bksl-nl """ [int] -> intbksl-nl Détermine le nombre entier dont l'écriture en base 2 est donnée par le tableau bits """bksl-nl passbksl-nlbksl-nl

Algorithmes classiques¶

Recherche d'occurrences¶

Appartient¶

Écrire une fonction appartient qui étant donné un tableau (éventuellement vide) tab d'entiers et entier e, détermine si l'élément e est présent dans le tableau tab.

###

import randombksl-nldef testpy-undappartient():bksl-nl # Tests pour la fonction appartient bksl-nl assert appartient([], 0) == Falsebksl-nl assert appartient([0, 1, 2, 3], 0) == Truebksl-nl assert appartient([0, 1, 2, 3], 3) == Truebksl-nl assert appartient([0, 1, 2, 3], 4) == Falsebksl-nl return Truebksl-nlbksl-nl# from tp import appartientbksl-nltestpy-undappartient()bksl-nlbksl-nl 5/5

def appartient(tab, e):bksl-nl """ [int], int -> boolbksl-nl Détermine si l'élément e est présent dans le tableau tab. """bksl-nl passbksl-nlbksl-nl

Modifier la fonction appartient en une fonction appartient2 pour que celle-ci renvoie l'indice de la première occurrence de e dans tab si e est présent dans tab, -1 sinon.
Modifier le code de la fonction appartient2 en une fonction appartient3 pour que celle-ci renvoie l'indice de la dernière occurrence de e dans tab si e est présent dans tab, -1 sinon ?

Indice des occurrences¶

Écrire une fonction indices_occurrences qui étant donné un tableau (éventuellement vide) tab d'entiers de type quelconque et un entier e, détermine la liste des indices (rangés par ordre croissant) des éléments de tab qui sont égaux à e.

###

def testpy-undindicespy-undoccurrences():bksl-nl # Tests pour la fonction indicespy-undoccurrencesbksl-nl assert indicespy-undoccurrences([], 0) == []bksl-nl assert indicespy-undoccurrences([0, 1, 2, 3], 0) == [0]bksl-nl assert indicespy-undoccurrences([0, 1, 2, 0], 0) == [0, 3]bksl-nl assert indicespy-undoccurrences([0, 1, 2, 3], 2) == [2]bksl-nl assert indicespy-undoccurrences([0, 1, 2, 3], 4) == []bksl-nl return Truebksl-nlbksl-nl# from tp import indicespy-undoccurrencesbksl-nltestpy-undindicespy-undoccurrences()bksl-nlbksl-nl 5/5

def indicespy-undoccurrences(tab, e):bksl-nl """ [int], int -> [int]bksl-nl Détermine les indices des occurrences de e dans le tableau tab. """bksl-nl passbksl-nlbksl-nl

En déduire une fonction nombre_occurrences qui étant donné un tableau tab et un élément e renvoie le nombre d'occurrences de l'élément e dans le tableau tab. Écrire correctement la docstring de cette fonction ainsi que sa documentation.

Occurrences¶

Écrire une fonction occurrences qui étant donné un tableau tab renvoie un dictionnaire structuré de la manière suivante :

l'ensemble des clés du dictionnaire est l'ensemble des valeurs de tab ;
à chaque clé k est associée la liste des indices des occurrences de k dans tab

###

def testpy-undoccurrences():bksl-nl """ Tests pour la fonction occurrences """bksl-nl print("Tests de occurrences passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import occurrencesbksl-nl# testpy-undoccurrences()bksl-nlbksl-nl 5/5

def occurrences(tab):bksl-nl """ [int] -> { int:[int] }bksl-nl Associe à chaque valeur de tab la liste des indices des occurrences de cette valeur """bksl-nl passbksl-nlbksl-nl

Écrire la fonction occurrences en ne réalisant qu'un seul parcours de tab.

Recherche de maximum¶

Écrire une fonction maximum qui étant donné un tableau non vide tab d'entiers détermine la valeur du plus grand des éléments de ce tableau, ainsi que le premier indice pour lequel ce maximum est atteint.

###

import randombksl-nldef testpy-undmaximum():bksl-nl # Tests pour la fonction maximumbksl-nl assert maximum([1]) == (1, 0)bksl-nl assert maximum([1, 2, -1]) == (2, 1)bksl-nl assert maximum([1, 2, -1, 2]) == (2, 1)bksl-nl for py-und in range(1000):bksl-nl tab = [random.randint(-10, 10) for py-und in range(random.randint(1, 10))]bksl-nl expected = max(tab), tab.index(max(tab))bksl-nl assert maximum(tab) == expected, f"Le test suivant n'a pas été validé.\nEntrée : {tab }\nSortie : {maximum(tab)}\nAttendu : {expected}"bksl-nl return Truebksl-nlbksl-nl# from tp import maximumbksl-nltestpy-undmaximum()bksl-nlbksl-nl 5/5

def maximum(tab):bksl-nl """ [int], int -> int, intbksl-nl len(tab) > 0bksl-nl Détermine le maximum des éléments de tab, ainsi que le premier indice pour lequel ce maximum est atteint. """bksl-nl passbksl-nlbksl-nl

Modifier la fonction maximum en une fonction maximum2 afin que celle-ci renvoie la valeur du plus grand des éléments du tableau tab ainsi que le dernier indice pour lequel ce maximum est atteint.

Vérification de tri¶

Écrire une fonction est_trie_croissant qui étant donné un tableau tab, renvoie True si le tableau est trié par ordre croissant, False sinon.

###

def testpy-undestpy-undtriepy-undcroissant():bksl-nl """ Tests pour la fonction estpy-undtriepy-undcroissant """bksl-nl print("Tests de estpy-undtriepy-undcroissant passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import estpy-undtriepy-undcroissantbksl-nl# testpy-undestpy-undtriepy-undcroissant()bksl-nlbksl-nl 5/5

def estpy-undtriepy-undcroissant(tab):bksl-nl """ [int] -> boolbksl-nl Détermine si le tab est trié par ordre croissant """bksl-nl passbksl-nlbksl-nl

Documents¶

Mémento python