Tickets gagnants
Épreuve blanche
Cet exercice est rédigé comme une épreuve pratique de NSI. À ce titre et afin de coller au maximum aux conditions d'examen, le corrigé n'est pas proposé.
Si vous réalisez cet exercice en classe, n'hésitez pas à contacter l'enseignant :
- si vous avez des questions
- ou afin de faire vérifier votre code à chaque question.
Bornes incluses
Dans tout cet exercice les bornes des intervalles étudiés seront incluses. Ainsi l'intervalle de nombres entiers allant de 5 à 9 contient les valeurs 5, 6, 7, 8 et 9.
Une plateforme de jeu en ligne lance un nouveau jeu de hasard. Ce jeu se déroule en deux temps :
- durant la semaine, le joueur achète tout d'abord un ticket virtuel sur la plateforme. Ce ticket contient deux nombres entiers
aetb(tous les deux compris entre \(0\) et \(10^9\)) qui constituent un intervalle. On garantit quea <= b; - en fin de semaine a lieu le tirage au sort du numéro gagnant
c(un nombre entier compris entre \(0\) et \(10^9\)).
Un ticket est considéré gagnant si le numéro tiré au sort est compris dans l'intervalle désigné par le ticket. Les valeurs de début et de fin de chaque intervalle sont incluses dans ce dernier. Par exemple :
- le numéro
7est compris dans l'intervalle(5, 9); - le numéro
7est compris dans l'intervalle(5, 7); - le numéro
7est compris dans l'intervalle(7, 9); - le numéro
7n'est pas compris dans l'intervalle(8, 9).
Un ticket n'est valable qu'une semaine.
1. Ticket gagnant ?
Écrire la fonction est_gagnant qui prend trois paramètres :
a: la valeur de début de l'intervalle d'un ticket ;b: la valeur de fin de l'intervalle d'un ticket ;c: la valeur du numéro choisi au hasard le vendredi soir.
Cette fonction renvoie le booléen indiquant si le ticket comprenant l'intervalle (a, b) « contient » le numéro gagnant c.
Exemples
>>> est_gagnant(5, 9, 7)
True
>>> est_gagnant(5, 7, 7)
True
>>> est_gagnant(7, 9, 7)
True
>>> est_gagnant(8, 9, 7)
False
2. Combien de tickets gagnants ?
Un joueur achète plusieurs tickets. Le numéro gagnant tiré au sort en fin de semaine est utilisé pour tous ses tickets. Il souhaite savoir combien de tickets gagnants il a achetés.
Un intervalle est représenté sous la forme d'un couple (a, b) dans lequel a est la valeur de début et b celle de fin.
Les différents intervalles correspondants aux tickets achetés par le joueur sont donnés dans une liste. Par exemple [(5, 10), (8, 17)] représente deux tickets : le premier avec l'intervalle (5, 10) et le second l'intervalle (8, 17).
Écrire la fonction nombre_gagnants qui prend deux paramètres :
tickets: une liste de couples d'entiers donnant les intervalles de chacun des tickets ;c: la valeur du numéro gagnant.
Cette fonction renvoie le nombre de tickets gagnants parmi ceux listés dans tickets.
Aide
La fonction est_gagnant de la question précédente est déjà importée dans cet éditeur. Vous pouvez directement l'utiliser.
Exemples
>>> tickets = [(5, 10), (8, 17)]
>>> nombre_gagnants(tickets, 4)
0
>>> nombre_gagnants(tickets, 9)
2
>>> nombre_gagnants(tickets, 12)
1
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
3. Réduction des intervalles
La plateforme de jeu en ligne assure que, chaque semaine, au moins un des tickets achetés est gagnant.
Pour ce faire, elle effectue le tirage au sort parmi l'ensemble des valeurs contenues dans les intervalles des ticket vendus.
Si par exemple les tickets vendus sont décrits par la liste [(5, 10), (8, 17), (20, 22)], le numéro gagnant doit être choisi dans les intervalles de la liste [(5, 17), (20, 22)]. En effet, les deux premiers intervalles (5, 10) et (8, 17) se « chevauchent ». Ils peuvent être regroupés en un unique intervalle « isolé » (5, 17). Le dernier intervalle est déjà « isolé » et reste inchangé.
La plateforme doit donc, connaissant l'ensemble des tickets vendus, déterminer les intervalles « isolés » correspondants.
Pour ce faire, elle utilise la démarche suivante (on garantit qu'au moins un ticket a été vendu) :
- on trie la liste des tickets. Cette action a pour effet de classer les tickets par ordre de valeurs de début croissantes. Si deux valeurs de début sont égales, le ticket dont la valeur de fin est la plus petite sera placé en avant l'autre ;
- on crée une liste vide
resultat; - on initialise deux variables
minietmaxiaux valeurs de début et de fin du premier intervalle ; - on parcourt l'ensemble des intervalles
(a, b): - si la valeur de début de l'intervalle lu est inférieure ou égale à la valeur
maxi:- on met à jour cette dernière en lui affectant la valeur la plus grande parmi la valeur de fin de l'intervalle lu et
maxi;
- on met à jour cette dernière en lui affectant la valeur la plus grande parmi la valeur de fin de l'intervalle lu et
- sinon :
- on ajoute à la liste
resultatle couple(mini, maxi);
- on ajoute à la liste
- en fin de boucle, on ajoute le dernier intervalle
(mini, maxi)à la listeresultat.
La fonction reduction prend en paramètres une liste de couples d'entiers intervalles contenant au moins un intervalle.
Cette fonction renvoie la liste des intervalles « isolés » triés dans l'ordre des valeurs de début croissantes.
La fonction proposée ne passe pas les tests et comporte des erreurs...
Corriger cette fonction. Les lignes à modifier sont indiquées par le commentaire # !.
Exemples
>>> intervalles = [(5, 10), (8, 17), (20, 22)]
>>> reduction(intervalles)
[(5, 17), (20, 22)]
>>> intervalles = [(5, 17), (20, 22)]
>>> reduction(intervalles)
[(5, 17), (20, 22)]
>>> intervalles = [(2, 30), (1, 2), (2, 2) ]
>>> reduction(intervalles)
[(1, 30)]
>>> tickets = [(1, 10), (2, 9)]
>>> reduction(intervalles)
[(1, 10)]
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
4. Tirage au sort de la valeur gagnante
La plateforme de jeu souhaite pour finir tirer au sort la valeur gagnante parmi les valeurs des intervalles isolés déterminés à la question précédente.
Pour ce faire elle procède en trois temps :
- elle dénombre le nombre de valeurs possibles sur l'ensemble des intervalles. On note
nb_valeursce total ; - elle choisit aléatoirement un rang compris entre
0(inclus) etnb_valeurs(exclu) ; - elle parcourt l'ensemble des intervalles jusqu'à ce que le rang choisi soit celui d'une des valeur de cet intervalle.
Considérons par exemple les intervalles [(5, 17), (20, 22)] :
- le nombre total de valeurs vaut
13 + 3 = 16; - on choisit un rang aléatoire entre
0(inclus) et16(exclu). On suppose que cette valeur estk = 14; - le premier intervalle ne contient pas la
14-ième valeur. En effet5 + 14 > 17. On passe à l'intervalle suivant et on considère que le rang vaut désormaisk = 14 - 13 = 1(le premier intervalle compte13valeurs) ; - le second intervalle contient la valeur cherchée. En effet
20 + 1 <= 22. Cette valeur vaut20 + 1 = 21.
Le choix du rang aléatoire est fait à l'aide de la fonction randrange du module random.
Cette fonction prend en paramètres deux entiers a et b (a <= b) et renvoie un entier aléatoire c tel que a <= c < b.
La fonction k_ieme, qu'il est demandé d'écrire, prend en paramètres une liste d'intervalles isolés ainsi que l'indice d'une valeur et renvoie la valeur d'indice k obtenue en parcourant successivement les différents intervalles. Ainsi k_ieme([(5, 17), (20, 22)], 14) renvoie 21.
Compléter les fonctions k_ieme et tirage_au_sort. Cette seconde fonction prend en paramètre une liste d'intervalle isolée et renvoie une valeur au hasard parmi ceux-ci en respectant la démarche expliquée plus haut.
Exemples
>>> k_ieme([(5, 17), (20, 22)], 0)
5
>>> k_ieme([(5, 17), (20, 22)], 1)
6
>>> k_ieme([(5, 17), (20, 22)], 12)
17
>>> k_ieme([(5, 17), (20, 22)], 13)
20
>>> k_ieme([(5, 17), (20, 22)], 14)
21
>>> k_ieme([(5, 17), (20, 22)], 15)
22
>>> tirage_au_sort([(5, 5)]) # une seule valeur possible -> résultat prévisible
5
# Tests (insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)