Aller au contenu

Révisions

Consignes

Pour récupérer les fichiers du tp, connectez-vous au site de la vie scolaire. Une archive vous a été envoyée, contenant les documents utiles pour le tp. Le fichier tp_template.py contient les codes du tp prétapés à compléter. Le fichier tp_test.py contient les différentes fonctions de test que les fonctons que vous écrivez doivent passer avec succès.

Vous sauvegarderez ces fichiers dans votre répertoire personnel, avec un chemin de la forme :

NSI/Chapitre x - nom du chapitre/TP/TP1 - nom du tp/

et vous renommerez le fichier tp_templates.py en tp_nom_prénom.py.

Ainsi pour ce premier TP votre répertoire de travail ressemblera à :

├── NSI
│   └── Chapitre 1 - Récursivité
│       └── TP
│           └── TP1 - Révisions
│               ├── 1 - Révisions.zip
│               ├── tp_sujet.pdf
│               ├── tp_template.py
│               └── tp_tests.py

É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 27 26 25 24 23 22 21 20 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

Nombre de bits d'un entier

Plus grand entier écrit avec k bits

Écrire une fonction encadre qui étant donné un nombre entier k détermine la valeur du plus grand entier que l'on puisse écrire en base 2 avec k bits.

Indication. Le plus grand entier que l'on puisse écrire en base 2 sur 4 bits est \(\overline{1111}^2\), soit \(1 + 2 + 4 + 8 = 15\).

###
def testpy-undencadre():bksl-nl # Tests pour la fonction encadrebksl-nl maxs = [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]bksl-nl for i in range(len(maxs)):bksl-nl expected = maxs[i]bksl-nl assert encadre(i + 1) == expected, f"\ Le test suivant n'a pas été validé.\nEntrée : {i + 1}\nSortie : {encadre(i + 1)}\nAttendu : {expected}"bksl-nl return Truebksl-nlbksl-nl# from tp import encadrebksl-nltestpy-undencadre()bksl-nlbksl-nl 5/5

def encadre(k):bksl-nl """ int -> intbksl-nl Détermine le plus grand entier que l'on puisse écrire sur k bits """bksl-nl passbksl-nlbksl-nl

Nombre de bits d'un entier

À l'aide de la fonction encadre, écrire une fonction nombre_bits qui étant donné un entier n détermine le nombre k de bits présents dans l'écriture en base 2 du nombre n. On ne se souciera pas de l'efficacité de la fonction nombre_bits.

Indication. Le nombre de bits k recherché est le plus petit nombre tel que n <= encadre(k).

###
import mathbksl-nldef testpy-undnombrepy-undbits():bksl-nl # Tests pour la fonction nombrepy-undbitsbksl-nl for i in range(1, 1024):bksl-nl expected = int(math.log2(i)) + 1bksl-nl assert nombrepy-undbits(i) == expected, f"\ Le test suivant n'a pas été validé.\nEntrée : {i}\nSortie : {nombrepy-undbits(i)}\nAttendu : {expected}"bksl-nl return Truebksl-nlbksl-nl# from tp import nombrepy-undbitsbksl-nltestpy-undnombrepy-undbits()bksl-nlbksl-nl 5/5

def nombrepy-undbits(n):bksl-nl """ int -> intbksl-nl Détermine le nombre de bits de n dans son écriture en base 2 """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

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

Documents