Entraînement pour le devoir surveillé 4⚓︎
Exercice 1
On souhaite faire une fonction qui renvoie la deuxième plus grande valeur, appelée deuxième maximum, d'un tableau d'entiers.
Si le maximum a plusieurs occurrences dans le tableau, alors le deuxième maximum est égal au maximum.
S'il y a moins de deux valeurs dans le tableau, il n'y a pas de deuxième maximum.
valeurs1 = [5, 7, 3, 14, 25, 11, 19, 1]
valeurs2 = [16, 4, 6, 16, 3]
valeurs3 = [9]
- Dans le tableau
valeurs1, le maximum est 25 et le deuxième maximum est 19. - Dans le tableau
valeurs2, le maximum est 16 et le deuxième maximum est également 16. - Dans le tableau
valeurs3, il n'y a pas de deuxième maximum.
Écrire le code de la fonction deuxieme_max qui prend en paramètre un tableau d'entiers et qui renvoie la deuxième plus grande valeur du tableau.
>>> deuxieme_max([5, 7, 3, 14, 25, 11, 19, 1])
19
>>> deuxieme_max([16, 4, 6, 16, 3])
16
>>> deuxieme_max([9]) # None ne s'affiche pas dans le terminal
>>>
Indications
Indication 1
Il faut une variable pour le maximum et une autre pour le deuxième maximum.
Puisqu'il peut ne pas y avoir de deuxième maximum, ni de maximum, on commence par initialiser ces deux variables avec None.
Indication 2
Lors du parcours du tableau, il y a essentiellement 3 cas possibles :
-
Soit on n'a pas encore vu de maximum, soit la nouvelle valeur est plus grande que le maximum actuel.
-
Soit on n'a pas encore vu de deuxième maximum, soit la nouvelle valeur est plus grande que le deuxième maximum.
-
Soit la nouvelle valeur est inférieure au deuxième maximum.
Indication 3
Lorsqu'on voit un nouveau maximum, l'ancien maximum devient le nouveau deuxième maximum.
Contraintes
Il est interdit d'utiliser max, sort ou sorted.
# Tests (insensible à la casse)(Ctrl+I)
Exercice 2
On souhaite écrire une fonction qui compte le nombre de A qu'il y a dans des mots de la forme "AAAAA....AAABBB....BBBBBBB", c'est-à-dire composés par une suite de A (éventuellement aucun) puis une suite de B (éventuellement aucun).
Certains des mots qui seront étudiés seront très très long (plusieurs milliards de milliards de lettres). Il faut donc trouver un moyen astucieux de compter les A.
Nous allons utiliser la dichotomie. L'idée c'est que nous allons chercher la position du dernier A par dichotomie.
Pour l'instant nous supposons qu'il y a au moins un A. Nous allons utiliser 2 variables, g et d, tels que si on note i l'indice du dernier A, alors g <= i < d. L'indice g correspond donc à un A et d n'est pas l'indice d'un A (il peut être en dehors du mot).
Il y a 2 cas :
# On a mot[m] == "A"
mot = "...AAAAAAAAAAABBBBBB..."
↑ ↑ ↑
g m d
# On peut donc faire avancer g
mot = "...AAAAAAAAAAABBBBBB..."
↑ ↑
g d
# On a mot[m] == "B"
mot = "...AAAAAABBBBBBBBBBB..."
↑ ↑ ↑
g m d
# On peut donc faire reculer d
mot = "...AAAAAABBBBBBBBBBB..."
↑ ↑
g d
On s'arrête lorsque g et d se suivent :
mot = "...AAAAAABBBBBBBBBBB..."
↑↑
gd
S'il n'y a pas de A, alors on peut répondre 0 en regardant juste le premier symbole du mot.
Écrire le code de la fonction compte_les_a qui prend en paramètre un mot non-vide composé par une suite de A puis une suite de B et qui renvoie le nombre de A dans ce mot.
>>> compte_les_a("BBBBBB")
0
>>> compte_les_a("AAABBBBBB")
3
>>> compte_les_a("A"*147 + "B"*981)
147
Indications
Indication 1
Si le premier symbole est un B, alors il n'y a pas de A.
Indication 2
Au début, pour s'assurer que d n'est pas sur un A, il faut qu'il soit égal à la longueur du mot, pour correspondre au premier indice qui sort du mot.
Indication 3
Lorsqu'on voit un A en m, il faut faire avancer g mais pas au dela de m, parce qu'on ne sait pas ce qu'il y a en m+1.
De même lorsqu'on fait reculer d, il ne faut pas aller avant m car on ne sait pas ce qu'il y a en m-1.
Indication 4
À la fin, la différence entre g et d doit être exactement de 1.
Indication 5
Une fois le dernier A trouvé, il faut en déduire le nombre de A.
S'il y a un seul A, alors g=0 et d=1.
S'il y a 2 A, alors g=1 et d=2.
...
Contrainte
Les mots pouvant être très très long, dans les tests secrets, le nombre de lectures du mot est limité à 500, même s'il y a des milliards de milliards de lettres.
# Tests (insensible à la casse)(Ctrl+I)
# Tests (insensible à la casse)(Ctrl+I)
D'autres exercices pour s'entraîner
Vous pouvez aussi aller regarder ces exercices :
- Le bon enclos : un exercice sur les données en table.
- Concours de l'Eurovision : un exercice sur les dictionnaires.
- Recherche dichotomique (booléen) : recherche dichotomique de base.
- Recherche dichotomique (indice) : recherche dichotomique de base.
- Sommet d'un tableau unimodal : un autre exercice sur la dichotomie.
- Indice d'une panne : un autre exercice sur la dichotomie. Attention, il est plus difficile parce qu'il n'y a pas de code à trous.
# Tests(insensible à la casse)(Ctrl+I)