Afficher une somme¶

1. On donne un entier \(\mathtt{s}\) et une liste L d’entiers. Ecrire une fonction estSomme(L, s) qui renvoie True si la somme des éléments de L vaut \(\mathtt{s}\) et False sinon.

   Voici quelques exemples de comportement de estSomme :

   [3, 2, 1], 6 -> True
   [3, 2, 1], 8 -> False
   

2. (Afficher une addition) Vous allez devoir coder une fonction d’affichage de messages comme celui-ci

   42 + 10 + 20 est égal à 72
   

   ou encore celui-là :

   42 + 10 + 20 est différent de 81
   

   Plus précisément, on vous donne

   • une liste L de trois entiers (nommés ci-dessous a, b et c juste pour la description de la question)
   • un entier \(s\)

   et vous devez écrire une fonction afficherSomme(L, s) qui devra obligatoirement utiliser la fonction estSomme et qui affichera le message

   a + b + c est égal à s
   

   si on a \(a+b+c=s\) et sinon qui affichera

   a + b + c est différent de s
   

   Bien sûr, dans ces messages, a, b, c et s doivent apparaître remplacés par leurs valeurs comme dans les exemples ci-dessus.

Indice de masse corporelle¶

1. Ecrire une fonction imc(p, t) qui à partir du poids p en kilogrammes et de la taille t en mètre d’un individu renvoie son indice de masse corporelle (IMC) et qui se calcule par la formule \(\mathtt{\ds\frac{m}{t^2}}\). Par exemple, si une personne mesure 1,74 m et pèse 65,5 kg, son IMC vaut environ 21,63.

2. Ecrire une fonction info_corpulence(p, t) qui à partir du poids p en kilogrammes et de la taille t en mètre d’un individu affiche une information sur la corpulence de la personne. La fonction calculera son IMC avec la fonction de la question précédente et indiquera les résultats suivants :

   • corpulence : anorexie si l’IMC est inférieure à 16,5
   • corpulence : maigreur si l’IMC est entre 16,5 et 18,5
   • corpulence : normale si l’IMC est entre 18,5 et 25
   • corpulence : surpoids si l’IMC est entre 25 et 30
   • corpulence : obésité modérée si l’IMC est entre 30 et 35
   • corpulence : obésité sévère si l’IMC est entre 35 et 40
   • corpulence : obésité maladive si l’IMC est supérieure à 40.

   Les intervalles seront de la forme \(\mathtt{[a, b[}\). Pour une personne qui mesure 1,74 m et pèse 65,5 kg, le message à afficher sera :

   corpulence : normale
   

Histoire de zéros¶

1. On donne une liste dont les éléments sont parmi 0 ou 1.

   Ecrire une fonction compterZeros(L) qui renvoie le nombre de zéros que contient la liste L. Par exemple, si L est la liste

   [0, 0, 1, 0, 1, 1, 1, 0, 1]
   

   la fonction doit renvoyer 4.

2. Utiliser la fonction compterZeros pour écrire une fonction estMajoritaire(L) qui renvoie

   • 0 si les zéros sont majoritaires dans L ou en nombre égal aux uns
   • 1 sinon.

   Avec l’exemple de la liste de la question précédente, la fonction devra renvoyer 1.

Somme des chiffres¶

On admet que la fonction dont le code est dans la cellule ci-dessous renvoie la somme des chiffres de l’entier n :

def sommeChiffres(n):
    return sum(map(int, str(n)))

1. Tester la fonction sommeChiffres(n) pour \(\mathtt{n=578679}\).

2. Ecrire une fonction afficherSomme(n) qui se contente d’afficher le message suivant

   La somme des chiffres du nombre n vaut s
   

   et où n est remplacé par la valeur de \(\mathtt{n}\) et où s est remplacé par la somme des chiffres de n. Par exemple, pour \(\mathtt{n=578679}\), l’appel sommeChiffres(n) affiche le message suivant :

   La somme des chiffres du nombre 578679 vaut 42
   

3. Écrire une fonction nb_dsum(N, s) qui renvoie le nombre d’entiers entre 0 et N (inclus) et dont la somme des chiffres vaut s. Appliquer à N valant 1 million et s = 42 (on trouvera 6062 entiers).

Entiers narcissiques¶

L’entier 153 est dit narcissique car il a \(\mathtt{p=3}\) chiffres et qu’il vaut la somme des cubes de ses chiffres (en base 10) :

\(1^p + 5^p + 3^p = 1^3 + 5^3 + 3^3 = 1+125+27 = 153\)

Plus généralement, on dit qu’un entier \(\mathtt{n>0}\), ayant \(\mathtt{p}\) chiffres, est narcissique si \(\mathtt{n}\) vaut la somme de ses chiffres élevés à la puissance \(\mathtt{p}\). Les chiffres sont les chiffres de l’écriture de \(\mathtt{n}\) en base 10.

On aura besoin de la fonction chiffres suivante :

def chiffres(n):
    return [int(c) for c in str(n)]

L = chiffres(2038)
print(L)

et qui affiche ici

[2, 0, 3, 8]

Autrement dit, \(\mathtt{chiffres(n)}\) renvoie la liste formée des entiers qui constituent les chiffres en base 10 de l’entier n.

1. Ecrire une fonction estNarcissique(n) qui renvoie True si l’entier n est narcissique et False sinon.
2. En utilisant la fonction précédente, afficher la liste de tous les entiers narcissiques avant un million.

Plus loin, plus proche¶

1. (Écart entre deux nombres) Ecrire une fonction ecart(a, b) qui renvoie l’écart entre les deux entiers a et b. Voici quelques exemples de comportement de la fonction ecart :

   82 , 42 -> 40
   1970 , 2038 -> 68
   42 , 42 -> 0
   42 , -10 -> 52
   

2. (Afficher l’écart) Ecrire une fonction afficherEcart(a, b) qui affiche le message :

   L'écart entre a et b est de e
   

   où a, b et e sont remplacées par les valeurs adaptées. Voici quelques exemples de comportement de la fonction afficherEcart :

   82 , 42 -> L'écart entre 82 et 42 est de 40
   1970 , 2038 -> L'écart entre 1970 et 2038 est de 68
   42 , 42 -> L'écart entre 42 et 42 est de 0
   42 , -10 -> L'écart entre 42 et -10 est de 52
   

3. (Proximité de 81) Ecrire une fonction plusProcheDe81(a, b) qui renvoie l’entier le plus proche de 81 parmi a ou b. La fonction devra obligatoirement utiliser la fonction ecart. Si les deux nombres sont à égale distance de 81, la fonction retournera indifféremment l’un ou l’autre. Voici quelques exemples de comportement de la fonction plusProcheDe81 :

   42 , 100 -> 100
   80 , 82 -> 82
   42 , 42 -> 42
   

Volume d’un cylindre¶

On utilisera \(\pi\) en l’important du module standard math.

1. Écrire une fonction aire_disque qui prend en paramètre un nombre r et renvoie l’aire du disque de rayon \(r\), définie par \(S=\pi r^2\). Tester la fonction pour un rayon valant 10.

2. On rappelle que le volume \(V\) d’un cylindre de hauteur \(h\) et de base un disque d’aire \(S\) vaut \(V=S\times h\).

   Écrire une fonction volume_cyl calculant le volume d’un cylindre et qui prend en paramètres

   • un nombre r désignant le rayon de la base
   • un nombre h désignant la hauteur du cylindre

   La fonction volume_cyl devra impérativement utiliser la fonction aire_disque. Tester la fonction pour un rayon valant 10 et une hauteur valant 2.

3. Cette question est indépendante de ce qui précède. Ecrire une fonction afficher_litres qui prend en paramètre un nombre v et qui se contente d’afficher le volume correspondant en litres sous la forme suivante :

   Volume : v litres
   

   Par exemple, l’appel afficher_litres(42.1) doit afficher exactement ceci :

   Volume : 42.1 litres
   

4. Votre réponse à cette question doit utiliser les fonctions définies dans les questions précédentes et doit tenir sur une seule ligne. Cette question ne demande pas de définir de nouvelle fonction.

   On dispose de deux cuves cylindriques remplies de jus de pommes :

   • le premier cylindre a une hauteur de 12 décimètres et une base de rayon de 4 décimètres,
   • le second cylindre a une hauteur de 8 décimètres et une base de rayon de 2 décimètres.

   Ecrire, en utilisant la fonction afficher_litres, un code qui affiche le volume de jus de pommes contenu au total dans les deux conteneurs, exprimé en litres. Pas de panique, il n’y a aucune conversion d’unités à faire puisque 1 décimètre cube correspond a un volume de 1 litre.

Calcul d’une durée¶

1. Écrire une fonction hms_to_s(h, m, s) qui retourne en secondes une durée exprimée en heures, minutes et secondes. Vérifier que 1h30m = 5400s et 3h20m15s = 12015s.
2. Écrire une fonction s_to_hms(sec) qui prend en paramètre une durée exprimée en secondes et la retourne exprimée en heures, minutes et secondes sous forme de liste [h, m, s]. Vérifier que s_to_hms(5400) retourne la liste [1, 30, 0], et que s_to_hms(12015) retourne la liste [3, 20, 15].
3. Écrire une fonction afficher_temps capable d’afficher une liste [h, m, s] sous la forme h heures m minutes et s secondes. Par exemple, afficher_temps([2, 42, 16]) affiche 2 heures 42 minutes et 16 secondes.
4. Sans définir de nouvelle fonction, écrire un code, tenant de préférence sur une seule ligne, qui affiche le temps écoulé comme à la question précédente entre 13h58m et 15h31m30s.

Arrondi au quart de point¶

Voici des exemples d’arrondi de note au quart de point le plus proche :

12.66     -->     12.75
12.9     -->     13
18.11     -->     18.0
8.5     -->     8.5
9.88     -->     10
13.25     -->     13.25

La fonction suivante prend en paramètre un nombre qui représente une note et renvoie la note qui est son arrondi au quart de point le plus proche :

def arrondir(note):
    pe=int(note)
    pf=note-pe
    if 0<=pf<0.125:
        r=0.
    elif 0.125<=pf<0.375:
        r=.25
    elif 0.375<=pf<0.625:
        r=.50
    elif 0.625<=pf<.875:
        r=.75
    else:
        r=1
    return pe+r

Cette fonction doit être présente dans le code une fois pour toutes et ne doit pas être modifiée. Il est attendu que vous appeliez la fonction arrondir quand vous en aurez besoin. Il N’est PAS attendu que vous fassiez des copier-coller du code ci-dessus pour servir de base à de nouvelles fonctions.

1. (Tester arrondir) Tester la fonction arrondir sur les notes suivantes, (une par une, sans les placer dans une liste) :

   12,66    12,9    18,11    8,5    9,88    13,25
   

2. (Calculer une moyenne) Cette question est indépendante de ce qui précède. Écrire une fonction moyenne qui calcule la moyenne d’une liste L de notes donnée en paramètre. Par exemple, si L est la liste [12.66, 12.9, 18.11, 8.5, 9.88, 13.25] alors, la moyenne vaut 12.55

3. Cette question est indépendante de ce qui précède. Écrire une fonction afficherNote qui affiche une note N sur 20 sous le format suivant :

   Votre note : N / 20
   

   suivi du message ADMIS ou NON ADMIS suivant que la note est supérieure ou égale à 10 ou pas. La fonction ne renvoie rien.

   Tester la fonction.

   Par exemple, afficherNote(12.55) doit afficher les deux lignes suivantes :

   Votre note :  12.55 / 20
   ADMIS
   

4. (Arrondir une liste de notes) Cette question utilise uniquement la fonction arrondir. Ecrire une fonction arrondirListe qui prend une liste de notes en paramètre et renvoie une nouvelle liste constituée des notes arrondies au quart de point le plus proche. Voici un exemple du comportement de la fonction

   [12.66, 12.9, 18.11, 8.5, 9.88, 13.25] ->
   [12.75, 13, 18.0, 8.5, 10, 13.25]
   

5. (Synthèse de tout ce qui précède) Cette question ne demande pas de définir de nouvelle fonction.

   Votre réponse à cette question doit utiliser les fonctions définies dans les questions précédentes.

   Soit une liste de notes, par exemple [12.66, 12.9, 18.11, 8.5, 9.88, 13.25]. Écrire un code qui

   • calcule la moyenne de la liste de notes arrondies au quart de point le plus proche
   • arrondit cette moyenne au quart de point le plus proche
   • affiche uniquement la moyenne arrondie ainsi que le message adéquat ADMIS ou NON ADMIS.

   Le code doit tenir sur une seule ligne.

   Par exemple, pour la liste ci-dessus, le code doit afficher :

   Votre note :  12.5 / 20
   ADMIS
   

Formule de Keith et Craver¶

La formule de Keith et Craver permet de déterminer le jour de la semaine (ie lundi, mardi, etc) correspondant à une date donnée (par exemple, le 14 juillet 1789 qui était un mardi).

Ci-dessous, en voici une implémentation sous forme de fonction Python. La fonction kc retourne sous forme d’entier (\(\texttt{1 = lundi, 2 = mardi, ..., 7 = dimanche}\)) le jour de la semaine correspondant à une date passée en paramètre comme suit : j (jour), m (mois) et a (année).

def kc(j, m, a):
    z = a - (m<3)
    return (j + 23*m//9 + 3 -2*(m>=3) + a + z//4 - z//100 + z//400)%7 +1

Voici un exemple d’utilisation :

def kc(j, m, a):
    z = a - (m<3)
    return (j + 23*m//9 + 3 -2*(m>=3) + a + z//4 - z//100 + z//400)%7 +1

# Test du jour de la semaine du 14 juillet 2018
print(kc(14, 7, 2018))

6

• Lignes 6 et 7 : le 14 juillet 2018 est un samedi (6e jour de la semaine).

Cette fonction doit être utilisée telle quelle, sans chercher à comprendre comment elle fonctionne. Vous devez réécrire (copier-coller) une fois et une seule cette fonction pour pouvoir l’utiliser par la suite mais il est inapproprié de copier/coller le corps de la fonction lignes 2 et 3 dans votre propre code. Il est seulement attendu d”utiliser la fonction kc.

1. Vérifier la validité des dates suivantes en calculant leur code entre 1 et 7 :

   • dimanche 13 janvier 2019
   • mardi 14 juillet 1789
   • dimanche 10 mai 1981
   • jeudi 16 juillet 1998
   • mardi 19 janvier 2038 (le bug de l’an 2038)

2. En utilisant un appel à la fonction kc, écrire une fonction est_vendredi13(m,a) qui renvoie True si le 13 du mois m et de l’année a est un vendredi (et False sinon). Combien y-a-t-il de vendredis 13 dans l’année 2018 ?

3. Ecrire et tester une fonction jour_semaine qui accepte en argument une liste date, supposée de la forme [jour,  mois,  année] et qui retourne le jour de la semaine correspondant en toutes lettres (ex : lundi, mardi, .., dimanche).

   Par exemple, jour_semaine([14, 7, 1789]) vaut la chaîne mardi.

   On pourra utiliser une liste JOURS_SEMAINE formée des noms des jours de la semaine.

Fractions¶

Dans cet exercice, une fraction sera représentée par une liste de 2 entiers positifs :

[numérateur, dénominateur].

Par exemple, la fraction \(\frac{22}{7}\) sera représentée par la liste [22, 7]. Plus généralement, la fraction \(\frac{a}{b}\) sera représentée par la liste [a, b].

1. Écrire une fonction aff qui affiche une fraction frac donnée en paramètre. Par exemple, aff([22,7]) affichera 22 / 7.

2. Écrire une fonction add(frac1, frac2) qui retourne la somme des fractions frac1 et frac2. On appliquera la formule suivante : \(\frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}\). Par exemple, add([1,3],[7,10]) retournera [31,30]. On ne cherchera pas à obtenir une fraction simplifiée (autrement dit une fraction irréductible).

3. Écrire une fonction harmonique(n) qui calcule la somme \(1+\frac{1}{2}+...+\frac{1}{n}\). Vérifier que harmonique(6) affiche 1764 / 720.

4. Écrire une fonction simplifier(frac) qui simplifie la fraction frac reçue en paramètre. Par exemple, simplifier([140, 100]) doit renvoyer [7,5]. On utilisera la fonction gcd importée du module standard math afin de simplifier la fraction.

   Si vous essayez de simplifier harmonique(12), vous allez constater que l’exécution va être extrêmement longue.

   Quitte à récrire légèrement le code de la fonction add, parvenir à accélérer le calcul de harmonique(12)

Le moins présent¶

On donne une liste L d’entiers et on demande de déterminer l’élément le moins présent de la liste L. Par exemple, si L est la liste :

[11, 12, 12, 11, 11, 10, 11, 12, 11, 10]

alors l’élément le moins présent est 10 (deux fois, les autres étant présents au moins trois fois). Si deux éléments sont aussi peu présents l’un que l’autre, l’élément à donner est celui qui apparaît le premier dans la liste. Par exemple, si L est la liste :

L=[13, 12, 10, 13, 11, 13, 12, 13, 11, 10]

l’élément demandé est 12, présent deux fois, comme 10 mais qui lui arrive après dans la liste.

Plus précisément, on écrira deux fonctions :

• count(L, elt) qui renvoie le nombre d’indices de la liste L où l’élément elt est présent
• moins_present(L) qui renvoie l’élément demandé et qui appellera la fonction précédente.

Pour chacune des deux fonctions ci-dessus, on fera un parcours de la liste avec une boucle for.

L’algorithme proposé n’est pas du tout optimal.

Périmètre d’un polygone¶

Un point \(\mathtt{M}\) du plan sera vu comme une liste \(\mathtt{[x, y]}\) de deux entiers, son abscisse \(\mathtt{x}\) et son ordonnée \(\mathtt{y}\). Par exemple, on peut considérer le point \(\mathtt{M=[4, 7]}\). On considère par ailleurs une liste \(\mathtt{L}\) de \(\mathtt{n}\) points du plan.

Par exemple, pour \(\mathtt{n=5}\), on pourrait disposer de la liste suivante :

\(\mathtt{L=[[0,0], [4,0], [4,7], [0,4], [-3,4]]}\)

La liste \(\mathtt{L}\) représente un polygone du plan. Les sommets du polygone sont donnés, dans l’ordre, par les éléments de la liste.

1. Ecrire une fonction dist(M, N) qui renvoie la distance entre deux points \(\mathtt{M}\) et \(\mathtt{N}\). On rappelle la formule :

   \(\mathtt{MN=\sqrt{(x_N-x_M)^2+(y_N-y_M)^2}}\).

2. Ecrire une fonction perimetre(L) qui renvoie le périmètre du polygone représenté par \(\mathtt{L}\). Par exemple, si \(\mathtt{L}\) est une liste de 5 points \(\mathtt{A}\), \(\mathtt{B}\), \(\mathtt{C}\), \(\mathtt{D}\) et \(\mathtt{E}\) et représentant un polygone \(\mathtt{ABCDE}\), son périmètre est

   \(\mathtt{AB + BC+ CD+ DE + EA}\).

   Dans le cas de la liste L donnée en exemple ci-dessus, perimetre(L) devra renvoyer 24.

   La fonction perimetre devra utiliser la fonction de la question 1.

   Cet exercice est directement inspiré d’une question lue sur le forum Python du site OpenClassrooms.

Dessiner les tétraminos¶

On demande de dessiner la figure suivante :

Il s’agit des 7 pièces, appelées tétraminos, que le jeu Tétris utilise. Chaque pièce est constitué de 4 briques carrées (d’où le nom du jeu, Tétris). De haut en bas et de gauche à droite, le nom usuel des blocs et les couleurs utilisées sont données dans tableau suivant :

On écrira une fonction square(tlc, side, color) qui dessine une brique carrée connaissant

• la variable tlc (top left corner) désignant le sommet en haut à gauche du carré,
• le côté du carré
• la couleur de la pièce.

La fonction square fera appel à la fonction Rectangle de Matplotlib ; on utilisera l’option edgecolor='black' qui tracera en noir le contour du carré et l’option facecolor qui colorie l’intérieur du carré.

Toute succession rectiligne d’au moins deux carrés utilisera une boucle for. Le bloc O utilisera deux boucles for imbriquées.

Disques disjoints colorés¶

On se donne une domaine carré de taille \(\mathtt{d\times d}\) et on veut placer dans ce domaine \(\mathtt{N}\) disques colorés et de même rayon \(\mathtt{r}\) et qui soient deux à deux disjoints :

Les couleurs seront successivement choisies dans la liste suivante :

colors=["red", "green", "blue", "cyan", "orange", "magenta"]

Les ingrédients de l’algorithme pourront être les suivants :

• au fur et à mesure, on insère tout centre d’un nouveau disque dans une liste L initialement vide
• on répète \(\mathtt{N}\) fois la génération d’un disque
• pour générer un disque, on choisit avec précaution un centre aléatoire, de coordonnées entières pour simplifier, dans le domaine (utiliser randrange)
• pour tester la validité du centre choisi, on s’assure que sa distance \(\mathtt{d}\) à chacun des centres déjà construits vérifie \(\mathtt{d>2r}\)
• un centre aléatoire pouvant ne pas convenir, la recherche du centre sera placée dans une boucle while.

On écrira des fonctions :

• dist(A, B) calculant la distance entre deux points ;
• isvalid(center, L, r) fonction booléenne qui teste si le centre est assez éloigné des centres présents dans L ;
• rd_disk(M, r) qui génère un centre aléatoire
• draw(M, r, N) qui génère le dessin complet, y compris le rectangle englobant

Le dessin ci-dessus a été généré par l’appel draw(250, 15, 42).

Cet exercice m’a été communiqué par mon collègue P. Piccinini.

Date du jour de Pâques¶

L’algorithme de Butcher-Meeus permet de calculer le jour et le mois du dimanche de Pâques d’une année donnée, à partir de l’an 1583.

Ecrire une fonction jourPaques(y) qui renvoie une liste [jour, mois] représentant la date du dimanche de Pâques de l’an y.

Par exemple, jourPaques(2042) doit renvoyer [6, 4] pour le 6 avril.

On appliquera pas à pas l’algorithme tel qu’expliqué sur la page Wikipedia.

Liste croissante¶

Avant de résourdre cet exercice, on pourra consulter la partie du cours expliquant comment on peut interrompre une boucle for avec return.

Ecrire une fonction est_croissante qui détermine si une liste d’entiers passée en paramètre est croissante (i.e. renvoie True) et False sinon.

Qu’une liste L soit croissante signifie que \(\mathtt{L[i]\leq L[i+1]}\) pour tout indice i pour lequel l’inégalité a un sens.

Exemples :

[5, 6, 6, 6, 10] -> True
[5, 6, 6, 6, 4] -> False
[42] -> True

Toujours la moyenne¶

Écrire une fonction toujoursLaMoyenne qui prend en paramètre une liste de notes (sur 20) et renvoie True si toutes les notes valent 10 ou plus que 10. Le code sera pénalisé s’il n’utilise pas une boucle while pour résoudre le problème.

Voici des exemples de comportements attendus :

[12, 19, 10, 18, 20] -> True
[10] -> True
[12, 15, 9, 19] -> False

Pairs d’abord, impairs ensuite¶

On donne une liste \(\mathtt{L}\) d’entiers et on demande d’écrire une fonction \(\mathtt{f}\) qui renvoie True si dans la liste \(\mathtt{L}\) apparaissent D’ABORD les entiers pairs de la liste et ENSUITE les entiers impairs de la liste.

Voici quelques exemples de comportements de \(\mathtt{f}\) :

Entiers consécutifs croissants ou pas¶

Ecrire une fonction \(\mathtt{f}\) qui prend en paramètre une liste \(\mathtt{L}\) d’entiers et qui renvoie True si la liste est constituée d’entiers consécutifs croissants et qui renvoie False sinon. Ci-contre, voici quelques exemples de comportements attendus de \(\mathtt{f}\).

Liste monotone¶

Une liste d’entiers est dite monotone ou bien si elle est croissante ou bien si elle est décroissante.

Par exemple, les listes [5, 5, 6, 6, 6, 10] ou [5, 5, 4, 1, 1] sont monotones mais la liste [42, 35, 35, 40, 34] ne l’est pas.

Ecrire une fonction est_monotone qui détermine si une liste d’entiers est monotone (i.e. renvoie True et False sinon).

Afin de traiter uniformément les deux cas de listes croissantes ou décroissantes, on écrira une fonction booléenne meme_signe(a, b) qui renvoie True si a et b sont des entiers de même signe et False sinon. On considèrera que l’entier 0 a deux signes à la fois.

On fera attention à bien gérer le cas des listes dont les premiers termes sont identiques.

Exemples :

[5, 5, 6, 6, 6, 10] -> True
[5, 5, 6, 6, 6, 10, 9] -> False
[5, 5, 6, 6, 6, 10, 10, 9] -> False
[5, 5, 6, 6, 6, 6] -> True
[5, 5, 6, 6, 6, 6, 4, 4] -> False
[5, 5, 6, 6, 6, 5] -> False
[42, 5, 5, 6, 6, 6, 5] -> False
[42] -> True
[42, 42, 42, 42, 42] -> True
[5, 4] -> True
[4, 5] -> True
[5, 4, 3, 3, 0] -> True
[5, 4, 3, 42, 43, 44] -> False
[5, 4, 3, 3, 42] -> False
[] -> True

Suppression alternée d’entiers dans une liste¶

On écrit côte à côte tous les entiers entre 1 et 128. On supprime un élément sur deux en commençant par le premier, ce qui donne la liste suivante :

2, 4, 6, 8, 10, ..., 124, 126, 128

On répète l’opération de suppression mais en commençant cette fois par le dernier élément, ce qui donne la liste :

2, 6, 10, ..., 122, 126

et on recommence l’opération à partir du début et ainsi de suite en alternant début et fin de liste jusqu’à ce que la liste ne contiennne plus qu’un seul nombre. On demande de déterminer ce nombre (on trouvera 86).

Pour cela, on écrira :

• une fonction supprimer(L) qui renvoie la liste des éléments d’une liste L dont on a supprimé le premier, le troisième et tous les éléments placés à un rang impair,
• une fonction inverser(L) qui renvoie la liste des éléments de L écrits dans l’ordre inverse

puis on appelera ces fonction dans une boucle while.

Cette question a été lue sur le forum MathStackExchange : alternate deletion of integers between 1 and 128, which is the last one?

Suite unimodale¶

Observez la suite suivante :

12 15 17 18 19 20 17 13 10

La suite commence par augmenter strictement pour atteindre sa plus grande valeur puis elle décroît strictement.

Une telle suite sera dite unimodale : c’est donc une suite d’entiers qui atteint sa plus grande valeur en une unique valeur \(M\) (dans l’exemple ci-dessus, c’est \(M=20\)) et qui est croissante au sens strict avant d’atteindre \(M\) et décroissante au sens strict après avoir atteint \(M\).

La suite ci-dessous n’est pas unimodale :

12 15 17 17 18 19 20 24 25 29

en effet, elle prend la même valeur (17) sur deux indices consécutifs.

De même, la suite ci-dessous n’est pas unimodale

12 15 17 14 13 20 21 19 11

puisqu’elle croit puis décroît puis croît encore.

Enfin la suite ci-dessous n’est pas unimodale

12 15 17 18 19

car elle ne décroît jamais.

Vous disposez d’une suite d’au moins trois entiers sous forme d’une liste L, par exemple

L = [12, 15, 17, 18, 19, 20, 17, 13, 10]

et vous devez construire une fonction estUnimodale(L) qui renvoie True si la suite des entiers de L est unimodale et False sinon. Dans le cas de la liste L donnée en exemple, estUnimodale(L) vaut True.

Suite super croissante¶

Soit S un série croissante de données composée de valeurs réelles. On dira que S est une super croissante si la suite des écarts entre termes consécutifs est strictement croissante. Par exemple, la suite ci-dessous

1 3 7 12

est super croissante puisque les écarts consécutifs valent 2, 4 et 5 et donc vont en croissant strictement. En revanche, la suite

1 3 4 7

N’est PAS super croissante puisque les écarts consécutifs valent 2, 2 et 3 et ne vont pas en croissant STRICTEMENT.

Plus précisément, en tout indice \(\mathtt{i}\) de la série où cela a un sens, on examine si l’écart entre la \(\mathtt{i^{\text{e}}}\) valeur et la \(\mathtt{(i-1)^{\text{e}}}\) valeur est bien strictement inférieur à l’écart entre la \(\mathtt{(i+1)^{\text{e}}}\) valeur et la \(\mathtt{i^{\text{e}}}\) valeur.

Écrire une fonction est_super_croissante qui retourne True si la série S passée en paramètre, et supposée être croissante, est une super croissance, et False sinon.

Tester avec les trois séries suivantes :

[0.0, 1.0, 2.30, 3.74, 5.28, 6.90, 8.59, 10.33, 12.13, 13.97] --> True
[-278.0, -274.0, -250.14, -191.30, -83.99, 84.39, 325.79, 651.68, 1073.18, 1601.05] --> True
[-9.0, -2.0, 3.62, 8.81, 13.74, 18.49, 23.10, 27.60, 31.99, 36.31] --> False

Deuxième plus petit élément d’une liste¶

1. Ecrire une fonction mini qui prend en paramètre une liste non vide L d’entiers et renvoie le plus petit élément de la liste L.

   Voici quelques exemples de comportement de la fonction mini:

   [81, 42, 65, 12, 81] -> 12
   [42, 81, 65] -> 42
   [81, 81, 81] -> 81
   [81] -> 81
   

2. Écrire une fonction tousSaufLui qui prend en paramètres :

   • une liste L d’entiers
   • un entier a

   et qui renvoie une nouvelle liste comprenant tous les éléments de L sauf ceux qui valent a. Le contenu de la liste initiale L doit être préservé après un appel à la fonction tousSaufLui.

   Voici quelques exemples de comportement de tousSaufLui(L, a) pour a = 81 et les listes L suivantes :

   [65, 81, 31, 81, 9, 81, 81, 32] -> [65, 31, 9, 32]
   [65, 31, 9, 32] -> [65, 31, 9, 32]
   [81, 81, 81] -> []
   

3. Écrire une fonction deuxiemePlusPetit qui prend en paramètre une liste d’entiers L ayant au moins deux éléments distincts et qui renvoie la plus petite valeur de la liste L mais qui soit différente du minimum de la liste L autrement dit la fonction doit renvoyer la deuxième valeur de L si L était triée dans l’ordre croissant.

   Voici quelques exemples de comportement de la fonction deuxiemePlusPetit :

   [8, 20, 8, 16] -> 16
   [8, 9, 8, 7, 9, 8, 5] -> 7
   [4, 4, 4, 3] -> 4
   [81, 42] -> 81
   

   Votre fonction devra utiliser les fonctions précédentes.

Deux plus grands éléments d’une liste¶

On donne une liste d’entiers L, ayant au moins deux éléments et on demande d’écrire une fonction deux_premiers(L) qui renvoie la liste M formée des deux plus grands entiers de L. La liste M sera ordonnée dans le sens croissant. Il est possible que les deux entiers de L soient identiques (lorsque le plus grand élément de L est présent au moins deux fois dans L). Voici quelques exemples de comportements :

[4, 3, 6, 7, 7, 8, 8, 7, 4, 9] → [8, 9]
[4, 5] → [4, 5]
[5, 4] → [4, 5]
[5, 4, 3, 2, 5, 5] → [5, 5]

La méthode de codage de la fonction est libre, quitte à utiliser une fonction auxiliaire.

On pourra néanmoins suivre les indications suivantes :

• créer deux variables a et b qui initialement représentent les éléments L[0] et L[1] avec la contrainte que \(\mathtt{a\leq b}\)
• parcourir L
• à chaque nouvel élément de L, mettre à jour les variables a et b pour qu’elles représentent les deux plus grands éléments de L parmi ceux qui ont déjà été examinés lors du parcours.

Deux plus grands éléments distincts d’une liste¶

On donne une liste d’entiers L comprenant au moins deux entiers distincts et on demande d’écrire une fonction deux_premiers(L) qui renvoie la liste M formée des deux plus grands entiers distincts de L. La liste M sera ordonnée dans le sens croissant. Voici quelques exemples de comportements :

[4, 3, 6, 7, 7, 8, 8, 7, 4, 9] → [8, 9]
[4, 5] → [4, 5]
[5, 4] → [4, 5]
[5, 4, 3, 2, 5, 5] → [4, 5]

La méthode de codage de la fonction est libre, quitte à utiliser une fonction auxiliaire.

On pourra néanmoins suivre les indications suivantes :

• créer deux variables a et b qui initialement représentent les éléments L[0] et L[1] avec la contrainte que \(\mathtt{a\leq b}\)
• parcourir L
• à chaque nouvel élément de L, mettre à jour les variables a et b pour qu’elles représentent les deux plus grands éléments de L parmi ceux qui ont déjà été examinés lors du parcours et faire en sorte que ces éléments soient distincts si c’est possible.

Les plus petits devant¶

On donne une liste L d’entiers et on demande de modifier L pour faire en sorte que chaque occurrence du plus petit élément de L soit placée en début de liste. Par exemple, soit la liste L

L = [50, 20, 30, 20, 20, 10, 50, 10, 70, 10, 80, 10]

Son plus petit élément vaut 10 et apparaît 4 fois, aux indices 5, 7, 9 et 11. On doit donc modifier la liste L en la liste :

[10, 10, 10, 10, 20, 50, 50, 20, 70, 30, 80, 20]

Il est attendu que L soit juste modifiée (par des échanges d’éléments) et non pas qu’une nouvelle liste soit reconstruite. Toutefois, créer une nouvelle liste est préférable à un code qui ne marche pas ou à une absence de code.

On pourra parcourir L et maintenir une liste des indices des éléments minimaux de L, quitte à repartir d’une nouvelle liste si le minimum courant change. Il n’est pas nécessaire de parcourir plusieurs fois la liste L mais si c’est nécessaire, cette solution sera préférable à une absence de code ou à un code qui ne fonctionne pas.

Une fois la liste des indices obtenue, on procédera aux échanges demandés. On pourra utiliser la fonction d’échange suivante :

def echanger(L, i, j):
    # échange les termes d'indices i et j de L
    L[i],L[j]=L[j], L[i]

Nombre d’éléments distincts d’une suite croissante¶

On donne une liste croissante d’entiers, par exemple

L = [42, 42, 81, 82, 82, 82, 82, 89, 92, 98]

et on demande de calculer le nombre d’éléments distincts de la liste. Dans l’exemple précédent, ce nombre est 6. On écrira une fonction effectif(L) qui renverra le nombre d’éléments distincts de L. Utiliser deux boucles for imbriquées sera pénalisé.

Voici quelques exemples de comportement de la fonction :

[42, 42, 81, 82, 82, 82, 82, 89, 92, 98] -> 6
[42, 42, 42, 42, 42, 43, 43, 43, 43, 43] -> 2
[42] -> 1
[42, 42, 42, 42, 42] -> 1
[] -> 0
[10, 20, 30, 40, 50, 60, 70] -> 7
[42, 81, 81, 81, 81, 90] -> 3

Intersection de deux listes strictement croissantes¶

On donne deux listes L et M constituées d’entiers rangés dans l’ordre strictement croissant, en particulier, dans chaque liste, les entiers sont distincts. On demande de construire la liste N formée des entiers communs aux deux listes. Les éléments de N seront écrits dans l’ordre croissant. On écrira une fonction inter(L, M) qui renverra N.

Voici un exemple de comportement :

L = [12, 13, 14, 18, 21, 22, 24, 26, 28]
M = [10, 13, 15, 19, 21, 22, 26, 29]
N = [13, 21, 22, 26]

Votre méthode de génération de N doit utiliser que les listes L et M sont croissantes. Le code devra fonctionner pour des listes de tailles très grandes (de l’ordre du million ou du milliard d’éléments). Pour tester la fonction inter sur des listes de taille de l’ordre du million, on utilisera le code suivant :

def perf(n):
    from random import sample
    from time import perf_counter
    R=range(n)
    L =sorted(sample(R, n//4))
    M=sorted(sample(R, n//3))
    begin_perf=perf_counter()
    inter(L, M)
    print("%.2f" %(perf_counter()-begin_perf))


perf(4*10**6)

L’affichage devra survenir dans un temps de l’ordre d’une seconde.

Liste d’entiers symétrique par rapport à zéro¶

On dit qu’une liste d’entiers est « symétrique par rapport à zéro » si ses éléments non nuls peuvent se partionner en paires formées d’éléments opposés ie de la forme \(x\) et \(-x\). Par exemple, chacune des trois listes ci-dessous est opposée :

[-5, 0, 3, 5, -3]
[7, -1, -9, -7, 9, 1]
[-5, 0, 0, 4, 5, 0, -4]

Ecrire une fonction estSym(L) qui partant d’une liste L d’entiers renvoie un booléen qui vaut True si la liste L est symétrique par rapport à zéro et False sinon. Tester avec les listes ci-dessus.

Eléments majoritaires d’une liste¶

On donne une liste L dont les éléments sont des chiffres entre 0 et 9, par exemple

L = [5, 4, 8, 5, 5, 2, 8, 1, 8, 2, 7, 1].

Soit \(\mathtt{N}\) le nombre d’occurrences maximal parmi les éléments de L. Par exemple, avec la liste ci-dessus, on a \(\mathtt{N = 3}\) puisque

• aucun élément de la liste n’apparaît plus de 3 fois dans L
• au moins un élément de L apparaît exactement 3 fois, par exemple l’élément 8.

On demande d’écrire une fonction majoritaires(L) qui prend en paramètre une liste L de chiffres et qui renvoie la liste M des éléments distincts de L dont exactement \(\mathtt{N}\) occurrences sont présentes dans la liste L où \(\mathtt{N}\) est, comme expliqué ci-dessus, le nombre d’occurrences maximal parmi les éléments de L. Ainsi, avec L = [5, 4, 8, 5, 5, 2, 8, 1, 8, 2, 7, 1], la liste à trouver est M = [5, 8] car les éléments 5 et 8 de la liste L apparaissent chacun le nombre maximal \(\mathtt{N}\) de fois.

Suggestion de résolution. On pourra créer une liste auxiliaire nbOccur de longueur 10 et telle que nbOccur[i] vaille le nombre d’occurrences de l’entier i dans la liste L.

Le tableau ci-dessous donne d’autres exemples du comportement attendu de la fonction majoritaires :

Supprimer les doublons¶

Ecrire une fonction eliminer_doublons(L) qui partant d’une liste d’entiers retourne une liste composée des valeurs de L, mais dans laquelle les multiples valeurs égales de L (s’il y en a) n’ont été copiées qu’une seule fois. L’ordre de la liste renvoyée devra repecter l’ordre d’entrée des éléments de la liste initiale. On dira ainsi de la liste retournée qu’elle ne contient pas de doublon. Exemples :

On rappelle que Python dispose d’un test d’appartenance dans une liste.

Ils sont uniques !¶

On donne une liste L d’entiers et on demande d’écrire une fonction solitaires(L) qui renvoie la liste sansDoublons des éléments de L qui ne sont présents qu’une seule fois dans L.

Voici quelques exemples de comportement :

[2, 2, 2, 2, 1, 5, 2, 3, 5, 4] → [1, 3, 4]
[42, 42, 42, 42, 42] → []
[42] → [42]

Ainsi, pour la liste L=[2, 2, 2, 2, 1, 5, 2, 3, 5, 4], la liste sansDoublons ne contient pas 5 qui est présent deux fois, ni 2 présent cinq fois.

On pourra procéder comme suit :

• initialiser une liste eff, de même longueur que L, des effectifs de la liste ; au départ eff ne contient que des zéros et à la fin de sa construction, est telle que eff[i] est le nombre d’apparitions dans L de l’élément de L à l’indice i ;
• construire eff, en parcourant la liste L et en comptant le nombre de fois que l’élément courant est présent parmi les éléments déjà examinés ;
• construire la liste des éléments d’indice i dans L tels que eff[i] vaille 1.

Doublons d’une liste croissante¶

On donne une liste L d’entiers écrits dans l’ordre croissant et on demande de déterminer la liste D des éléments qui apparaissent au moins deux fois dans cette liste. Voici quelques exemples :

[1, 1, 2, 3, 3, 3, 3, 3] -> [1, 3]
[1, 1, 1, 1, 1, 1, 1] -> [1]
[2, 2, 4, 4] -> [2, 4]
[1, 1, 1, 2, 2, 2, 2, 2, 2] -> [1, 2]
[1, 2, 3, 4, 4] -> [4]
[2] -> []
[3, 4, 4, 5, 5] -> [4, 5]
[1, 1, 1, 4, 5, 6] -> [1]
[2, 2, 3, 3, 4, 5, 6, 6, 7] -> [2, 3, 6]
[1, 2, 3] -> []

On procédera de la manière suivante : parcourir la liste L et à certaines étapes, si l’élément courant est identique au précédent, on placera l’élément courant dans la liste D, vide au début.

Lancers de dé¶

1. Ecrire une fonction lancer_un_de sans paramètre et qui simule un coup de dé à 6 faces.

2. Ecrire une fonction lancers qui effectue \(n\) lancers de dés en utilisant la fonction lancer_un_de et renvoie une liste resultats de 7 éléments tels que si \(i\) est un entier entre 1 et 6 alors resultats[i] est le nombre de fois que le dé à sorti la valeur \(i\). Le premier élément de la liste resultats sera arbitrairement fixé à 0.

   Tester pour \(n\) valant 1 million.

Toujours plus¶

On appelle Toujours Plus le jeu utilisant un seul dé et dont la règle est la suivante : on répète le lancer du dé jusqu’à ce que la valeur lue sur le dé diminue strictement par rapport au lancer précédent. Autrement dit, si le lancer de dé est supérieur ou égal au lancer précédent, la partie continue, sinon, la partie est terminée.

Voici trois exemples de parties complètes de Toujours Plus :

2 4 5 5 2
4 1
5 5 5 6 6 6 5

En particulier, une partie de Toujours Plus dure au moins 2 coups.

1. Écrire une fonction jouerToujoursPlus, sans paramètre et qui simule une partie de Toujours Plus. La fonction devra renvoyer la liste des lancers successifs de la partie.
2. Simuler une partie 100000 fois et vérifier qu’une partie dure, en moyenne, 3 lancers.

Balles dans des boîtes¶

On dispose de \(n\) balles et de \(n\) bacs (dans ce qui suit on prendra \(n=100000\)). On lance au hasard \(N\) fois (par exemple \(N=100\)) chacune des balles dans un des bacs. En moyenne, quel est le nombre de balles dans le bac le plus rempli ?

Ce problème est connu sous le nom de Balls into Bins et permet d’illustrer le problème des collisions dans une table de hachage.

FACE quatre fois de suite¶

1. Ecrire une fonction lancer_piece qui simule le lancer d’une pièce de monnaie équilibrée. La fonction retournera la chaîne « PILE » ou la chaîne « FACE ».

2. On dispose d’une pièce de monnaie. On cherche à savoir quel est, en moyenne, le minimum de lancers qu’il faut effectuer pour obtenir 4 fois FACE consécutivement.

   Créer une fonction attente qui effectue une suite de lancers de la pièce et qui renvoie le nombre de lancers qu’il aura fallu faire pour obtenir pour la première fois 4 fois FACE de suite.

3. Ecrire une fonction test qui itère n fois l’expérience de la fonction attente la fonction attente. Vérifier qu’il faut en moyenne 30 lancers pour obtenir 4 fois de suite FACE.

   Tester sur \(n=10^5\) expériences.

Suite alternée pile ou face¶

Soit l’expérience consistant à lancer une pièce équilibrée n fois et à observer si oui ou non, les résultats de succèdent de manière alternée, c’est-à-dire pile, face, pile, face, etc ou bien face, pile, face, pile, etc.

Ecrire une fonction tirage_alterne(n) qui simule l’expérience et renvoie True ou False selon qu’il y aura eu alternance ou pas.

Suite aléatoire croissante¶

Dans cet exercice, on utilisera le résultat suivant : étant donné une liste L (disons d’entiers), la méthode sort appliquée à la liste L a pour effet de modifier la liste L en la triant dans l’ordre croissant. Par exemple, vous pourrez tester le code suivant :

L=[2, 8, 6, 7, 2, 1]
print(L)
L.sort()
print(L)

qui affiche

[2, 8, 6, 7, 2, 1]
[1, 2, 2, 6, 7, 8]

Noter que le code suivant est inapproprié et incorrect car L.sort() ne renvoie aucune liste :

L=[2, 8, 6, 7, 2, 1]
print(L)
L=L.sort()
print(L)

Écrire une fonction aleat_croissante(a, b, n) qui prend en paramètres trois entiers a, b et n avec \(\mathtt{a\leq b}\) et \(\mathtt{n\geq 0}\) et qui renvoie une liste croissante formée de n entiers aléatoires compris entre a et b (au sens large).

Voici quelques exemples d’appels de la fonction :

aleat_croissante(17, 19, 2) -> [17, 19]
aleat_croissante(16, 27, 1) -> [22]
aleat_croissante(18, 29, 8) -> [19, 19, 24, 24, 26, 26, 26, 29]
aleat_croissante(25, 26, 0) -> []
aleat_croissante(10, 31, 3) -> [14, 22, 24]

On répètera n fois le choix d’un entier aléatoire entre a et b

Jeu de dé : premier coup gagnant¶

Camille et Dominique lancent un dé à tour de rôle jusqu’à ce qu’un 6 sorte et la partie est gagnée. On convient que Camille commence la partie.

1. Simuler à l’aide d’une fonction jouer() le jeu précédent. La fonction renverra 1 si Camille gagne et 0 sinon.
2. En répétant le jeu 1000 fois déterminer la probabilité pour Camille de gagner le jeu (on devra trouver un nombre proche de \(\mathtt{6/11}\)).

Tirage du loto (version fonction)¶

Écrire une fonction tirerLoto ne prenant aucun paramètre et qui renvoie un tirage aléatoire des 5 numéros d’un loto. On rappelle qu’un tirage de loto est formée de 5 numéros distincts entre 1 et 49. On ne tirera pas de « numéro Chance ».

Ainsi, l’appel tirerLoto() pourra générer une liste telle que [42, 32, 48, 47, 20] mais pas telle que [42, 32, 48, 42, 20] puisque dans cette dernière liste, le numéro 42 apparaît deux fois.

On utilisera une boucle while pour placer au fur et à mesure les numéros tirés dans une liste L initialement vide. On rappelle que si L est une liste d’entiers et x un entier alors l’expression x in L vaut True si l’entier x est dans la liste L et False sinon.

Jeu du 421¶

Le jeu du 421 consiste à obtenir avec 3 dés une combinaison contenant une fois le chiffre 4, une fois le chiffre 2 et une fois le chiffre 1. Par exemple, si vous jetez trois dés simultanément et que vous obtenez la combinaison 2, 1 et 4, vous avez gagné ; si vous obtenez 1, 4, 1 alors votre coup n’est pas gagnant.

L’exercice va demander combien de jets de 3 dés sont nécessaires, en moyenne, pour faire un 421.

1. Ecrire une fonction est421 qui prend en paramètre une liste de trois entiers et renvoie

   • True si la liste, à la fois, contient 4, contient 2 et contient 1
   • False sinon.

   Ainsi :

   • est421([6, 2, 1]) = False
   • est421([1, 1, 1]) = False
   • est421([2, 4, 1]) = True
   • est421([1, 2, 4]) = True
   • est421([4, 2, 1]) = True

2. Ecrire une fonction tirage421 qui renvoie, sous forme de liste, un tirage aléatoire de trois dés. Par exemple, si vous tirez les nombres

   6, 2, 2
   

   alors la fonction doit renvoyer la liste [6, 2, 2]. Les nombres peuvent avoir été tirés simultanément ou l’un après l’autre, c’est indifférent.

3. Ci-dessous, on appelle suite gagnante toute succession de lancers de trois dés, autant de fois que nécessaire, pour « sortir » 421. Par exemple, la suite de 7 lancers suivants est une suite gagnante :

   523 144 643 235 451 252 214
   

   Écrire une fonction nombreSuitesGagnantes qui ne prend aucun paramètre et qui

   • simule une suite gagnante,
   • renvoie le nombre de lancers de la suite gagnante

   Par exemple, nombreSuitesGagnantes renvoie 7 dans le cas de la suite gagnante ci-dessus.

4. On fait 1000 suites gagnantes. Calculer le nombre moyen de lancers d’une suite gagnante (le résultat théorique est 36).

Nombre de bus et division¶

Chaque bus d’une compagnie de transport peut contenir exactement p passagers.

1. Ecrire une fonction nb_bus(n, p) qui renvoie le nombre k d’une flotte de bus pour le transport de n passagers. Par exemple, si p=100 alors si n=2024 on aura k=201 et si n=2100 on aura k=210.
2. On peut démontrer que le nombre k de la question précédente est en fait le quotient de la division entière de n+p-1 par p. Vérifier ce résultat en effectuant 1.000.000 de comparaisons de chaque résultat en choisissant au hasard n entre 0 et 1.000.000 et p entre 1 et 10.000.

Paradoxe des anniversaires¶

On souhaite vérifier expérimentalement que si un groupe d’individus est constitué d’au moins 23 personnes, alors il y a une chance sur deux que deux personnes du groupe aient le même jour d’anniversaire.

Une année sera constituée de 365 jours et un jour de l’année sera identifié par un numéro entre 1 et 365.

1. Ecrire une fonction groupe_aleat(n) qui génère un liste de \(\mathtt{n}\) dates d’anniversaire aléatoires. Par exemple, si n=8 alors groupe_aleat(n) pourrait renvoyer une liste telle que :

   [221, 82, 316, 26, 93, 82, 84, 213]
   

2. Cette question est indépendante de la précédente. Ecrire une fonction contientDoublon(L) qui renvoie True si la liste L, formée d’entiers, contient un doublon et False sinon (indication : utilisez deux boucles imbriquées).

3. Ecrire une fonction freq_meme_jour(n, N) qui génère \(\mathtt{N}\) listes aléatoires de \(n\) jours de l’année et renvoie la proportion de groupes parmi les \(N\) groupes qui contiennent deux jours identiques. Par exemple, si freq_meme_jour(8, 5) générait les 5 listes de dates suivantes :

   [221, 82, 316, 26, 93, 82, 84, 213]
   [275, 95, 102, 235, 200, 92, 244, 297]
   [136, 289, 204, 284, 1, 48, 358, 177]
   [179, 63, 272, 134, 160, 319, 151, 272]
   [78, 331, 193, 200, 254, 193, 118, 217]
   

   alors freq_meme_jour(8, 5) renverrait 0.6 puisqu’on constate que sur les 5 groupes, il y en a exactement trois où il y a deux jours identiques (le premier groupe avec 82, le quatrième avec 272 et le dernier avec 193) d’où la proportion de \(\frac 35=\text{0,6}\).

   Vous aurez besoin de la fonction contientDoublon de la question précédente. Si vous n’avez pas réussi à la coder, vous pourrez utiliser la fonction suivante (sans chercher à comprendre comment son code fonctionne) :

   def contientDoublon(L):
       return len(L)!=len(set(L))
   

4. Vérifier qu’à partir de 23 personnes, il y a au moins une chance sur deux que parmi les individus du groupe, deux personnes aient le même jour d’anniversaire (répéter à chaque fois l’expérience \(N=10000\) fois).

Mélanger une liste¶

Ecrire une fonction melange(n) qui renvoie une liste M formée de n entiers qui constituent un mélange aléatoire des entiers entre 0 et n-1 inclus. Par exemple, si \(\mathtt{n=5}\), l’appel melange(n) pourrait renvoyer la liste M = [3, 1, 4, 0, 2].

On appliquera la méthode suivante, qui va être illustrée sur la génération de la liste M=melange(5) donnée en exemple. Voici les étapes :

• on tire aléatoirement un entier entre 0 et 4, par exemple 3 et on place cette valeur dans une liste M au départ vide. On a donc pour l’instant M=[3] ;
• on tire à nouveau un entier aléatoire entre 0 et 4, par exemple 1, et on complète la liste M avec la valeur tirée, ce qui donne M=[3, 1].
• on recommence et on tire aléatoirement 3, qui a déjà été tiré à une étape précédendente. On ne rajoute pas ce tirage à M et on continue ;
• on tire encore aléatoirement encore un entier entre 0 et 4, on obtient par exemple 4 et on le rajoute à la liste M car il n’a jamais été tiré antérieurement, ce qui donne M=[3, 1, 4].
• on continue ainsi jusqu’à ce que la liste M contienne 5 éléments.

On utilisera une boucle while et on rappelle qu’on peut tester l’appartenance d’un élément x à une liste M avec l’expression x in M.

Tester pour n valant 10, 100, 1000 ou 10000 (on devrait observer une certaine lenteur d’exécution).

Gagner au jeu de craps¶

Le jeu de craps se joue avec deux dés à 6 faces. Le joueur jette une première fois les deux dés. Soit t le total de deux faces sorties.

• Si t vaut 7 ou 11 alors le joueur a gagné.

• Si t vaut 2, 3 ou 12 alors le joueur a perdu.

• Sinon, le joueur rejoue les deux dés, dont le total des faces est noté \(\mathtt{s}\), jusqu’à ce que \(\mathtt{s = t}\) ou que \(\mathtt{s = 7}\) :

  • lorsque s=t alors le joueur est gagnant,
  • lorsque s=7 alors le joueur est perdant.

1. Ecrire une fonction craps qui simule une partie de craps et renvoie True si le joueur a gagné et False sinon.
2. En générant un million de parties de craps, déterminer la probabilité de gagner au craps.

Le dilemme de Monty Hall¶

Dans ce qui suit on présente le déroulement d’un ancien jeu télévisé américain, dit jeu de Monty Hall.

Dans un studio de télévision, Camille est en face de trois portes fermées. Derrière une seule des trois portes se trouve une voiture de luxe. Le but de Camille est de gagner cette voiture. Derrière chacune des deux autres portes se trouve une chèvre. L’animateur du jeu, Monty, est présent sur le plateau et sait derrière quelle porte se trouve la voiture. Monty demande à Camille de lui désigner une des trois portes, ce que fait Camille. Monty ouvre alors une autre porte et derrière laquelle se trouve une chèvre :

Monty demande alors à Camille d’ouvrir une des deux portes restantes avec la possibilité de gagner la voiture si elle la découvre.

Que doit faire Camille pour avoir le plus de chances de gagner la voiture ? Ouvrir la porte initiale ou ouvrir l’autre porte ? Où est-ce que le choix est indifférent ?

On définira deux fonctions monty1() et monty2() qui simuleront chacune des deux stratégies possibles. On partira d’une liste jeu=["voiture", "chèvre", "chèvre"] et on mélangera cette liste par shuffle(L) où shuffle est une fonction de mélange à importer du module random.

Puis on appellera 1000 fois chacune des deux fonctions pour savoir si une stratégie est préférable à l’autre.

Mélange de Fisher-Yates¶

L’algorithme de Fisher-Yates permet de mélanger une liste aléatoirement. Dans cet exercice, la liste choisie sera toujours la liste des n premiers entiers à partir de 1, par exemple, si n=4 ce sera la liste L=[1, 2, 3, 4]. On devra écrire une fonction fisher_yates(n) qui génère un mélange aléatoire M de tous les entiers de la liste L. Par exemple, l’appel fisher_yates(4) pourrait générer la liste M = [2, 3,  4, 1].

Ce qui suit décrit l’algorithme sur la base de l’exemple précédent :

• la longueur de la liste est n=4 ;
• on dispose d’une liste, pour l’instant vide M=[]
• on tire un indice aléatoire entre 1 et n=4, par exemple i=2 et on cherche l’élément de L qui est en i-ème position, c’est-à-dire ici 3 et on le place dans M, ce qui donne M=[2] ; puis on « raye » l’élément 2 de la liste L en mettant 0 à sa place ce qui donne L=[1, 0, 3, 4] ;
• comme il ne reste plus que 3 entiers aléatoires à trouver, on choisit un entier aléatoire i entre 1 et n-1=3, imaginons que ce soit i=3 ; on cherche alors dans L le i-ème élément parmi ceux qui n’ont pas déjà été tirés. Ici, le 3e élément de L=[1, 0, 3, 4] qui n’a pas été tiré est 4 (on n’a donc pas compté l’élément de L où il y a 0). On rajoute cet élément à M ce qui donne M=[2, 4] ; enfin, on raye de L l’élément que l’on vient de tirer ce qui donne L=[1, 0, 3, 0] ;
• on recommence puique notre liste M n’a pas encore n éléments : on choisit un entier aléatoire i entre 1 et 2, par exemple i=1 et on cherche dans L le i-ème élément parmi ceux qui n’ont pas déjà été tirés. Ici, le 1er élément de L=[1, 0, 3, 0] qui n’a pas été tiré est 1. On rajoute cet élément à M ce qui donne M=[2, 4, 1] ; enfin, on raye de L l’élément que l’on vient de tirer ce qui donne L=[0, 0, 3, 0].
• Et on continuerait ainsi de suite tant que la liste L n’est pas formée que de zéros.

Les deux premières questions sont indépendantes.

1. Ecrire une fonction consecutifs(n) qui renvoie la liste de tous les entiers consécutifs entre 1 et n (supposé entier valant au moins 1). Par exemple, consecutif(4) renvoie [1, 2, 3, 4].

2. Ecrire une fonction rang(L, i) où L représente une liste et i un entier entre 1 et n=len(L) et qui renvoie l’indice j de la i-ème valeur de L qui soit non nulle. Par exemple, si

   L=[42, 33, 0, 0, 81, 0, 82, 31]

   et i=4 alors rang(L, i)=6 car 82 est la 4e valeur non nulle de L et que 82 est à l’indice 6 de la liste L. On supposera qu’il existe toujours une valeur de L qui convienne.

3. En déduire un code de la fonction fisher_yates(n).

   Tester votre fonction pour n valant 10, 100, 1000 ou 10000 (et dans ce dernier cas, l’exécution ne sera pas instantanée).

L’algorithme P¶

L’algorithme P ou encore mélange de Knuth est un algorithme optimal de mélange aléatoire d’une liste L.

L’algorithme consiste à faire une succession d’échanges élémentaires. Précisons : si on dispose d’une liste L, on appelle échange élémentaire l’échange du dernier élément de la liste avec un élément aléatoire de la liste L. Par exemple, si L est la liste L=[10, 11, 12, 13, 14], alors la liste L=[10, 14, 12, 13, 11] est un échange élémentaire : on a choisi une position aléatoire dans L, ici la 2e position et on a échangé l’élément avec le dernier.

L’algorithme P consiste à faire la succession d’échanges élémentaires :

• sur la totalité de la liste,
• puis sur tous les éléments sauf le dernier,
• puis sur tous les éléments sauf les deux derniers,
• et ainsi de suite jusqu’à n’avoir qu’un seul élément (auquel cas il n’y a plus d’échange).

Par exemple, si au départ L=[10, 11, 12, 13, 14] alors on peut avoir les étapes suivantes :

• on choisit au hasard disons la 2e position, ce qui donne L=[10, 14, 12, 13, 11]
• on choisit au hasard disons la 3e position, ce qui donne L=[10, 14, 13, 12, 11]
• on choisit au hasard disons la 2e position, ce qui donne L=[10, 13, 14, 12, 11]
• on choisit au hasard disons la 1re position, ce qui donne L=[13, 10, 14, 12, 11]
• et on n’a plus de choix, on est arrivé en tout début de liste.

D’où la liste aléatoire L=[13, 10, 14, 12, 11].

Ecrire une fonction algo_P(L) qui mélange aléatoirement tous les éléments d’une liste L. Par exemple, si L=[10, 11, 12, 13, 14] alors l’appel algo_P(L) pourrait modifier la liste L en la liste [13, 10, 14, 12, 11].

Pour échanger les éléments d’indice i et j d’une liste L, on pourra utiliser le code suivant :

L[i], L[j] = L[j], L[i]

On testera sur des listes formées d’entiers consécutifs à partir de 1 (comme [1, 2, 3, 4, 5]) de longueur 10, 100 ou 10000000.

Somme, maximum¶

1. Écrire le code de la fonction définie par

   \(f(n)= -n^3+28n+1\)

   et tester ce code.

2. Ecrire une fonction somme_f(a, b) qui prend en paramètres deux entiers \(a\) et \(b\) que l’on supposera toujours vérifier \(a\leq b\) et qui renvoie la somme suivante :

   \(f(a)+f(a+1)+\cdots+f(b-1)+f(b)\)

   Par exemple, somme_f(3, 6) vaudra \(f(3)+f(4)+f(5)+f(6)=76\). La fonction \(f\) précédente doit être réutilisée.

3. Ecrire une fonction max_f(a, b) qui prend en paramètres deux entiers \(a\) et \(b\) que l’on supposera toujours vérifier \(a\leq b\) et qui renvoie la plus grande valeur prise par f en les points \(a, a+1,..., b\).

   Par exemple, on trouvera que max_f(-5, 10) vaut 58.

Diviseurs, nombre premier¶

Dans cet exercice, tous les entiers considérés sont strictement positifs.

On rappelle qu’un entier \(d\) est dit un diviseur d’un entier \(n\) si \(n\) est un multiple de \(d\). Par exemple, \(10\) est un diviseur de \(2020\) mais n’est pas un diviseur de \(2024\).

1. Ecrire une fonction diviseurs(n) qui renvoie la liste de tous les diviseurs de l’entier n. Voici quelques exemples du comportement de la fonction diviseurs :

   42 -> [1, 2, 3, 6, 7, 14, 21, 42]
   41 -> [1, 41]
   81 -> [1, 3, 9, 27, 81]
   75 -> [1, 3, 5, 15, 25, 75]
   1 -> [1]
   

2. Un entier est dit premier s’il admet exactement DEUX diviseurs. Par exemple, 42 n’est pas premier car il admet au moins trois diviseurs, par exemple 1, 6 et 42. En revanche, 41 est premier car ses seuls diviseurs sont 1 et 41.

   Ecrire une fonction estPremier(n) qui renvoie True si l’entier n est premier et False sinon. La fonction doit utiliser la fonction diviseur de la question précédente.

Plus grand diviseur impair : méthode rapide¶

Soit un entier \(n>0\). On cherche, de manière efficace, le plus grand diviseur impair \(d\) de \(n\). Par exemple :

• si \(n=42\) alors \(d=21\),
• si \(n=45\) alors \(d=45\),
• si \(n=64\) alors \(d=1\),
• si \(n=1000\) alors \(d=125\).

On peut vérifier que \(d=n/p\) où \(p\) est la plus grande puissance de 2 divisant \(n\). Par exemple, si \(n=1000\) alors la plus grande puissance de 2 divisant \(n\) est \(p=2^3=8\) et donc le plus grand diviseur impair de \(n\) est \(d=n/p=1000/8=125\).

1. Ecrire une fonction \(\mathtt{p2(n)}\) qui renvoie \(\mathtt{p}\) en testant toutes les puissances de 2, c’est-à-dire 1, 2, 4, 8, etc.
2. Ecrire une fonction maxDivImpair(n) qui utilise la fonction précédente et renvoie le plus grand diviseur impair de \(\mathtt{n}\). Calculer maxDivImpair(416241604).

Nombre de zéros qui terminent un entier (version fonction)¶

On demande d’écrire une fonction zeros(n) qui prenant un entier \(\mathtt{n\geq 0}\) en paramètre, par exemple \(\mathtt{n=4205000}\), renvoie le nombre de zéros qui terminent l’écriture décimale du nombre \(\mathtt{n}\); dans l’exemple précédent, ce nombre est 3. On pourra remarquer que c’est l’exposant de la plus grande puissance de 10 dont \(\mathtt{n}\) soit multiple. On utilisera obligatoirement une boucle for. Ne pas oublier le cas \(\mathtt{n=0}\).

Décomposer en groupes de 2 ou 3¶

On se donne un entier positif \(n\) et on cherche les solutions \((x, y)\) en nombres entiers positifs de l’équation

\(\ds 2x+3y=n\)

Par exemple, si \(n=42\) alors l’équation admet la liste suivante de 8 solutions :

[[21, 0], [18, 2], [15, 4], [12, 6],
[9, 8], [6, 10], [3, 12], [0, 14]]

1. Ecrire une fonction solve(n) qui renvoie la liste des solutions de l’équation ci-dessus, une solution étant vue comme une liste [x, y] à deux éléments.
2. Si \(\mathtt{n}\) est un entier positif, on appelle \(\mathtt{q}\) le quotient entier de \(\mathtt{n}\) par 3 et \(\mathtt{r}\) le reste de \(\mathtt{n}\) par 2. Ecrire une fonction f(n) qui renvoie le quotient par 2 de \(\mathtt{q+2-r}\).
3. Vérifier pour tous les entiers \(\mathtt{n}\) entre 0 et 1000 que le nombre de solutions entières positives de l’équation \(\mathtt{2x+3y=n}\) est \(\mathtt{f(n)}\). La suite \(\mathtt{f(n)}\) est répertoriée ICI.

Entier différence de deux carrés¶

Tout entier qui, divisé par 4, admet un reste autre 2, peut s’écrire comme différence de deux carrés parfaits. Par exemple, prenons 2021 dont le reste de la division par 4 est 1 ou encore 2024 dont le reste de la division par 4 est 0 (et est donc différent de 2 dans chaque cas) ; alors :

\(\ds 2021= 45^2-2^2, \quad 2024 = 507^2-505^2\).

On demande d’écrire une fonction diff_carres(n) qui prend en paramètre un entier n et qui renvoie :

• l’objet None si n est un entier pair et non multiple de 4 (par exemple 2022),
• une liste de deux entiers [a, b] telle que \(\mathtt{n=a^2-b^2}\) sinon.

On pourra utiliser les identités suivantes où \(\mathtt{k}\) est un entier :

• identité A : \(\mathtt{2k+1=(k+1)^2-k^2}\)
• identité B : \(\mathtt{4k=(k+1)^2-(k-1)^2}\)

Exemples de comportement :

12 : [4, 2]
13 : [7, 6]
14 : None
15 : [8, 7]

Calcul itératif du ppcm¶

On se donne deux entiers \(\mathtt{a}\) et \(\mathtt{b}\) strictement positifs et on cherche le ppcm \(\mathtt{m}\) de ces deux entiers par application de l’algorithme suivant : on crée une suite de couples \(\mathtt{(x, y)}\) jusqu’à ce que \(\mathtt{x = y}\). La suite est initialisée avec (a, b) et si \(\mathtt{(x, y)}\) est le couple courant alors le couple suivant \(\mathtt{(X, Y)}\) est défini par la condition suivante :

• si \(\mathtt{x =\min(x, y)}\) alors \(\mathtt{Y=y}\) et \(\mathtt{X}\) est le plus petit multiple de a supérieur ou égal à \(\mathtt{y}\)
• si \(\mathtt{y =\min(x, y)}\) alors \(\mathtt{X=x}\) et \(\mathtt{Y}\) est le plus petit multiple de b supérieur ou égal à \(\mathtt{x}\).

Lorsque l’algorithme s’arrête alors \(\mathtt{x}\) (ou \(\mathtt{y}\)) est le ppcm des deux entiers \(\mathtt{a}\) et \(\mathtt{b}\).

Par exemple, si \(\mathtt{a=16}\) et \(\mathtt{b=60}\), le tableau ci-dessous montre la suite des couples :

et on lit donc à la dernière ligne que le ppcm de \(\mathtt{a}\) et \(\mathtt{b}\) est 240.

Ecrire une fonction ppcm(a, b) qui implémente cet algorithme.

ppcm de plusieurs entiers¶

Si \(\mathtt{a_1, \dots, a_n}\) sont des entiers strictement positifs, le ppcm de ces entiers est le plus petit entier qui soit multiple de chacun des entiers. Par exemple, le ppcm de 16, 42 et 60 est 1680 car

\(1680=16\times 105 =42\times 40=60\times 28\)

et aucun entier non nul et strictement inférieur à 1680 n’est multiple simultanément de 16, 42 et 60.

Pour calculer le ppcm de \(\mathtt{n\geq 3}\) entiers, il suffit de savoir calculer le ppcm de deux entiers. En effet, on peut montrer que le ppcm des entiers \(\mathtt{a_1, \dots, a_n}\) s’obtient en prenant le ppcm de \(\mathtt{m}\) et \(\mathtt{a_n}\) où \(\mathtt{m}\) est le ppcm de \(\mathtt{a_1, \dots, a_{n-1}}\). Donc pour calculer le ppcm de 16, 42 et 60, on calcule le ppcm de 16 et 42, qui vaut 336 puis on calcule le ppcm de 336 et 60 qui vaut 1680.

Ecrire une fonction ppcm(L) qui calcule le ppcm des entiers d’une liste donnée L. Pour cela, on donne le code d’une fonction ppcm2 qui calcule le ppcm de deux entiers et que l’on pourra utiliser librement :

def ppcm2(a, b):
    from math import gcd
    return a*b//gcd(a, b)

Somme des termes d’une récurrence double¶

On considère la suite d’entiers calculés successivement de la manière suivante : le nombre courant s’obtient en retirant au triple du dernier nombre calculé le double de l’avant dernier nombre calculé. Si on part de 1 et 3, la suite calculée commence par

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023

Par exemple, \(\mathtt{63= 3\times 31 - 2\times 15 = 93-30=63}\).

1. On demande de calculer la somme des \(n\) premiers éléments de cette suite. Par exemple, si \(n=5\) alors la somme vaut \(57\).
2. En comparant plusieurs valeurs successives de \(s\) à la puissance de 2 immédiatement supérieure, essayez de deviner une formule qui exprime \(s\) en fonction du rang \(n\) (on trouvera \(s=2^{n+1}-n-2\)).

Nombres de Perrin¶

On considère la séquence infinie de nombres dits nombres de Perrin. Elle est définie comme suit :

• les trois premiers sont : 3, 0 et 2
• chaque nombre suivant est la somme de l’avant-dernier et de l’avant-avant dernier calculés.

Ainsi, dans la séquence, le nombre suivant est 0 + 3 = 3, le suivant encore est 2 + 0 = 2 qui est suivi de 3 + 2 = 5 .

Voici la liste des 10 premiers nombres de Perrin :

Ecrire une fonction perrin(n) qui renvoie le \(\mathtt{n^\text{e}}\) nombre de Perrin. En particulier, calculer le 1000e nombre de Perrin. On trouvera un très grand nombre commençant par 100299.

Sommes d’entiers consécutifs¶

1. Ecrire une fonction somme_consecutifs(i, j) qui renvoie la somme de tous les entiers entre les entiers \(\mathtt{i}\) et \(\mathtt{j}\) où on suppose que \(\mathtt{i\leq j}\). Par exemple, somme_consecutifs(10, 15) vaut \(10+11+12+13+14+15=75\).

2. On donne un entier \(\mathtt{n\geq 0}\). De combien de façons peut-on écrire comme \(\mathtt{n}\) comme somme d’entiers consécutifs entre 1 et \(\mathtt{n}\) ? Par exemple, pour \(\mathtt{n=15}\), c’est possible de 4 façons :

   \(15,\quad 7+8,\quad 4+5+6,\quad 1+2+3+4+5.\)

Somme des carrés¶

1. Ecrire une fonction somme2(n) qui renvoie \(1^2+2^2+3^2+\dots+(n-1)^2 +n^2\).
2. Dans les deux dernières questions, il est attendu d’utiliser une boucle while.
   1. Montrer que 42 est le plus petit entier n tel que la somme \(1^2+2^2+3^2+\dots+(n-1)^2 +n^2\) dépasse strictement 25000.
   2. Trouver le plus petit entier n tel que la somme \(1^2+2^2+3^2+\dots+(n-1)^2 +n^2\) dépasse strictement 25000.
   3. Trouver le plus petit entier n tel que la somme \(1^2+2^2+3^2+\dots+(n-1)^2 +n^2\) dépasse strictement \(10^{14}\).

Nature d’un quadrilatère¶

Rappelons quelques définitions de géométrie. Un quadrilatère \(\mathtt{ABCD}\) est dit un

• parallélogramme si \(\mathtt{AB=CD}\) et \(\mathtt{AD=BC}\)
• rectangle si c’est un parallélogramme tel que l’angle en \(\mathtt{A}\) soit droit
• losange si c’est un parallélogramme tel que \(\mathtt{AB=AD}\)
• carré si c’est un rectangle et aussi un losange.

Par ailleurs, on identifie un point M du plan à la liste [x, y] de ses coordonnées dans un repère orthonormé donné. On rappelle que si \(\mathtt{A=[xA, yA]}\) et \(\mathtt{B=[xB, yB]}\) alors le carré de la distance entre \(\mathtt{A}\) et \(\mathtt{B}\) vaut \(\mathtt{AB^2=(xB-xA)^2+(yB-yA)^2}\).

On observera que pour comparer des distances, on peut se contenter de comparer les carrés des distances. Pour établir que l’angle en U du triangle \(\mathtt{UVW}\) est un angle droit, on peut utiliser le théorème de Pythagore et établir que \(\mathtt{UV^2+UW^2=VW^2}\).

1. Écrire une fonction longueurs(A, B, C, D) qui recevant les coordonnées des sommets \(\mathtt{A}\), \(\mathtt{B}\), \(\mathtt{C}\) et \(\mathtt{D}\) d’un quadrilatère renvoie la liste des carrés des quatre côtés \(\mathtt{AB^2}\), \(\mathtt{BC^2}\), \(\mathtt{CD^2}\) et \(\mathtt{DA^2}\) ainsi que \(\mathtt{AC^2}\), le carré de la diagonale.

2. Ecrire une fonction quadrilatere(A, B, C, D) qui recevant les coordonnées des sommets \(\mathtt{A}\), \(\mathtt{B}\), \(\mathtt{C}\) et \(\mathtt{D}\) d’un quadrilatère, affiche exactement une des chaînes suivantes :

   • "Carré" si le quadrilatère \(\mathtt{ABCD}\) est un carré,
   • "Rectangle" si le quadrilatère \(\mathtt{ABCD}\) est un rectangle,
   • "Losange" si le quadrilatère \(\mathtt{ABCD}\) est un losange,
   • "Parallélogramme" si le quadrilatère \(\mathtt{ABCD}\) est un parallélogramme
   • "Quelconque" sinon.

   On utilisera la question 1 et on supposera que les points ont des coordonnées entières.

   Voici 5 exemples de sortie du programme :

   (0, 0) (5, 0) (7, 3) (2, 8) : Quelconque
   (0, 0) (5, 0) (7, 3) (2, 3) : Parallélogramme
   (1, 2) (7, -1) (5, -5) (-1, -2) : Rectangle
   (-1, -2) (3, 1) (3, 6) (-1, 3) : Losange
   (0, 0) (3, 1) (2, 4) (-1, 3) : Carré
   

Triangle magique¶

Dans le triangle ci-dessous

on demande de trouver toutes les façons de répartir les 6 jetons sur leurs emplacements en sorte que sur chaque côté, la somme des numéros fasse toujours 11.

Plusieurs méthodes sont possibles. On pourra tester toutes les répartitions a priori possibles en utilisant des boucles for imbriquées. On pourra avoir besoin d’écrire une fonction sans_doublon(L) qui prend en argument une liste L d’entiers entre 1 et 6 et renvoie True si cette liste contient une fois et une seule chaque entier entre 1 et 6.

Divisibilité par 7 : le critère de Chika¶

Pour savoir si un entier \(n\), écrit en base 10, est multiple de 7, comme c’est le cas de \(\mathtt{77=7\times 11}\), \(\mathtt{42=7\times 6}\) ou \(\mathtt{490=7\times 70}\), on peut utiliser le procédé suivant et redécouvert en 2019 par Chika, un collégien nigérian de 12 ans :

• on supprime le chiffre des unités \(u\) de \(n\) ce qui donne un entier nommé \(m\)
• on calcule \(N=m+5u\)

Alors \(n\) est multiple de 7 si et seulement \(N\) l’est. Si nécessaire, on peut recommencer le procédé avec \(N\) et cela jusqu’à ce qu’on rencontre un entier assez petit que l’on sait être (ou ne pas être) multiple de 7.

Par exemple, 69132 est-il un multiple de 7 ? On applique la règle plusieurs fois de suite :

• \(\mathtt{6913 + 5\times 2=6923}\)
• \(\mathtt{692 + 5\times 3=707}\)

Il est clair que 707 est un multiple de 7 donc cela signifie que 69132 est un multiple de 7. Bien sûr, on aurait pu continuer comme suit :

• \(\mathtt{70 + 5\times 7=105}\)
• \(\mathtt{10 + 5\times 7=35}\)
• \(\mathtt{3 + 5\times 5=28}\)
• \(\mathtt{2 + 5\times 8=42}\)
• \(\mathtt{4 + 5\times 2=14}\)
• \(\mathtt{1 + 5\times 4=21}\)
• \(\mathtt{2 + 5\times 1=7}\)

jusqu’à obtenir 7.

Ecrire une fonction est_multiple_7(n) qui partant d’un entier n applique l’algorithme ci-dessus et renvoie True si n est multiple de 7 et False sinon. A l’aide d’une boucle while, on continuera le procédé jusqu’à trouver un entier à un chiffre ou bien 49.

Puissance de 2 commençant par …¶

On cherche la plus petite puissance de 2 dont l’écriture en base 10 commence par un entier donné. Par exemple, la plus petite puissance de 2 commençant par 42 est \(\mathtt{n=2^{32}=4294967296}\). On admet qu’une telle puissance de deux existe toujours.

Ecrire une fonction \(\mathtt{dominant(d)}\) qui renvoie l’exposant de la plus petite puissance de 2 qui commence par l’entier \(\mathtt{d}\). Ainsi \(\mathtt{dominant(42)}\) vaut 32. On devra en particulier déterminer \(\mathtt{dominant(2020)}\) et \(\mathtt{dominant(7629)}\).

On remarquera que les \(\mathtt{k}\) premiers chiffres d’un entier \(\mathtt{n}\) sont en fait le quotient de n par une puissance de 10 bien choisie. On pourra utiliser la fonction suivante qui retourne le nombre de chiffres d’un entier n :

from math import log10

def nb_chiffres10(n):
    return int(1+log10(n))

# Affiche 8
print(nb_chiffres10(56965011))

Nombres hautement composés¶

Un nombre entier \(\mathtt{n> 1}\) est dit hautement composé s’il contient strictement plus de diviseurs que tous les entiers \(\mathtt{m}\) tels que \(\mathtt{1\leq m< n}\). Par exemple, \(\mathtt{6}\) est hautement composé car un entier entre 1 et 5 admet au plus 3 diviseurs tandis que 6 en admet 4.

1. Ecrire une fonction diviseurs(n) qui renvoie la liste des diviseurs de l’entier n.
2. Ecrire une fonction hautementPremiers(N) qui renvoie la liste de tous les entiers hautement premiers \(\mathtt{n}\) tels que \(\mathtt{1\leq n \leq N}\). Appliquer à \(\mathtt{N=10000}\).

Billes en rectangle¶

Cet exercice n’est pas un exercice de dessin. On se donne \(N\) billes, ci-dessous \(N=12\)

et on veut les regrouper de toutes les façons possibles en rectangles de tailles \(n\times p\) (ci-dessus \(2\times 6\), \(3\times 4\)) puis sélectionner un rectangle de contour le plus petit possible (ci-dessus, les contours ont pour longueurs 16 et 14 donc le rectangle cherché est de dimensions \(3\times 4\)). On supposera que les rectangles ne sont pas aplatis.

Ecrire une fonction plus_petit_contour(N) qui renvoie la liste [n, p] formée des dimensions d’un rectangle contenant les N billes et de contour minimal. Par exemple,

• plus_petit_contour(12)=[3, 4]
• plus_petit_contour(2020)=[20, 101]
• plus_petit_contour(2024)=[44, 46]
• plus_petit_contour(6804000)=[2592, 2625]

On procédera de la manière suivante : chaque dimension du rectangle étant un diviseur de \(N\), on parcourra les diviseurs de \(N\) et pour chaque dimension possible, on recherchera l’autre dimension ce qui permettra de faire la sélection.

Elément le plus proche des éléments d’une liste¶

On donne une liste L formée de \(\mathtt{n\geq 1}\) nombres entiers, par exemple

\(\mathtt{\ds L=[32, 79, 52, 87, 59, 38, 27, 71]}\)

et on donne un entier \(\mathtt{x}\). L’objectif de l’exercice est de déterminer l’entier \(\mathtt{y}\) de la liste \(\mathtt{L}\) dont \(\mathtt{x}\) est le plus proche. En cas d’ex aequo, on prendra celui qui apparait le premier dans la liste.

Pour la liste \(\mathtt{L = [32, 79, 52, 87, 59, 38, 27, 71]}\), voici des exemples de comportement :

x = 45 -> y = 52
x = 100 -> y = 87
x = 9 -> y = 27

1. Ecrire une fonction dist(a, b) qui renvoie la distance entre deux nombres \(\mathtt{a}\) et b. On n’utilisera pas la fonction abs. Par exemple, dist(42, 30) tout comme dist(30, 42) renverront 12.

2. Ecrire une fonction plus_proche(L, x) qui renvoie le nombre y décrit au début de l’énoncé. La fonction devra utiliser la fonction dist.

   Cet exercice a été proposé sur le forum Python d’OpenClassrooms.

Elément le plus proche d’une subdivision régulière¶

On donne une liste L formée de \(\mathtt{n\geq 1}\) nombres entiers régulièrement espacés, par exemple

\(\mathtt{\ds L = [-6, 4, 14, 24, 34, 44]}\)

et on donne un entier \(\mathtt{x}\). On demande de déterminer l’entier \(\mathtt{y}\) de la liste \(\mathtt{L}\) dont \(\mathtt{x}\) est le plus proche. En cas d’égalité, on prendra le plus petit. On écrira une fonction plus_proche(L, x). Il n’y a pas de limitation sur la taille \(\mathtt{n}\) de la liste \(\mathtt{L}\). On pourra commencer par traiter les cas particuliers où \(\mathtt{x}\) n’est pas compris entre les éléments extrêmes de \(\mathtt{L}\). Ensuite, avec une division entière, on cherchera le plus grand élément de L inférieur ou égal à \(\mathtt{x}\).

Pour la liste \(\mathtt{L = [-6, 4, 14, 24, 34, 44]}\), voici des exemples de comportement :

x = -9 -> y = -6
x = -6 -> y = -6
x = 12 -> y = 14
x = 19 -> y = 14
x = 20 -> y = 24
x = 44 -> y = 44
x = 46 -> y = 44

Cet exercice a été proposé sur le forum Python d’OpenClassrooms.

Comparer des moyennes¶

Chaque semestre, Arthur passe 5 matières dont les coefficients sont

1er semestre
2, 3, 1, 1, 3

2e semestre
4, 2, 3, 3, 4

Voici ses notes pour les deux semestres de cette année, dans l’ordre des coefficients ci-dessus :

1er semestre
20, 9, 19, 16, 19

2e semestre
 3, 12, 2, 1, 11

On dispose par ailleurs de deux formules pour calculer sa moyenne :

• soit on calcule la moyenne pondérée de ses notes sur toute l’année sans tenir compte du fait qu’il y a deux semestres ;
• soit on fait la moyenne pondérée de chaque semestre puis on fait la moyenne des deux semestres.

1. Vérifier qu’avec la 1re formule, Arthur n’est pas reçu à son année tandis qu’il est reçu si on utilise la 2de formule

2. 1. Plus généralement, si le semestre 1 comporte N1 matières, le semestre 2 de N2 matières, si \(\mathtt{coeffs1}\) et \(\mathtt{coeffs2}\) sont les listes des coefficients de chaque semestre, et si \(\mathtt{notes1}\) et \(\mathtt{notes2}\) sont les listes des notes de chaque semestre, écrire une fonction \(\mathtt{compare(note1, notes2, coeffs1, coeffs2)}\) qui indique si, oui ou non, \(\mathtt{m1 \leq m2}\) où \(\mathtt{m1}\) est la moyenne obtenue par le premier calcul et \(\mathtt{m2}\) par le 2nd.

      On commencera par écrire une fonction \(\mathtt{moyenne(notes, coeffs)}\) qui calcule une moyenne pondérée d’une liste de notes de coefficients \(\mathtt{coeffs}\) et on ramènera tous les calculs de moyenne à une utilisation de cette fonction. On pouura utiliser que si L et M sont deux listes alors L+M est la concaténation des listes L et M. Tester avec les notes d’Arthur.

   2. Générer aléatoirement N1, N2, la liste des coefficients, une liste de notes et en répétant l’expérience N fois, examiner si une formule est toujours plus intéressante qu’une autre.

Fonction non injective¶

Soit la fonction mathématique \(\mathtt{f(x, y)=173xy -410x^2y^2+42y +2024x}\).

On recherche 2 points distincts à coordonnées entières, \(\mathtt{(a, b)}\) d’une part et \(\mathtt{(c, d)}\) d’autre part, tels que \(\mathtt{f(a, b)=f(c,d)}\).

Pour cela, on considère un entier \(A>0\) assez grand et un « carré » de points \(\mathtt{-A\leq x, y\leq A}\) et on parcourt les couples d’entiers \(\mathtt{x, y}\) du carré en mémorisant dans une liste V les valeurs \(\mathtt{f(x, y)}\) en les points non déjà rencontrés ainsi que, dans une 2e liste XY, les couples (x, y) correspondants et à chaque étape, on examine si la valeur de la fonction a déjà été rencontrée (grâce à la liste V) et si oui, en quel couple (grâce à la liste XY). On pourra mémoriser dans \(\mathtt{XY}\) les couples sous forme de liste [x, y].

Dans le cas de la fonction ci-dessus, on trouvera par exemple que \(\mathtt{f(0, 81)=f(-1, -2)}\).

Persistance multiplicative¶

Etant donné un entier positif \(\mathtt{n}\) écrit en base 10, on peut calculer le produit \(\mathtt{p}\) de ses chiffres. Par exemple, si \(\mathtt{n=39}\) alors \(\mathtt{p=3\times 9=27}\). La persistance multiplicative de \(\mathtt{n}\) est alors le nombre de fois qu’il faut répéter cette opération pour que le produit soit un nombre ayant un seul chiffre. Ainsi, la persistance de \(\mathtt{n=39}\) est 3 car les produits successifs sont : 39 → 27 → 14 → 4. La persistance de 5 est 0 puisqu’il n’y aucune multiplication à faire.

On aura besoin de la fonction ci-dessous :

def digits(n):
    return list(map(int, str(n)))

Cette fonction renvoie la liste des chiffres en base 10 de l’entier n. Par exemple,

digits(2024)=[2, 0, 2, 4].

1. Ecrire une fonction prod_liste(L) qui étant donné une liste L d’entiers renvoie le produit des entiers de la liste. Par exemple, prod([25, 3, 2]) = 150. On pourra considérer que si L est la liste vide alors prod_liste(L)=1.
2. Utiliser la fonction digits(n) pour écrire le code d’une fonction prod(n) qui renvoie le produit des chiffres de l’entier n.
3. 1. Écrire une fonction persistance(n) qui renvoie la persistance multiplicative de n. Ainsi, persistance(39)=3.
   2. Le nombre actuellement connu ayant la plus grande persistance est 277777788888899. Calculer sa persistance.
4. Trouver le premier entier entre 1 et 1000 ayant la plus grande persistance multiplicative.

Nombres de Catalan¶

Le nombre de Catalan d’indice \(n\), noté \(C_n\), est défini à partir des nombres de Catalan précédents. Plus précisément, \(C_1=1\) et

\(C_n=C_1\times C_{n-1}+C_2\times C_{n-2}+\cdots+C_{n-1}\times C_{1}.\)

Ainsi

• \(C_2=C_1\times C_1=1\times 1=1\),
• \(C_3=C_1\times C_2+C_2\times C_1=1\times 1+1\times 1=2\),
• \(C_4=C_1\times C_3+C_2\times C_2 + C_3\times C_1 =1\times 2+1\times 1+2\times 1=5\)
• \(C_5=C_1\times C_4+C_2\times C_3 + C_3\times C_2 + C_4\times C_1=1\times 5+1\times 2+2\times 1+ 5\times 1=14\).

Les 10 premiers nombres de Catalan sont :

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862

1. Ecrire une fonction cat(L) qui partant d’une liste L de n éléments renvoie la somme suivante :

   L[0]*L[n-1] + L[1]*L[n-2] +  L[2]*L[n-3] + ... + L[n-1]*L[0]

   Par exemple, si L=[5, 2, 4, 7, 3] alors cat(L) = 74.

2. En déduire une fonction catalan(n) qui renvoie le nombre de Catalan d’indice n. Par exemple, catalan(42) doit renvoyer 10113918591637898134020.

Nombres de Bernoulli¶

Les nombres de Bernoulli forment une suite infinie de fractions dont voici les 11 premières valeurs :

\(\displaystyle 1, \frac 12, -\frac 16, 0, -\frac 1{30}, 0, \frac 1{42}, 0, -\frac 1{30},0, \frac 5{66}, \dots\)

Ces nombres seront notés \(B_m\) où \(m=0,1,2\dots\) (noter que l’indice \(m\) commence à 0, comme pour les indices d’une liste). Chaque nombre de Bernoulli \(B_m\) (où \(m>0\)) peut se calculer à l’aide des précédents \(B_0, B_1, \dots, B_{m-1}\) grâce à la formule suivante :

\(\displaystyle (m+1)B_{m}=-\sum _{k=0}^{m-1}{m+1 \choose k}B_{k}.\)

Pour calculer explicitement \(B_m\), il suffit donc de calculer le membre de droite et de diviser le résultat obtenu par \(m+1\). Le lien Wikipédia fourni ci-dessus donne le détail du calcul de \(B_1\), \(B_2\), \(B_3\) et \(B_4\).

Ecrire un fonction bernoulli(n) qui renvoie la liste des \(\mathtt{n+1}\) premiers nombres de Bernoulli. On construira une liste initialement formée uniquement du premier nombre de Bernoullli et, à chaque étape d’une boucle, on calculera la nombre de Bernoulli courant et on l’ajoutera à la fin de la liste. Pour calculer le coefficient binomial, on importera la fonction comb du module math (on suppose que votre version de Python est au moins 3.7). Pour calculer avec des fractions et non pas des nombres flottants, on importera la classe Fraction du module standard fractions.

Vérifier que

\(B_{42}=\Frac{1520097643918070802691}{1806}.\)

Fonction binomiale¶

1. Écrire une fonction factorielle qui renvoie la valeur factorielle de n où n étant passé en paramètre. Par exemple \(1!=1\) et \(5!=120\). On convient que \(0!=1\). On écrira une version de la fonction factorielle utilisant une boucle for.

2. On rappelle que si \(n\) et \(p\) sont des entiers positifs ou nuls, le coefficient binomial est défini par

   \(\binom{n}{p}=\begin{cases}\displaystyle\frac{n!}{p!(n-p)!}& \text{si } 0\leq p\leq n\\0& \text{sinon}\end{cases}\)

   Ecrire une fonction binomial(n, p) qui renvoie le coefficient binomial ci-dessus.

3. 1. Ecrire une fonction pascal qui vérifie l’identité de Pascal : \(\binom{n}{p}+\binom{n}{p+1}=\binom{n+1}{p+1}\) valable pour tous entiers \(n, p\geq 0\).
   2. Vérifier l’identité pour tous les entiers \(n\) et \(p\) entre 0 et 100. Un mauvais codage de la question précédente pourra produite une erreur pour \(n\) un peu au delà de 50.

4. Ecrire une fonction maxBinomial(n) qui renvoie la valeur maximale de tous les coefficients binomiaux \(\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \cdots , \binom{n}{n}\)

5. Ecrire une fonction verifMaxBinomial(n) qui vérifie que la valeur maximale de tous les coefficients binomiaux \(\binom{n}{0}, \binom{n}{1}, \binom{n}{2}, \cdots, \binom{n}{n}\) est \(\binom{n}{m}\) où \(m\) est le quotient la division entière de \(n\) par 2.

Valeur approchée de \(\pi\)¶

Pour chaque entier \(n\), on considère la « somme » suivante :

\(S_n=\frac{1}{1}-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}-\cdots\pm\frac{1}{2n-1}\)

Explication : la somme alterne addition et soustraction et contient au total \(n\) fractions. Par exemple, \(S_4=\frac{1}{1}-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}\) et \(S_5=\frac{1}{1}-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}\). La dernière opération effectuée (plus ou moins) dépend de la valeur de \(n\).

1. On admet que \(4\times S_n\) est une valeur approchée de \(\pi=3,1415926\dots\) et qu’elle est d’autant meilleure que \(n\) est grand. Ecrire une fonction pi_approx(n) qui calcule \(S_n\). Calculer une valeur approchée de \(\pi\) en prenant \(n=1000\).
2. Trouver le plus petit entier \(n\) tel que l’écart entre \(S_n\) et \(3.141592\) soit inférieur à \(10^{-6}\) ?

Quotient illimité¶

On donne trois entiers \(\mathtt{a, b, n>0}\) et on demande d’écrire une fonction quo_dec(a, b, n) qui détermine la liste L des chiffres du quotient de \(\mathtt{a}\) par \(\mathtt{b}\) avec \(\mathtt{n}\) décimales. Par exemple, si \(\mathtt{a=22}\) et \(\mathtt{b=7}\) et \(\mathtt{n=20}\) on obtiendra que L vaut :

[3, 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5, 7, 1, 4]

Pour cela, on commencera par placer le quotient entier de \(\mathtt{a}\) par \(\mathtt{b}\) en première position de L et on fera suivre des décimales demandées. Pour obtenir ces décimales, on appliquera la méthode vue en classe de 6e, voir par exemple Pratique avec DÉCIMALES pour vous rafraîchir la mémoire.

a=1076825233969550892368765865908909828003038267654921050616858441627304937095412
b=342764117664681504901177527623702904503014768549643256761838650532817379076979

def list2digits(L):
    return str(L[0]) + ',' + ''.join(map(str,L[1:]))


L=[3, 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5, 7, 1, 4, 2, 8, 5, 7, 1, 4]
print( list2digits(L))

3,14285714285714285714

Nombre de Lychrel¶

1. On donne un nombre entier n par la liste L de ses chiffres en base 10, en commençant par le chiffre des unités. Par exemple, si n = 2038 alors L = [8, 3, 0, 2]. Soit m l’entier déduit de n en inversant l’ordre des chiffres de n. Par exemple, si n=2030 alors m = 302. On demande de construire la liste des chiffres de n + m. On écrira une fonction somme_miroir(n) qui renvoie la liste des chiffres de n + m. On dira que n + m est la somme en miroir de n.

2. On donne un nombre entier n par la liste L de ses chiffres en base 10. Ecrire une fonction estPalindrome(n) qui renvoie True si n est un nombre palindromique, c’est-à-dire que n = m où m l’entier déduit de n en inversant l’ordre des chiffres de n. Par exemple, 4702074 est un nombre palindromique.

3. Etant donné un entier positif n, construire la liste de ses chiffres, en commençant par le chiffre des unités. On écrira une fonction nombreChiffres(n).

   Par exemple, nombreChiffres(2038)=[8, 3, 0, 2].

4. Etant donné la liste L des chiffres d’un entier positif n (commençant par le chiffre des unités), déterminer la valeur de n. On écrira une fonction chiffresNombre(L).

   Par exemple, chiffresNombre([8, 3, 0, 2])=2038.

5. On part d’un entier n et on calcule les sommes en miroir successives en partant de n jusqu’à ce que le nombre obtenu soit une nombre palindromique (en supposant que cela se produise). Ecrire une fonction lychrel(n) qui renvoie le nombre palindromique trouvé ainsi que le nombre d’itérations. Pour n=89, on trouvera 24 itérations et pour \(\mathtt{n=10911}\), on trouvera 55 étapes.

   Pour information, un nombre de Lychrel est un entier pour lequel la suite des itérés ne donne jamais un nombre palindromique (on ne connait pour l’instant aucun tel nombre, le plus petit candidat est 196).

Racine carrée d’un nombre complexe¶

Python prend en charge la gestion des nombres complexes : le nombre complexe \(\mathtt{a+ib}\) (où \(\mathtt{a, b}\) sont réels) est défini en Python par un appel complex(a, b), ou encore par a + jb :

z1 = complex(1, -2)
z2 = 1+3j
print(z1)
print(z1 * z2)

(1-2j)
(7+1j)

On cherche à écrire notre propre fonction csqrt(z) qui renvoie une racine carrée du nombre complexe z. On utilisera le résultat mathématique suivant : si \(z=a+ib\) est un nombre complexe (\(a\) et \(b\) étant réels) alors le nombre complexe

\(Z=\sqrt{\ds\frac{a+\sqrt{a^2+b^2}}2}+i\ds\frac b{\sqrt{2(a+\sqrt{a^2+b^2})}}\)

est une racine carrée de \(z\).

On demande d’écrire une fonction csqrt(z) qui renvoie Z. On testera avec le nombre complexe \(z=7+24i\) et on devra trouver \(Z=4+3i\). On vérifiera en calculant \(Z^2\) et aussi en calculant z**0.5 (qui est permis en Python).

Tables de multiplication¶

On représente la table de multiplication d’un entier \(m\) par une liste de ces 10 premiers multiples \(m\), \(2m\), \(3m\), etc ; par exemple la table de 7 est la liste

[7, 14, 21, 28, 35, 42, 49, 56, 63, 70]

Des tables de multiplication sont représentées par une liste de tables de multiplication et donc par une liste de listes.

Ecrire une fonction tables_mult(L) qui à partir d’une liste L d’entiers strictement positifs renvoie les tables de multiplication des éléments de L. Par exemple, si L=[5, 0, 7, 42] alors table_mult(L) sera la liste suivante :

[[5, 10, 15, 20, 25, 30, 35, 40, 45, 50],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[7, 14, 21, 28, 35, 42, 49, 56, 63, 70],
[42, 84, 126, 168, 210, 252, 294, 336, 378, 420]]

Regrouper par signe¶

On donne une liste L d’entiers et on demande de regrouper les éléments de L suivant leur signe. Le regroupement sera une liste M formée de 3 objets :

• la liste N formée des éléments négatifs de L ;
• un entier z indiquant le nombre d’occurrences de zéro dans la liste L ;
• la liste P formée des éléments positifs de L.

Voici quelques exemples de comportement :

[42, -17, 33] → [[-17], 0, [42, 33]]
[42, 17, -81, 0, 33, -53, 0, 25, 0] → [[-81, -53], 3, [42, 17, 33, 25]]
[21, 23, 42] → [[], 0, [21, 23, 42]]

On ecrira une fonction signes(L) qui renverra la liste M.

Regrouper par paires¶

On donne une liste L et on demande de regrouper les éléments de L par paires d’éléments successifs. Ci-dessous quelques exemples de comportements :

[] → []
[42] → [[42]]
[42, 17] → [[42, 17]]
[42, 17, 33] → [[42, 17], [33]]
[42, 17, 33, 25] → [[42, 17], [33, 25]]

On ecrira une fonction parPaires(L) qui renverra la liste M des paires. Une paire sera une liste formée de 2 éléments successifs de L. La dernière liste de M ne contiendra qu’un seul élément si la liste L est formé d’un nombre impair d’éléments.

Chaînage par paires¶

Dans ce qui suit, partant d’une liste d’entiers L telle que

L = [15, 12, 16, 15, 10, 11]

on cherche à générer la liste suivante :

M = [[15, 12], [12, 16], [16, 15], [15, 10], [10, 11]]

Plus précisément, on donne une liste L d’entiers, et on construit la liste M formée des listes [a, b] à deux éléments a et b qui sont placés à des positions consécutives dans la liste L et où a prend toutes les positions successives possibles dans la liste L. On écrira une fonction chainage(L) qui renvoie M.

Pour information, cette fonction imite la fonction pairwise du module itertools.

Séparer suivant la parité des valeurs¶

On donne une liste L d’entiers et on demande de construire une liste P=[L0, L1] où L0 est la liste (éventuellement vide) des entiers pairs de L, placés dans leur ordre d’apparition dans L et, de même, L1 est la liste des entiers impairs de L.

Par exemple, si L=[42, 81, 31, 82, 81, 65, 9] alors P=[[42, 82], [81, 31, 81, 65, 9]].

On construira une fonction separer(L) qui renverra P.

Séparer des entiers selon la parité des indices¶

On donne une liste L d’entiers et on demande de placer dans une liste C deux listes :

• la première contient les entiers de L placés à un indice pair,
• la deuxième contient les entiers de L placés à un indice impair.

Par exemple si L=[42, 81, 31, 42, 2019, 2024, 33] alors

C=[[42, 31, 2019, 33], [81, 42, 2024]]

On écrira une fonction separerIndices(L) qui renverra C.

Pivot¶

1. On donne une liste d’entiers, par exemple L=[24, 81, 12, 12, 42, 31, 82, 75, 42, 13]. On donne un entier p de la liste L, qu’on appelera le pivot, par exemple p=42. On demande de construire deux listes d’entiers A et B où

   • la liste A est formée des entiers x de L tels que \(\mathtt{x<p}\),
   • la liste B est formée des entiers x de L tels que \(\mathtt{x>p}\).

   On écrira une fonction separer(L, p) qui renverra la liste [A, B]. Dans le cas de l’exemple, la liste renvoyée sera :

   [[24, 12, 12, 31, 13], [81, 82, 75]]
   

   Si les listes en compréhension vous sont connues, vous les utiliserez.

2. Ecrire une fonction npivots(L, p) utilisant la fonction separer() et renvoyant le nombre d’éléments de L dont la valeur est p. Dans le cas de l’exemple, npivots(L, p) vaudra 2.

Décompression de liste¶

On donne une liste L de listes de deux éléments, par exemple

L=[["Pomme", 2], ["Kiwi", 3], ["Orange", 0], ["Poire", 2]]

Chaque liste de deux éléments dans L est formée d’une chaîne de caractères s et d’un entier positif ou nul n. On demande de contruire une liste M de chaînes contenant pour chaque liste [s, n] figurant dans L, la chaîne s mais répétée n fois.

Avec l’exemple ci-dessus, la liste M attendue est :

['Pomme', 'Pomme', 'Kiwi', 'Kiwi', 'Kiwi', 'Poire', 'Poire']

Séparer les abscisses et les ordonnées¶

On donne une liste L de points du plan, chaque point étant donné par une liste de ses deux coordonnées. Ecrire une fonction separer(L) qui renvoie la liste formée de deux listes suivantes :

• la liste des abscisses des points de L, dans leur ordre d’apparition dans L
• la liste des ordonnées des points de L, dans leur ordre d’apparition dans L.

Par exemple, si L est la liste suivante

L = [[4, 9], [-2, -3], [0, -3], [2038, 2048]]

alors, separer(L) doit renvoyer la liste suivante :

[[4, -2, 0, 2038], [9, -3, -3, 2048]]

Si cette notion vous est connue, il est possible de donner une solution utilisant une liste en compréhension.

Rectangle à partir d’une de ses diagonales¶

Cet exercice n’est pas un exercice de dessin

Un point du plan est représenté par une liste de deux entiers. Par exemple, le point d’abscisse 42 et d’ordonnée 81 est représenté par la liste [42, 81].

On considère un rectangle dont les sommets sont des points à coordonnées entières. On donne les coordonnées de deux extrémités D1 et D2 d’une de ses deux diagonales. On demande d’écrire une fonction sommets(D1, D2) qui renvoie la liste des 4 sommets du rectangle correspondant, en commençant par le sommets D1 et en sorte que les sommets soient listés dans le sens des aiguilles d’une montre.

Par exemple, si D1 = [6, 1] et D2 = [3, 5] alors sommets(D1, D2) sera la liste suivante :

[[6, 1], [3, 1], [3, 5], [6, 5]]

Reconstruire les sommets d’un rectangle¶

Cet exercice n’est pas un exercice de dessin.

Un point du plan est représenté par une liste de deux entiers. Par exemple, le point d’abscisse 42 et d’ordonnée 81 est représenté par la liste [42, 81].

On considère un rectangle ABCD dont les sommets sont à coordonnées entières et dont les côtés AB, BC, CD et DA sont parallèles aux axes. On donne une liste L=[x1, x2, y1, y2] où

• x1 est la plus petite des abscisses des sommets du rectangle,
• x2 est la plus grande des abscisses des sommets du rectangle,
• y1 est la plus petite des ordonnées des sommets du rectangle,
• y2 est la plus grande des ordonnées des sommets du rectangle.

On demande de déterminer la liste des sommets [A, B, C, D] du rectangle. Le premier sommet A de la liste sera le sommet placé en bas à gauche. Les sommets seront listés dans le sens inverse des aiguilles d’une montre. Chaque sommet sera représenté par une liste [x, y] des coordonnées du sommet.

On écrira une fonction rect(L) où L sera la liste L=[x1, x2, y1, y2].

Par exemple, si L=[3, 6, 1, 5] alors rect(L) sera la liste

[[3, 1], [6, 1], [6, 5], [3, 5]]

Jeu de cartes¶

Une carte à jouer, par exemple le Valet de Pique, sera vue comme une liste de deux chaînes, dans l’exemple ce sera

ma_carte = ["Valet", "Pique"]

Un jeu de 32 ou 52 cartes sera simplement vu comme une liste Python de toutes les cartes et donc une liste de listes de deux chaînes. Ecrire une fonction jeu_cartes(n) qui génère et renvoie un jeu de n cartes où n vaut 32 ou 52. On utilisera une liste de valeurs et d’enseignes :

VALEURS = ["As", "Deux", etc, "Dame", "Roi"]
ENSEIGNES = ["Pic", "Cœur", "Carreau", "Trèfle"]

Evénement périodique¶

Imaginons un événement se répétant régulièrement un certain nombre de fois dans la journée à partir d’une certaine heure ; on cherche à générer la liste des moments de la journée où l’événement se produit. Par exemple, si un événement se produit 7 fois à partir de 13h15 tous les 2h15, la liste cherchée sera :

[[13, 15], [15, 30], [17, 45], [20, 0], [22, 15], [0, 30], [2, 45]]

ce qui se comprend : 13h15, puis 15h30, puis 17h45, etc. jusqu’à 2h45.

On notera qu’on indique une heure de la journée par [h, m] où le nombre d’heures vérifie \(\mathtt{0\leq h<24}\) et le nombre de minutes vérifie \(\mathtt{0\leq m<60}\).

Plus précisément, on donne

• une période de temps \(\mathtt{T}\), en heures et minutes, sous forme de liste, par exemple [1, 15] pour traduire 1 h 15 min ;
• un moment de départ, sous la forme d’une liste indiquant l’heure en heures et minutes, par exemple [15, 30] signifie 15 h 30 ;
• un entier désignant le nombre de fois qu’on va répéter la période, par exemple n=6.

On demande de produire les \(\mathtt{n}\) moments de la journée où l’événement a lieu. On écrira une fonction.

Nom de qui a la meilleure note¶

On donne une liste L formée de listes de deux éléments :

• le premier est un nom
• le second est une note,

par exemple :

L =[
["Florian", 12], ["Ambre", 13],
["Emile", 5], ["Emma", 13],
["Aristide", 7]]

Ecrire une fonction nom_meilleure_note(L) qui renvoie le nom de la personne qui a eu la meilleure note. Si la meilleure note a été obtenue plusieurs fois, le nom donné sera le dernier de la liste. Avec la liste ci-dessus, la fonction doit renvoyer la chaîne "Emma".

Cette question a été discutée sur le forum Python d’OpenClassrooms.

Moyenne pondérée¶

On donne une liste formée de notes pondérées, une note pondérée étant une liste formée d’une note entière entre 0 et 20 et d’un coefficient associé à la note.

On demande de calculer la moyenne de la liste de notes pondérées. On arrondira cette moyenne à 2 chiffres après la virgule, comme le montre l’exemple ci-dessous :

print(round(10.357142857142858,2))

10.36

Si on prend la liste des 5 notes pondérées ci-dessous :

[14, 3]
[8, 4]
[12, 4]
[7, 2]
[9, 1]

on obtiendra une moyenne de 10,36.

On écrira une fonction myn(N) où N est un liste de notes pondérées autrement dit une liste de listes de deux éléments, le premier élément étant une note, le second étant le coefficient.

Séparer des entiers suivant leur nombre de chiffres¶

1. On donne une liste d’entiers positifs et on demande de placer dans une liste C quatre listes :

   • la première contient les entiers de L ayant 1 seul chiffre
   • la deuxième contient les entiers de L ayant 2 chiffres
   • la troisième contient les entiers de L ayant 3 chiffres
   • la dernière contient les autres nombres.

   Par exemple si L=[42, 81, 5, 2019, 424242, 2020, 2024] alors

   C=[[5], [42, 81], [], [2019, 424242, 2020, 2024]].

   On écrira une fonction separer(L).

2. Ecrire une fonction maj(L) utilisant la fonction separer(L) qui renvoie True si les nombres ayant au moins 4 chiffres sont majoritaires dans L et qui renvoie False sinon.

Liste des diviseurs¶

1. On donne une liste L d’entiers strictement positifs et on demande d’écrire un code qui génère une liste D des listes de diviseurs de chaque entier de L. On rappelle que d est un diviseur de N signifie juste que N est un multiple de d autrement dit que \(\mathtt{N=d\times q}\) pour un certain entier q. Par exemple, si L=[2019,2027, 43, 25] alors

   D=[[1, 3, 673, 2019], [1, 2027], [1, 43], [1, 5, 25]].

   On écrira une fonction div(L). Les diviseurs apparaîtront dans l’ordre croissant.

2. Utiliser la fonction précédente pour générer une liste P des nombres premiers de L. On rappelle qu’un nombre premier p (par exemple 43 mais pas 42) est un entier p>1 et admettant exactement deux diviseurs strictement positifs, à savoir lui-même p et 1. Dans l’exemple ci-dessus, on obtiendra que P=[2027, 43].

Statistiques sur des contrôles¶

Ci-dessous, le tableau des notes sur 20 de 12 étudiants aux 3 contrôles d’une UE :

Lorsqu’un contrôle reçoit la valeur -1 c’est que l’étudiant est absent. Si un étudiant est absent à au moins un contrôle, il est considéré comme absent à l’UE et ne reçoit pas de moyenne. Noter qu’en fait les notes de chaque étudiant sont accessibles via un indice i qui varie entre 1 et le nombre n d’étudiants, dans l’exemple c’est n=12. Noter que les identifiants commencent à 1 et pas à 0.

La liste des notes des étudiants de l’exemple est donnée dans la cellule ci-dessous. Le prénom des étudiants n’est pas utilisé, seul leur identifiant servira dans la suite. Noter que les notes du premier étudiant (indice 0) de la liste sont les notes de l’étudiant d’identifiant 1 (et non pas 0).

notes=[[12, 5,  11] ,
[18, 17, 16],
[-1, 9, -1],
[8, 12, 15],
[2, 4, 5],
[10, 10, 11],
[7, 7, 5],
[20, 20, 20],
[14, -1, -1],
[15, 18, 13],
[12, 11, -1],
[-1, 5, -1]]

Dans les questions ci-dessous, votre code doit être capable de traiter les situations les plus générales : un nombre quelconque d’étudiants, un nombre quelconque de contrôles.

1. Ecrire une fonction moyenne(i, notes) qui calcule la moyenne de l’étudiant d’identifiant donné \(\mathtt{i\geq 1}\) dans une liste appelée notes. Dans l’exemple, Marc, d’identifiant 2, a 17 de moyenne donc moyenne(2, notes) renvoie 17.
2. Ecrire une fonction absents(notes) qui retourne une liste de listes, chaque liste donnant les identifiants des étudiants absents au 1er, 2e, etc contrôle. Dans l’exemple, absents(notes) renvoie la liste [[3, 12], [9], [3, 9, 11, 12]].
3. Ecrire une fonction moyenne_eme_controle(notes, nro) qui renvoie la liste des id d’étudiants ayant eu au moins la note de 10 au contrôle identifié par le numéro valant nro (donc numéro 1 pour le premier contrôle, numéro 2 pour le deuxième, etc). Avec l’exemple ci-dessus et nro=2, on devra obtenir : [2, 4, 6, 8, 10, 11].

Relevé de températures¶

On relève la température pendant une semaine dans 4 villes ce qui donne le tableau suivant :

Il s’agit juste d’un exemple avec 4 villes et votre code doit fonctionner pour un nombre quelconque de villes.

Chaque ville est repérée par un indice commençant à 0 (on ne tiendra pas compte des noms de villes). Les températures relevées sont fournies dans une liste de 7 entiers. Le relevé est donné par une liste de listes. Dans l’exemple ci-dessus, cette liste est :

releve=[
[28, 25, 29, 31, 33, 32, 35],
[27, 26, 30, 29, 32, 34, 34],
[24, 22, 27, 28, 28, 31, 31],
[25, 24, 27, 27, 27, 28, 32]]

1. Ecrire une fonction tempMax(releve) qui renvoie une liste [t, j, v] où t est la température maximale du relevé, j l’indice du jour de la semaine (entre 0 et 6) correspondant à la température maximale et v le numéro de la ville (à partir de 0) où cette température a été relevée. Dans l’exemple, ci-dessus, l’appel renverra la liste suivante :

   [35, 6, 0]
   

2. Ecrire une fonction maxiJour2ville(releve, j) qui à partir d’un indice j de jour de la semaine (entre 0 et 6) renvoie le numéro de la ville (à partir de 0) où il a fait le plus chaud le jour j.

   Par exemple, si j = 2 (mercredi) alors c’est à Castres qu’il a fait le plus chaud donc la réponse attendue est 1.

Transposer une liste de listes¶

On se donne un tableau L d’entiers de \(\mathtt{n}\) lignes et \(\mathtt{p}\) colonnes vu comme une liste de \(\mathtt{n}\) listes ayant chacune \(\mathtt{p}\) entiers. Par exemple, le tableau :

4 6 9
7 0 6
9 1 2
1 3 6

est représenté par la liste Python :

L = [[4, 6, 9], [7, 0, 6], [9, 1, 2], [1, 3, 6]]

On appelle transposé du tableau L le tableau obtenu en échangeant les lignes et les colonnes : la première ligne du transposé de L est la première colonne de L, et ainsi de suite. Dans l’exemple, c’est le tableau

4 7 9 1
6 0 1 3
9 6 2 6

représenté par la liste Python :

[[4, 7, 9, 1], [6, 0, 1, 3], [9, 6, 2, 6]]

Ecrire une fonction transposer(L) qui renvoie le tableau transposé du tableau L. Vérifier que si l’on transpose deux fois de suite, on retombe sur le tableau initial.

Scinder une liste en deux¶

On donne une liste \(\mathtt{L}\) et un entier positif m et on cherche à contruire une liste [L1, L2] où \(\mathtt{L1}\) est la liste des m premiers éléments de \(\mathtt{L}\) et \(\mathtt{L2}\) est la liste formée des autres éléments de \(\mathtt{L}\). Si \(\mathtt{m\geq n}\) où \(\mathtt{n}\) est la longueur de la liste \(\mathtt{L}\) alors on supposera que \(\mathtt{L1=L}\) et que \(\mathtt{L2}\) est vide. Voici quelques exemples de comportements :

L = [8, 3, 8, 1, 6, 7] , m = 2 → [[8, 3], [8, 1, 6, 7]]
L = [3, 1, 4, 3, 4, 6] , m = 3 → [[3, 1, 4], [3, 4, 6]]
L = [2, 1, 5, 5, 9, 8] , m = 7 → [[2, 1, 5, 5, 9, 8], []]

Ecrire une fonction scinder(L, m) qui renvoie la liste [L1, L2].

Diagonale descendante d’une grille¶

On vous donne un tableau 2D d’entiers sous la forme d’une liste L de listes, par exemple le tableau à 7 lignes et 4 colonnes suivant :

L=[
[95, 42, 31, 98],
[50, 98, 60, 41],
[85, 94, 15, 90],
[83, 42, 38, 33],
[69, 96, 70, 23],
[90, 27, 10, 24],
[46, 81, 55, 29]]

print(L)

On vous donne une position d’indice de ligne i et d’indice de colonne j, par exemple i=3 et j=1 dans le tableau ci-dessus et qui contient l’élément 42.

On demande de déterminer, sous forme de liste, les éléments du tableau L qui se trouvent sur la diagonale descendante contenant la case du tableau d’indices i et j. Avec l’exemple ci-dessus, la liste attendue est :

[85, 42, 70, 24]

On écrira une fonction diagDesc(L, i, j) qui renverra la liste demandée.

On pourra énumérer les éléments de la diagonale dans l’ordre de son choix.

Pour écrire le code, on utilisera que les cases d’indices u et v de la diagonale de L, descendante et contenant la case d’indices i et j vérifient exactement la relation u - v = i - j. Ainsi, dans l’exemple ci-dessus, la case d’indices u=5 et v=3 est bien sur la diagonale puisque u - v = 5 - 3 = 2 et i - j = 3 - 1 = 2.

Matrice de covariance¶

Si \(\mathtt{Z}\) est une liste de \(\mathtt{n}\) nombres, on appelle moyenne de \(\mathtt{Z}\) le nombre \(\mathtt{moy(Z)}\) suivant

\(\mathtt{moy(Z)=\frac 1n \left( Z[0]+Z[1]+\dots + Z[n-1]\right)}\)

Si \(\mathtt{X}\) et \(\mathtt{Y}\) sont deux listes de nombres, de même taille \(\mathtt{n}\), et de moyennes notée \(\mathtt{mX}\) et \(\mathtt{mY}\), on appelle covariance de \(\mathtt{X}\) et \(\mathtt{Y}\) le nombre \(\mathtt{cov(X, Y)}\) :

\(\mathtt{cov(X, Y)=\frac 1{n-1} \left((X[0]-mX)(Y[0]-mY)+\dots + (X[0]-mX)(Y[0]-mY)\right)}\)

On donne une liste \(\mathtt{L}\) de \(\mathtt{p}\) listes de nombres, chacune de longueur \(\mathtt{n}\). On appelle matrice de covariance de \(\mathtt{L}\) la liste \(\mathtt{C}\) de \(\mathtt{p}\) listes, chacune de longueur \(\mathtt{p}\) telle que pour tous indices \(\mathtt{i, j=0,\dots, p-1}\) :

\(\mathtt{C[i][j]=cov(L[i], L[j])}\)

Ecrire une fonction mat_cov(L) qui renvoie cette matrice. On pourra écrire des fonction auxiliaires et on veillera à ne pas répéter inutilement certains calculs.

Par exemple, si L est la liste suivante :

[[ 64.  66.  68.  69.  73.]
 [580. 570. 590. 660. 600.]
 [ 29.  33.  37.  46.  55.]]

alors la matrice de covariance est

[[  11.5    50.     34.75]
 [  50.   1250.    205.  ]
 [  34.75  205.    110.  ]]

Triangle de Floyd vertical avec liste de listes¶

Soit le triangle de Floyd vertical à \(\mathtt{n=9}\) lignes :

1
2 10
3 11 18
4 12 19 25
5 13 20 26 31
6 14 21 27 32 36
7 15 22 28 33 37 40
8 16 23 29 34 38 41 43
9 17 24 30 35 39 42 44 45

Plus généralement, soit le motif consistant en un triangle formé de \(n\) lignes et de \(n\) colonnes et composé d’entiers consécutifs à partir de 1 et disposés en colonnes de la manière suivante :

• on lit les \(n\) premiers entiers à partir de 1 dans la première colonne,
• on lit les \(n-1\) entiers suivants dans la 2e colonne à partir de la 2e ligne,
• et ainsi de suite jusqu’à la dernière colonne qui ne contient qu’un seul entier.

On demande d’écrire un code qui pour un entier \(\mathtt{n\geq 1}\) donné construise la liste de listes d’entiers représentant le triangle de Floyd vertical à \(\mathtt{n}\) lignes. Par exemple, pour \(\mathtt{n=4}\), le motif est

1
2 5
3 6 8
4 7 9 10

et la liste recherchée est :

[[1], [2, 5], [3, 6, 8], [4, 7, 9, 10]]

Transformation du boustrophédon¶

On demande de construire un triangle de nombres dont voici les 8 premières lignes :

1
0   1
1   1   0
0   1   2   2
5   5   4   2   0
0   5   10  14  16  16
61  61  56  46  32  16  0
0   61  122 178 224 256 272 272

La construction du triangle suit le procédé d’écriture précisé ci-dessous :

• Chaque ligne contient autant de nombres que sa position, ie la \(\mathtt{n}\)-ème ligne contient \(\mathtt{n}\) entiers
• Les lignes de rang pair s’écrivent de gauche à droite, les lignes de rang impair de droite à gauche
• La première ligne contient uniquement 1
• Dans chaque ligne à partir de la 2e, le premier nombre écrit est 0
• Chaque nombre de chaque ligne, à partir du 2e, s’obtient en ajoutant le dernier que l’on a écrit et celui qui se trouve derrière et au-dessus du nombre à écrire.

Dans le tableau ci-dessus, par exemple :

• 7e ligne : \(\mathtt{46=32+16}\)
• 8e ligne : \(\mathtt{178=122+46}\).

On écrira une fonction boustrophedon(n) qui affichera les \(\mathtt{n}\) premières lignes du triangle.

Rotation horaire d’une matrice carrée¶

Ecrire une fonction rotate(M) qui étant donné une matrice carrée M renvoie la matrice déduite de M par rotation d’un quart de tour dans le sens des aiguilles d’une montre.

Par exemple, voici une matrice M et la matrice rotate(M) :

\(M=\left(\begin{array}{rrrrrr}23 & 51 & 75 & 50 & 56 & 94 \\52 & 93 & 97 & 17 & 99 & 79 \\21 & 33 & 61 & 97 & 82 & 10 \\42 & 69 & 20 & 18 & 80 & 69 \\54 & 58 & 54 & 86 & 20 & 44 \\23 & 12 & 41 & 53 & 27 & 78\end{array}\right)\quad N=\left(\begin{array}{rrrrrr}23 & 54 & 42 & 21 & 52 & 23 \\12 & 58 & 69 & 33 & 93 & 51 \\41 & 54 & 20 & 61 & 97 & 75 \\53 & 86 & 18 & 97 & 17 & 50 \\27 & 20 & 80 & 82 & 99 & 56 \\78 & 44 & 69 & 10 & 79 & 94\end{array}\right)\)

(cf. ci-dessous pour pouvoir récupérer les valeurs de cet exemple).

En déduire une fonction antiRotate(M) qui renvoie la matrice déduite de M par rotation d’un quart de tour dans le sens inverse des aiguilles d’une montre.

Ci-dessous, les valeurs utilisables dans un code Python de la matrice qui a été donnée en exemple :

[[23, 51, 75, 50, 56, 94],
 [52, 93, 97, 17, 99, 79],
 [21, 33, 61, 97, 82, 10],
 [42, 69, 20, 18, 80, 69],
 [54, 58, 54, 86, 20, 44],
 [23, 12, 41, 53, 27, 78]]

Remplir une matrice en diagonale¶

1. Écrire une fonction remplirDiagonale(A, lig, col, k)

   • qui remplit, par les entiers consécutifs à partir de l’entier \(\mathtt{k}\), la partie de la diagonale montante de \(\mathtt{A}\) commençant à la position d’indices (lig, col)
   • qui renvoie la dernière valeur inscrite dans la diagonale.

   Par exemple, si \(\mathtt{A}\) est la matrice nulle de taille \(\mathtt{8\times 9}\) alors remplirDiagonale(A, 5, 2, 81) renverra \(\mathtt{86}\) et la matrice \(\mathtt{A}\) sera remplie comme suit :

   0 0  0  0  0  0  0 86 0
   0 0  0  0  0  0 85  0 0
   0 0  0  0  0 84  0  0 0
   0 0  0  0 83  0  0  0 0
   0 0  0 82  0  0  0  0 0
   0 0 81  0  0  0  0  0 0
   0 0  0  0  0  0  0  0 0
   0 0  0  0  0  0  0  0 0
   

   On utilisera une boucle while dont la condition garantira que la progression sur la diagonale reste bien à l”intérieur de la matrice.

2. Écrire une fonction remplirEnDiagonales(n, p), qui à partir de deux entiers \(\mathtt{n,p>0}\), construit la matrice \(\mathtt{M}\) de taille \(\mathtt{n\times p}\) et remplit, suivant ses diagonales montantes, par les entiers consécutifs \(\mathtt{0, 1, 2, \dots, np-1.}\)

   Par exemple, si \(\mathtt{n=5}\) et \(\mathtt{p=4}\), la matrice \(\mathtt{M}\) à obtenir doit s’afficher comme suit :

    0  2  5  9
    1  4  8 13
    3  7 12 16
    6 11 15 18
   10 14 17 19
   

Somme des carrés des éléments d’une matrice¶

1. Ecrire une fonction f(M) qui renvoie la somme des carrés de chacun des termes d’une matrice carrée \(\mathtt{M}\).
2. Ecrire une fonction g(M) qui renvoie la trace de la matrice \(\mathtt{M\trans{M}}\) où \(\mathtt{\trans{M}}\) désigne la transposée de \(\mathtt{M}\). On rappelle que la trace d’une matrice carrée est la somme des éléments de sa diagonale principale.
3. En testant sur 100 matrices carrées aléatoires M, de taille aléatoire \(\mathtt{n\in\ens{1,\dots, 10}}\), vérifier que les nombres f(M) et g(M) sont égaux.

Matrice à symétrie verticale¶

1. Ecrire une fonction colEgales(M, j, k) où M est une matrice et qui renvoie True si les colonnes de M d’indices j et k sont égales et False sinon. Par exemple, si M est la matrice ci-dessous :

   1 5 2 5
   0 4 3 4
   2 8 9 8
   0 4 6 4
   

   alors colEgales(M, 1, 3) renvoie True.

2. Observez les matrices suivantes ; les deux premières admettent une symétrie verticale mais pas la dernière :

   1 5 3 5 1
   0 4 6 4 0
   2 8 0 8 2
   0 4 5 4 0
   

   1 5 5 1
   0 4 4 0
   2 8 8 2
   0 4 4 0
   

   1 1
   4 0
   

   Ecrire une fonction estSymVert(M) qui renvoie True si M admet une symétrie verticale et False sinon. Tester et afficher.

Border une matrice par des zéros¶

Soit \(\mathtt{A}\) une matrice. Ecrire une fonction \(\mathtt{b(A)}\) qui renvoie la matrice \(\mathtt{B}\) obtenue à partir de \(\mathtt{A}\) en bordant de \(\mathtt{0}\) la matrice \(\mathtt{A}\). Par exemple, si \(\mathtt{A}\) est la matrice :

23  5  7 14 16
 4  6 13 20 22
10 12 19 21  3
11 18 25  2  9

alors \(\mathtt{b(A)}\) est la matrice suivante

0  0  0  0  0  0 0
0 23  5  7 14 16 0
0  4  6 13 20 22 0
0 10 12 19 21  3 0
0 11 18 25  2  9 0
0  0  0  0  0  0 0

Retirer le bord d’une matrice¶

Soit \(\mathtt{A}\) une matrice. Ecrire une fonction \(\mathtt{r(A)}\) qui renvoie la matrice \(\mathtt{B}\) obtenue à partir de \(\mathtt{A}\) en retirant le pourtour de \(\mathtt{A}\) ie la première et la dernière colonne et la première et la dernière ligne. Par exemple, si \(\mathtt{A}\) est la matrice :

23  5  7 14 16
 4  6 13 20 22
10 12 19 21  3
11 18 25  2  9

alors \(\mathtt{r(A)}\) est la matrice suivante

 6 13 20
12 19 21

Matrice magique¶

On donne une matrice de taille \(\mathtt{n\times p}\). On note \(\mathtt{N=np}\), par exemple, si \(\mathtt{n=2}\) et \(\mathtt{p=3}\) alors \(\mathtt{N=6}\). On dit qu’une matrice \(\mathtt{A}\) de taille \(\mathtt{n\times p}\) est bien remplie si ses coefficients sont tous les entiers entre 1 et \(\mathtt{N}\). Par exemple, la matrice suivante, de taille \(\mathtt{2\times 3}\) est bien remplie :

4 1 6
2 5 3

1. Ecrire une fonction qui f(A) qui dit si une matrice \(\mathtt{A}\) est bien remplie.

2. Une matrice carrée de taille \(\mathtt{n\times }\) est dite magique si les \(\mathtt{(2n+2)}\) sommes suivantes sont toutes égales entre elles :

   • la somme de n’importe quelle ligne
   • la somme de n’importe quelle colonne
   • la somme de l’une des deux diagonales

   Par exemple, la matrice suivante est magique :

   17 24  1  8 15
   23  5  7 14 16
    4  6 13 20 22
   10 12 19 21  3
   11 18 25  2  9
   

   Ecrire une fonction estMagique(A) qui dit si une matrice \(\mathtt{A}\) est magique.

Demi-carré en mode texte de hauteur variable¶

On donne un entier \(n\geq 0\). On demande d’écrire un code qui affiche un demi-carré rempli par des caractères X et s’étendant sur \(n\) lignes.

Par exemple, si \(n=5\), le code doit afficher :

X
X X
X X X
X X X X
X X X X X

Générer un motif en forme de croix¶

1. On vous donne un entier impair \(n>1\) et vous devez générer un motif rempli d’un zéro et de uns. Par exemple, si \(n=9\), le motif a la forme suivante :

   1 1 1 1 0 1 1 1 1
   

   Ecrire une fonction ligne(n) qui affiche le motif. On pourra supposer que n est toujours impair. Le motif est une ligne formée de \(n\) chiffres valant 0 ou 1. Deux chiffres seront toujours séparés d’un unique espace. Le chiffre au milieu de la ligne vaut 0 et les autres valent 1.

2. Vous allez devoir créer une fonction croix(n) qui devra invoquer la fonction précédente pour générer un motif en forme de croix décrit ci-après. On part d’un entier impair \(n>1\) et le motif est de forme carrée, rempli de zéros ou de uns, en sorte que les zéros forment une croix. Par exemple, si \(n=9\), le motif est généré par l’appel croix(9) :

   1 1 1 1 0 1 1 1 1
   1 1 1 1 0 1 1 1 1
   1 1 1 1 0 1 1 1 1
   1 1 1 1 0 1 1 1 1
   0 0 0 0 0 0 0 0 0
   1 1 1 1 0 1 1 1 1
   1 1 1 1 0 1 1 1 1
   1 1 1 1 0 1 1 1 1
   1 1 1 1 0 1 1 1 1
   

   Le motif est un carré formé de \(n\times n\) chiffres valant 0 ou 1. Deux chiffres seront toujours séparés d’un unique espace. Les axes vertical et horizontal de symétrie du carré sont formés de 0 et les autres parties du carré sont formées de 1.

Motif triangulaire de nombres¶

Dans cet exercice, vous allez devoir afficher un motif dépendant d’un entier \(n\). Par exemple, pour \(n=6\) le motif est le carré suivant :

1 0 0 0 0 0
1 2 0 0 0 0
1 2 3 0 0 0
1 2 3 4 0 0
1 2 3 4 5 0
1 2 3 4 5 6

Ecrire une procédure motif prenant un paramètre entier \(n\geq 0\) et qui affiche une suite de \(n\) lignes telle que la \(k\)-ième ligne (pour chaque \(k\) entre 1 et \(n\)) soit formée de \(n\) nombres entiers organisés de la façon suivante :

• chaque ligne commence par la suite des \(k\) premiers entiers : \(1\), \(2\), etc. jusqu’à \(k\)
• la ligne est ensuite complétée par des zéros.

Les nombres dans chaque ligne seront séparés par une espace.

L’exemple ci-dessus correspond à ce qu’affiche motif(6).

Triangle d’entiers consécutifs¶

On demande d’afficher un motif de \(n\) lignes, par exemple pour \(n=5\) le motif sera :

1
1 2 1
1 2 3 2 1
1 2 3 4 3 2 1
1 2 3 4 5 4 3 2 1

Plus précisément, écrire une fonction triangle_entiers(n) qui affiche n lignes formées d’entiers disposés de la manière suivante :

la k-ème ligne énumère les entiers de 1 à k dans l’ordre croissant puis les énumère en décroissant jusqu’à 1.

Suite de Prouhet¶

La suite de Prouhet est une suite de motifs formée de 0 et de 1. Ci-dessous, les 4 premiers motifs :

0
0 1
0 1 1 0
0 1 1 0 1 0 0 1

Cette suite est une suite de motifs composés de 0 et de 1 de la manière suivante : chaque motif T s’obtient à partir du précédent U en adjoignant à U la suite V obtenue à partir de U en échangeant tout 0 en 1 et tout 1 en 0.

Par exemple, ci-dessus, la suite 0 1 1 0 1 0 0 1 est obtenue :

• à partir de la suite précédente U = 0 1 1 0
• en construisant, à partir de la suite U, la suite inversée V = 1 0 0 1
• en mettant bout à bout U et V

1. Ecrire une fonction prouhet(n) qui renvoie sous forme de liste de 0 et de 1, le i-ème motif de la suite de Prouhet. Par exemple, prouhet(4) vaudra la liste [0, 1, 1, 0, 1, 0, 0, 1].
2. Ecrire une fonction afficher_liste(L) qui affiche horizontalement une liste L de nombres en séparant deux nombres voisins dans la liste par un espace.
3. Afficher les 5 premières lignes de la suite de Prouhet avec la fonction afficher_liste.

Pyramide de disques¶

On cherche à dessiner une pyramide en utilisant une fonction qui va afficher les lignes de la pyramide.

1. Ecrire une fonction \(\mathtt{f}\) qui dessine, à partir d’une position donnée un alignement horizontal de \(\mathtt{n}\) disques tangents, de couleur noire et tous de même rayon \(\mathtt{r}\). Plus précisément, \(\mathtt{f}\) prendra en paramètres \(\mathtt{x}\), \(\mathtt{y}\), \(\mathtt{n}\) et \(\mathtt{r}\) où le couple \(\mathtt{(x,y)}\) désigne les coordonnées du centre du premier disque (le plus à gauche), \(\mathtt{n}\) est le nombre de disques à dessiner et \(\mathtt{r}\) le rayon de chaque disque.

   

2. Ecrire une fonction \(\mathtt{g(h,r)}\) qui dessine une pyramide de base horizontale, formée d’une hauteur de \(\mathtt{h}\) disques, tous de rayon \(\mathtt{r}\) . Par exemple, \(\mathtt{g(5, 20)}\) affichera la pyramide ci-contre. La fonction \(\mathtt{g}\) appelera la fonction \(\mathtt{f}\).

   

Carrés emboîtés¶

1. Cette question a pour objet de faire dessiner un carré de côté de longueur donnée et dont un des sommets est \((0, 0)\). Plus précisément, écrire une fonction carre(a) qui prend en paramètre un entier \(a>0\) et dessine le carré de côtés parallèles aux axes, dont le sommet en haut à gauche est \((0,0)\) et de côté de longueur \(a\). Par exemple, un appel tel que carre(100) doit dessiner une figure comme ci-dessous :

   

2. Utiliser la fonction carre(a) pour dessiner un motif formé de \(n\) carrés emboîtés comme ci-dessous. Le côté OA du carré initial ainsi que les distances, comme la distance ST, entre deux carrés successifs, seront toutes identiques à une valeur \(c\) que vous choisirez librement. Dans le dessin ci-dessous, on a choisi \(n=8\) et \(c=15\).

   

Paintball¶

Cet exercice simule un séquence de tirs à billes sur un carton portant une cible :

1. Dessiner une cible bicolore de couleurs jaune et noir alternées constituée de \(n\) disques concentriques. Le disque central est de couleur jaune et de rayon r et le rayon de chaque disque augmente de r en même temps qu’il change de couleur. La cible est parfaitement ajustée dans un carton carré de fond gris. On écrira une fonction cible(n, r).

2. Un joueur tire au hasard à l’intérieur du carton (ou sur le bord du carton) \(N\) billes de couleur rouge. Ecrire une fonction tirs(N, R) qui dessine le carton, la cible et les impacts des billes. On utilisera la fonction uniforme(a, b) du module random qui génère un flottant aléatoire entre les deux valeurs a et b

   Voici un exemple de sortie attendue :

   

3. Un joueur effectue N tirs aléatoires dans le carton. On vous demande d’écrire de modifier la fonction précédente pour qu’elle montre la cible mais aussi calcule et affiche le nombre de billes qui ont atteint la cible, autrement dit qui sont dans une zone colorée.

   On rappelle que la distance de l’origine \((0,0)\) au point de coordonnées \((x,y)\) est donnée par la formule \(\displaystyle\sqrt{x^2+y^2}\)

   Dans l’exemple présenté à la question 2, le nombre à trouver est 6.

Déplacement vertical¶

Dans cet exercice, on demande de dessiner le mouvement d’un mobile quand il suit des directions données dans une liste.

Plus précisément, on demande d’écrire une fonction bouger(L) qui prend en argument une liste L formée de nombres valant 1 ou 2. Le nombre 1 représente un déplacement vers la droite de 20 pixels et le nombre 2 représente un déplacement vers le haut de 20 pixels. Un appel bouger(L) provoque le déplacement du mobile suivant les différentes valeurs de L. Le mobile commence son déplacement en \((0,0)\).

Pour la liste des 35 déplacements ci-dessous :

L=[1, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2,
   1, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2,
   1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2]

la trajectoire aura la forme suivante :

Signes plus emboîtés¶

1. Créer une fonction croix(r) qui dessine une croix de centre \((0,0)\) et dont tous les côtés mesurent une distance de r. Un côté est la distance entre deux sommets consécutifs et une croix est formée de 12 côtés de même longueur. Ainsi, chaque branche de la croix aura une longueur et une largeur valant r.

   

2. Utiliser la fonction croix pour générer un motif de n croix emboîtées. L’espacement entre deux croix successives sera placé dans une variable esp. Les dessins ci-dessous ont été obtenus pour n=15 et une valeur initiale de r=200.

   

Triangles emboîtés¶

Construire un emboîtements de triangles comme dans la figure ci-dessous.

Le principe est simple : étant donné un triangle \(ABC\), on construit un autre triangle \(UVW\) tel que \(U\) soit sur le segment AB et tel que \(AU=AB/10\) et de même pour les autres côtés :

Il suffit ensuite de répéter cette construction avec le triangle \(UVW\).

On aura besoin de la transformation \(\mathtt{T(P, Q)}\) qui renvoie les coordonnées du point placé à 1/10 de PQ à partir de P :

def T(P, Q):
    return (P[0]+(Q[0]-P[0])/10, P[1]+(Q[1]-P[1])/10)

On écrira une fonction emboiter(A, B, C) qui étant donné un triangle \(\mathtt{ABC}\) comme ci-dessus dessine le triangle \(\mathtt{UVW}\) et renvoie la liste des coordonnées de \(\mathtt{U}\), \(\mathtt{V}\) et \(\mathtt{W}\).

Dans le dessin ci-dessus, la fonction emboiter a été appelée 25 fois. Pour des raisons esthétiques, on préférera un triangle équilatéral pour triangle initial.

Dessiner une frise¶

Cet exercice codé en Turtle est corrigé en vidéo.

1. Ecrire une fonction motif(x, y, e) qui dessine la ligne polygonale ci-dessous

   

   On supposera que tout écart entre deux segments parallèles voisins est constant, stocké dans la variable \(\mathtt{e}\). La largeur totale est donc de \(\mathtt{5e}\) et la hauteur totale de \(\mathtt{4e}\).

   Le motif commence au point de coordonnées (x, y).

2. En déduire un programme de tracé de \(n\) frises comme ci-dessous où \(n=6\) :

   

Equerres de disques¶

1. Ecrire une fonction equerreDessiner(x,y, n, color) une équerre formée de \(\mathtt{2n-1}\) disques de diamètre d=20 et de couleur color et dont l’angle droit est positionné au point \((x,y)\). Exemple pour n=5, (x, y)=(100, 200) et color=purple (pour bien comprendre, une bulle noire a été placée en (0,0)):

   

2. Dessiner un motif \(n\times n\) formé d’équerres remplis de disques, les équerres étant alternativement rouges et noires. On utilisera la question précédente.

   

Logo Google Drive¶

Dessiner le logo de Google Drive :

Les couleurs sont le bleu par défaut de Matplotlib, la couleur orange et la couleur vert. Tous les angles visibles sont de 60° ou de 120°. Chaque bande est un parallélogramme dont le grand côté est de longueur double du petit. Chaque bande sera dessinée avec Polygone et l’option color.

Indication¶

On utilisera le résultat décrit plus bas et dont les données sont fournies par la figure suivante :

Le point \(\mathtt{A=(x_A, y_A)}\) étant donné ainsi qu’un angle \(\mathtt{\alpha}\) (en radians pour Python) et une distance \(\mathtt{d}\) alors le point \(\mathtt{M}\) tel que \(\mathtt{AM=d}\) et \(\mathtt{(\overrightarrow{i}, \overrightarrow{AM})=\alpha}\) a pour coordonnées :

\(\mathtt{x_M=x_A+d\cos\alpha\quad y_M=y_A+d\sin\alpha}\)

où \(\mathtt{\overrightarrow{i}}\) est le vecteur unitaire de l’axe des abscisses.

On importera du module math les fonctions cos, sin et la constante pi et on construira dans le code Python une fonction extremite(A, d, alpha) renvoyant les coordonnées de M défini ci-dessus et qu’on utilisera pour construire la figure.

Construire un histogramme¶

Dans cet exercice, une note est un nombre entier entre 0 et 20 (observer que cela fait 21 notes possibles). Le but de l’exercice est de dessiner, sans utiliser les possibilités spécifiques qu’offre Matplotlib, un histogramme de notes.

1. Écrire une fonction effectifs_par_notes qui prend en paramètre une liste L constituée d’un nombre indéterminé de notes et renvoie une liste t de 21 entiers tels que t[v] soit le nombre de notes valant v dans la liste L.

   Ainsi, pour L=[8,13,12,8,6,19] on aura, par exemple, t[12]=1 et t[8]=2. Autrement dit, t[v] est le nombre d’occurrences de la note v dans la liste L. Au départ, t sera une liste composée de 21 zéros.

   Pour tester, on pourra utiliser la liste suivante :

   notes=[14, 8, 17, 13, 16, 15, 12, 0, 5, 17, 10, 18,
   17, 7, 16, 1, 13, 2, 14, 11, 5,
   7, 7,11, 1, 10, 13, 2, 13, 12,
   3, 6, 12, 14, 19]
   

2. Tracer un axe vertical et un axe horizontal avec 21 « bulles » représentant toutes les notes possibles (de 0 à 20). L’axe vertical est là seulement pour permettre de mieux lire l’histogramme.

3. Ecrire une fonction baton qui prend en paramètre un entier n et une hauteur h et dessine un bâton de hauteur h au-dessus du point d’abscisse correspondant à la note n (il faut au préalable tracer les axes horizontal et vertical).

3. On se donne une liste L de notes. Dessiner l’histogramme de L. On rappelle que l’histogramme de L est constitué des segments verticaux issus de chaque note n et de hauteur le nombre d’occurrences de la note n dans la liste L.

   Si la liste est par exemple constituée des 35 notes suivantes :

   14, 8, 17, 13, 16, 15, 12,
   0, 5, 17, 10, 18, 17, 7,
   16, 1, 13, 2, 14, 11, 5,
   7, 7, 11, 1, 10, 13, 2,
   13, 12, 3, 6, 12, 14, 19
   

   alors l’histogramme pourra ressembler à ceci

   

Remplissage de bassins¶

On dispose d’une succession de colonnes dont les hauteurs sont données dans une liste d’entiers positifs. Cette succession définit un relief :

Ce relief a été obtenu pour la liste suivante :

[19, 4, 14, 16, 14, 6, 12, 18, 10, 20, 21, 21, 10,
19, 17, 17, 27, 22, 23, 20, 5, 19, 17, 22, 6, 8, 10,
9, 14, 13, 13, 17, 7, 20, 11, 7, 3, 6, 5, 8, 2, 1, 6,
10, 2, 5, 20, 13, 22, 23, 26, 26, 14, 13, 7, 17, 2,
13, 5, 4, 7, 0, 13, 21, 2, 0, 3, 11, 4, 19, 11, 15,
11, 13, 7, 0, 17, 0, 3, 4]

Lorsqu’il se met à pleuvoir, l’eau peut remplir des cavités dont les parois sont des colonnes. On demande de dessiner les bassins remplis par la pluie lorsque la quantité d’eau retenue est maximale. Avec le motif précédent, le dessin à obtenir est le suivant :

Pour cela, on déterminera successivement chaque bassin par sa paroi à gauche et sa paroi à droite en parcourant la liste des hauteurs des colonnes à partir de la gauche. Plus précisément, on se donnera une paroi de gauche d’un bassin à remplir et de contenance maximale (en supposant qu’un tel bassin existe). Cette paroi a un flanc situé entre deux hauteurs \(\mathtt{h1}\) et \(\mathtt{h2}\) avec \(\mathtt{h1\leq h2}\). On cherche alors la paroi située à sa droite, de hauteur la plus haute possible, inférieure à h2 et valant au moins \(\mathtt{h1}\).

Le code à fournir contient deux parties :

• le calcul des parois de chaque bassin
• le tracé du relief puis des bassins

Il sera utile de créer une ou plusieurs fonctions.

Cet exercice provient d’une question sur le forum Python d’OpenClassrooms. Le problème est connu sous le nom de Trapping Rain Water et admet une solution astucieuse de complexité linéaire.

Fizz-buzz en VF¶

Ecrire une procédure \(\mathtt{f(n)}\) où \(\mathtt{n\geq 1}\) est un entier et qui affiche les entiers de 1 à \(\mathtt{n}\) avec les contraintes suivantes :

• si le nombre à afficher est multiple de 3, au lieu de l’afficher, la procédure affiche le mot coco ;
• si le nombre est multiple de 4, la procédure affiche seulement le mot rico ;
• si le nombre est multiple, à la fois, de 3 et de 4, la procédure affichera uniquement le mot cocorico.

Les affichages seront effectués sur des lignes distinctes.

Par exemple, l’appel \(\mathtt{f(13)}\) doit afficher les lignes ci-dessous :

1
2
coco
rico
5
coco
7
rico
coco
10
11
cocorico
13

Cet exercice s’appelle le Fizz-buzz a été popularisé en 2007. Pour l’évaluation de l’exercice, la qualité du code, et pas seulement le résultat, sera prise en compte.

Inspirez, expirez !¶

La respiration carrée (Sama Vritti) est un exercice de respiration consistant à alterner de narine quand on respire. Le cycle est le suivant :

• on inspire par la narine droite
• on pause la respiration
• on expire par la narine gauche
• on pause la respiration
• on inspire par la narine gauche
• on pause la respiration
• on expire par la narine droite
• on pause la respiration.

On demande d’écrire une fonction respirer(n, debut) qui affiche une suite de n cycles dont on connaît l’étape de départ (une inspiration ou une expiration de côté donné). L’inspiration est codée par I, l’expiration par E, le côté droit par D, le côté gauche par G. La pause de la respiration sera affichée par P. On affichera une étape par ligne et la fin d’un cycle sera suivie de l’affichage d’une ligne de tirets. Par exemple, respirer(3, "ID") affichera

ID
P
EG
P
IG
P
ED
P
------
ID
P
EG
P
IG
P
ED
P
------
ID
P
EG
P
IG
P
ED
P
------

Suite de Syracuse¶

1. Soit la fonction \(f\) définie pour \(n> 0\) entier par :

   • \(f(n)\) est la moitié de \(n\) si \(n\) est pair
   • \(f(n)\) vaut \(3n+1\) si \(n\) est impair

   Par exemple f(13) = 40 ou encore f(10) = 5.

   Coder en Python cette fonction. Tester avec \(f(13)\) et \(f(10)\).

2. On itère la fonction \(f\) en partant d’un entier \(n>0\). Par exemple, si \(n=13\), on obtient :

   13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
   

   La conjecture de Syracuse affirme que si on itère \(f\) depuis n’importe quel entier \(n>0\) alors, on tombera forcément sur 1 (ce qui se produit bien pour l’exemple ci-dessus).

   Écrire une fonction seq qui

   • prend \(n\) en paramètre,
   • affiche les itérés de la suite depuis le premier itéré, à savoir \(n\) jusqu’au dernier, à savoir \(1\).

3. Écrire une fonction saut(x) qui renvoie le nombre d’itérations pour arriver à \(1\) quand la suite commence avec \(x\) (si \(x=13\), il y a donc 9 itérations pour arriver à 1).

4. Déterminer à l’aide de la fonction fonction saut(x) le plus petit entier \(n\) tel qu’il faille exactement 100 itérations à partir de \(n\) pour arriver à \(1\) (vous devez trouver \(n=107\)).

Fibonacci¶

Voici les 12 premiers termes de la suite de Fibonacci :

\(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144\)

Plus généralement, les deux premiers termes de cette suite sont 1 et encore 1 et, chaque terme de la suite à partir du troisième s’obtient en faisant la somme des deux précédents. Par exemple, ci-dessus, \(89 = 34 + 55\).

1. Le but de cette question est juste de permettre facilement de visualiser les termes de la suite. Écrire une fonction fibo_liste(n) qui, pour un entier \(n\geq 2\), construit la liste des \(n\) premiers termes de la suite de Fibonacci. On utilisera la méthode append. Tester en affichant la liste.

2. Cette question n’utilise pas la question précédente.

   Ecrire une fonction fibo qui renvoie le \(n\)-ième terme de la suite de Fibonacci. Par exemple, fibo(12) vaut 144. On observera qu’il est totalement INUTILE de stocker TOUS les termes de la suite antérieurs au terme à calculer, il suffit juste de disposer des deux termes qui précèdent le terme recherché.

Multiplication du paysan russe (boucle while)¶

La multiplication dite « du paysan russe » ramène une multiplication de deux entiers naturels à une suite d’additions ou de divisions par 2. En voici une illustation à travers le produit \(\mathtt{85\times 18 = 1530}\) :

Cette multiplication est basée sur la propriété suivante : si \(\mathtt{a,b\in\N}\) alors

\(\mathtt{a\times b=\begin{cases}0 & \text{si } \mathtt{a} = 0\\\mathtt{a/2\times 2b}& \text{si } \mathtt{a} \text{ est pair et non nul}\\\mathtt{(a-1)\times b +b} & \text{sinon}\end{cases}}\)

Dans l’illustration ci-dessus, la 3e colonne est remplie lorsque a est impair.

Ecrire un fonction paysan(a, b) qui implémente la multiplication ci-dessus en utilisant une boucle while. Tester en choisissant des entiers aléatoires.

Suite d’entiers¶

On définit une suite de nombres entiers de la manière suivante :

• le premier élement vaut 0
• le deuxième élément vaut 1
• pour obtenir l’élément \(\mathtt{v}\) au rang \(\mathtt{r\geq 3}\), on considère l’élément x au rang r-2 ; si \(\mathtt{r-1}\) est un multiple de 3 alors \(\mathtt{v = x}\) et sinon \(\mathtt{v=x+1}\).

Ainsi, les 13 premiers éléments de la suite sont donnés dans le tableau suivant :

r | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13
---------------------------------------------------------
v | 1 | 0 | 1 | 1 | 1 | 1 | 2 | 1 | 2 | 2  | 2  | 2  | 3

Par exemple :

• le 12e élément vaut 2 car le 10e élément vaut 2 et que \(\mathtt{12-1=11}\) n’est pas un multiple de 3
• le 13e élément vaut 3 car \(\mathtt{13-1=12}\) est un multiple de 3 et le 11e élément vaut 2.

On donne un rang r et on demande de calculer la valeur v de la liste qui est au rang r. Par exemple, si r = 2030 on trouvera que v = 338. On écrira une fonction f(r). Le code à écrire ne nécessite de construire aucune liste.

La suite \(\mathtt{f(r)}\) est répertoriée ICI.

Pyramide de cubes¶

On dispose de cubes pour monter une pyramide. Voici par exemple une pyramide de hauteur 3 :

D’une manière générale, le dernier étage de la pyramide est formé d’un seul cube ; ce cube repose sur un carré de 2x2 cubes qui repose lui-même sur un carré de 3x3 cubes et ainsi de suite jusqu’au premier niveau.

On dispose de \(\mathtt{N}\) cubes et on cherche à connaître :

• la hauteur de la plus haute pyramide que l’on peut construire avec ces \(\mathtt{N}\) cubes
• le nombre de cubes utilisés.

On écrira une fonction pyramide(N) qui renverra une liste [h, t] où h est la hauteur de la pyramide et t le nombre total de cubes utilisés pour la construire.

Par exemple, pyramides(42) renvoie [4, 30]. En effet, une pyramide de hauteur 4 nécessite 30 cubes ce qui est moins que 42 mais une pyramide de hauteur 5 nécessite 55 cubes ce qui dépasse 42.

De même, pyramides(5) renvoie [2, 5] car une pyramide de hauteur 2 nécessite pile 5 cubes.

Cet exercice reprend l’exercice du site france-ioi intitulé Département d’architecture : construction d’une pyramide

Sous-listes d’une liste¶

On donne une liste L d’entiers entre 0 et 9, par exemple

\(\mathtt{L = [5, 5, 0, 8, 1, 4, 2, 3, 7, 8, 1, 4, 2, 3, 3]}\)

On observe que cette liste contient exactement à deux reprises la sous-liste M = [8, 1, 4, 2] : en effet, les chiffres 8, 1, 4, 2 apparaissent les uns à la suite des autres dans L en exactement deux endroits.

Ecrire une fonction nb_sous_listes(L, M) qui renvoie le nombre de sous-listes identiques à M et qui sont présentes dans L. Avec l’exemple ci-dessus, la fonction doit renvoyer 2.

Plus petit entier non nul (découpage en fonctions)¶

1. Écrire une fonction mini(L, i) qui prend en paramètre

   • une liste L d’entiers
   • un indice valide positif i de la liste L

   et renvoie le plus petit des éléments de la liste L et ayant un indice supérieur ou égal à i.

   Voici quelques exemples de comportement de la fonction :

   [40, 10, 50, 20] 0 -> 10
   [40, 10, 50, 20] 1 -> 10
   [40, 10, 50, 20] 2 -> 20
   [40, 10, 50, 20] 3 -> 20
   

2. Écrire une fonction plusPetitNonNul(L) qui prend en paramètre une liste L d’entiers non tous nuls et qui renvoie le plus petit indice d’un élément non nul de L.

   Voici quelques exemples de comportement de la fonction :

   [50, 10, 0, 90] -> 0
   [0, 0, 70, 0, 42] -> 2
   [0, 0, 70] -> 2
   [42] -> 0
   

3. En utilisant les deux fonctions précédentes, écrire une fonction miniNonNul(L) qui prend en paramètre une liste L d’entiers non tous nuls et qui renvoie le plus petit élément non nul de L.

   Voici quelques exemples de comportement de la fonction :

   [50, 0, 0, 90, 10] -> 10
   [0, 80, 10, 60, 0] -> 10
   [0, 0, 0, 40, 0, 30, 0] -> 30
   [0, 0, 0, 40, 0, 50, 0] -> 40
   [0, 0, 0, 40, 0, 0, 0] -> 40
   [0, 0, 0, 0, 0, 0, 40] -> 40
   [50, 80, 10, 60, 40] -> 10
   [42] -> 42
   

Minimum des entiers pairs (découpage en fonctions et boucle for)¶

1. On donne une liste L d’entiers et un indice valide de la liste (l’indice est appelé debut) tel que L[debut] soit pair. Construire une fonction mini(L, debut) qui renvoie la valeur du plus petit des éléments pairs de la liste L et ayant un indice supérieur ou égal à debut. Par exemple, si L=[81, 32, 10, 21, 42, 11, 12, 9, 12, 65, 46] et si debut=4 alors mini(L, debut) vaut 12.

2. On donne une liste L d’entiers contenant au moins un entier pair et on demande d’écrire une fonction ind_elt_pair(L) qui renvoie le plus petit indice i de L tel que L[i] soit pair. Par exemple, si L=[81, 19, 31, 21, 42, 11, 12] alors ind_elt_pair(L) vaudra 4. Il est attendu que votre code utilise une boucle for.

3. On donne une liste L d’entiers contenant au moins un entier pair. Ecrire une fonction miniPairs qui renvoie le plus petit des éléments de L qui soit pair. Par exemple :

   [81, 32, 12, 9, 12, 65, 46] -> 12
   [81, 65, 46] -> 46
   

   Il est attendu que la fonction miniPairs utilise les deux fonctions des questions précédentes.

Minimum des entiers pairs (découpage en fonctions et boucle while)¶

1. On donne une liste L d’entiers et un indice valide de la liste (l’indice est appelé debut) tel que L[debut] soit pair. Construire une fonction mini(L, debut) qui renvoie la valeur du plus petit des éléments pairs de la liste L et ayant un indice supérieur ou égal à debut. Par exemple, si L=[81, 32, 10, 21, 42, 11, 12, 9, 12, 65, 46] et si debut=4 alors mini(L, debut) vaut 12.

2. On donne une liste L d’entiers contenant au moins un entier pair et on demande d’écrire une fonction ind_elt_pair(L) qui renvoie le plus petit indice i de L tel que L[i] soit pair. Par exemple, si L=[81, 19, 31, 21, 42, 11, 12] alors ind_elt_pair(L) vaudra 4. Il est attendu que votre code utilise une boucle while.

3. On donne une liste L d’entiers contenant au moins un entier pair. Ecrire une fonction miniPairs qui renvoie le plus petit des éléments de L qui soit pair. Par exemple :

   [81, 32, 12, 9, 12, 65, 46] -> 12
   [81, 65, 46] -> 46
   

   Il est attendu que la fonction miniPairs utilise les deux fonctions des questions précédentes.