{"id":1016,"date":"2017-03-31T01:56:02","date_gmt":"2017-03-30T23:56:02","guid":{"rendered":"http:\/\/www2.mathnique.com\/site\/?page_id=1016"},"modified":"2017-03-31T18:00:13","modified_gmt":"2017-03-31T16:00:13","slug":"listes","status":"publish","type":"page","link":"https:\/\/www.mathnique.com\/site\/listes\/","title":{"rendered":"Listes"},"content":{"rendered":"<ul>\n<li><span style=\"color: #ff0000;\"><strong>Cours sur les listes :<\/strong><\/span>\n<ul>\n<li><em><span style=\"color: #ff0000;\"><b>D\u00e9finition du type abstrait liste<br \/>\n<\/b><\/span><\/em>Ce type de structure de donn\u00e9es est utile pour les donn\u00e9es qui doivent \u00eatre trait\u00e9es s\u00e9quentiellement, chaque \u00e9l\u00e9ment est reli\u00e9 \u00e0 un autre \u00e9l\u00e9ment et un seul.<br \/>\nElle permet de simuler des situations de la vie courante\u00a0: liste d\u2019articles pour les magasins, liste de personnes, liste d\u2019objets divers....<br \/>\n<em>Cas particuliers de listes :<\/em><\/li>\n<li>Les files (FIFO : First In , First Out):Les \u00e9l\u00e9ments sont ajout\u00e9s \u00e0 la queue et supprim\u00e9s \u00e0 la t\u00eate<\/li>\n<li>Les piles (LIFO : Last In, Last Out) :\n<p>On n'y acc\u00e8de que par le sommet qui est le dernier \u00e9l\u00e9ment rentr\u00e9. Les \u00e9l\u00e9ments sont<br \/>\najout\u00e9s et supprim\u00e9s au sommet.<\/li>\n<li>\u00a0<b><em><span style=\"color: #ff0000;\">d\u00e9finition it\u00e9rative d'une liste<br \/>\n<\/span><\/em><\/b>Soit \u00e9l\u00e9ment : type T;Une liste est un ensemble fini d'\u00e9l\u00e9ments. Il existe une relation d'ordre entre les places (ou les rangs) des \u00e9l\u00e9ments d'une liste.Les op\u00e9rateurs minimaux sont :<\/p>\n<p>liste vide :\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; liste<\/p>\n<p>Cet op\u00e9rateur est dit constante car il est d\u00e9fini \u00e0 partir de rien.<br \/>\nlongueur\u00a0: \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 liste \u00a0 \u00a0 ------&gt; entier<\/p>\n<p>i\u00e8me \u00a0 \u00a0 \u00a0 :\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 liste\u00a0 \u00a0 \u00a0 ------&gt; \u00e9l\u00e9ment<\/p>\n<p>Ces 2 op\u00e9rateurs sont dits observateurs car \u00e0 partir d\u2019au moins un type d\u00e9fini, ils<br \/>\nrenvoient un type pr\u00e9d\u00e9fini.<\/p>\n<p>ins\u00e9rer\u00a0: \u00a0 \u00a0 \u00a0 liste, entier, \u00e9l\u00e9ment\u00a0 ------&gt; liste<br \/>\nsupprimer\u00a0: \u00a0 liste, entier\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; liste<\/p>\n<p>Ces 2 op\u00e9rateurs sont dits op\u00e9rateurs internes\u00a0 car \u00e0 partir d\u2019au moins un type d\u00e9fini,<br \/>\nils renvoient un type d\u00e9fini.<br \/>\nOn peut enrichir cette sp\u00e9cification en ajoutant les op\u00e9rateurs suivants qui s\u2019appellent des extensions de type\u00a0:<\/p>\n<p>estmembrede\u00a0:\u00a0 liste, \u00e9l\u00e9ment\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; bool\u00e9en<\/p>\n<p>rechercher\u00a0:\u00a0 \u00a0 \u00a0 liste, \u00e9l\u00e9ment\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; entier<\/p>\n<p>inverser\u00a0: \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 liste\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; liste<\/p>\n<p>concat\u00e9ner\u00a0:\u00a0 \u00a0 \u00a0 liste, liste\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; liste<\/p>\n<p>Une liste lin\u00e9aire est une structure de donn\u00e9es qui a la d\u00e9finition inductive suivante\u00a0:<br \/>\n- ou bien elle est vide, on l\u2019appelle alors la liste vide not\u00e9e nil (en Pascal) ou [] (en Caml)<\/p>\n<p>- ou bien elle est form\u00e9e de 2 parties\u00a0:<br \/>\n- un premier \u00e9l\u00e9ment appel\u00e9\u00a0 t\u00eate T<\/p>\n<p>- un deuxi\u00e8me \u00e9l\u00e9ment appel\u00e9 reste ou queue Q qui est une liste<br \/>\nVoici une\u00a0 d\u00e9finition th\u00e9orique\u00a0sous plusieurs formes :<\/p>\n<p>type \u00e9l\u00e9ment\u00a0: \u2026\u2026\u2026\u2026\u2026..\u00a0;<br \/>\nliste = ( liste vide | liste non vide) o\u00f9 liste non vide = ( \u00e9l\u00e9ment\u00a0; liste)<\/p>\n<p>type \u00e9l\u00e9ment\u00a0: \u2026\u2026\u2026\u2026\u2026..\u00a0;<br \/>\nliste = nil ou ( \u00e9l\u00e9ment\u00a0; liste)<\/p>\n<p>&nbsp;<\/p>\n<p>type \u00e9l\u00e9ment\u00a0: \u2026\u2026\u2026\u2026\u2026..\u00a0;<br \/>\nliste = nil + \u00e9l\u00e9ment\u00a0 liste\u00a0;<\/p>\n<p>En Caml\u00a0 [ 1\u00a0; 2\u00a0; 3 ] est une liste qu\u2019on peut aussi cr\u00e9er par 1\u00a0:\u00a0: ( 2\u00a0:\u00a0: ( 3\u00a0:\u00a0: [] )<br \/>\nLe compilateur de Caml reconna\u00eet automatiquement une liste d\u00e8s que l\u2019on utilise soit la<br \/>\nnotation d\u2019ajout (\u00a0:\u00a0: ) soit les crochets [ ] et les points-virgules\u00a0; de s\u00e9paration des<br \/>\n\u00e9l\u00e9ments.<\/p>\n<p>Les op\u00e9rateurs minimaux sont :<\/p>\n<p>liste vide :\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; liste<\/p>\n<p>estvide\u00a0:\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 liste\u00a0 \u00a0 ------&gt; bool\u00e9en<\/p>\n<p>t\u00eate\u00a0 \u00a0 \u00a0 :\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 liste \u00a0 ------&gt; \u00e9l\u00e9ment<\/p>\n<p>ajouterd\u00e9but\u00a0 :\u00a0 \u00a0 liste, \u00e9l\u00e9ment\u00a0 ------&gt; liste<br \/>\nqueue\u00a0: \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 liste\u00a0 ------&gt; liste<\/p>\n<p>Ces 2 op\u00e9rateurs sont dits op\u00e9rateurs internes\u00a0 car \u00e0 partir d\u2019au moins un type d\u00e9fini,<br \/>\nils renvoient un type d\u00e9fini.<br \/>\nOn peut enrichir cette sp\u00e9cification en ajoutant les op\u00e9rateurs suivants qui s\u2019appellent des extensions de type\u00a0:<\/p>\n<p>estmembrede\u00a0:\u00a0 liste, \u00e9l\u00e9ment\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; bool\u00e9en<\/p>\n<p>rechercher\u00a0:\u00a0 \u00a0 \u00a0 liste, \u00e9l\u00e9ment\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; entier<\/p>\n<p>inverser\u00a0: \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 liste\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; liste<\/p>\n<p>concat\u00e9ner\u00a0:\u00a0 \u00a0 \u00a0 liste, liste\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; liste<\/li>\n<li>\u00a0<b><b><em><span style=\"color: #ff0000;\">d\u00e9finition r\u00e9cursive d'une liste :<br \/>\n<\/span><\/em><\/b><\/b>Une liste lin\u00e9aire est une structure de donn\u00e9es qui a la d\u00e9finition inductive suivante\u00a0:<br \/>\n- ou bien elle est vide, on l\u2019appelle alors la liste vide not\u00e9e nil (en Pascal) ou [] (en Caml)<br \/>\n- ou bien elle est form\u00e9e de 2 parties\u00a0:<br \/>\n- un premier \u00e9l\u00e9ment appel\u00e9\u00a0 t\u00eate T<br \/>\n- un deuxi\u00e8me \u00e9l\u00e9ment appel\u00e9 reste ou queue Q qui est une liste<br \/>\nVoici une\u00a0 d\u00e9finition th\u00e9orique\u00a0sous plusieurs formes :<br \/>\ntype \u00e9l\u00e9ment\u00a0: \u2026\u2026\u2026\u2026\u2026..\u00a0;<br \/>\nliste = ( liste vide | liste non vide) o\u00f9 liste non vide = ( \u00e9l\u00e9ment\u00a0; liste)type \u00e9l\u00e9ment\u00a0: \u2026\u2026\u2026\u2026\u2026..\u00a0;<br \/>\nliste = nil ou ( \u00e9l\u00e9ment\u00a0; liste)type \u00e9l\u00e9ment\u00a0: \u2026\u2026\u2026\u2026\u2026..\u00a0;<br \/>\nliste = nil + \u00e9l\u00e9ment\u00a0 liste\u00a0;<\/p>\n<p>En Caml\u00a0 [ 1\u00a0; 2\u00a0; 3 ] est une liste qu\u2019on peut aussi cr\u00e9er par 1\u00a0:\u00a0: ( 2\u00a0:\u00a0: ( 3\u00a0:\u00a0: [] )<br \/>\nLe compilateur de Caml reconna\u00eet automatiquement une liste d\u00e8s que l\u2019on utilise soit la<br \/>\nnotation d\u2019ajout (\u00a0:\u00a0: ) soit les crochets [ ] et les points-virgules\u00a0; de s\u00e9paration des<br \/>\n\u00e9l\u00e9ments.<\/p>\n<p>Les op\u00e9rateurs minimaux sont :<\/p>\n<p>liste vide :\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; liste<\/p>\n<p>estvide\u00a0:\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 liste\u00a0 \u00a0 ------&gt; bool\u00e9en<\/p>\n<p>t\u00eate\u00a0 \u00a0 \u00a0 :\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 liste \u00a0 ------&gt; \u00e9l\u00e9ment<\/p>\n<p>ajouterd\u00e9but\u00a0 :\u00a0 \u00a0 liste, \u00e9l\u00e9ment\u00a0 ------&gt; liste<br \/>\nqueue\u00a0: \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 liste\u00a0 ------&gt; liste<\/p>\n<p>Ces 2 op\u00e9rateurs sont dits op\u00e9rateurs internes\u00a0 car \u00e0 partir d\u2019au moins un type d\u00e9fini,<br \/>\nils renvoient un type d\u00e9fini.<br \/>\nOn peut enrichir cette sp\u00e9cification en ajoutant les op\u00e9rateurs suivants qui s\u2019appellent des extensions de type\u00a0:<\/p>\n<p>estmembrede\u00a0:\u00a0 liste, \u00e9l\u00e9ment\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; bool\u00e9en<\/p>\n<p>rechercher\u00a0:\u00a0 \u00a0 \u00a0 liste, \u00e9l\u00e9ment\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; entier<\/p>\n<p>inverser\u00a0: \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 liste\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; liste<\/p>\n<p>concat\u00e9ner\u00a0:\u00a0 \u00a0 \u00a0 liste, liste\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 ------&gt; liste<\/p>\n<p><b><em><span style=\"color: #ff0000;\"><br \/>\n<\/span><\/em><\/b><\/li>\n<\/ul>\n<\/li>\n<li><span style=\"color: #ff0000;\"><strong>Exercices :<\/strong><\/span>\n<ul>\n<li><span style=\"color: #ff0000;\"><em>Sujet<\/em><\/span> : Exercice 3 de E3A : \u00a0<a href=\"http:\/\/www2.mathnique.com\/site\/wp-content\/uploads\/2017\/03\/e3aO3.pdf\">e3aO3<\/a><\/li>\n<li><em><span style=\"color: #ff0000;\">Corrig\u00e9<\/span> <\/em>:<br \/>\ntype element : integer;<br \/>\nliste = ^.cellule ;<br \/>\ncellule = record<br \/>\nvaleur : element;<br \/>\nsuivant :liste;<br \/>\nend;<br \/>\n<b>function IndiceTripletMaximal(lst : liste):entier;<br \/>\n<\/b>function longueur(L : liste): integer;<br \/>\n<b>begin<br \/>\n<\/b>\u00a0 if L = nil then longueur := 0<br \/>\nelse longueur := 1 + longueur(L^.suivant);<br \/>\n<b>end;<br \/>\n<\/b><b>begin\u00a0<\/b>(* on suppose que la liste au au moins 3 \u00e9l\u00e9ments *)<br \/>\nsommemaximale :=0;<br \/>\nI := 1;<br \/>\nrepeat<br \/>\nsomme3termesconsecutifs:=lst^.valeur+lst^.suivant.valeur + lst^.suivant.suivant.valeur;<br \/>\nif somme3termesconsecutifs &gt; somme maximale<br \/>\nthen<br \/>\nbegin<br \/>\nsommemaximale := somme3termesconsecutifs;<br \/>\nindicepointe:=I;<br \/>\nend;<br \/>\nI:= I +1 ;<br \/>\nlst:=lst^.suivant;<br \/>\nuntil I = longueur(lst) - 1;<br \/>\nIndiceTripletMaximal := indicepointe;<br \/>\n<b>end;<\/b><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Cours sur les listes : D\u00e9finition du type abstrait liste Ce type de structure de donn\u00e9es est utile pour les donn\u00e9es qui doivent \u00eatre trait\u00e9es s\u00e9quentiellement, chaque \u00e9l\u00e9ment est reli\u00e9 \u00e0 un autre \u00e9l\u00e9ment et un seul. Elle permet de simuler des situations de la vie courante\u00a0: liste d\u2019articles pour les magasins, liste de personnes, &hellip; <a href=\"https:\/\/www.mathnique.com\/site\/listes\/\" class=\"more-link\">Continuer la lecture<span class=\"screen-reader-text\"> de &laquo;&nbsp;Listes&nbsp;&raquo;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"class_list":["post-1016","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/1016","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/comments?post=1016"}],"version-history":[{"count":8,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/1016\/revisions"}],"predecessor-version":[{"id":1098,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/1016\/revisions\/1098"}],"wp:attachment":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/media?parent=1016"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}