Interclasser deux listes ordonnées en une liste qui contient tous les éléments de manière ordonnée.

1- Profil : interclassement : deux listes d'entiers -> une liste d'entier

2- Sémantique : 
     interclassement l1 l2 = l, l est la liste qui contient tous les éléments de l1 et l2. On suppose que l1 et l2 sont ordonnées par ordre croissant, l est ordonnée par ordre croissant. 

     interclassement [1;3;5;7] [0;2;4;6;8] = [0;1;2;3;4;5;6;7;8]
     interclassement [] [3;7;10] = [3;7;10]

3- Equations de récurrence : 

     interclassement [] []          = []

     interclassement [] y::reste_l2 = y::reste_l2

     interclassement x::reste_l1 [] = x::reste_l1

     interclassement x::reste_l1 y::reste_l2 =  /* si on reprend l'exemple x=1 reste_l1=[3;5;7]
                                                                           y=0 reste_l2=[2;4;6;8] */

             si x<y alors x::(interclassement reste_l1 y::reste_l2)
                    sinon y::(interclassement x::reste_l1 reste_l2)

4- Implantation en Ocaml :
let rec interclassement (l1:int list) (l2:int list) : int list =
    match l1 with 
          [] -> l2
          | x::reste_l1 -> match l2 with 
                                    [] -> l1
                                    | y::reste_l2 -> if x<y then x::(interclassement reste_l1 l2) 
                                                            else y::(interclassement l1 reste_l2);;

============================
  Une suite est elle ordonnée par ordre croissant ? 

1- Profil : ordonnée : liste d'entiers -> booléen

2- Sémantique : 
        ordonnée l <=> l est une liste ordonnée par ordre croissant. 
        
        ordonnée [4;76;8;90] = faux
        ordonnée [3;45;78;93;107] = vrai
        ordonnée [3] = vrai
        ordonnée [] = vrai

3- Equations de récurrences : 
        ordonnée []             = vrai
        ordonnée [x]            = vrai

FAUX    ordonnée x::y::reste_liste = if x<y then ordonnée reste_liste 
                                            else faux


        ordonnée [34;45;32;45] -> if (x=34< y=45) then ordonnée [32;45] -> vrai
        ordonnée [123;345;32;23] -> ordonnée [32;23] -> faux

CORRECTION ordonnée x::y::reste_liste = if (x<y) then ordonnée(y::reste_liste)

                                                 else faux

4- Implantation : 
   let rec ordonnee (l:int list) = 
       match l with 
             [] -> true 
            |[_] -> true 
            | x::y::reste_liste -> if (x<y) then ordonnee(y::reste_liste) else false;;

=============================================================

Calcul de l'ensemble des parties à n éléments. 

1- Profil : parties entier -> liste de liste d'entiers

2- Sémantique :
      parties (n) = la liste qui contient tous les sous ensembles d'un ensemble de taille n. 
                    un ensemble est représenté par une liste, un élément de l'ensemble est représenté par un entier. 

      parties (3) = [ [];  
                      [1] ; [2] ; [3] ; 
                      [1;2] ; [1;3] ; [2;3] ;
                      [1;2;3] ]  /* ensemble de départ [1;2;3] */

      parties (0) = [ [] ]

      parties (1) = [ [] ; [1] ]

      parties (2) = [ [] ; [1] ; [2] ; [1;2] ]

3- Equations de récurrences : 

     parties (0) = [[]]
     parties (n) = (parties (n-1))@(ajouter n (parties (n-1)))

  avec ajouter définie par 
  1- Profil : ajouter entier, une liste de listes d'entier -> une liste de listes d'entiers
  2- sémantique : ajouter n ll = rajoute n à toutes les sous listes de ll
                  ajouter 3 [ [] ; [1] ; [2] ; [1;2] ] = [ [3] ; [3;1] ; [3;2] ; [3;1;2] ]
                  ajouter 3 [] = []
                  ajouter 3 [[]] = [ [3]]
  3- Equations de récurrence : 
                  ajouter n [] = []
                  ajouter n l::reste_des_listes = (n::l)::(ajouter n reste_des_listes)


4- Implantation : 
let rec ajouter (n:int) (ll:int list list) : int list list = 
        match ll with 
              [] -> []
              | l::reste_ll -> (n::l)::(ajouter n reste_ll);;

let rec parties (n:int) : int list list = 
    match n with 0 -> [[]]
          | _ -> (parties (n-1))@(ajouter n (parties (n-1)));;

let rec parties_rapide (n:int) : int list list =
    match n with 0 -> [[]]
          | _ -> let ap_rec=(parties_rapide (n-1)) in ap_rec@(ajouter n ap_rec);;

============================================================================
Le compte est bon : on a un but x et une liste d'entiers. Peut on combiner les entiers de la liste pour obtenir x ? 
    -> on se limite à l'addition 

1- Profil : compte_est_bon : un entier et une liste d'entiers -> booléen
2- Sémantique :
            compte_est_bon but liste <=> on peut trouver des éléments dans liste dont la somme fait but. 
           
            compte_est_bon 10 [2;4;12;67;8] = vrai
            compte_est_bon 17 [2;4;12;67;8] = faux
       
3- Equations de récurrences : 
  
            compte_est_bon 0   []       = vrai
            compte_est_bon x+1 []       = faux
            compte_est_bon 0   y::reste = vrai
            compte_est_bon x+1 y::reste = (*on utilise y*)         (compte_est_bon (x+1-y) reste)  ||
                                          (*on n'utilise pas y*)   (compte_est_bon (x+1) reste)


4- Implantation:
let rec compte_est_bon (but:int) (liste : int list) : bool =
    match (but,liste) with 
          | 0,[] -> true
          | _,[] -> false
          | 0,y::reste -> true
          | _,y::reste -> (if ((but-y) <0) then false
                                           else compte_est_bon (but-y) reste) || 
                          (compte_est_bon but reste);;