{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Université d’Orléans - Licence 1 semestre 1 - 2026-27
Programmation et Algorithmique 1 \n",
"TP 03 (enseignant)
\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": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"False\n",
"True\n"
]
}
],
"source": [
"def est_vide(l) :\n",
" return len(l) == 0\n",
"\n",
"\n",
"taille_max = 5\n",
"\n",
"# tests de la fonction\n",
"liste1 = [1, 4, 5]\n",
"print(est_vide(liste1))\n",
"liste2 = []\n",
"print(est_vide(liste2))"
]
},
{
"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": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"False\n",
"False\n",
"True\n"
]
}
],
"source": [
"def est_pleine(l) :\n",
" return len(l) == taille_max\n",
"\n",
"# tests de la fonction\n",
"liste1 = [1, 4, 5]\n",
"print(est_pleine(liste1))\n",
"liste2 = []\n",
"print(est_pleine(liste2))\n",
"liste3 = [7, 5, 1, 3, 8]\n",
"print(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": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"sommet : 5\n",
"sommet : indéfini, la pile est vide\n",
"sommet : 7\n"
]
}
],
"source": [
"def afficher_sommet(l) :\n",
" if not est_vide(l) :\n",
" print(\"sommet :\", l[len(l) - 1])\n",
" else :\n",
" print(\"sommet : indéfini, la pile est vide\")\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": 4,
"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",
" if not est_vide(l) :\n",
" return l.pop()\n",
" else :\n",
" return -1\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": 5,
"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",
" if not est_pleine(l) :\n",
" l.append(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": 6,
"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",
" while not est_pleine(l1) and not est_vide(l2) :\n",
" l1.append(l2.pop())\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": [],
"source": [
"def est_croissante(liste) :\n",
" croiss = True\n",
" i = 0\n",
" while croiss and i + 1 < len(liste) :\n",
" croiss = liste[i] <= liste[i + 1]\n",
" i += 1\n",
" return croiss\n",
"\n",
" # ou\n",
" # for i in range(len(liste) - 1) :\n",
" # if liste[i] > liste[i + 1] :\n",
" # return False\n",
" # return True\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)) "
]
},
{
"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": [],
"source": [
"def est_decroissante(liste) :\n",
" decroiss = True\n",
" i = 0\n",
" while decroiss and i + 1 < len(liste) :\n",
" decroiss = liste[i] >= liste[i + 1]\n",
" i += 1\n",
" return decroiss\n",
"\n",
" # ou\n",
" # for i in range(len(liste) - 1) :\n",
" # if liste[i] < liste[i + 1] :\n",
" # return False\n",
" # return True\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": [],
"source": [
"def est_constante(liste) :\n",
" return est_croissante(liste) and est_decroissante(liste)\n",
"\n",
" # ou, si on reproduit le code précédent :\n",
" # for i in range(len(liste) - 1) :\n",
" # if liste[i] != liste[i + 1] :\n",
" # return False\n",
" # return True\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": [],
"source": [
"def est_sans_doublon(liste) :\n",
" sans_doublon = True\n",
" for i in range(len(liste)) :\n",
" sans_doublon = liste.count(liste[i]) == 1\n",
" if not sans_doublon :\n",
" break \n",
" return sans_doublon\n",
"\n",
" # ou, toujours avec le même genre de code\n",
" # for i in range(len(liste)) :\n",
" # if liste.count(liste[i] > 1 :\n",
" # return False\n",
" # return True\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": [],
"source": [
"def est_strictement_decroissante(liste) :\n",
" return est_decroissante(liste) and est_sans_doublon(liste)\n",
"\n",
"def est_strictement_croissante(liste) :\n",
" return est_croissante(liste) and est_sans_doublon(liste)\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",
" liste = []\n",
" i = 0\n",
" j = 0\n",
" while i < len(liste1) and j < len(liste2) :\n",
" if liste1[i] < liste2[j] :\n",
" liste.append(liste1[i])\n",
" i += 1\n",
" elif liste2[j] < liste1[i] :\n",
" liste.append(liste2[j])\n",
" j += 1\n",
" else :\n",
" liste.append(liste1[i])\n",
" i += 1\n",
" j += 1\n",
" if i == len(liste1) :\n",
" for k in range(j, len(liste2)) :\n",
" liste.append(liste2[k])\n",
" else :\n",
" for k in range(i, len(liste1)) :\n",
" liste.append(liste1[k])\n",
" return liste\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": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"True\n",
"False\n",
"False\n"
]
}
],
"source": [
"# Détermine si une liste est un PIC\n",
"\n",
"def pic(l) :\n",
" longueur = len(l)\n",
" if (longueur < 3) :\n",
" # Liste trop courte pour être un Pic\n",
" return False \n",
" else :\n",
" croissance = False # pour savoir si la montée existe bien\n",
" nb_montees = 0 # pour vérifier qu'il n'y a pas de plateau \n",
" decroissance = False # pour savoir si la descente existe bien\n",
" nb_descentes = 0\n",
" for i in range(0, longueur - 1):\n",
" if (l[i] < l[i+1]) and not decroissance : # montée\n",
" croissance = True\n",
" nb_montees += 1\n",
" else :\n",
" if (l[i] > l[i+1]) and croissance : # descente\n",
" decroissance = True\n",
" nb_descentes += 1\n",
" if (nb_montees + nb_descentes == longueur - 1) and croissance and decroissance :\n",
" # pic sans plateau\n",
" return True\n",
" else:\n",
" return False\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": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"True\n",
"False\n",
"False\n"
]
}
],
"source": [
"# Détermine si une liste est une vallée\n",
"\n",
"def vallee(l) :\n",
" n = len(l)\n",
" if (n < 3): # liste trop courte\n",
" return False\n",
" else:\n",
" croissance = False\n",
" nb_montees = 0\n",
" decroissance = False\n",
" nb_descentes = 0\n",
" for i in range(0, n-1):\n",
" if l[i] > l[i+1] and not croissance : # descente\n",
" decroissance = True\n",
" nb_descentes += 1\n",
" elif l[i] < l[i+1] and decroissance : # montée\n",
" croissance = True\n",
" nb_montees += 1\n",
" if (nb_montees + nb_descentes == n-1) and croissance and decroissance :\n",
" # vallée sans plateau\n",
" return True\n",
" else:\n",
" return False\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
}