Troisieme — Programme officiel (BO 2020) · Math@mine
Un distributeur automatique doit rendre la monnaie en utilisant le minimum de pieces. Pour rendre 2,70 euros, comment procede-t-il ?
Muhammad ibn Musa al-Khwarizmi (vers 780–850), mathematicien et astronome perse, a travaille a la Maison de la Sagesse a Bagdad. Son nom, latinise en Algoritmi, est a l’origine du mot algorithme.
Dans son traite Al-Kitab al-mukhtasar fi hisab al-jabr wal-muqabala, il a decrit des procedures systematiques (des algorithmes !) pour resoudre des équations. Ces méthodes pas-a-pas, applicables mecaniquement, sont le fondement meme de la programmation moderne.
Bien avant les ordinateurs, les humains executaient des algorithmes : les recettes de cuisine, les méthodes de calcul de la division posee, la construction a la règle et au compas… sont des algorithmes !
L’ordinateur choisit un nombre entre 1 et 1000. A chaque etape, tu proposes un nombre et l’ordinateur repond « trop grand », « trop petit » ou « gagne ! ».
Ces caracteristiques decoulent de la definition meme d’un algorithme : une suite d’instructions qui doit etre finie (elle se termine), non ambigue (chaque etape est claire), et efficace (elle resout bien le problème pose). Un algorithme qui ne se termine pas ou qui est ambigu ne remplit pas son role.
En 3e, on utilise deux langages pour programmer des algorithmes :
=.
# Affectation de variables x = 5 # x vaut 5 y = 3 # y vaut 3 somme = x + y # somme vaut 8 x = x + 1 # x vaut maintenant 6 print(somme) # Affiche : 8 print(x) # Affiche : 6
En Python, = n’est pas une egalite mathematique, c’est une affectation. L’instruction x = x + 1 signifie « prendre la valeur actuelle de x, ajouter 1, et stocker le résultat dans x ». En maths, \(x = x + 1\) n’aurait aucun sens !
age = 15 → entier (int)taille = 1.72 → décimal (float)prenom = "Alice" → chaine de caracteres (str)majeur = False → booleen (bool)age = int(input("Quel age as-tu ? ")) if age >= 18: print("Tu es majeur.") else: print("Tu es mineur.")
note = float(input("Note sur 20 : ")) if note >= 16: print("Tres bien !") elif note >= 12: print("Bien.") elif note >= 10: print("Assez bien.") else: print("Insuffisant.")
| Operateur | Signification | Exemple |
|---|---|---|
== | Egal a | x == 5 |
!= | Different de | x != 0 |
< | Strictement inferieur | x < 10 |
<= | Inferieur ou egal | x <= 20 |
> | Strictement superieur | x > 0 |
>= | Superieur ou egal | x >= 18 |
for)for repete un bloc d’instructions un nombre de fois connu a l’avance.
for i in range(1, 11): print(i, "au carre =", i**2) # Affiche : # 1 au carre = 1 # 2 au carre = 4 # ... # 10 au carre = 100
range(a, b) genere les entiers de a a b-1. Donc range(1, 11) donne 1, 2, 3, …, 10.
range(n) genere les entiers de 0 a n-1.
while)while repete un bloc d’instructions tant qu’une condition est vraie. Le nombre de repetitions n’est pas forcement connu a l’avance.
p = 1 n = 0 while p <= 1000: p = p * 2 n = n + 1 print("2 puissance", n, "=", p) # Affiche : 2 puissance 10 = 1024
Si la condition du while n’est jamais fausse, le programme tourne indefiniment (boucle infinie). Il faut toujours s’assurer que la condition finira par devenir fausse.
def aire_rectangle(longueur, largeur): """Calcule l'aire d'un rectangle.""" return longueur * largeur # Utilisation : resultat = aire_rectangle(5, 3) print(resultat) # Affiche : 15
def est_pair(n): """Verifie si un nombre est pair.""" if n % 2 == 0: return True else: return False print(est_pair(7)) # False print(est_pair(12)) # True
return pour renvoyer le résultatdef est_premier(n): """Teste si n est un nombre premier.""" if n < 2: return False for d in range(2, int(n**0.5) + 1): if n % d == 0: return False return True # Afficher les nombres premiers jusqu'a 50 for i in range(2, 51): if est_premier(i): print(i, end=" ") # 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
def syracuse(n): """Affiche la suite de Syracuse a partir de n.""" while n != 1: print(n, end=" → ") if n % 2 == 0: n = n // 2 else: n = 3 * n + 1 print(1) syracuse(7) # 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
import random def approx_pi(n): """Approxime pi par la methode de Monte-Carlo avec n points.""" dans_cercle = 0 for i in range(n): x = random.random() y = random.random() if x**2 + y**2 <= 1: dans_cercle += 1 return 4 * dans_cercle / n print(approx_pi(100000)) # Affiche une valeur proche de 3.14159...
Algorithmique et Python : teste d’abord ton intuition, puis lis l’explication.
« Une boucle for s’arrete toujours (elle termine). »
Cette affirmation est-elle correcte ?
Oui ! Une boucle for parcourt un nombre fini d’éléments, donc elle s’arrete toujours.
for = nombre d’iterations connu → termine toujours. while = peut boucler indefiniment.« while True ne s’arrete jamais. »
Cette affirmation est-elle correcte ?
Faux ! while True peut s’arreter grace a l’instruction break.
while True + break est un schema courant pour une boucle avec condition d’arret interne.« range(5) genere les entiers de 0 a 5 inclus. »
Cette affirmation est-elle correcte ?
Faux ! range(5) genere 0, 1, 2, 3, 4. Le 5 est exclu.
range(n) = {0, 1, …, n-1} (n éléments). La borne superieure est toujours exclue.« En Python, i = i + 1 est une équation mathematique. »
Cette interprétation est-elle correcte ?
Faux ! = est l’operateur d'affectation en Python, pas d’egalite. i = i + 1 signifie « incrementer \(i\) de 1 ».
En maths, \(i = i + 1\) n’a aucune solution. En Python, c’est une instruction valide.
= (affectation), == (test d’egalite). Maths : \(=\) (egalite).« En Python, 7 / 2 donne 3 (division entiere). »
Cette affirmation est-elle correcte ?
Faux ! En Python 3, 7 / 2 donne 3.5. Pour la division entiere : 7 // 2 donne 3.
/ = division décimale. // = division entiere (quotient). % = reste (modulo).| Concept | Python | Description |
|---|---|---|
| Variable | x = 5 | Stocker une valeur en memoire |
| Affichage | print(x) | Afficher une valeur |
| Saisie | input("...") | Demander une valeur a l’utilisateur |
| Condition | if / elif / else | Executer selon une condition |
| Boucle for | for i in range(n) | Repeter n fois |
| Boucle while | while condition | Repeter tant que la condition est vraie |
| Fonction | def f(x): return ... | Bloc reutilisable avec entrees/sorties |
L’algorithme du distributeur de monnaie (algorithme « glouton ») :
def rendre_monnaie(montant_cents): """Rend la monnaie avec le minimum de pieces.""" pieces = [200, 100, 50, 20, 10] noms = ["2 euros", "1 euro", "50 cents", "20 cents", "10 cents"] reste = montant_cents for i in range(len(pieces)): nb = reste // pieces[i] if nb > 0: print(nb, "piece(s) de", noms[i]) reste = reste % pieces[i] rendre_monnaie(270) # Affiche : # 1 piece(s) de 2 euros # 1 piece(s) de 50 cents # 1 piece(s) de 20 cents
Pour rendre 2,70 euros : 1 piece de 2 euros + 1 piece de 50 centimes + 1 piece de 20 centimes = 3 pieces.
La strategie optimale est la recherche dichotomique : on propose toujours le milieu de l’intervalle restant.
Il faut au maximum 10 etapes car \(2^{10} = 1024 > 1000\).
En général, pour un nombre entre 1 et \(N\), il faut au plus \(\lceil \log_2(N) \rceil\) etapes.