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

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

Nombre d'occurrences¶

Écrire une fonction nombre_occurrences qui étant donné un tableau (éventuellement vide) tab d'entiers et un entier e, détermine le nombre de fois où l'élément e est apparait dans le tableau tab (on appelle ce nombre le nombre d'occurrences de l'élément e).

###

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

def nombrepy-undoccurrences(tab, e):bksl-nl """ [int], int -> intbksl-nl Détermine le nombre d'éléments de tab qui sont égaux à e. """bksl-nl passbksl-nlbksl-nl

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.

Rappel. On pourra soit faire appel à la fonction nombre_occurrences pour initialiser le tableau d'indice des éléments égaux à e à la bonne taille, ou bien initialiser un tableau vide et ajouter les indices des éléments égaux à e au fur et à mesure à l'aide de l'instruction t.append(elem).

###

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

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

Tri par sélection¶

Écrire une fonction tri_selection qui prend en paramètre un tableau non vide tab de nombres entiers et qui trie ce tableau en place (c'est-à-dire que le tableau est modifié) par ordre croissant des valeurs. On utilisera l'algorithme suivant :

On parcourt le tableau de gauche à droite :
- on recherche le minimum du tableau entre cette position courante et la fin du tableau ;
- on échange alors les 2 valeurs

###

def testpy-undtripy-undselection():bksl-nl """ Tests pour la fonction tripy-undselection """bksl-nl data = [bksl-nl [[0], [0]],bksl-nl [[9,4,6,1], [1,4,6,9]],bksl-nl [[1, 52, 6, -9, 12], [-9, 1, 6, 12, 52]],bksl-nl [[1, 2], [1, 2]]bksl-nl ]bksl-nl for tab, tabpy-undtri in data:bksl-nl out = tripy-undselection(tab)bksl-nl assert out == tabpy-undtri, f"\ Le test suivant n'a pas été validé.\nEntrée : {tab}\nSortie : {out}\nAttendu : {tabpy-undtri}"bksl-nl print("Tests de tripy-undselection passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import tripy-undselectionbksl-nltestpy-undtripy-undselection()bksl-nlbksl-nl 5/5

def tripy-undselection(tab):bksl-nl """ [int] -> [int]bksl-nl len(tab) > 0bksl-nl Trie en place le tableau tab, à l'aide de l'algorithme du tri par sélection """bksl-nl passbksl-nlbksl-nl