Programmer une fonction renverse, prenant en paramètre une chaîne de caractères non vide mot et renvoie cette chaîne de caractères en ordre inverse.

Exemple :

>>> renverse("")
""
>>> renverse("abc")
"cba"
>>> renverse("informatique")
"euqitamrofni"

On s’intéresse à la suite d’entiers définie par :

• les deux premières valeurs sont égales à 1 ;
• ensuite, chaque valeur est obtenue en faisant la somme des deux valeurs qui la précèdent.

La troisième valeur est donc $1+1 = 2$, la quatrième est $1+2 = 3$, la cinquième est $2+3 = 5$, la sixième est $3 + 5 = 8$, et ainsi de suite.

Cette suite d’entiers est connue sous le nom de suite de Fibonacci.

Écrire en Python une fonction fibonacci qui prend en paramètre un entier n supposé strictement positif et qui renvoie le terme d’indice n de cette suite.

Exemples :

>>> fibonacci(1)
1
>>> fibonacci(2)
1
>>> fibonacci(25)
75025

Écrire une fonction ecriture_binaire_entier_positif qui prend en paramètre un entier positif n et renvoie une une chaine de caractère correspondant à l‘écriture binaire de n.

On rappelle que :

• l’écriture binaire de 25 est 11001 car $25 = 1 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0$ ;
• n % 2 vaut 0 ou 1 selon que n est pair ou impair ;
• n // 2 donne le quotient de la division euclidienne de n par 2.

Il est interdit dans cet exercice d’utiliser la fonction bin de Python.

Exemples :

>>> 5 % 2
1
>>> 5 // 2
2
>>> ecriture_binaire_entier_positif(0)
'0'
>>> ecriture_binaire_entier_positif(2)
'10'
>>> ecriture_binaire_entier_positif(105)
'1101001'

On rappelle que :

• le nombre $a^n$ est le nombre $a \times a \times a \times \dots \times a$, où le facteur $a$ apparaît $n$ fois,
• en langage Python, l’instruction t[-1] permet d’accéder au dernier élément du tableau t.

Dans cet exercice, l’opérateur ** et la fonction pow ne sont pas autorisés.

Programmer en langage Python une fonction liste_puissances qui prend en argument un nombre entier a, un entier strictement positif n et qui renvoie la liste de ses puissances $\rm{[a^1, a^2, ..., a^n]}$.

Programmer également une fonction liste_puisssances_borne qui prend en arguments un nombre entier a supérieur ou égal à 2 et un entier borne, et qui renvoie la liste de ses puissances, à l’exclusion de $\rm{a^0}$, strictement inférieures à borne.

Exemples :

>>> liste_puissances(3, 5)
[3, 9, 27, 81, 243]
>>> liste_puissances(-2, 4)
[-2, 4, -8, 16]
>>> liste_puissances_borne(2, 16)
[2, 4, 8]
>>> liste_puissances_borne(2, 17)
[2, 4, 8, 16]
>>> liste_puissances_borne(5, 5)
[]

Le nombre d’occurrences d’un caractère dans une chaîne de caractère est le nombre d’apparitions de ce caractère dans la chaîne.

Exemples :

• le nombre d’occurrences du caractère ‘o’ dans ‘bonjour’ est 2 ;
• le nombre d’occurrences du caractère ‘b’ dans ‘Bébé’ est 1 ;
• le nombre d’occurrences du caractère ‘B’ dans ‘Bébé’ est 1 ;
• le nombre d’occurrences du caractère ‘ ‘ dans ‘Hello world !’ est 2.

On cherche les occurrences des caractères dans une phrase. On souhaite stocker ces occurrences dans un dictionnaire dont les clefs seraient les caractères de la phrase et les valeurs l’occurrences de ces caractères.

Par exemple : avec la phrase 'Hello world !' le dictionnaire est le suivant :

{'H': 1,'e': 1,'l': 3,'o': 2,' ': 2,'w': 1,'r': 1,'d': 1,'!': 1}

L’ordre des clefs n’a pas d’importance.

Écrire une fonction nbr_occurrences prenant comme paramètre une chaîne de caractères chaine et renvoyant le dictionnaire des nombres d’occurrences des caractères de cette chaîne.

On considère la fonction eleves_du_mois prenant en paramètres eleves et notes deux tableaux non vides de même longueur, le premier contenant le nom des élèves et le second, des entiers positifs désignant leur note à un contrôle de sorte que eleves[i] a obtenu la note notes[i].

Cette fonction renvoie le couple constitué de la note maximale attribuée et des noms des élèves ayant obtenu cette note regroupés dans un tableau.

Ainsi, l’instruction eleves_du_mois(['a', 'b', 'c', 'd'], [15, 18, 12, 18]) renvoie le couple (18, ['b', 'd']).

Compléter le code suivant:

def eleves_du_mois(eleves, notes):
    note_maxi = 0
    meilleurs_eleves =  ...

    for i in range(...) :
        if notes[i] == ... :
            meilleurs_eleves.append(...)
        elif notes[i] > note_maxi:
            note_maxi = ...
            meilleurs_eleves = [...]

    return (note_maxi,meilleurs_eleves)

Exemples :

>>> eleves_nsi = ['a','b','c','d','e','f','g','h','i','j']
>>> notes_nsi = [30, 40, 80, 60, 58, 80, 75, 80, 60, 24]
>>> eleves_du_mois(eleves_nsi, notes_nsi)
(80, ['c', 'f', 'h'])

L'objectif de cet exercice est d'écrire deux fonctions récursives dec_to_bin et bin_to_dec assurant respectivement la conversion de l'écriture décimale d'un nombre entier vers son écriture en binaire et, réciproquement, la conversion de l'écriture en binaire d'un nombre vers son écriture décimale.

Dans cet exercice, on s'interdit l'usage des fonctions Python bin et int.

L'exemple suivante montre comment obtenir l'écriture en binaire du nombre 25 :

$$ \begin{array}{rcl} 25 & = & 2 \times 12 + 1 \\ &=& 2 \times (2 \times 6 + 0) + 1 \\ &=& 2 \times (2 \times (2 \times 3 + 0) + 0) + 1 \\ &=& 2 \times (2 \times (2 \times (2 \times 1 + 1) + 0) + 0) + 1 \\ &=& 2 \times (2 \times (2 \times (2 \times (2 \times 0 + 1) + 1) + 0) + 0) + 1 \\ &=& 1 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 \\ &=& \overline{11001}_2 \end{array}$$

L'écriture binaire de 25 est donc 11001.

On rappelle également que

• l'expression a // 2 calcule le quotient de la division euclidienne de a par 2 ;
• l'expression a % 2 calcule le reste dans la division euclidienne de a par 2.

On indique enfin qu'en Python si mot = "informatique", alors

• l'expression mot[-1] vaut 'e', c'est-à-dire le dernier caractère de la chaîne de caractères mot ;
• l'expression mot[:-1] vaut 'informatiqu' , c'est-à-dire l'ensemble de la chaîne de caractères mot privée de son dernier caractère.

Compléter, puis tester, le code des deux fonctions situées à la page suivante.

On précise que la fonction récursive dec_to_bin prend en paramètre un nombre entier et renvoie une chaîne de caractères contenant l'écriture en binaire du nombre passé en paramètre.

Exemple :

>>> dec_to_bin(25)
'11001'

La fonction récursive bin_to_dec prend en paramètre une chaîne de caractères représentant l'écriture d'un nombre en binaire et renvoie l'écriture décimale de ce nombre.

>>> bin_to_dec('101010')
42

def dec_to_bin(nb_dec):
    q, r = nb_dec // 2, nb_dec % 2
    if q == ...: 
        return ... 
    else:
        return dec_to_bin(...) + ... 

def bin_to_dec(nb_bin):
    if len(nb_bin) == 1:
        if ... == '0': 
            return 0
        else:
            return ... 
    else:
        if nb_bin[-1] == '0':
            bit_droit = 0
        else:
            ...
        return ... * bin_to_dec(nb_bin[:-1]) + ... 

On affecte à chaque lettre de l'alphabet un code selon le tableau ci-dessous :

A	B	C	D	E	F	G	H	I	J	K	L	M
1	2	3	4	5	6	7	8	9	10	11	12	13

N	O	P	Q	R	S	T	U	V	W	X	Y	Z
14	15	16	17	18	19	20	21	22	23	24	25	26

Cette table de correspondance est stockée dans un dictionnaire dico où les clés sont les lettres de l’alphabet et les valeurs les codes correspondants.

dico = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5, "F": 6,
        "G": 7, "H": 8, "I": 9, "J": 10, "K": 11, "L": 12,
        "M": 13, "N": 14, "O": 15, "P": 16, "Q": 17,
        "R": 18, "S": 19, "T": 20, "U": 21, "V": 22,
        "W": 23, "X": 24, "Y": 25, "Z": 26}

Pour un mot donné, on détermine d’une part son code alphabétique concaténé, obtenu par la juxtaposition des codes de chacun de ses caractères, et d’autre part, son code additionné, qui est la somme des codes de chacun de ses caractères.

Par ailleurs, on dit que ce mot est « parfait » si le code additionné divise le code concaténé.

Exemples :

• Pour le mot "PAUL", le code concaténé est la chaîne '1612112', soit l’entier 1612112. Son code additionné est l’entier 50 car 16 + 1 + 21 + 12 = 50. 50 ne divise pas l’entier 1612112 ; par conséquent, le mot "PAUL" n’est pas parfait.
• Pour le mot "ALAIN", le code concaténé est la chaîne '1121914', soit l’entier 1121914. Le code additionné est l’entier 37 car 1 + 12 + 1 + 9 + 14 = 37. 37 divise l’entier 1121914 ; par conséquent, le mot "ALAIN" est parfait.

Compléter la fonction codes_parfait située à la page suivante et qui prend en paramètre un mot en majuscule et renvoie un triplet constitué du code additionné, du code concaténé et d’un booléen indiquant si le mot est parfait ou non.

On rappelle que pour tester si un entier b divise un entier a, on utilise l’opérateur modulo a % b qui renvoie le reste de la division euclidienne de a par b. Si a % b vaut 0, alors b divise a.

def codes_parfait(mot):
    """Renvoie un triplet 
    (code_additionne, code_concatene, mot_est_parfait) où :
    - code_additionne est la somme des codes des lettres du mot ;
    - code_concatene est le code des lettres du mot concaténées ;
    - mot_est_parfait est un booléen indiquant si le mot est 
    parfait."""
    code_concatene = ""
    code_additionne = ... 
    for c in mot:
        code_concatene = code_concatene + ... 
        code_additionne = code_additionne + ... 
    code_concatene = int(code_concatene)
    mot_est_parfait = ... 
    return code_additionne, code_concatene, mot_est_parfait

Exemples :

>>> codes_parfait("PAUL")
(50, 1612112, False)
>>> codes_parfait("ALAIN")
(37, 1121914, True)

Écrire une fonction min_et_max qui prend en paramètre un tableau de nombres tab non vide, et qui renvoie la plus petite et la plus grande valeur du tableau sous la forme d’un dictionnaire à deux clés min et max.

Les tableaux seront représentés sous forme de liste Python.

L’utilisation des fonctions natives min, max et sorted, ainsi que la méthode sort n’est pas autorisée.

Exemples :

>>> min_et_max([0, 1, 4, 2, -2, 9, 3, 1, 7, 1])
{'min': -2, 'max': 9}
>>> min_et_max([0, 1, 2, 3])
{'min': 0, 'max': 3}
>>> min_et_max([3])
{'min': 3, 'max': 3}
>>> min_et_max([1, 3, 2, 1, 3])
{'min': 1, 'max': 3}
>>> min_et_max([-1, -1, -1, -1, -1])
{'min': -1, 'max': -1}

Écrire une fonction enumere qui prend en paramètre un tableau tab (type list) et renvoie un dictionnaire d dont les clés sont les éléments de tab avec pour valeur associée la liste des indices de l’élément dans le tableau tab.

Exemple :

>>> enumere([])
{}
>>> enumere([1, 2, 3])
{1: [0], 2: [1], 3: [2]}
>>> enumere([1, 1, 2, 3, 2, 1])
{1: [0, 1, 5], 2: [2, 4], 3: [3]}

Écrire une fonction ajoute_dictionnaires qui prend en paramètres deux dictionnaires d1 et d2 dont les clés sont des nombres et renvoie le dictionnaire d défini de la façon suivante :

• Les clés de d sont celles de d1 et celles de d2 réunies.
• Si une clé est présente dans les deux dictionnaires d1 et d2, sa valeur associée dans le dictionnaire d est la somme de ses valeurs dans les dictionnaires d1 et d2.
• Si une clé n’est présente que dans un des deux dictionnaires, sa valeur associée dans le dictionnaire d est la même que sa valeur dans le dictionnaire où elle est présente.

Exemples :

>>> ajoute_dictionnaires({1: 5, 2: 7}, {2: 9, 3: 11})
{1: 5, 2: 16, 3: 11}
>>> ajoute_dictionnaires({}, {2: 9, 3: 11})
{2: 9, 3: 11}
>>> ajoute_dictionnaires({1: 5, 2: 7}, {})
{1: 5, 2: 7}

Écrire une fonction a_doublon qui prend en paramètre un tableau trié de nombres dans l’ordre croissant et renvoie True si ce tableau contient au moins deux nombres identiques, False sinon.

Exemple :

>>> a_doublon([])
False
>>> a_doublon([1])
False
>>> a_doublon([1, 2, 4, 6, 6])
True
>>> a_doublon([2, 5, 7, 7, 7, 9])
True
>>> a_doublon([0, 2, 3])
False

On considère des tableaux de nombres dont tous les éléments sont présents exactement trois fois à la suite, sauf un élément qui est présent une unique fois et que l'on appelle « l'intrus ». Voici quelques exemples :

tab_a = [3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8, 5, 5, 5]
#l'intrus est 7

tab_b = [8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3]
#l'intrus est 8

tab_c = [5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8]
#l'intrus est 3

On remarque qu'avec de tels tableaux :

• pour les indices multiples de 3 situés strictement avant l'intrus, l'élément correspondant et son voisin de droite sont égaux,
• pour les indices multiples de 3 situés après l'intrus, l'élément correspondant et son voisin de droite - s'il existe - sont différents.

Ce que l'on peut observer ci-dessous en observant les valeurs des paires de voisins marquées par des caractères ^ :

[3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8]
 ^  ^     ^  ^     ^  ^     ^  ^     ^  ^     ^  ^
 0        3        6        9        12       15

Dans des tableaux comme celui ci-dessus, un algorithme récursif pour trouver l’intrus consiste alors à choisir un indice i multiple de 3 situé approximativement au milieu des indices parmi lesquels se trouve l’intrus.

Puis, en fonction des valeurs de l’élément d’indice i et de son voisin de droite, à appliquer récursivement l’algorithme à la moitié droite ou à la moitié gauche des indices parmi lesquels se trouve l’intrus.

Par exemple, si on s’intéresse à l’indice 12, on voit les valeurs 2 et 4 qui sont différentes : l’intrus est donc à gauche de l’indice 12 (indice 12 compris)

En revanche, si on s’intéresse à l’indice 3, on voit les valeurs 9 et 9 qui sont identiques : l’intrus est donc à droite des indices 3-4-5, donc à partir de l’indice 6.

Compléter la fonction récursive trouver_intrus proposée page suivante qui met en œuvre cet algorithme.

def trouver_intrus(tab, g, d):
    '''
    Renvoie la valeur de l'intrus situé entre les indices g et d 
    dans la liste tab où :
    tab vérifie les conditions de l'exercice,
    g et d sont des multiples de 3.
    '''
    if g == d:
        return ...

    else:
        nombre_de_triplets = (d - g) // ...
        indice = g + 3 * (nombre_de_triplets // 2)
        if ... :
            return ...
        else:
            return ...

Exemples :

>>> trouver_intrus([3, 3, 3, 9, 9, 9, 1, 1, 1, 7, 2, 2, 2, 4, 4, 4, 8, 8, 8], 0, 18)
7

>>> trouver_intrus([8, 5, 5, 5, 9, 9, 9, 18, 18, 18, 3, 3, 3], 0, 12)
8

>>> trouver_intrus([5, 5, 5, 1, 1, 1, 0, 0, 0, 6, 6, 6, 3, 8, 8, 8], 0, 15)
3