← Retour au chapitre

Fiche à trous · Seconde · Mathématiques

Algorithmique et programmation Python

Complétez de mémoire, puis vérifiez avec la page de corrigé.

Programmer, en mathématiques, ne sert pas à faire de l'informatique : cela sert à écrire un raisonnement de façon si précise qu'une machine puisse l'exécuter. Un algorithme qui ne marche pas n'est presque jamais un problème de langage — c'est un raisonnement incomplet, et le programme se contente de le dire tout haut.

Les briques du langage

Définition — variable et affectation :

les briques : variable et conditionn = 5 # une variable, sans déclarationif n > 3: # deux points, puis un bloc indenté print("grand")else: print("petit")
2.

En Python, l'indentation n'est pas une commodité de lecture : c'est la syntaxe elle-même. Ce qui est décalé sous un `if` s'exécute quand la condition est vraie ; ce qui revient à gauche s'exécute dans tous les cas. Un décalage mal placé change le programme sans provoquer d'erreur, ce qui en fait la faute la plus difficile à trouver.

Piège

Écrire `if n = 3:` au lieu de `if n == 3:`.

un `=` range, un `==` demande. Dans un `if`, on demande toujours.

Les deux boucles

Règle

les deux boucles : nombre connu, conditiontotal = 0for i in range(1, 11): # i prend 1, 2, … 10 — jamais 11 total = total + iprint(total) # affiche 55n = 100while n > 1: # tant que la condition est vraie n = n // 2 # division entière
4.

Piège

Écrire une boucle `while` dont la condition ne peut jamais devenir fausse.

avant d'écrire le corps de la boucle, se demander : quelle ligne, à l'intérieur, rapproche de la sortie ? Si la réponse n'est pas immédiate, la boucle est infinie.

Les fonctions

Définition — fonction et return :

une fonction : elle renvoie une valeurdef maximum(liste): m = liste[0] # on part du premier for x in liste: if x > m: m = x return m # renvoie, n'affiche pasprint(maximum([3, 9, 2, 7])) # affiche 9
6.

Quatre algorithmes à connaître

Chercher un maximum

  1. 7.
  2. 8.
  3. 9.

Exemple

L'algorithme d'Euclide calcule le PGCD de deux entiers. Le suivre à la main sur 48 et 18.

  1. 10.
  2. 11.
  3. 12.
  4. 13.
  5. 14.

Résultat :

Le test de primalité illustre le seul souci d'efficacité du programme de seconde. Tester tous les diviseurs de 2 à fonctionne, mais devient très lent pour un grand . Or si a un diviseur supérieur à , il en a nécessairement un inférieur : il suffit donc de tester jusqu'à . Pour , on passe d'un million de tests à mille.

test de primalité, arrêté à la racinedef est_premier(n): if n < 2: return False # 0 et 1 ne sont pas premiers d = 2 while d * d <= n: # équivaut à d <= racine de n if n % d == 0: return False # un diviseur trouvé : on s'arrête d = d + 1 return True
16.

Deux détails de ce programme méritent d'être remarqués. Le `return False` à l'intérieur de la boucle est ici volontaire : dès qu'un diviseur est trouvé, il n'y a plus rien à chercher, et sortir immédiatement fait gagner tout le reste du parcours. Et la condition s'écrit `d * d <= n` plutôt que `d <= sqrt(n)` : on compare deux entiers au lieu d'un entier et d'un décimal approché, ce qui supprime tout risque d'arrondi.

Piège

Écrire `return True` à l'intérieur de la boucle, symétriquement au `return False`.

on ne peut conclure « premier » qu'après avoir tout testé : le `return True` va donc à l'extérieur de la boucle, aligné avec le `while`.

  • `=` range une valeur, `==` compare : ai-je le bon signe dans mon test ?
  • L'indentation correspond-elle exactement à ce que je veux répéter ?
  • `range(1, 11)` s'arrête à 10 : ai-je vérifié mes bornes ?
  • Dans un `while` : quelle ligne rapproche de la sortie ?
  • Ma fonction renvoie-t-elle avec `return`, ou se contente-t-elle d'afficher ?
  • Ai-je testé mon programme sur un cas dont je connais la réponse ?

Corrigé · à détacher

Algorithmique et programmation Python

  1. 1. Une variable est un nom qui désigne une valeur. L'affectation `n = 5` ne signifie pas « égale 5 » mais « range 5 dans la case appelée ». La différence apparaît dès qu'on écrit `n = n + 1` : mathématiquement absurde, cette ligne est parfaitement claire en programmation — elle remplace le contenu de par ce contenu augmenté de 1.
  2. 2. Deux points, puis un bloc indenté : l'indentation fait le programme.
  3. 3. La boucle `for` répète un nombre de fois connu à l'avance : `for i in range(1, 11)` fait prendre à `i` les valeurs 1 à 10 — la borne de droite est exclue, et c'est l'erreur d'un débutant sur deux. La boucle `while` répète tant qu'une condition reste vraie : le nombre de tours n'est pas connu, et il faut garantir que la condition finira par devenir fausse.
  4. 4. Nombre de tours connu : for. Condition d'arrêt : while.
  5. 5. Une fonction regroupe un traitement sous un nom, avec des paramètres en entrée. L'instruction `return` renvoie une valeur à celui qui a appelé la fonction, et interrompt son exécution. Elle ne doit pas être confondue avec `print`, qui affiche sans rien renvoyer : une fonction qui affiche mais ne renvoie rien ne peut pas être réutilisée dans un calcul.
  6. 6. Une fonction renvoie ; elle n'affiche pas.
  7. 7. Initialiser avec le premier élément de la liste, jamais avec 0 : une liste de nombres négatifs donnerait un maximum faux.
  8. 8. Parcourir tous les éléments, y compris le premier — le comparer à lui-même ne coûte rien et simplifie l'écriture.
  9. 9. Remplacer la valeur retenue chaque fois qu'on rencontre plus grand.
  10. 10. Le principe : on remplace le plus grand par le reste de sa division par le plus petit, et on recommence jusqu'à ce que le reste soit nul.
  11. 11. Premier tour : reste de 48 par 18.
  12. 12. Deuxième tour : reste de 18 par 12.
  13. 13. Troisième tour : reste de 12 par 6.
  14. 14. Le reste est nul : le PGCD est le dernier diviseur employé, soit 6.
  15. 15. PGCD(48 ; 18) = 6, en trois tours de boucle
  16. 16. Le test `d * d <= n` évite d'appeler une racine carrée : plus rapide, et exact.