{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Université d’Orléans - Licence 1 semestre 1 - 2026-27
Programmation et Algorithmique 1 \n",
"TP 03
\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Exercice 1 - Les listes comme des piles\n",
"\n",
"Une liste peut représenter le concept de \"pile\". \n",
"Tous se passe comme pour une pile d'assiettes :\n",
"\n",
"- une pile peut être vide ;\n",
"- une pile peut être pleine. La valeur de la taille maximum est donnée dans le premier script (variable taille_max) et cette variable sera utilisée chaque fois que ce sera nécessaire ;\n",
"- une pile non vide possède un sommet (la valeur d'indice le plus élevé) ;\n",
"- on peut empiler une valeur \"en haut\" de la pile (ce qui revient à placer cette valeur au sommet de la pile), si la pile n'est pas pleine ;\n",
"- on peut dépiler, c'est-à-dire récupérer le sommet de la pile (qui est sorti de la pile), si la pile n'est pas vide ;\n",
"\n",
"Pour toutes ces fonctionnalités, on pourra utiliser les méthodes classiques des listes. Les listes que nous utiliserons seront des listes d'**entiers positifs**."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## question 1\n",
"Ecrivez une fonction est_vide(l) qui retourne une valeur booléenne disant si oui ou non la liste l est vide."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"liste1 = [1, 4, 5] est vide ? ... False\n",
"liste2 = [] est vide ? ... True\n"
]
}
],
"source": [
"def est_vide(l) :\n",
" # retourne True si len(l) vaut 0, False sinon\n",
" pass\n",
"\n",
"\n",
"taille_max = 5\n",
"\n",
"# tests de la fonction\n",
"liste1 = [1, 4, 5]\n",
"print(\"liste1 = [1, 4, 5] est vide ? ...\", est_vide(liste1))\n",
"liste2 = []\n",
"print(\"liste2 = [] est vide ? ...\", est_vide(liste2))\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## question 2\n",
"Ecrivez une fonction est_pleine(l) qui retourne une valeur booléenne disant si oui ou non la liste l est pleine. On rappelle que la pile contiendra au maximum 5 éléments, même si une liste python peut en fait contenir bien plus d'éléments. "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"liste1 = [1, 4, 5] est pleine ? ... False\n",
"liste2 = [] est pleine ? ... False\n",
"liste3 = [7, 5, 1, 3, 8] est pleine ? ... True\n"
]
}
],
"source": [
"def est_pleine(l) :\n",
" # retourne True si len(l) vaut taille_max, False sinon\n",
" pass\n",
"\n",
"# tests de la fonction\n",
"liste1 = [1, 4, 5]\n",
"print(\"liste1 = [1, 4, 5] est pleine ? ...\", est_pleine(liste1))\n",
"liste2 = []\n",
"print(\"liste2 = [] est pleine ? ...\", est_pleine(liste2))\n",
"liste3 = [7, 5, 1, 3, 8]\n",
"print(\"liste3 = [7, 5, 1, 3, 8] est pleine ? ...\", est_pleine(liste3))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## question 3\n",
"Ecrivez une fonction afficher_sommet(l) qui affiche le sommet de la liste l, sans le retirer de la pile. Attention, une pile vide n'a pas de sommet, l'affichage sera alors à adapter."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"5\n",
"liste vide, pas de sommet\n",
"7\n"
]
}
],
"source": [
"def afficher_sommet(l) :\n",
" # si la liste n'est pas vide, on affiche le dernier élément\n",
" # sinon, on affiche un message adapté\n",
" pass\n",
"\n",
"# tests de la fonction\n",
"liste1 = [1, 4, 5]\n",
"afficher_sommet(liste1)\n",
"liste2 = []\n",
"afficher_sommet(liste2)\n",
"liste3 = [7]\n",
"afficher_sommet(liste3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## question 4\n",
"Ecrivez une fonction depiler(l) qui supprime le sommet de la liste l et **LE RETOURNE**, quand la liste n'est pas vide. Si la liste est vide, la fonction retourne la valeur -1."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"liste avant dépilage : [1, 4, 5]\n",
"sommet : 5\n",
"liste après dépilage : [1, 4]\n",
"\n",
"liste avant dépilage : [1]\n",
"sommet : 1\n",
"liste après dépilage : []\n",
"\n",
"liste avant dépilage : []\n",
"sommet : -1\n",
"liste après dépilage : []\n"
]
}
],
"source": [
"def depiler(l) :\n",
" # si la liste n'est pas vide, on récupère le sommet par pop et on le retourne\n",
" # sinon, on retourne -1\n",
" pass\n",
"\n",
"# tests de la fonction\n",
"liste1 = [1, 4, 5]\n",
"print(\"liste avant dépilage :\", liste1)\n",
"s1 = depiler(liste1)\n",
"print(\"sommet :\", s1)\n",
"print(\"liste après dépilage :\", liste1)\n",
"print()\n",
"liste2 = [1]\n",
"print(\"liste avant dépilage :\", liste2)\n",
"s2 = depiler(liste2)\n",
"print(\"sommet :\", s2)\n",
"print(\"liste après dépilage :\", liste2)\n",
"print()\n",
"liste3 = []\n",
"print(\"liste avant dépilage :\", liste3)\n",
"s3 = depiler(liste3)\n",
"print(\"sommet :\", s3)\n",
"print(\"liste après dépilage :\", liste3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## question 5\n",
"Ecrivez une fonction empiler(l, n) qui empile la valeur n sur la liste l si la liste n'est pas pleine. Si la liste est pleine, rien ne se passe."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1, 4, 5, 8]\n",
"[1, 4, 5, 8, 11]\n",
"[1, 4, 5, 8, 11]\n"
]
}
],
"source": [
"def empiler(l, n) :\n",
" # si la liste n'est pas pleine, on ajoute n au bout de la liste l\n",
" # sinon, on ne fait rien\n",
" pass\n",
" \n",
"\n",
"# tests de la fonction\n",
"liste1 = [1, 4, 5]\n",
"empiler(liste1, 8)\n",
"print(liste1)\n",
"\n",
"empiler(liste1, 11)\n",
"print(liste1)\n",
"\n",
"empiler(liste1, 9)\n",
"print(liste1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## question 6\n",
"Ecrivez une fonction empiler_liste(l1, l2) qui empile les valeurs contenues dans l2 sur la liste l1, et ceci tant que la liste l1 n'est pas pleine. Attention, l'empilage se fera par dépilage de l2. Autrement dit, on retire le sommet de l2 pour l'empiler sur l1. On arrête quand l1 est pleine ou quand l2 a été vidée."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1, 4, 5, 8, 7]\n",
"[2, 3]\n",
"[1, 7, 3, 2]\n",
"[]\n"
]
}
],
"source": [
"def empiler_liste(l1, l2) :\n",
" # tant que la liste l1 n'est pas pleine et que la liste l2 n'est pas vide :\n",
" # - on dépile la liste l2\n",
" # - on empile la valeur dépilée sur la liste l1\n",
" pass\n",
"\n",
"# tests de la fonction\n",
"liste1 = [1, 4, 5]\n",
"liste2 = [2, 3, 7, 8]\n",
"\n",
"empiler_liste(liste1, liste2)\n",
"print(liste1)\n",
"print(liste2)\n",
"\n",
"liste3 = [1]\n",
"liste4 = [2, 3, 7]\n",
"\n",
"empiler_liste(liste3, liste4)\n",
"print(liste3)\n",
"print(liste4)\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Exercice 2 - Quelques fonctions pour les listes\n",
"\n",
"Dans cet exercice, on va coder des fonctions utiles sur les listes d'entiers"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# question 1\n",
"\n",
"Codez la fonction est_croissante(liste) qui dit si les éléments de la liste sont rangés en ordre croissant. \n",
"- Remarque 1 : on considère que la liste [1, 3, 3, 4, 4], qui comporte des valeurs égales, est croissante. La croissance est donc considérée au sens large.\n",
"- Remarque 2 : la liste vide sera considérée, par extension, comme croissante.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[3, 5, 8] est croissante ? True\n",
"[3, 3, 8] est croissante ? True\n",
"[3, 8, 5] est croissante ? False\n",
"[] est croissante ? True\n",
"[3] est croissante ? True\n",
"[1, 2, 3, 4, 5, 6, 8, 7, 9] est croissante ? False\n",
"[1, 2, 3, 4, 5, 6, 7, 9, 8] est croissante ? False\n",
"[1, 2, 3, 4, 5, 6, 7, 8, 9] est croissante ? True\n"
]
}
],
"source": [
"def est_croissante(liste) :\n",
" pass\n",
"\n",
"\n",
"# tests de la fonction\n",
"l1 = [3, 5, 8]\n",
"print(l1, \"est croissante ?\", est_croissante(l1))\n",
"l2 = [3, 3, 8]\n",
"print(l2, \"est croissante ?\", est_croissante(l2)) \n",
"l3 = [3, 8, 5]\n",
"print(l3, \"est croissante ?\", est_croissante(l3)) \n",
"l4 = []\n",
"print(l4, \"est croissante ?\", est_croissante(l4))\n",
"l5 = [3]\n",
"print(l5, \"est croissante ?\", est_croissante(l5)) \n",
"l6 = [1, 2, 3, 4, 5, 6, 8, 7, 9]\n",
"print(l6, \"est croissante ?\", est_croissante(l6))\n",
"l7 = [1, 2, 3, 4, 5, 6, 7, 9, 8]\n",
"print(l7, \"est croissante ?\", est_croissante(l7))\n",
"l8 = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
"print(l8, \"est croissante ?\", est_croissante(l8))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# question 2\n",
"\n",
"Codez la fonction est_decroissante(liste) qui dit si les éléments de la liste sont rangés en ordre décroissant. \n",
"- Remarque 1 : on considère que la liste [4, 4, 3, 3, 1], qui comporte des valeurs égales, est décroissante. La décroissance est donc considérée au sens large.\n",
"- Remarque 2 : la liste vide sera considérée, par extension, comme décroissante."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[3, 5, 8] est décroissante ? False\n",
"[8, 3, 3] est décroissante ? True\n",
"[8, 5, 3] est décroissante ? True\n",
"[] est décroissante ? True\n",
"[3] est décroissante ? True\n"
]
}
],
"source": [
"def est_decroissante(liste) :\n",
" pass\n",
"\n",
"# tests de la fonction\n",
"l1 = [3, 5, 8]\n",
"print(l1, \"est décroissante ?\", est_decroissante(l1))\n",
"l2 = [8, 3, 3]\n",
"print(l2, \"est décroissante ?\", est_decroissante(l2)) \n",
"l3 = [8, 5, 3]\n",
"print(l3, \"est décroissante ?\", est_decroissante(l3)) \n",
"l4 = []\n",
"print(l4, \"est décroissante ?\", est_decroissante(l4))\n",
"l5 = [3]\n",
"print(l5, \"est décroissante ?\", est_decroissante(l5)) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# question 3\n",
"\n",
"Codez la fonction est_constante(liste) qui dit si les éléments de la liste sont tous égaux. Vous vous resservirez obligatoirement des deux fonctions précédentes. \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[3, 5, 8] est constante ? False\n",
"[3, 3] est constante ? True\n",
"[8, 8, 3, 8] est constante ? False\n",
"[] est constante ? True\n",
"[3] est constante ? True\n"
]
}
],
"source": [
"def est_constante(liste) :\n",
" pass\n",
"\n",
"# tests de la fonction\n",
"l1 = [3, 5, 8]\n",
"print(l1, \"est constante ?\", est_constante(l1))\n",
"l2 = [3, 3]\n",
"print(l2, \"est constante ?\", est_constante(l2)) \n",
"l3 = [8, 8, 3, 8]\n",
"print(l3, \"est constante ?\", est_constante(l3)) \n",
"l4 = []\n",
"print(l4, \"est constante ?\", est_constante(l4))\n",
"l5 = [3]\n",
"print(l5, \"est constante ?\", est_constante(l5)) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# question 4\n",
"\n",
"Codez la fonction est_sans_repetition(liste) qui dit si la liste est sans aucun doublon. Vous pourrez utiliser la méthode *count* des listes."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[3, 5, 8] est sans doublon ? True\n",
"[3, 3] est sans doublon ? False\n",
"[8, 8, 3, 8] est sans doublon ? False\n",
"[] est sans doublon ? True\n",
"[3] est sans doublon ? True\n"
]
}
],
"source": [
"def est_sans_doublon(liste) :\n",
" pass\n",
"\n",
"# tests de la fonction\n",
"l1 = [3, 5, 8]\n",
"print(l1, \"est sans doublon ?\", est_sans_doublon(l1))\n",
"l2 = [3, 3]\n",
"print(l2, \"est sans doublon ?\", est_sans_doublon(l2)) \n",
"l3 = [8, 8, 3, 8]\n",
"print(l3, \"est sans doublon ?\", est_sans_doublon(l3)) \n",
"l4 = []\n",
"print(l4, \"est sans doublon ?\", est_sans_doublon(l4))\n",
"l5 = [3]\n",
"print(l5, \"est sans doublon ?\", est_sans_doublon(l5)) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# question 5\n",
"\n",
"Seulement en réutilisant des fonctions déjà écrites, codez deux fonctions est_strictement_croissante(liste) et est_strictement_decroissante(liste) qui disent si oui ou non la liste est strictement (dé)croissante (dans ce cas, par exemple, [3, 3, 4] est croissante mais pas strictement croissante par exemple)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[3, 5, 8] est strictement croissante ? True\n",
"[8, 3, 3] est strictement décroissante ? False\n",
"[8, 5, 3] est strictement décroissante ? True\n",
"[] est strictement décroissante ? True\n",
"[3] est strictement croissante ? True\n"
]
}
],
"source": [
"def est_strictement_decroissante(liste) :\n",
" pass\n",
"\n",
"def est_strictement_croissante(liste) :\n",
" pass\n",
"\n",
"# tests des fonctions\n",
"l1 = [3, 5, 8]\n",
"print(l1, \"est strictement croissante ?\", est_strictement_croissante(l1))\n",
"l2 = [8, 3, 3]\n",
"print(l2, \"est strictement décroissante ?\", est_strictement_decroissante(l2)) \n",
"l3 = [8, 5, 3]\n",
"print(l3, \"est strictement décroissante ?\", est_strictement_decroissante(l3)) \n",
"l4 = []\n",
"print(l4, \"est strictement décroissante ?\", est_strictement_decroissante(l4))\n",
"l5 = [3]\n",
"print(l5, \"est strictement croissante ?\", est_strictement_croissante(l5)) "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Exercice 3 - Fusion de listes strictement croissantes\n",
"\n",
"La fusion de deux listes strictement croissantes donne une liste strictement croissante selon les exemples suivants :\n",
"- la fusion de [2, 4, 6] et de [1, 3, 7] donne [1, 2, 3, 4, 6, 7]\n",
"- la fusion de [2, 4, 6] et de [2, 4, 7] donne [2, 4, 6, 7]\n",
"- la fusion de [2, 4, 6] et de [] donne [2, 4, 6]\n",
"- la fusion de [2, 4, 6] et de [2, 4, 6] donne [2, 4, 6]\n",
"\n",
"En résumé, on garde tous les éléments des deux listes, sans doublon, et rangés en ordre croissant.\n",
"\n",
"Dans cet exercice vous n'avez **pas le droit d'utiliser** la méthode *sort*.\n",
"\n",
"Codez et testez la méthode fusion(liste1, liste2) qui retourne la liste fusion de liste1 et liste2\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def fusion(liste1, liste2) :\n",
" pass\n",
" \n",
"# tests de la fonction\n",
"l1 = [2, 4, 6]\n",
"l2 = [1, 3, 7]\n",
"print(\"fusion({0}, {1}) = {2}\".format(l1, l2, fusion(l1, l2)))\n",
"l1 = [2, 4, 6]\n",
"l2 = [2, 4, 7]\n",
"print(\"fusion({0}, {1}) = {2}\".format(l1, l2, fusion(l1, l2)))\n",
"l1 = [2, 4, 6]\n",
"l2 = []\n",
"print(\"fusion({0}, {1}) = {2}\".format(l1, l2, fusion(l1, l2)))\n",
"l1 = [2, 4, 6]\n",
"l2 = [2, 4, 6]\n",
"print(\"fusion({0}, {1}) = {2}\".format(l1, l2, fusion(l1, l2)))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Exercice 4 - Listes et reliefs\n",
"\n",
"Dans cet exercice, on souhaite vérifier si les valeurs entières d'une liste sont constantes (on parle alors de \"Plateau\"), ou croissantes puis décroissantes (on parle alors d'un \"Pic\") ou, enfin, décroissantes puis croissantes (on parle alors d'une \"Vallée\"). "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## question 1\n",
"Ecrire une fonction pic(l) qui prend en paramètre une liste et retourne True si la liste est un pic, c'est-à-dire que les valeurs de la liste sont strictement croissantes jusqu'à une position p (tel que 0 < p < longeur de la liste-1), puis strictement décroissantes, sans plateau au sommet. Par exemple (1, 3, 4, 2, 0, -1) est un pic, mais (1, 3, 4, 4, 2, 0, -1) n'en est pas un. \n",
"\n",
"Pour vérifier qu'il n'y a pas de \"plateau\", on pourra compter le nombre de montées et le nombre de descentes, puis vérifier que leur somme est égale au nombre de valeurs du tuple moins 1. "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Détermine si une liste est un PIC\n",
"\n",
"def pic(l) :\n",
" pass\n",
" \n",
"l1 = [1, 2, 3, 2, 0]\n",
"l2 = [1, 2, 3, 3, 3, 0]\n",
"l3 = [3, 2, 4, 1]\n",
"print(pic(l1))\n",
"print(pic(l2))\n",
"print(pic(l3))\n",
" \n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## question 2\n",
"Ecrire une fonction vallee(l) qui prend en paramètre une liste et retourne True si la liste est une vallée, c'est-à-dire que les valeurs de la liste sont strictement décroissantes jusqu'à une position p (tel que 0 < p < longeur du tuple-1), puis strictement croissantes, sans plateau dans la vallée. Par exemple (1, -1, -2, 0, 1, 2, 3) est une vallée, mais (2, 1, 0, 0, 2, 3) n'en est pas une. \n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Détermine si une liste est une vallée\n",
"\n",
"def vallee(l) :\n",
" pass\n",
"\n",
"# Test vallee(l)\n",
"l1=[3, 2, 0, 4, 5, 6]\n",
"l2=[3, 2, 0, 0, 4, 5]\n",
"l3=[2, 1, 0, 1, 2, 1]\n",
"print(vallee(l1))\n",
"print(vallee(l2))\n",
"print(vallee(l3))\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.3"
}
},
"nbformat": 4,
"nbformat_minor": 2
}