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]
Diviser pour régner  Récursivité 

Diviser pour régner

 Publié le January 29, 2023  |  6 minutes  |  1157 mots  |  David Latreyte

Dans quel cas ? On parvient à découper un problème en sous-problèmes indépendants les uns des autres. On poursuit cette démarche jusqu’à aboutir à une situation simple : cas de base. La solution du cas de base est généralement simple à obtenir et permet la construction de la solution du problème. Remarque C’est l’indépendance des sous-problèmes qui permet la construction de la solution globale directe par recombinaison des solutions intermédiaires. [Lire]
Diviser pour régner 

Décomposition d'un problème en sous-problèmes

 Publié le January 29, 2023  |  1 minutes  |  57 mots  |  David Latreyte

Principe

  • On décompose le problème en sous-problèmes plus simples.
  • On résout les sous-problèmes.
  • On combine les sous-problèmes de façon à construire la solution du problème initial.

Indépendance des sous-problèmes

  • Si les sous-problèmes sont indépendants les uns des autres : « Diviser pour règner ».
  • Si les sous-problèmes dépendent les uns des autres : « Programmation dynamique ».
Diviser pour régner  Programmation dynamique 

Recherche des plus grand et petit éléments dans un tableau

 Publié le January 26, 2022  |  6 minutes  |  1158 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 le maximum et le minimum des éléments dans un tableau. Générer une liste contenant un million de termes choisis aléatoirement entre un et mille milliards. Réponse 1 2 3 4 from random import randint if __name__ == "__main__": tab = [randint(1, int(1e12)) for i in range(int(1e6))] Utiliser les fonctions min et max fournies par le langage Python afin d’afficher les maximum et minimum dans la liste. [Lire]
Diviser pour régner  Recherche 

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]
Diviser pour régner  Récursivité 

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]
Diviser pour régner  Récursivité  Traitement images 

Le tri fusion

 Publié le November 18, 2020  |  12 minutes  |  2410 mots  |  David Latreyte

Le tri fusion d’un tableau Description du tri Dans cette partie, nous allons essayer de comprendre les principes sur lesquels s’appuie ce tri. Son implémentation, pour des tableaux ou des listes chaînées, sera développée dans les prochaines sections. Le tri fusion s’appuie sur la méthode Diviser pour régner pour trier les $n$ éléments d’une séquence $S$ : Diviser : Si la séquence $S$ est composée de 0 ou un élément, retourner $S$ immédiatement ; cette séquence est déjà triée. [Lire]
Diviser pour régner  Tri