Concours CPGE

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  Turbo-Pascal

function valeur(s:somme):integer;

begin

if somme = nil then valeur := 0

Else valeur := s.contenu + valeur(s.suivant);

end;

Partie 1 - Payer le compte exact

Question 2

1. Soit un entier naturel p.
   Notons pr(p) la propriété suivante :"la démarche gloutonne réussit pour le prix p à payer"
   Etape 1 - pour p = 0, la somme à payer est vide donc la démarche gloutonne réussit.
   Etape 2 - soit p un entier naturel. Supposons que la démarche gloutonne réussit pour le prix p à payer. Soit maintenant le prix p + 1 à payer. Alors de 2 choses l'une,
   - ou bien  d D p + 1 = d . Alors on prend uniquement d et on a ainsi payé le prix p + 1
   - ou bien  d D p + 1  d  mais par hypothèse de récurrence , on sait payer gloutonnement pour p. Comme l'utilisateur dispose toujours de toutes les espèces dont il a besoin alors il  ajoute alors la dénomination 1 et il peut ainsi payer gloutonnement le prix p + 1.
   Conclusion : d'après les étapes 1 et 2, la démarche gloutonne réussit toujours.
2. Turbo-Pascal
   function glouton(sys : systeme ; p : integer) : somme;
   begin
   if p = 0 then glouton := nil
   else begin
   d := sys.contenu;
   if d  p then glouton := cons(d ; glouton(sys, p - d))
   else glouton := glouton(sys.suivant, p)

end;

end;
Question 3

1. La stratégie gloutonne peut échouer dans cetains cas , par exemple si l'acheteur dispose du porte-feuille P = (5,2,2,2) et doit payer p = 6.
   La stratégie gloutonne oblige à prendre la plus grande dénomination de P à savoir 5 mais on ne peut pas disposer de 1 pour payer 6 !!!
   On peut payer le prix 6 par (2,2,2) mais cette stratégie n'est pas gloutonne !!!
2. function paye_glouton(pf : somme ; p : integer) : somme ;

var d : integer; queue : liste;

begin
if p = 0 then paye_glouton := nil
else if pf = nil then (* on ne peut payer *)
paye_glouton := nil
else begin
d:= pf^.contenu;

queue:= pf^.suivant;
if d  p
then paye_glouton := cons(d ; paye_glouton(queue,p-d))
else  paye_glouton :=  nil

end;

end;

Question 4

Partie 2 - Payer le compte exact et optimal

Partie 3 - Etude des systèmes monétaires