(**************************************************************************) (* *) (* Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre, *) (* Kim Nguyen, Laurent Sartre *) (* *) (* Informatique - MP2I/MPI - CPGE 1re et 2e années. *) (* Cours et exercices corrigés. Éditions Ellipses, 2022. *) (* *) (* https://www.informatique-mpi.fr/ *) (* *) (**************************************************************************) let rec gcd (u: int) (v: int) : int = if v = 0 then u else gcd v (u mod v) let rec extended_gcd (u: int) (v: int) : int * int * int = if v = 0 then (1, 0, u) else let x,y,d = extended_gcd v (u mod v) in (y, x - y*(u/v), d) let div_mod u v m = let x, _, d = extended_gcd v m in assert (d = 1); let r = (x * u) mod m in if r < 0 then r + m else r let rec fact n = if n < 2 then 1 else n * fact (n-1) let rec power a n = if n = 0 then 1 else let b = power a (n/2) in if n mod 2 = 0 then b * b else a * b * b let rec pop n = if n = 0 then 0 else pop (n/2) + if n mod 2 = 1 then 1 else 0 let pop n = pop (if n < 0 then n land max_int else n) let rec print_binary ~len fmt = function | 0 | 1 as b -> Format.fprintf fmt "%s%d" (String.make (len - 1) '0') b | n -> Format.fprintf fmt "%a%d" (print_binary ~len:(len-1)) (n/2) (n mod 2) let print_binary fmt n = if n < 0 then Format.fprintf fmt "1%a" (print_binary ~len:62) (n land max_int) else print_binary ~len:63 fmt n (* exo prog dyn ; voir aussi Bintree.all *) let catalan n = let c = Array.make (n + 1) 0 in c.(0) <- 1; for i = 1 to n do for j = 0 to i - 1 do c.(i) <- c.(i) + c.(j) * c.(i - 1 - j) done done; c let rec itv_aux acc lo hi = if lo >= hi then acc else itv_aux (hi-1 :: acc) lo (hi-1) let interval lo hi = itv_aux [] lo hi let rec exists lo hi p = lo < hi && (p lo || exists (lo + 1) hi p) let rec for_all lo hi p = lo >= hi || p lo && for_all (lo + 1) hi p let rec fold_interval lo hi acc f = if lo >= hi then acc else fold_interval (lo + 1) hi (f acc lo) f let sum_interval lo hi f = fold_interval lo hi 0 (fun s i -> s + f i) let iverson b = if b then 1 else 0