{"id":260,"date":"2017-02-06T20:43:40","date_gmt":"2017-02-06T19:43:40","guid":{"rendered":"http:\/\/www2.mathnique.com\/site\/?page_id=260"},"modified":"2017-03-31T18:11:18","modified_gmt":"2017-03-31T16:11:18","slug":"programmes","status":"publish","type":"page","link":"https:\/\/www.mathnique.com\/site\/programmes\/","title":{"rendered":"Concours CPGE"},"content":{"rendered":"<ul>\n<li><span style=\"color: #ff0000;\">Algorithme glouton (Polytechnique 2002)<\/span>\n<ul>\n<li>Sujet :\u00a0<a href=\"http:\/\/www2.mathnique.com\/site\/wp-content\/uploads\/2017\/02\/compoinformp02.pdf\">compoinformp02<\/a><\/li>\n<li>Corrig\u00e9 :<br \/>\n<b>Pr\u00e9-requis:\u00a0 <\/b>typeliste =^.cellule;<\/p>\n<p>cellule = record<\/p>\n<p>contenu : integer;<\/p>\n<p>suivant : liste;<\/p>\n<p>end;<\/p>\n<p>systeme = liste;<\/p>\n<p>somme = liste;<\/p>\n<p>function cons(contenu:integer;suivant:liste) : liste;<\/p>\n<p>var r : liste;<\/p>\n<p>begin<\/p>\n<p>new(r);<\/p>\n<p>r^.contenu :=contenu;<\/p>\n<p>r^.suivant :=suivant;<\/p>\n<p>cons := r;<\/p>\n<p>end;<\/p>\n<p><b>Question 1\u00a0 Turbo-Pascal<\/b><\/p>\n<p>function valeur(s:somme):integer;<\/p>\n<p>begin<\/p>\n<p>if somme = nil then valeur := 0<\/p>\n<p>Else valeur := s.contenu + valeur(s.suivant);<\/p>\n<p>end;<\/p>\n<p><b>Partie 1 - Payer le compte exact<\/b><\/p>\n<p><b>Question 2<\/b><\/p>\n<ol>\n<li>Soit un entier naturel p.<br \/>\nNotons pr(p) la propri\u00e9t\u00e9 suivante :\"la d\u00e9marche gloutonne r\u00e9ussit pour le prix p \u00e0 payer\"<br \/>\nEtape 1 - pour p = 0, la somme \u00e0 payer est vide donc la d\u00e9marche gloutonne r\u00e9ussit.<br \/>\nEtape 2 - soit p un entier naturel. Supposons que la d\u00e9marche gloutonne r\u00e9ussit pour le prix p \u00e0 payer. Soit maintenant le prix p + 1 \u00e0 payer. Alors de 2 choses l'une,<br \/>\n- ou bien\u00a0 d D p + 1 = d . Alors on prend uniquement d et on a ainsi pay\u00e9 le prix p + 1<br \/>\n- ou bien\u00a0 d D p + 1\u00a0 d\u00a0 mais par hypoth\u00e8se de r\u00e9currence , on sait payer gloutonnement pour p. Comme l'utilisateur dispose toujours de toutes les esp\u00e8ces dont il a besoin alors il\u00a0 ajoute alors la d\u00e9nomination 1 et il peut ainsi payer gloutonnement le prix p + 1.<br \/>\nConclusion : d'apr\u00e8s les \u00e9tapes 1 et 2, la d\u00e9marche gloutonne r\u00e9ussit toujours.<\/li>\n<li><b>Turbo-Pascal<\/b><br \/>\nfunction glouton(sys : systeme ; p : integer) : somme;<br \/>\nbegin<br \/>\nif p = 0 then glouton := nil<br \/>\nelse begin<br \/>\nd := sys.contenu;<br \/>\nif d\u00a0 p then glouton := cons(d ; glouton(sys, p - d))<br \/>\nelse glouton := glouton(sys.suivant, p)<\/li>\n<\/ol>\n<p>end;<\/p>\n<p>end;<br \/>\n<b>Question 3<\/b><\/p>\n<ol>\n<li>La strat\u00e9gie gloutonne peut \u00e9chouer dans cetains cas , par exemple si l'acheteur dispose du porte-feuille P = (5,2,2,2) et doit payer p = 6.<br \/>\nLa strat\u00e9gie gloutonne oblige \u00e0 prendre la plus grande d\u00e9nomination de P \u00e0 savoir 5 mais on ne peut pas disposer de 1 pour payer 6 !!!<br \/>\nOn peut payer le prix 6 par (2,2,2) mais cette strat\u00e9gie n'est pas gloutonne !!!<\/li>\n<li>function paye_glouton(pf : somme ; p : integer) : somme ;<\/li>\n<\/ol>\n<p>var d : integer; queue : liste;<\/p>\n<p>begin<br \/>\nif p = 0 then paye_glouton := nil<br \/>\nelse if pf = nil then (* on ne peut payer *)<br \/>\npaye_glouton := nil<br \/>\nelse begin<br \/>\nd:= pf^.contenu;<\/p>\n<p>queue:= pf^.suivant;<br \/>\nif d\u00a0 p<br \/>\nthen paye_glouton := cons(d ; paye_glouton(queue,p-d))<br \/>\nelse\u00a0 paye_glouton :=\u00a0 nil<\/p>\n<p>end;<\/p>\n<p>end;<\/p>\n<p>Question 4<\/p>\n<p><b>Partie 2 - Payer le compte exact et optimal<\/b><\/p>\n<p><b>Partie 3 - Etude des syst\u00e8mes mon\u00e9taires<\/b><\/li>\n<\/ul>\n<\/li>\n<li><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Algorithme glouton (Polytechnique 2002) Sujet :\u00a0compoinformp02 Corrig\u00e9 : Pr\u00e9-requis:\u00a0 typeliste =^.cellule; cellule = record contenu : integer; suivant : liste; end; systeme = liste; somme = liste; function cons(contenu:integer;suivant:liste) : liste; var r : liste; begin new(r); r^.contenu :=contenu; r^.suivant :=suivant; cons := r; end; Question 1\u00a0 Turbo-Pascal function valeur(s:somme):integer; begin if somme = nil &hellip; <a href=\"https:\/\/www.mathnique.com\/site\/programmes\/\" class=\"more-link\">Continuer la lecture<span class=\"screen-reader-text\"> de &laquo;&nbsp;Concours CPGE&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-260","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/260","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=260"}],"version-history":[{"count":3,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/260\/revisions"}],"predecessor-version":[{"id":1109,"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/pages\/260\/revisions\/1109"}],"wp:attachment":[{"href":"https:\/\/www.mathnique.com\/site\/wp-json\/wp\/v2\/media?parent=260"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}