\thumb

\sectionnn{Programmation fonctionnelle}

%%%%%%%%%%%%%%%%%%%

\begin{exo}{Réécriture}{Lycée André Theuriet, Civray}{1}{5} 
\label{exo:03-reecriture}
Réécrire de façon fonctionnelle le programme suivant:

\begin{listing}{}{03-reecriture.py}\end{listing}

\begin{Remarque}
la fonction \texttt{hash} renvoie la valeur de hachage d'un objet. Une fonction de hashage produit un condensé des données de l'objet. Ce condensé est de taille fixe, dont la valeur diffère suivant la fonction utilisée.
\end{Remarque} 
\end{exo}

\begin{corrige}
Voici une possibilité:

\begin{listing}{}{03-reecriture-corrige.py}\end{listing}

\end{corrige}

%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Fonction carré}{Lycée Camille Claudel, Blois}{1}{5} 
\'Ecrire en Python de manière fonctionnelle une fonction \texttt{carre(n)} qui affiche sous forme de liste le carré des entiers de 0 à $n$ (compris).
\end{exo}

\begin{corrige}
Une possibilité est la suivante:

\begin{listing}{}{03-fctcarre.py}\end{listing}
\end{corrige}


%%%%%%%%%%%%%%%%%%%

\begin{exo}{Compteur d'occurrences}{Lycée Henri Alain-Fournier, Bourges}{2}{10} 
À l'aide de la fonction \texttt{reduce} du module \texttt{functools}, écrire en Python une fonction \texttt{compteur(liste,mot)} qui retourne le nombre d'occurrences de la chaîne \texttt{mot} dans la liste \texttt{liste}.
\end{exo}

\begin{corrige}
Une possibilité est la suivante:

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/03-compteur-occurrences.py}}}
\vspace*{-10pt}
\begin{listing}{}{03-compteur-occurrences.py}\end{listing}

\Par

Dans cet exemple, le programme retourne \og 3 \fg; ce n'est pas un bug : le\linebreak premier \og Le \fg{} n'est pas compté (car il a une majuscule) mais dans le mot \og poulailler \fg, la chaîne \og le \fg{} apparaît une fois. Il y a donc bien trois\linebreak occurrences de \og le \fg{} dans la liste.
\newpage
\end{corrige}


%%%%%%%%%%%%%%%%

\begin{exo}{Taille d'une liste}{Lycée Sainte-Anne, Brest}{2}{10} 
Supposons que la fonction \texttt{len} n'existe pas.

\'Ecrire, en Python et en utilisant le paradigme de la programmation\linebreak fonctionnelle, une fonction récursive \texttt{taille(liste)} admettant une liste comme argument et retournant sa taille.
\end{exo}

\begin{corrige}
Une première possibilité est la suivante:

\begin{listing}{Version  itérative}{03-tailleListe.py}
\end{listing}

Une deuxième possibilité est, en utilisant la récursivité:

\begin{listing}{Version  fonctionnelle récursive}{03-tailleListe2.py}
\end{listing}
\end{corrige}

%%%%%%%%%%%%%%%%%%

\begin{exo}{Calcul d'une taille moyenne}{Lycée Raoul Follereau, Nevers}{2}{15} 
On dispose d'une liste de dictionnaires \texttt{gens}:
\enlargethispage*{5em}
\Par
{\ttfamily
gens = [\\
\hspace*{1cm} {’nom’: ’Pierre’ , ’taille’: 178},\\
\hspace*{1cm}  {’name’: ’Marie’ , ’taille’: 181},\\
\hspace*{1cm}  {’name’: ’Paul’ , ’taille’: 157}\\
]
}

\newpage

\'Ecrire en Python de manière fonctionnelle une fonction \texttt{average(gens)}\linebreak admettant une liste de dictionnaires de la forme décrite précédemment et\linebreak retournant la taille moyenne des personnes figurant dans cette liste.


\textit{Aide :} on utilisera les fonctions :
\begin{center}
\texttt{reduce} et \texttt{filter(fonction,dictionnaire)},
\end{center}
cette dernière fonction renvoyant un dictionnaire contenant tous les éléments du dictionnaire d'origine pour lesquelles \texttt{fonction = True}.

On pourra aussi importer la fonction \texttt{add} du module \texttt{operator} de sorte que \texttt{reduce(add,liste)} retourne la somme des éléments de \texttt{liste}.
\end{exo}

\begin{corrige}
Voici une possibilité :\vspace*{-3mm}\enlargethispage*{5em}

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/03-calcul-taille-moyenne.py}}}
\vspace*{-10pt}
\begin{listing}{}{03-calcul-taille-moyenne.py}
\end{listing}

\Par\Par

Ce programme affiche \og 172 \fg, qui correspond à la taille moyenne des trois personnes du dictionnaire.
\newpage
\end{corrige}



%%%%%%%%%%%%%%%%%

\begin{exo}{Une fonction \og pipeline\_each \fg}{Lycée François Mauriac, Bordeaux}{3}{10}
\label{exo:03-pipeline} 
On souhaite écrire en Python une fonction \texttt{pipeline}\verb+_+\texttt{each(liste,fonctions)} comme suit:
\begin{itemize}
\item son premier paramètre (\texttt{liste}) reçoit une liste de chaînes de caractères;
\item son second paramètre (\texttt{fonctions}) reçoit une liste d'une ou plusieurs\linebreak fonctions qui, chacune, reçoit une liste de chaînes en argument et y effectue un traitement.
\end{itemize}
La fonction \texttt{pipeline}\verb+_+\texttt{each(liste,fonctions)} doit appliquer, tour à tour, chacune des fonctions de la liste \texttt{fonctions} à la liste de chaînes de caractères \texttt{liste}. Puis elle doit renvoyer cette liste à l'issue des traitements successifs.
\Par

Compléter le programme suivant afin d'avoir en affichage :

{\ttfamily
['Le Monde Est À Nous;', ' Il Ne Faut Pas Le Détériorer;']
}

\enlargethispage*{5em}

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/03-pipeline_each-enonce.py}}}
\vspace*{-10pt}
\begin{listing}{}{03-pipeline_each-enonce.py}\end{listing}

\end{exo}

\begin{corrige}
Une solution envisageable est la suivante:\vspace*{-3mm}

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/03-pipeline_each-corrige.py}}}
\vspace*{-10pt}
\begin{listing}{}{03-pipeline_each-corrige.py}\end{listing}
\end{corrige}

\newpage

\sectionnn{Diviser pour régner}

\begin{exo}{Fonction \og maximum \fg{} d'une liste }{Lycée Jean-Joseph Fourier, Auxerre}{1}{15} 
\label{exo:fct-max-liste}
On dispose d'une liste \texttt{L} de nombres.

En utilisant la méthode du \og diviser pour régner \fg, implémenter une fonction \texttt{maximum(L,debut,fin)} retournant le maximum de \texttt{L}.
\end{exo}

\begin{corrige}
L'idée consiste à diviser en deux la liste \texttt{L} en deux parties et à trouver le maximum des deux parties. Le maximum global sera la plus grande des valeurs ainsi trouvées. On doit partager en deux jusqu'à obtenir des listes élémentaires (à 1 élément). On doit alors utiliser la récursivité.

Une fonction possible est alors la suivante :\vspace*{-3mm}

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/03-FctMaximum.py}}}
\vspace*{-10pt}
\begin{listing}{}{03-FctMaximum.py}\end{listing}
\end{corrige}

%%% NEW 2025

\begin{exo}{Le tri fusion}{Lycée Richelieu, Versailles}{2}{15}
Le \textit{tri fusion} est un algorithme de tri efficace qui suit le paradigme \og diviser pour régner \fg. Il divise la liste à trier en deux moitiés, trie chaque moitié récursivement, puis fusionne les deux moitiés triées pour obtenir la liste triée complète.

Notre objectif est d'implémenter l'algorithme de tri fusion en Python.

\Par

\textit{Instructions:}

\begin{questions}
    \item Écrivez une fonction \texttt{tri\_fusion(liste)} qui prend une liste d'entiers en entrée et retourne une nouvelle liste triée.
    \item La fonction doit suivre les étapes suivantes :
    \begin{itemize}
        \item Si la liste est vide ou ne contient qu'un seul élément, elle est déjà triée. Retournez-la telle quelle.
        \item Divisez la liste en deux moitiés.
        \item Triez récursivement chaque moitié en appelant \texttt{tri\_fusion} sur chaque moitié.
        \item Fusionnez les deux moitiés triées pour obtenir la liste triée complète.
    \end{itemize}
    \item Écrivez une fonction auxiliaire \texttt{fusion(gauche, droite)} qui prend deux listes triées en entrée et retourne une seule liste triée contenant tous les éléments des deux listes.
    \item Testez votre fonction \texttt{tri\_fusion} avec plusieurs listes d'entiers pour vérifier qu'elle fonctionne correctement.
\end{questions}
\end{exo}

\begin{corrige}
Le programme proposé page ci-contre répond aux instructions de l'énoncé.\newpage

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/03-tri-fusion.py}}}
\vspace*{-10pt}

\begin{listing}{}{03-tri-fusion-print.py}\end{listing}
\end{corrige}

%%% NEW 2025

\begin{exo}{Recherche binaire récursive}{Lycée François Mauriac, Bordeaux}{2}{20}
La recherche binaire est un algorithme efficace pour trouver un élément dans une liste triée. Elle fonctionne en divisant la liste en deux à chaque étape et en déterminant dans quelle moitié se trouve l'élément recherché.

\Par

Notre objectif est d'implémenter la recherche binaire de manière récursive en Python.

\textit{Instructions}:

\begin{questions}
    \item Écrivez une fonction \texttt{recherche\_binaire(liste, element, debut, fin)} qui prend en entrée une liste triée \texttt{liste}, un élément à rechercher \texttt{element}, et les indices de début \texttt{debut} et de fin \texttt{fin} de la portion de la liste à rechercher. La fonction doit retourner l'indice de l'élément s'il est trouvé, sinon \texttt{-1}.
    \item La fonction doit suivre les étapes suivantes :
    \begin{itemize}
        \item Calculez l'indice du milieu de la portion de la liste.
        \item Comparez l'élément au milieu avec l'élément recherché.
        \item Si l'élément au milieu est égal à l'élément recherché, retournez l'indice du milieu.
        \item Si l'élément recherché est inférieur à l'élément au milieu, appelez récursivement la fonction sur la moitié gauche de la liste.
        \item Si l'élément recherché est supérieur à l'élément au milieu, appelez récursivement la fonction sur la moitié droite de la liste.
        \item Si la portion de la liste est vide (c'est-à-dire que \texttt{debut} dépasse \texttt{fin}), retournez \texttt{-1}.
    \end{itemize}
    \item Testez votre fonction \texttt{recherche\_binaire} avec plusieurs listes triées et éléments pour vérifier qu'elle fonctionne correctement.
\end{questions}
\end{exo}

\begin{corrige}
Voici une proposition répondant aux instructions:\enlargethispage*{5em}

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/03-recherche-binaire.py}}}
\vspace*{-10pt}

\begin{listing}{}{03-recherche-binaire-print.py}\end{listing}
\newpage
\end{corrige}

%%%%%%%%%%%%%%%%%%%

\begin{exo}{Algorithme de Karatsuba}{Lycée polyvalent Émile Zola, Aix-en-Provence}{3}{30} 
\label{prog:algo-karatsuba}
\index{Karatsuba (algorithme de)}
L'objectif de cet exercice est d'utiliser l'algorithme de Karatsuba afin de\linebreak trouver le produit de deux polynômes $P$ et $Q$.

On rappelle qu'un \textit{polynôme en $X$ de degré $n$} est une expression de la forme :
\[
P(X)=\sum_{k=0}^n a_k X^k.
\]

On représente alors en Python le polynôme $P$ par la liste \texttt{[a0,a1,..,an]} des coefficients $a_0$, $a_1$, ..., $a_n$.

\begin{questions}
\item \'Ecrire une fonction \texttt{standardise(P,Q)} qui retourne un couple de deux listes de dimension $\max\big(\deg(P);\deg(Q)\big)$, où $\deg(P)$ représente le\linebreak degré de $P$.

Par exemple, si $P(X)=3+2X$ et $Q(X)=5-7X+4X^2$ (soit en\linebreak Python : \texttt{P = [3,2]} et \texttt{Q = [5,-7,4]}), la fonction devra retourner:\linebreak \texttt{([3,2,0] , [5,-7,4])}.

\item \'Ecrire une fonction \texttt{add(P,Q)} qui retourne une liste dont les éléments sont les coefficients de la somme des deux polynômes $P$ et $Q$, puis une fonction \texttt{sous(P,Q)} qui retourne sous forme de liste le résultat de $P(X)-Q(X)$.

Par exemple, si $P(X)=3+2X$ et $Q(X)=5-7X+4X^2$ alors :
\begin{itemize}
\item \texttt{add(P,Q) = [8,-5,4]};
\item \texttt{sous(P,Q) = [-2,9,-4]}. 
\end{itemize}

\item L'algorithme de Karatsuba consiste à décomposer $P$ et $Q$ de la manière suivante:
\[
\begin{cases}
P(X) & = X^k P_1(X) + P_0(X),\quad \deg P_0 \leqslant k\\
Q(X) & = X^k Q_1(X) + Q_0(X),\quad \deg Q_0 \leqslant k
\end{cases}
\]
où $k = E\left(\dfrac{n}{2}\right)$ (partie entière de la moitié de \texttt{n}).

\begin{questions}
\item On suppose que:
\begin{align*} 
(PQ)(X) & = (P_0Q_0)(X)\\ 
& + \big( (P_0+P_1)(Q_0+Q_1) - P_0Q_0 - P_1Q_1\big)(X) X^k\\ 
& + (P_1Q_1)(X) X^{2k}.
\end{align*}

\'Ecrire une fonction \texttt{prodmonome(P,k)} qui renvoie sous forme de liste le produit du polynôme $P$ par $X^k$.

\item En déduire une fonction \texttt{prod(P,Q)} qui renvoie sous forme de liste le produit de deux polynômes $P$ et $Q$.\enlargethispage*{3em}

\item Tester cette fonction sur les polynômes:
\[
P(X)=5-2X^4+3X^3-X^2+2X-1 \text{ et }  Q(X)=-3+5X+2X^2.
\]
\end{questions}
\end{questions}
\end{exo}

\begin{corrige}
\begin{questions}
\item Une fonction possible est la suivante:\vspace*{-3mm}\enlargethispage*{5em}

\begin{listing}{}{03-karatsuba-q1.py}\end{listing}

\Par

\item Une fonction possible est la suivante:\vspace*{-3mm}

\begin{listing}{}{03-karatsuba-q2.py}\end{listing}

\item 
\begin{questions}
\item Une fonction possible est la suivante:\vspace*{-3mm}

\begin{listing}{}{03-karatsuba-q3a.py}\end{listing}

\Par
En effet,
\[
P(X) X^k = X^k \sum_{i=0}^n a_i X^i = \sum_{i=0}^n a_i X^{i+k} = \sum_{i=k+1}^{n+k} a_{i-k-1} X^{i}. 
\]
Ainsi, $a_0$ n'est plus le coefficient de $X^0$ mais de $X^{0+k}$, $a_1$ est celui de $X^{1+k}$, etc.

\Par

\item  ~\par\vspace*{-7mm}\begin{listing}{}{03-karatsuba-q3b.py}\end{listing}

\newpage

\item On définit dans cette question P et Q ainsi :

\begin{center}
\texttt{P , Q = [5,-2,3,-1,2,-1] , [-3,5,2]}
\end{center}

En appelant la fonction \texttt{prod}, on obtient la liste :
\begin{center}
\ttfamily [-15, 31, -9, 14, -5, 11, -1, -2, 0, 0, 0]
\end{center}
ce qui signifie que:
\[
PQ(X)=-15+31X-9X^2+14X^3-5X^4+11X^5-X^6-2X^7.
%ERR NON DETECTEE PQ(X)=-15+31X-9X^2+14X^3-5X^4+11X^5-X^6-12X^7.
\]
\end{questions}
\end{questions}

\qrset{height=1.1cm,version=5}\rput(-1,0.5){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/03-Karatsuba.py}}}
\textit{Télécharger le programme complet.}
\end{corrige}

%%%%%%%%%%%%%%%%%%%%

\begin{exo}{Le problème du sac à dos}{Lycée Camille Jullian, Bordeaux}{3}{30} 
\label{exo:sac-a-dos-1}
\index{Sac à dos (problème du)}
On dispose d'un sac à dos ne pouvant supporter qu'un poids $P$. On dispose de plus d'une collection de $n$ objets, chaque objet ayant un poids $p_i$ et une valeur $v_i$, $1 \leqslant i \leqslant n$, avec $p_1+p_2+\cdots+p_n>P$.

On souhaite mettre dans le sac le plus d'objets possible tout en maximisant la valeur totale des objets.

En utilisant une approche récursive \og diviser pour régner \fg, donner une\linebreak solution en Python qui affiche la valeur maximale.

Appliquer le programme au cas où l'ensemble des objets (poids,valeur) est :
\[
E = \{ (12,14) ; (1,2) ; (4,10) ; (1,1) ; (2,2) \}
\]
et où $P = 15$.
\end{exo}

\begin{corrige}
Pour résoudre un tel problème, il faut avant tout passer par une formalisation mathématique : une traduction algébrique.
\begin{itemize}
\item Notons $E = \{ (p_1,v_1) ; \cdots ; (p_n,v_n) \}$ l'ensemble des $n$ objets.
\item La solution attendue sera un $n$-uplet $(x_1;x_2;\ldots;x_n)$ où $x_i=0$ si l'on ne prend pas l'objet $i$ et $x_i=1$ dans le cas contraire.
\item Il faut alors que $\displaystyle\sum_{i=1}^n x_ip_i \leqslant P$ et $\displaystyle\sum_{i=1}^n x_iv_i$ maximale.
\end{itemize}

Nous avons vu dans le livre de Première NSI qu'une approche gloutonne était peu recommandée car dans certains cas, la solution donnée n'est pas optimale.

On nous demande ici une approche récursive de type \og diviser pour régner \fg. Il est alors important dans ce type d'exercices d'établir une formule de\linebreak récurrence. Le raisonnement prend nécessairement en compte le poids et la valeur d'un objet.

Notons $V(i,p)$ la valeur maximale des objets que l'on peut mettre dans un sac de capacité $p$ en ne prenant que les $i$ premiers objets. Ce qui nous intéresse est alors $V(n,P)$. On a alors:
\begin{itemize}
\item $V(0,p)=0$ car s'il n'y a pas d'objet, la valeur maximale est nécessairement 0;
\item Si $p_i > p$ alors $V(i,p)=V(i-1,p)$ car si le poids de l'objet $i$ est supérieure au poids maximal, on ne l'ajoute pas et la valeur maximale des objets reste inchangée par rapport à celle de l'étape précédente;
\item Enfin, si $p_i \leqslant p$ alors $V(i,p)=\max\big( V(i-1,p) ; V(i-1,p-p_i) + v_i \big)$ car il faut regarder la valeur obtenue en ajoutant la valeur de l'objet $i$ ($v_i$) à la valeur maximale correspondant à $i-1$ objets dans un sac de capacité $p-p_i$.
\end{itemize}

\newpage

Ces relations de récurrence nous mènent alors à l'implémentation suivante :

\qrset{height=1.1cm,version=5}\rput(-1,-0.7){
\psframebox{\qrcode{https://idl-live.prepamath.fr/ILTNSI/03-sac-a-dos.py}}}
\vspace*{-10pt}
\begin{listing}{}{03-sac-a-dos.py}\end{listing}

\Par

Cela donne avec notre exemple :

\hrulefill
{\ttfamily

\pychevrons E = [ (12,14) , (1,2) , (4,10) , (1,1) , (2,2) ]

\pychevrons P = 15

\pychevrons initSac(E,P)

18
}

\hrulefill

\og 18 \fg{}  est en effet la valeur maximale que l'on obtient en faisant $14 + 2 + 2$ (objets 1, 2 et 5).
\end{corrige}

\thumb
\AfficheCorrige
