(****************) (* JL - 13/5/17 *) (****************) (* Exercice 1 *) (* Le problème lui-même est considéré ici comme un sous-problème. *) (* 1. Il y a n sous-problèmes. *) (* 2. Il y a n·m sous-problèmes. *) (* 3. On compte les (i, j) tels que 1 <= i <= j <= n : il y a n·(n + 1)/2 sous-problèmes. *) (* Exercice 2 *) (* Versions itératives *) (* Si on note nb(i, j) le nombre de chemin pour arriver en (i, j), alors · nb(0, j) = nb (i, 0) = 1, · nb(i, j) = nb(i - 1, j) + nb(i, j - 1) + nb(i - 1, j - 1) si i > 0 et j > 0. *) (* Version matrice de tous les nombres de chemins *) (* Complexités spatiale et temporelle en n·p *) let nb_chemins n p = let tab_nb_chemins = make_matrix (n + 1) (p + 1) 1 in for i = 1 to n do for j = 1 to p do tab_nb_chemins.(i).(j) <- tab_nb_chemins.(i - 1).(j - 1) + tab_nb_chemins.(i - 1).(j) + tab_nb_chemins.(i).(j - 1) done; done; tab_nb_chemins.(n).(p) ;; (* Version où l'on stocke seulement les lignes successives *) (* Complexité spatiale en p *) let nb_chemins_bis n p = let ligne_nb_chemins = make_vect (p + 1) 1 in let en_bas_a_gauche = ref 1 in for i = 1 to n do for j = 1 to p do (* sauvegarde du futur coefficient en bas à gauche *) let en_bas = ligne_nb_chemins.(j) in ligne_nb_chemins.(j) <- ligne_nb_chemins.(j - 1) + en_bas + !en_bas_a_gauche; en_bas_a_gauche := en_bas done; en_bas_a_gauche := 1; done; ligne_nb_chemins.(p) ;; (* Version récursive matrice*) let nb_chemins_rec n p = let tab_nb_chemins = make_matrix (n + 1) (p + 1) 1 in let rec nb_chemins_memo n p = (* Un seul chemin si n = 0 ou m = 0 *) if tab_nb_chemins.(n).(p) = 1 && n > 0 && p > 0 then begin tab_nb_chemins.(n).(p) <- nb_chemins_memo (n - 1) p + nb_chemins_memo n (p - 1) + nb_chemins_memo (n - 1) (p - 1) end; tab_nb_chemins.(n).(p) in nb_chemins_memo n p ;; nb_chemins 1 1;; nb_chemins 0 0;; nb_chemins 2 3;; nb_chemins_bis 1 1;; nb_chemins_bis 0 0;; nb_chemins_bis 2 3;; nb_chemins_rec 1 1;; nb_chemins_rec 0 0;; nb_chemins_rec 2 3;; (* Exercice 3 *) (* La somme maximale partant d'un point (i, j) du triangle étant notée smax(i, j), on a · smax(n, j) = 0 pour tout j, · smaxi(i, j) = max(smax(i + 1, j), smax(i + 1, j + 1)) + triangle.(i).(j) si 0 <= j <= i. On parcourt le triangle par lignes de bas en haut et on stocke la valeur maximale d'un chemin partant d'un sommet donné sur la ligne. La solution se trouvera en première position à la dernière étape. *) let somme_max triangle = let n = vect_length triangle in let somme_max_ligne = make_vect (n + 1) 0 in for i = n - 1 downto 0 do for j = 0 to i do somme_max_ligne.(j) <- (max somme_max_ligne.(j) somme_max_ligne.(j + 1)) + triangle.(i).(j) done; done; somme_max_ligne.(0) ;; let triangle = [| [|3; 0; 0; 0|]; [|7; 4; 0; 0|]; [|2; 4; 6; 0|]; [|8; 5; 9; 3|] |] ;; somme_max triangle;; (* Exercice 4 *) (* on va stocker dans un tableau la taille du plus grand carré (pgc) de 1 dont le sommet inférieur droit est m(i, j). Si i = 0 ou j = 0, pgc(i, j) = 1 si m(i, j) = 1, 0 sinon Si i > 0 et j > 0, · pgc(i, j) = 0 si m(i, j) = 0 · pgc(i, j) = min(pgc(i - 1, j), pgc(i - 1, j - 1), pgc(i, j - 1)) + 1 si m(i, j) = 1 On renvoie les numéros de lignes et de colonnes du coin supérieur gauche ainsi que la taille d'un carré de 1 de taille maximale.*) let plus_grand_carre m = let n = vect_length m in let p = vect_length (m.(0)) in let pgc = make_matrix n p 0 in let imax = ref 0 in let jmax = ref 0 in let taille_maxi = ref 0 in for i = 0 to n - 1 do for j = 0 to p - 1 do if m.(i).(j) = 1 then begin pgc.(i).(j) <- if i * j = 0 then 1 else 1 + min (min pgc.(i - 1).(j) pgc.(i).(j - 1)) pgc.(i - 1).(j - 1); if pgc.(i).(j) > !taille_maxi then begin imax := i; jmax := j; taille_maxi := pgc.(i).(j) end end done; done; !imax - !taille_maxi + 2, !jmax - !taille_maxi + 2, !taille_maxi ;; let plus_grand_carre_bis m = let n = vect_length m in let p = vect_length (m.(0)) in let pgc = make_vect p 0 in let imax = ref 0 in let jmax = ref 0 in let taille_maxi = ref 0 in for i = 0 to n - 1 do let ex_pgc = copy_vect pgc in for j = 0 to p - 1 do if m.(i).(j) = 1 then begin pgc.(j) <- if i * j = 0 then 1 else 1 + min (min pgc.(j) pgc.(j - 1)) ex_pgc.(j - 1); if pgc.(j) > !taille_maxi then begin imax := i; jmax := j; taille_maxi := pgc.(j) end; end else pgc.(j) <- 0; done; done; !imax - !taille_maxi + 2, !jmax - !taille_maxi + 2, !taille_maxi ;; let m = [| [|1; 0; 0; 1; 1; 1|]; [|0; 1; 1; 1; 1; 0|]; [|0; 0; 1; 1; 1; 0|]; [|1; 0; 1; 1; 1; 1|]; [|1; 1; 1; 0; 0; 1|]; [|0; 1; 1; 1; 1; 1|] |] ;; plus_grand_carre m;; plus_grand_carre_bis m;; (* Exercice 5 *) (* entiers est un tableau contenant n0, n1, ..., n(k-1). On maintient dynamiquement un tableau parties de m + 1 couples (somme, liste) tel qu'à la fin de l'étape i ( = 0 .. k - 1 ), somme_parties.(smax) contient le couple correspondant à la partie de somme maximale <= smax parmi n0, n1, ..., ni. Soit S(i, smax) la somme maximale <= smax pour une partie de {n0, ..., ni}. Alors · S(-1, smax) = 0 pour tout smax, · Pour tout i >= 0, - Si smax < ni, S(i, smax) = S(i - 1, smax) [On ne peut pas ajouter ni sans dépassement, max inchangé] - Sinon, S(i, smax) = max( S(i - 1, smax), S(i - 1, smax - ni) + ni ) *** Notons somme_parties[i] le tableau somme_parties à la fin de l'étape i. On a donc, au départ (étape -1), somme_parties[-1].(smax) = (0, []). Et pour tout i, Si smax < ni, somme_parties[i].(smax) <- somme_parties[i-1].(smax) Sinon somme_parties[i].(smax) <- max( somme_parties[i-1].(smax), somme_parties[i-1].(smax - ni) "+ ni" ) Autrement dit, on ne met à jour somme_parties[i].(smax) que si smax >= ni et somme[i-1].(smax - ni) + ni > somme[i-1].(smax). *** Le résultat recherché sera à la fin de l'étape i = k - 1 dans parties.(m). *** Complexité temporelle : O(m·k) Complexité spatiale : O(m) *) let somme_max entiers m = let k = vect_length entiers in let somme_parties = make_vect (m + 1) (0, []) in (* matrice de couples (somme, partie) *) for i = 0 to k - 1 do let ni = entiers.(i) in let somme_parties_ex = copy_vect somme_parties in for smax = ni to m do let somme, partie = somme_parties_ex.(smax - ni) in let somme1, _ = somme_parties_ex.(smax) in if somme + ni > somme1 then somme_parties.(smax) <- (somme + ni, ni :: partie) done; done; somme_parties.(m) ;; somme_max [|7; 1; 2; 5; 13|] 29;; somme_max [|5; 2|] 6;;