Algorithmique et programmation

Variables et types, affectation, instruction conditionnelle, boucles bornées (for) et non bornées (while), fonctions Python, fonction aléatoire et simulation.

À propos de cette page

Cinq problèmes corrigés d’algorithmique : le rendu de monnaie d’une caisse automatique, un programme de calcul traduit en Python, un plan d’entraînement de course, l’algorithme d’Euclide pour découper des rubans et la simulation de la somme de deux dés.

5 problèmes, du plus simple au plus difficile. Écris tes réponses, puis « Vérifier ».

Résoudre un problème : la méthode

Je repère les données et ce que l’on cherche : elles deviennent des variables ou des paramètres, le résultat devient ce que la fonction renvoie.
J’écris l’algorithme en français en trois lignes : ce que l’on connaît au départ, ce que l’on répète, ce que l’on cherche à la fin.
Je choisis la structure : if pour des cas, for si le nombre de répétitions est connu, while sinon.
Je fais une trace à la main sur les premières valeurs (tableau des variables) pour vérifier le programme avant de lui faire confiance.
Je justifie par un calcul ce que le programme montre (une inégalité, une identité, une probabilité) et je conclus dans le contexte.

Problème 1 · Le rendu de monnaie d’une caisse automatique★★★Facile

Une caisse automatique rend la monnaie en billets de 10 € et de 5 € et en pièces de 2 € et de 1 €. Elle utilise toujours la plus grande valeur possible, pour rendre le moins de billets et de pièces. Les montants sont des nombres entiers d’euros.

def nombre_pieces(r):
    n = 0
    while r >= 10:
        r = r - 10
        n = n + 1
    while r >= 5:
        r = r - 5
        n = n + 1
    while r >= 2:
        r = r - 2
        n = n + 1
    n = n + r
    return n

def caisse(prix, donne):
    if donne < prix:
        return -1
    r = donne - prix
    return nombre_pieces(r)

nombre_pieces(r) renvoie le nombre de billets et de pièces rendus pour une somme r ; caisse(prix, donne) renvoie −1 quand le client n’a pas donné assez.

1. nombre_pieces(18) renvoie
r vaut 18 : un billet de 10 € (reste 8), un billet de 5 € (reste 3), une pièce de 2 € (reste 1). Après les trois boucles, n vaut 3, et la ligne n = n + r ajoute la pièce de 1 € : $10 + 5 + 2 + 1 = 18$ , soit 4 billets et pièces.
2. Avec r = 47, nombre de tours de la première boucle while :
r vaut 47, 37, 27, 17 puis 7 : après 4 tours, $7 ⩾ 10$ est faux et la boucle s’arrête.
3. nombre_pieces(47) renvoie
4 billets de 10 €, puis il reste 7 € : un billet de 5 € (reste 2), une pièce de 2 € (reste 0). La dernière ligne ajoute $r = 0$ : $4 + 1 + 1 = 6$ .
4. caisse(50, 33) renvoie
Les arguments sont pris dans l’ordre : prix = 50 et donne = 33. Le test $33 < 50$ est vrai : la fonction renvoie −1 et s’arrête, le client n’a pas donné assez.
5. caisse(33, 50) renvoie
Le test $50 < 33$ est faux : la fonction renvoie nombre_pieces(17). $17 = 10 + 5 + 2$ : 3 billets et pièces.
6. Justifier que la première boucle while peut être remplacée par les deux instructions n = r // 10 et r = r % 10. Contrôle : pour r = 83, valeur de r après ces deux instructions :
Rédaction attendue. On note $r_{0}$ la valeur de départ et $q$ le nombre de tours. Chaque tour retire 10 à r et ajoute 1 à n, qui valait 0 : à la sortie, n vaut $q$ et r vaut $r_{0} - 10 q$ . La boucle s’arrête dès que $r < 10$ . Elle n’a jamais rendu r négatif, car on ne retire 10 que si $r ⩾ 10$ . Donc $r_{0} = 10 q + r$ avec $0 ⩽ r < 10$ : $q$ est le quotient et r le reste de la division euclidienne de $r_{0}$ par 10, c’est-à-dire r // 10 et r % 10. Pour 83 : $83 = 10 \times 8 + 3$ , donc n vaut 8 et r vaut 3.

Problème 2 · Un programme de calcul★★★Moyen

Un programme de calcul est écrit en langage naturel :

Choisir un nombre x
a ← x + 3
b ← a²
c ← b − x²
d ← c − 4x
Afficher d

On le traduit en une fonction Python, en complétant la ligne de b :

def programme(x):
    a = x + 3
    b = a ** ...
    c = b - x ** 2
    d = c - 4 * x
    return d

1. Pour x = 4, b vaut
a vaut $4 + 3 = 7$ , puis b vaut $7^{2} = 49$ .
2. Pour x = 4, le programme affiche
c vaut $49 - 16 = 33$ , puis d vaut $33 - 4 \times 4 = 17$ .
3. Dans la fonction Python, les trois points de la ligne de b sont remplacés par
« b ← a² » s’écrit b = a ** 2 : la puissance s’écrit ** en Python.
4. Démontrer que, pour tout nombre x, le programme affiche $2 x + 9$ . Contrôle : programme(-7) renvoie
Rédaction attendue. On suit les variables avec un nombre x quelconque : $a = x + 3$ , $b = (x + 3)^{2} = x^{2} + 6 x + 9$ (identité remarquable), $c = x^{2} + 6 x + 9 - x^{2} = 6 x + 9$ , puis $d = 6 x + 9 - 4 x = 2 x + 9$ . Le programme affiche donc $2 x + 9$ . Contrôle : $2 \times (- 7) + 9 = - 5$ .
5. Valeur de x pour laquelle le programme affiche 0 :
$2 x + 9 = 0 ⟺ x = - \frac{9}{2} = - 4, 5$ .
6. On exécute for x in range(-10, 11): et l’on compte les entiers x pour lesquels programme(x) > 0. Nombre obtenu :
$2 x + 9 > 0 ⟺ x > - 4, 5$ . Parmi les entiers de $- 10$ à 10, ce sont ceux de $- 4$ à 10 : il y en a $10 - (- 4) + 1 = 15$ .

Problème 3 · Un plan d’entraînement★★★Moyen

Pour préparer une course, Inès court 5 km par séance la première semaine, puis augmente sa distance de 10 % chaque semaine, pendant 10 semaines. Le script ci-dessous calcule la distance totale sur ces 10 semaines (une séance par semaine) et compte les semaines où la séance dépasse 8 km.

d = 5
total = 0
c = 0
for s in range(1, 11):
    total = total + d
    if d > 8:
        c = c + 1
    d = d * 1.1
print(total, c)

1. Distance de la séance de la semaine 3 : km
Augmenter de 10 % revient à multiplier par 1,1 : semaine 2 : $5 \times 1, 1 = 5, 5$ km ; semaine 3 : $5, 5 \times 1, 1 = 6, 05$ km.
2. Nombre de tours de la boucle :
range(1, 11) parcourt s = 1, 2, …, 10 : un tour par semaine.
3. Justifier que, pendant le tour numéro s, la variable d vaut $5 \times 1, 1^{s - 1}$ . Contrôle : distance de la semaine 6, arrondie au centième : km
Rédaction attendue. d vaut 5 au premier tour, et la dernière ligne du bloc la multiplie par 1,1 à la fin de chaque tour. Au début du tour s, elle a donc été multipliée $s - 1$ fois par 1,1 : $d = 5 \times 1, 1^{s - 1}$ . Pour $s = 6$ : $5 \times 1, 1^{5} \approx 8, 05$ km.
4. Valeur finale de c :
La semaine 5, $d = 5 \times 1, 1^{4} \approx 7, 32$ ne dépasse pas 8 ; la semaine 6, $d \approx 8, 05$ le dépasse, et d augmente ensuite. Le test d > 8 est vrai pour les semaines 6 à 10 : c vaut 5.
5. Valeur de total affichée, arrondie au dixième : km
total additionne les 10 distances : $5 + 5, 5 + 6, 05 + \dots + 5 \times 1, 1^{9} \approx 79, 7$ km (la calculatrice ou le script donne 79,687…).

Problème 4 · L’algorithme d’Euclide et la découpe de rubans★★★Difficile

Un atelier dispose de deux rubans, l’un de 252 cm, l’autre de 180 cm. On veut les découper entièrement en morceaux de même longueur entière, la plus grande possible, sans perte : cette longueur est le plus grand diviseur commun de 252 et 180. On la calcule avec l’algorithme d’Euclide, qui remplace le couple (a ; b) par (b ; r), où r est le reste de la division de a par b, jusqu’à obtenir un reste nul.

def pgcd(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

1. Au premier tour de pgcd(252, 180), r vaut
$252 = 180 \times 1 + 72$ : le reste vaut 72. Le couple devient (180 ; 72).
2. Nombre de tours de boucle effectués par pgcd(252, 180) :
Tour 1 : $252 = 180 \times 1 + 72$ . Tour 2 : $180 = 72 \times 2 + 36$ . Tour 3 : $72 = 36 \times 2 + 0$ . Après le tour 3, b vaut 0 : la boucle s’arrête.
3. pgcd(252, 180) renvoie
À la sortie, a vaut 36 : c’est la longueur cherchée. Contrôle : $252 = 36 \times 7$ et $180 = 36 \times 5$ .
4. Nombre total de morceaux obtenus :
Le premier ruban donne $252 \div 36 = 7$ morceaux, le second $180 \div 36 = 5$ : $7 + 5 = 12$ morceaux de 36 cm.
5. Justifier que la boucle s’arrête toujours lorsque a et b sont des entiers strictement positifs. Contrôle : nombre de tours effectués par pgcd(180, 252) :
Rédaction attendue. À chaque tour, la nouvelle valeur de b est un reste de division par l’ancienne valeur de b : c’est un entier r tel que $0 ⩽ r < b$ . Les valeurs de b forment donc une suite d’entiers positifs strictement décroissante, qui ne peut pas être infinie : b atteint 0 et la boucle s’arrête. Pour pgcd(180, 252), le premier tour donne $180 = 252 \times 0 + 180$ : le couple devient (252 ; 180). On retrouve ensuite les 3 tours précédents, soit 4 tours.

Problème 5 · Simuler la somme de deux dés★★★Difficile

On lance deux dés équilibrés à six faces et l’on note la somme des deux numéros. On simule cette expérience en Python.

from random import randint

def somme():
    d1 = randint(1, 6)
    d2 = randint(1, 6)
    return d1 + d2

def freq7(n):
    c = 0
    for i in range(n):
        if somme() == 7:
            c = c + 1
    return c / n

def moyenne(n):
    s = 0
    for i in range(n):
        s = s + somme()
    return s / n

1. Nombre de couples (dé 1 ; dé 2) possibles :
Chaque dé a 6 issues : $6 \times 6 = 36$ couples, tous équiprobables.
2. Probabilité d’obtenir une somme égale à 7, en fraction irréductible :
Les couples de somme 7 sont (1 ; 6), (2 ; 5), (3 ; 4), (4 ; 3), (5 ; 2), (6 ; 1) : $\frac{6}{36} = \frac{1}{6}$ .
3. Un élève remplace la fonction somme par return randint(2, 12). Justifier que ce modèle est faux. Contrôle : probabilité d’obtenir 7 avec ce modèle, en fraction :
Rédaction attendue. randint(2, 12) rend les 11 sommes de 2 à 12 équiprobables : chacune aurait la probabilité $\frac{1}{11}$ . Or les sommes ne sont pas équiprobables : 2 ne s’obtient qu’avec le couple (1 ; 1), soit $\frac{1}{36}$ , alors que 7 s’obtient avec 6 couples, soit $\frac{1}{6}$ . Il faut simuler chaque dé, puis additionner.
4. freq7(10000) renvoie une valeur proche de la probabilité. Cette probabilité, arrondie au centième :
$\frac{1}{6} \approx 0, 17$ . La fréquence obtenue fluctue autour de cette valeur, par exemple 0,1652 ou 0,1689.
5. Pour n grand, moyenne(n) renvoie une valeur proche de
Sur six lancers d’un dé où chaque face sortirait une fois, le total serait $1 + 2 + \dots + 6 = 21$ , soit 3,5 par lancer. Pour la somme de deux dés, on s’attend à $3, 5 + 3, 5 = 7$ .
6. Une exécution de moyenne(100) et une de moyenne(10000) renvoient 6,74 et 7,0213. Valeur la plus vraisemblablement renvoyée par moyenne(10000) :
Plus n est grand, plus la moyenne observée est proche de 7 en général : 7,0213 vient de 10 000 répétitions, 6,74 de 100.

Bloqué sur ce chapitre ?

Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.

Réserver un 1^er cours → Voir les tarifs

Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs