Somme des $n$ nombres d'un tableau
Publié le January 29, 2023
| 3 minutes
| 452 mots
| David Latreyte
L’objectif de ce document est d’écrire et d’implémenter un algorithme s’appuyant sur le raisonnement « Diviser pour régner » qui permet de déterminer la somme des $n$ nombres (entiers) d’un tableau.
Écrire le code de fonction somme1 dont la spécification est : 1 2 3 4 5 6 7 def somme1(tab: List[float]) -> float: """ Calcul de la somme des nombres éléments de tab. Algorithme : Récursivité enveloppée """ Penser à écrire un jeu de tests.
[Lire]
Autour de la suite de Fibonacci
Publié le February 25, 2021
| 13 minutes
| 2563 mots
| David Latreyte
Rappel : récursivité terminale La définition de la fonction factorielle est $$ n! = \begin{cases} 1 & \text{if } n = 0 \cr n \times (n-1)! & \text{sinon} \end{cases} $$
Définir la fonction fact_env qui calcule la factorielle d’un entier naturel $n$, sans oublier le jeu de tests.
La spécification de la fonction est :
1 2 3 4 5 6 def fact_env(n: int) -> int: """ Retourne la factorielle de n.
[Lire]
Dessin de figures fractales
Publié le January 26, 2021
| 7 minutes
| 1402 mots
| David Latreyte
Le mot fractale vient du latin fractus qui signifie brisé. En effet, une figure fractale est un objet géométrique infiniment morcelé des détails sont observables à une échelle arbitrairement choisie.
En zoomant sur une partie de la figure, on peut retrouver toute la figure, on dit qu’elle est auto similaire.
http://www.maths-et-tiques.fr/index.php/detentes/les-fractales
http://fr.wikipedia.org/wiki/Fractalehttp://fr.wikipedia.org/wiki/Fractale
Introduction Dans le code suivant (qu’il faudra étudier et exécuter) :
Quel est le cas de base de l’algorithme récursif ?
[Lire]
Les tours de Hanoï
Publié le November 24, 2020
| 4 minutes
| 707 mots
| David Latreyte
Le problème mathématique des tours de Hanoï a été inventé par Édouard Lucas. Paru d’abord en fascicule en 1889 , il est publié ensuite dans le tome 3 de ses « Récréations mathématiques », parues à titre posthume en 1892. Il annonce que ce problème est dû à un de ses amis, N. Claus de Siam (anagramme de Lucas d’Amiens, Amiens étant sa ville de naissance), prétendument professeur au collège de Li-Sou-Stian (anagramme de Saint Louis, le lycée où Lucas enseignait).
[Lire]
Rotation d'une image bitmap d'un quart de tour
Publié le November 18, 2020
| 10 minutes
| 1994 mots
| David Latreyte
L’objectif de cette activité est l’écriture d’une fonction qui effectue la rotation d’une image bitmap de 90 degrés en utilisant le principe « Diviser pour régner ».
On peut manipuler des images en Python à l’aide du module PIL (Python Image Library). Une première partie de l’activité est consacrée à la prise en main de ce module. Dans un second temps, la fonction de manipulation des bits est développée.
Images numériques Définition L’image matricielle Une image matricielle, ou « carte de points » (de l’anglais « bitmap »), est une image constituée d’une matrice de points colorés, c’est-à-dire, constituée d’un tableau, d’une grille, où chaque case possède une couleur qui lui est propre et est considérée comme un point.
[Lire]
Tri par insertion
Chapitre 5,2
Publié le October 7, 2020
| 10 minutes
| 2026 mots
| David Latreyte
Objectifs Le tri par insertion a été étudié en classe de 1ère. Dans ce document, après un rappel du cours de 1ère, nous allons implémenter une version récursive de cet algorithme et ensuite utiliser la possibilité que les fonctions en Python ont d’accepter des fonctions comme paramètres, afin de rendre plus générale et utile cette fonction de tri.
Tri du joueur de cartes Le tri par insertion est un tri « naturel » souvent qualifié de « tri du joueur de carte ».
[Lire]
Programmation Fonctionnelle
Chapitre 5,1
Publié le October 6, 2020
| 7 minutes
| 1479 mots
| David Latreyte
Qu’est-ce que la programmation fonctionnelle ? S’il n’est pas facile de répondre précisément à cette question, on peut essayer de mettre en évidence les idées que le paradigme fonctionnel promeut :
Les fonctions doivent être des objets de première classe, c’est à dire que les fonctions doivent pouvoir être passées comme arguments à une fonction, les fonctions doivent aussi pouvoir être retournées par une fonction.
Les fonctions doivent (le plus possible) être pures, c’est à dire ne générer aucun effet de bord.
[Lire]
Recherche d'un élément dans un tableau : algorithmes itératifs et récursifs
Publié le September 9, 2020
| 4 minutes
| 829 mots
| David Latreyte
Recherche d’un élément dans un tableau La recherche d’éléments dans un tableau a déjà été évoquée en classe de première. Les deux algorithmes mis en œuvre à cette occasion, la recherche linéaire et la recherche dichotomique, utilisaient des boucles.
L’objectif de cette séance est de rapidement revoir ces algorithmes et de mettre en œuvres des algorithmes récursifs de même complexité. Quatre algorithmes de recherche vont donc être implémentés :
La recherche linéaire itérative ; La recherche linéaire récursive ; La recherche dichotomique itérative ; La recherche dichotomique récursive.
[Lire]
La récursivité appliquée aux chaînes de caractères et aux listes
Publié le September 8, 2020
| 11 minutes
| 2235 mots
| David Latreyte
Introduction Une chaîne de caractère est une structure de données qui permet de rassembler en un unique objet une succession ordonnée de caractères. Ainsi, une définition récursive d’une chaîne de caractères pourrait être :
Une chaîne de caractères est :
soit la chaîne de caractères vide ; soit constituée de son premier caractère et du reste des caractères qui forment aussi une chaîne de caractères (éventuellement vide). Une liste est une structure de données qui permet de rassembler en un unique objet une succession ordonnée d’objets (ou de valeurs).
[Lire]
Récursivité sur les entiers
Publié le September 5, 2020
| 19 minutes
| 3971 mots
| David Latreyte
To understand recursion, you must first understand recursion. La récurrence est un raisonnement mathématique courant et parmi les plus puissants pour démontrer des théorèmes ou construire des objets. Par exemple, on l’utilise dans un cours de mathématique de lycée pour montrer que :
Pour tout entier $n \geqslant 0$, on a : $1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2}$ ; Un entier naturel n’est autre que 0 ou le successeur d’un entier naturel (0 est 0, 1 est le successeur de 0, 2 est le successeur de 1, …).
[Lire]