"},{"solution":""},{"text":">EXERCICE 2 (4 points) 
 
On considère un tableau d'entiers tab (type list dont les éléments sont des 0 ou des 
1). On se propose de trier ce tableau selon l'algorithme suivant : à chaque étape du tri, le tableau est constitué de trois zones consécutives, la première ne contenant que des 0, la seconde n'étant pas triée et la dernière ne contenant que des 1.  
 
Zone de 0  Zone non triée  Zone de 1 
 
Tant que la zone non triée n'est pas réduite à un seul élément, on regarde son premier élément : 
  si cet élément vaut 0, on considère qu'il appartient désormais à la zone ne contenant 
que des 0 ; 
  si cet élément vaut 1, il est échangé avec le dernier élément de la zone non triée et on 
considère alors qu’il appartient à la zone ne contenant que des 1. 
 
Dans tous les cas, la longueur de la zone non triée diminue de 1. 
 
   
  
 Recopier sous Python en la complétant la fonction tri suivante : 
 
def tri(tab): 
    #i est le premier indice de la zone non triee, j le dernier indice.  
    #Au debut, la zone non triee est le tableau entier. 
    i= ... 
    j= ... 
    while i != j : 
        if tab[i]== 0: 
            i= ... 
        else : 
            valeur = tab[j] 
            tab[j] = ... 
            ... 
            j= ... 
    ... 
 
Exemple : 
>>> tri([0,1,0,1,0,1,0,1,0]) 
[0, 0, 0, 0, 0, 1, 1, 1, 1] 
  
 "},{"edit":""},{"solution":""}],[{"text":"Programme : Récursivité et dichotomie","title":"Sujet n°3"},{"text":"EXERCICE 1 (4 points) 
 
Programmer la fonction multiplication, prenant en paramètres deux nombres entiers n1 et n2, et qui renvoie le produit de ces deux nombres.  
Les seules opérations autorisées sont l’addition et la soustraction.  
 
Exemples : 
>>> multiplication(3,5) 
15 
>>> multiplication(-4,-8) 
32 
>>> multiplication(-2,6) 
-12 
>>> multiplication(-2,0) 
0 
 
 
 "},{"edit":""},{"solution":""},{"text":";EXERCICE 2 (4 points) 
 
Recopier et compléter sous Python la fonction suivante en respectant la spécification. On ne recopiera pas les commentaires. 
 
def dichotomie(tab, x): 
    """ 
        tab : tableau d’entiers trié dans l’ordre croissant 
        x : nombre entier 
        La fonction renvoie True si tab contient x et False sinon 
    """ 
 
    debut = 0  
    fin = len(tab) - 1 
    while debut <= fin: 
        m = ... 
        if x == tab[m]: 
            return ... 
        if x > tab[m]: 
            debut = m + 1 
        else: 
             fin = ...       
    return ... 
 
Exemples : 
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28) 
True 
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27) 
False 
  
 "},{"edit":""},{"solution":""}],[{"text":"Programme : Liste et dichotomie","title":"Sujet n°4"},{"text":"EXERCICE 1 (4 points) 
 
Ecrire une fonction qui prend en paramètre un tableau d'entiers non vide et qui renvoie la moyenne de ces entiers. La fonction est spécifiée ci-après et doit passer les assertions fournies. 
 
def moyenne (tab): 
    ''' 
        moyenne(list) -> float 
        Entrée : un tableau non vide d'entiers 
        Sortie : nombre de type float  
        Correspondant à la moyenne des valeurs présentes dans le 
        tableau 
    '''       
         
assert moyenne([1]) == 1 
assert moyenne([1,2,3,4,5,6,7]) == 4 
assert moyenne([1,2]) == 1.5 
 "},{"edit":""},{"solution":""},{"text":">EXERCICE 2 (4 points) 
 
Le but de l'exercice est de compléter une fonction qui détermine si une valeur est présente dans un tableau de valeurs triées dans l'ordre croissant. 
L'algorithme traite le cas du tableau vide. 
L'algorithme est écrit pour que la recherche dichotomique ne se fasse que dans le cas où la valeur est comprise entre les valeurs extrêmes du tableau. 
On distingue les trois cas qui renvoient False en renvoyant False,1 , False,2 et False,3. 
Compléter l'algorithme de dichotomie donné ci-après. 
 
def dichotomie(tab, x): 
    """ 
        tab : tableau trié dans l’ordre croissant 
        x : nombre entier 
        La fonction renvoie True si tab contient x et False sinon 
    """ 
    # cas du tableau vide 
    if ...: 
        return False,1 
 
    # cas où x n'est pas compris entre les valeurs extrêmes 
    if (x < tab[0]) or ...: 
        return False,2 
  
      
    debut = 0 
    fin = len(tab) - 1 
    while debut <= fin: 
        m = ... 
        if x == tab[m]: 
            return ... 
        if x > tab[m]: 
            debut = m + 1 
        else: 
            fin = ...       
    return ... 
 
 
Exemples : 
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],28) 
True 
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],27) 
(False, 3) 
>>> dichotomie([15, 16, 18, 19, 23, 24, 28, 29, 31, 33],1) 
(False, 2) 
>>> dichotomie([],28) 
(False, 1) 
  
 "},{"edit":""},{"solution":""}],[{"text":"Programme : Représentation des nombres, liste et tris","title":"Sujet n°5"},{"text":"EXERCICE 1 (4 points) 
 
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 : 
 
def convertir(T): 
    """ 
    T est un tableau d'entiers, dont les éléments sont 0 ou 1 et 
    représentant un entier écrit en binaire. Renvoie l'écriture 
    décimale de l'entier positif dont la représentation binaire 
    est donnée par le tableau T 
    """ 
 
Exemple : 
>>> convertir([1, 0, 1, 0, 0, 1, 1]) 
83 
>>> convertir([1, 0, 0, 0, 0, 0, 1, 0]) 
130