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. 

1
2
3
4
5
def est_pair(bits):
    """ [int] -> bool
    len(bits) > 0
    Détermine si le nombre dont l'écriture en base 2 est donnée par le tableau bits est pair. """
    pass

1
2
3
print(est_pair([0]))
print(est_pair([1]))
print(est_pair([1, 1, 0, 0, 1]))

True
False
False

Nombre de bits d'un entier

É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\).

À 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).

1
2
3
4
5
6
7
8
9
def encadre(k):
    """ int -> int
    Détermine le plus grand entier que l'on puisse écrire avec k bits. """
    pass 

def nombre_bits(n):
    """ int -> int
    Détermine le nombre de bits nécessaire à l'écriture de n en base 2. """
    pass

1
2
3
print(nombre_bits(1))
print(nombre_bits(15))
print(nombre_bits(16))

1
4
5

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. 

1
2
3
def est_plus_grand_kbits(bits):
    """ Détermine si le tableau bits correspond au plus  grand entier que l'on  puisse écrire sur k bits. """
    pass

1
2
3
print(est_plus_grand_kbits([1, 0, 1]))
print(est_plus_grand_kbits([1, 1, 0]))
print(est_plus_grand_kbits([1, 1, 1]))

False
False
True

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.

1
2
3
4
def base2_vers_base10(bits):
    """ [int] -> int
    Détermine le nombre dont l'écriture en base 2 est donnée par bits. """
    pass

1
2
3
4
print(base2_vers_base10([0]))
print(base2_vers_base10([1]))
print(base2_vers_base10([1, 0]))
print(base2_vers_base10([1, 0, 1, 0, 1, 0]))

0
1
2
42

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.

1
2
3
4
def appartient(tab, e):
    """ [int], int -> bool
    Détermine si l'élément e est présent dans le tableau tab. """
    pass

1
2
print(appartient([0, 1, 2, 3], 1))
print(appartient([0, 1, 2, 3], 4))

True
False

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).

1
2
3
4
def nombre_occurrences(tab, e ):
    """ [int], int, -> int
    Détermine le nombre d'éléments de tab qui sont égaux à e.  """
    pass

1
2
3
print(nombre_occurrences([0, 1, 2, 3, 1, 2, 1], 0))
print(nombre_occurrences([0, 1, 2, 3, 1, 2, 1], 2))
print(nombre_occurrences([0, 1, 2, 3, 1, 2, 1], 1))

1
2
3

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).

1
2
3
4
def indices_occurrences(tab, e):
    """ [int], int -> [int]
    Détermine les indices des occurrences de e dans le tableau tab. """
    pass

1
2
3
print(indices_occurrences([0, 1, 2, 3, 1, 2, 1], 0))
print(indices_occurrences([0, 1, 2, 3, 1, 2, 1], 2))
print(indices_occurrences([0, 1, 2, 3, 1, 2, 1], 1))

[0]
[2, 5]
[1, 4, 6]

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. 

1
2
3
4
5
def maximum(tab):
    """ [int] -> int, int
    len(tab) > 0
    Détermine le maximum des éléments de tab, ainsi que le premier indice pour lequel ce maximum est atteint. """
    pass

1
2
3
print(maximum([1]))
print(maximum([1, 2, -1]))
print(maximum([1, 2, -1, 2]))

(1, 0)
(2, 1)
(2, 1)