(* Question 3.2 & 3.3 *) type orientation = | NonInit | N (* Nord *) | NW (* Nord Ouest *) | W (* Ouest *);; let plssc x y = let m = vect_length x and n = vect_length y in let c = make_matrix (m+1) (n+1) 0 in let plssc_exhib = make_matrix (m+1) (n+1) NonInit in for i = 1 to m do for j = 1 to n do if (x.(i-1) = y.(j-1)) then ( c.(i).(j) <- c.(i-1).(j-1) + 1; plssc_exhib.(i).(j) <- NW; ) else ( c.(i).(j) <- max c.(i).(j-1) c.(i-1).(j); if c.(i).(j) = c.(i).(j-1) then plssc_exhib.(i).(j) <- W else plssc_exhib.(i).(j) <- N; ); done; done; (* Maintenant extrait le chemin *) (* pourrait être fait en récursif aussi *) let i = ref m and j = ref n in let une_plssc = ref [] in while !i > 0 && !j > 0 do match plssc_exhib.(!i).(!j) with | NW -> une_plssc := x.(!i-1) (* = y.(!j-1) *) :: !une_plssc; decr i; decr j; | W -> decr j; | N -> decr i; | _ -> failwith "Mauvais plssc_exhib"; done; (c.(m).(n), !une_plssc);; plssc [|1;2;3;4;7;9;10;3;1;4|] [|2;4;6;5;9;6;7;10;1;4|];; (* Question 2.6 *) (* la distance recherchée est en (i,j) car un plus court chemin passe évidemment par des noeuds d'étiquette inférieure à |V| *) (* Question 2.7 *) let floyd g = let n = vect_length g in let dist = make_matrix n n 0 in for i = 0 to n-1 do for j = 0 to n-1 do dist.(i).(j) <- g.(i).(j); done; done; for i = 0 to n-1 do for s = 0 to n-1 do for t = 0 to n-1 do if s <> t then ( let newdist = dist.(s).(i) + dist.(i).(t) in if dist.(s).(t) > newdist then dist.(s).(t) <- dist.(s).(i) + dist.(i).(t); ); done; done; done; dist;;