let fibo1 n = let acc1 = ref 1 and acc2 = ref 0 in
  let acc3 = ref !acc2 in
    for i=1 to n do
      acc3 := !acc1 + 0;
      acc1 := !acc1 + !acc2;
      acc2 := !acc3
    done;
    !acc2
;;

let rec fibo2 n = match n with
| 0 -> 0
| 1 -> 1
| _ -> fibo2 (n-2) + fibo2 (n-1)

let rec fibo_aux n acc1 acc2 = match n with
| 0 -> acc1
| _ -> fibo_aux (n-1) (acc2) (acc1+acc2);;

let rec aux n table = 
  if table.(n) = -1 then
    table.(n) <- (aux (n-1) table) + (aux (n-2) table);
  table.(n);;

let fibo4 n = let table = Array.make (n+1) (-1) in
  table.(0) <- 0;
  table.(1)<- 1;
  aux n table
;;
let rec fibo5 n =
  match n with
  | 0 -> 0
  | 1 -> 1
  | 2 -> 1
  | _ ->
    let p = n / 2 in
    let fp = fibo5 p in
    let fp_plus_1 = fibo5 (p + 1) in
    if n mod 2 = 0
    then fp_plus_1 * fp + fp * (fp_plus_1 - fp)
    else fp_plus_1 * fp_plus_1 + fp * fp
  ;;

  let rec appartenance x l =
    match l with
    | [] -> false
    | hd :: tl -> x = hd || appartenance x tl;;
    let rec test_ensemble l =
      match l with
      | [] -> true
      | x :: xs -> not (appartenance x xs) && test_ensemble xs;;


      let rec union l1 l2 =
        match (l1, l2) with
        | ([], l) -> l
        | (l, []) -> l
        | (x :: xs, y :: ys) ->
            if x < y then x :: union xs l2
            else if x > y then y :: union l1 ys
            else x :: union xs ys
          ;;

          let rec intersection l1 l2 =
            match (l1, l2) with
            | ([], _) | (_, []) -> []
            | (x :: xs, y :: ys) ->
                if x < y then intersection xs l2
                else if x > y then intersection l1 ys
                else x :: intersection xs ys
              ;;
              let rec difference l1 l2 =
                match (l1, l2) with
                | ([], _) -> []
                | (x :: xs, []) -> l1
                | (x :: xs, y :: ys) ->
                    if x < y then x :: difference xs l2
                    else if x > y then difference l1 ys
                    else difference xs ys
                  ;;
                  
                  let rec compteur1 x n =
                    if n - x < 0 then (0, n)
                    else
                      let a, remainder = compteur1 x (n - x) in
                      (a + 1, remainder)
                    ;;
                    let rec compteur2 x n p =
                      if n - x < 0 || p = 0 then (0, n)
                      else
                        let a, remainder = compteur2 x (n - x) (p - 1) in
                        (a + 1, remainder)
                      ;;
                      
                    ;;
                  ;;
                ;;
              ;;
            ;;
          ;;
        ;;
      ;;
    ;;
  ;;
;;

let monaie = [|1; 2; 5; 10; 20; 50; 100; 200; 500; 1000; 2000; 5000|];;
let monaie2 = [|5000; 2000; 1000; 500; 200; 100; 50; 20; 10; 5; 2; 1|];;
let monaie2content = [|1; 10; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1|];;
let monaieuk = [|30; 24; 12; 6; 3; 1|];;
let monaieukcontent = Array.make (Array.length monaieuk) 0;;

let compteur1 x n =
  let a = ref 0 in
  let n' = ref n in
  while !n' - x >= 0 do
    n' := !n' - x;
    a := !a + 1
  done;
  (!a, !n')
;;
let compteur2 x n p =
  let a = ref 0 in
  let n' = ref n in
  let p' = ref p in
  while !n' - x >= 0 && !p' > 0 do
    n' := !n' - x;
    p' := !p' - 1;
    a := !a + 1
  done;
  (!a, !n')
;;
let compteur3 x n p =
  let a = ref 0 in
  let n' = ref n in
  let p' = ref p in
  while !n' - x >= 0 && !p' > 0 do
    n' := !n' - x;
    p' := !p' - 1;
    a := !a + 1
  done;
  if !n' > 0 then
    (-1, !n')
  else
    (!a, !n')
  ;;
let rendu_illimite n =
  let result = ref [] in
  for k = 0 to Array.length monaie2 - 1 do
    let a = ref 0 in
    let ninterne = ref n in
    let x = monaie2.(k) in
    while !ninterne - x >= 0 do
      ninterne := !ninterne - x;
      a := !a + 1
    done;
    if !ninterne > 0 then
      a := -1;
    result := !result @ [!a]
  done;
  !result;;

let rendu_illimite2 n =
  let result = ref [] in
  for k = 0 to Array.length monaie2 - 1 do
    let a = ref 0 in
    let x = monaie2.(k) in
    let n' = ref n in
    while !n' - x >= 0 do
      n' := !n' - x;
      a := !a + 1
    done;
    result := !result @ [!a]
  done;
  !result;;