SHARE
TWEET

Untitled

a guest May 6th, 2019 109 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. (* Ex 1 *)
  3. let liste_entiers n =
  4.    let rec __liste_entiers n acc =
  5.    
  6.     (* On regarde si l'accumulateur est supérieur à n ou pas *)
  7.       match acc with
  8.      
  9.         (* Si oui, on ne rappelle pas la fonction et on retourne n-1 *)
  10.           | acc when acc >= n-1 -> [n-1]
  11.          
  12.           (* Sinon ba on rajoute, au début acc vaut 1 ensuite 2.. et sa forme 1::2::3::4..... *)
  13.           | _ -> acc :: (__liste_entiers (n) (acc+1)); in
  14.          
  15.     (*
  16.       Et on appelle la fonction, je rappelle que tout était
  17.       caché dans une fonction lol, et bien sûr la complexité c'est O(n)
  18.     *)
  19.     __liste_entiers n 0;;
  20.  
  21. liste_entiers 20;; (* petit test des familles *)
  22.  
  23.  
  24.  
  25. (* ça c'est juste du bonus *)
  26. let rec longueur l = match l with
  27.    | [] -> 0
  28.    | x::q -> 1+(longueur q);;
  29.  
  30.  
  31. (* Ex 2 *)
  32. let rec repetition x n = match n with
  33.  
  34.     (* Si le n est négatif, on quitte car c'est inadmissible *)
  35.     | n when n < 0 -> failwith "erreur"
  36.    
  37.     (* Si c'est 0 on renvoie une liste de 1 élément *)
  38.     | 0 -> [x]
  39.    
  40.     (*
  41.       Sinon on rappelle la fonction en diminuant l'accumulateur
  42.       et bien sûr quand celui vaut zéro on retombe sur le cas ci-dessus donc la fonction se termine
  43.       la complexité c'est O(n)
  44.      *)
  45.     | _ -> x :: (repetition x (n-1));;
  46.    
  47. repetition 5 10;; (* petit test des familles *)
  48.  
  49.  
  50.  
  51. (* Ex 3 *)
  52. let a = 4::3::2::1::[0];; (* Ceci va nous servir d'exemple pour les 4859 exercices suivants *)
  53. let rec appartient l a = match l with
  54.  
  55.     (* Si l est vide ba, il est clair que x ne peut pas appartenir donc on renvoie false *)
  56.     | [] -> false
  57.    
  58.     (* On teste si x=a, si c'est le cas, c'est qu'il appartient donc on renvoie direct true, pas le temps de naiser *)
  59.     | x::q when x=a -> true
  60.    
  61.     (* Sinon on explore jusqu'a retomber sur le 1er cas dans le cas ou x n'appartient pas *)
  62.     | x::q -> appartient q a;;
  63.    
  64. appartient a 47;; (* petit test des familles *)
  65.  
  66.  
  67. (* Ex 4 *)
  68. let a = 4::3::4::2::1::[0];; (* El famous exemple *)
  69. let rec sans_repetition l = match l with
  70.  
  71.     (* Si la liste est vide => pas de répétitions donc on renvoie true *)
  72.     | [] -> true
  73.    
  74.     (*
  75.       Sinon on itère, si on trouve que x appartient à q ça veut dire
  76.       qu'il existe 2 fois donc qu'il y a répétition don on rage quitte
  77.     *)
  78.     | x::q -> if (appartient q x) then false else sans_repetition q;;
  79.    
  80. sans_repetition a;; (* petit test des familles *)
  81.  
  82.  
  83. (* Ex 5 *)
  84. let a = 4::3::4::2::1::[0];;(* El famous example *)
  85. let rec supprime_repetition l = match l with
  86.  
  87.     (*
  88.       Si la liste est vide => il n'y a pas de répétions donc on quitte et on renvoie l
  89.       la liste vide (on aurait pu mettre l mais c'est juste pour faire propre)
  90.     *)
  91.     | [] -> []
  92.    
  93.     (* Si x appartient à q, ça veut dire qu'il existe au moins 2 fois donc on le remet pas *)
  94.     | x::q -> if (appartient q x) then (supprime_repetition q) else x::(supprime_repetition q);;
  95.    
  96. supprime_repetition a;; (* petit test des familles *)
  97.  
  98.  
  99. (* Ex 6 *)
  100. (* Je me suis embrouillé moi même, c'est la version non-optimisé avec utilisation d'accumulateur lol *)
  101. let a = 4::3::4::2::1::[0];;
  102. let retirer_un x l =
  103.     if (appartient l x) then
  104.         let rec __retirer_un x l acc =
  105.         match l with
  106.                 | [] -> []
  107.                 | y::q when x=y -> if acc=true then y::(__retirer_un x q acc) else (__retirer_un x q true)
  108.                 | y::q -> y::(__retirer_un x q acc); in (__retirer_un x l false);
  109.     else failwith "x n'appartient pas";;
  110.    
  111. retirer_un 4 a;; (* petit test des familles *)
  112.  
  113.  
  114.  
  115.  
  116. (* Ex 7 *)
  117. let a = 4::3::4::2::1::[0];;
  118. let rec retirer_tous x l = match l with
  119.  
  120.     (* Si la liste est vide on quitte *)
  121.     | [] -> []
  122.    
  123.     (* Si x=y, on l'enlève *)
  124.     | y::q when x=y -> retirer_tous x q
  125.    
  126.     (* Sinon on le met *)
  127.     | y::q -> y::(retirer_tous x q);;
  128.    
  129.    
  130. retirer_tous 4 a;; (* petit test des familles *)
  131.  
  132.  
  133.  
  134.  
  135.  
  136. (* Ex 8 *)
  137. let a = 4::3::4::2::1::[0];;
  138. let rec extraire n l = match n with
  139.  
  140.     (* Si n est négative, là on rage quitte *)
  141.     | n when n < 0 -> failwith "n invalide"
  142.    
  143.     (*
  144.       Si n=0, on quitte en renvoyant la liste
  145.       qui est pas forcément la liste l du début, attention c'est récursif
  146.     *)
  147.     | 0 -> l
  148.    
  149.     (* Sinon on itère jusqu'à ce que n=0, auquel cas on revient au cas du dessus *)
  150.     | _ -> match l with
  151.         (* Si on arrive là, c'est que la valeur de n est trop grande, du coup on rage quitte *)
  152.         | [] -> failwith "n invalide"
  153.        
  154.         (* Sinon on continue d'explorer la liste est espérer qu'à un moment n soit égal à 0 *)
  155.         | x::q -> if n-1=0 then x::(extraire (n-1) q) else (extraire (n-1) q);;
  156.        
  157. extraire 3 a;; (* petit test des familles *)
  158.  
  159.  
  160.  
  161. (* Ex 9 *)
  162. let a = 4::3::4::2::1::[0];;
  163. let reperer x l =
  164.    
  165.     (* Si x appartient, c'est bon *)
  166.     if (appartient l x) then
  167.         let rec __reperer x l = match l with
  168.        
  169.             (* Si c'est vide, on arrête la récursion *)
  170.             | [] -> []
  171.            
  172.             (* Sinon on continue d'explorer *)
  173.             | y::q -> if x=y then y::q else (__reperer x q); in (__reperer x l);
  174.            
  175.     else failwith "x n'appartient pas";; (* sinon on rage quitte *)
  176.    
  177. reperer 2 a;; (* petit test des familles *)
  178.  
  179.  
  180. (* Là c'est quand je m'embrouille xD *)
  181. (*
  182. let inserer n x l =
  183.     let dynamic = ref false in
  184.     let rec __inserer n1 n2 x l =
  185.        if !dynamic=false then
  186.         match n with
  187.                 | n when n < 0 -> failwith "n invalide"
  188.                 | 0 -> x::l
  189.                 | x::q -> match l with
  190.                     | [] -> dynamic := (x,n)
  191.                     | y::q -> if x=y then begin
  192.                                 dynamic := (x,n);
  193.                                 (__inserer (n-1) n x q);
  194.                                 end;
  195.                                 else (__inserer (n-1) n x q);
  196.         else
  197.             match l with
  198.                 | [] -> []
  199.                 | x::q -> if
  200.     ; in( __inserer n x l)
  201. *)
  202.    
  203.    
  204.    
  205.    
  206. (* Ex 10 *)
  207. let a = 4::3::4::2::1::[0];;
  208. let inserer n x l =
  209.     let rec _inserer n x l acc = match n with
  210.  
  211.         (* Si n est négtive on rage quitte *)
  212.         | n when n < 0 -> failwith "n invalide"
  213.    
  214.         (* Si n = 0, ba on rajoute juste l'élément *)
  215.         | 0 -> x::l
  216.    
  217.         (* Sinon, ba on itère jusqu'à ce qu'on arrive à l'élément n *)
  218.         | _ -> match l with
  219.    
  220.             (* Si on arrive là, c'est que la valeur de n est trop grande, du coup on rage quitte *)
  221.             | [] -> failwith "Sorry, length of the list too small"
  222.        
  223.             (* Sinon on explore tout en constuisant notre liste au fur et à mesure *)
  224.             | h::q -> if n!=acc then h::(inserer n x q (acc+1)) else x::h::q;
  225.    
  226.     (* et on oublie pas d'appeler la fonction *)
  227.     in _inserer n x l 0;;
  228.  
  229.  
  230.  
  231. inserer 3 999 a;; (* petit test des familles *)
  232.  
  233.  
  234.  
  235. (* Ex 11 *)
  236. let rec sous_mot m l = match m,l with (* double filtrage *)
  237.  
  238.     (* [] = [] donc on renvoie true *)
  239.     | [],[] -> true
  240.    
  241.     (* x::q != [] donc on renvoie faux *)
  242.     | x::q,[] -> false
  243.    
  244.     (* [] != x::q donc on renvoie faux *)
  245.     | [],x::q -> false
  246.    
  247.     (* On teste si x=y, si oui on continue d'explorer sinon on renvoie faux *)
  248.     | x::q,y::h -> if x=y then sous_mot q h else false;;
  249.  
  250. (* petit test des familles *)
  251.   sous_mot (1::2::3::4::[5]) (1::2::3::4::[5]);;  (* true *)
  252.   sous_mot (1::2::3::4::[5]) (1::2::9875::4::[5]);; (* false *)
  253.  
  254.  
  255.  
  256. (* Ex 12 *)
  257. let a = 4::3::4::2::1::[0];;
  258. let mirroir l =
  259.  
  260.     (*
  261.       l : la liste a inversé
  262.       g : la liste inversée
  263.      *)
  264.     let rec _mirroir l g = match l with
  265.    
  266.         (*
  267.           Si on arrive là,
  268.           c'est qu'on est arrivé au bout de la liste l,
  269.           du coup en renvoie g qui contient la liste l inversée
  270.         *)
  271.         | [] -> g
  272.        
  273.         (* on rappelle la fonction en stockant la valeur dans l'accumulateur *)
  274.         | x::q -> _mirroir q (x::g); in
  275.        
  276.         (* Voici ce qu'il se passe pour la liste 1::2::[3]
  277.        
  278.              - ETAPE 1 : g = []
  279.              - ETAPE 2 : g = [1]
  280.              - ETAPE 3 : g = 2::[1] (car on fait x::g, ici x = 2 et g = [1])
  281.              - ETAPE 4 : g = 3::2::[1]  (car on fait x::g, ici x = 3 et g = 2::[1])
  282.              - ETAPE 5 : l est vide donc on renvoie g
  283.          *)
  284.  
  285.        
  286.     _mirroir l [];; (* On appelle la fonction avec un accumulateur vide (une liste vide) *)
  287.     (* Fin de la fonction ici ;) *)
  288.  
  289.  
  290. mirroir a;; (* petit test des familles *)
  291.  
  292.  
  293.  
  294.  
  295. (* Ex 13 *)
  296. let a = 1::2::3::[4];;
  297. let b = 5::6::7::8::9::[10];;
  298. let rec concat m l = match m with
  299.  
  300.     (*
  301.       Si la liste m est vide, c'est qu'on la ajouté,
  302.       maintenant on teste si l=[],
  303.         Si oui ba on a fini donc on arrête et on quitte
  304.         Sinon on inverse l et m, comme m est déjà vide,
  305.         on l'indique explicitement, pour une meilleure lecture
  306.     *)
  307.     | [] -> if l=[] then [] else concat l []
  308.    
  309.     (* On ajoute tranquillement une après l'autre chaque valeur *)
  310.     | x::q -> x::(concat q l);;
  311.    
  312.    
  313. concat a b;; (* et le teste qui va avec bien sûr *)
  314.  
  315.  
  316. (* Ex 14 *)
  317. let a = 4::3::4::2::1::[0];;
  318. let f x = x*x;; (* notre fonction *)
  319. let rec parcours l f = match l with
  320.  
  321.     (* Si la liste est vide on quitte *)
  322.     | [] -> []
  323.    
  324.     (* Sinon on remplace chaque valeur x par f x *)
  325.     | x::q -> (f x)::(parcours q f);;
  326.              
  327. (* le test *)
  328. parcours a f;;
  329.  
  330.  
  331.  
  332. (* Ex 15 *)
  333. let a = 4::3::4::2::1::[0];;
  334. let f x = x*x;; (* notre fonction *)
  335. let parcours_envers l f =
  336.     let rec _parcours_envers l f acc = match l with
  337.    
  338.         (* Si la liste est vide, on renvoie la liste inversée contenu dans acc *)
  339.         | [] -> acc
  340.        
  341.         (* Sinon on explore tout en ajoutant dans l'accumulateur f x *)
  342.         | x::q -> _parcours_envers q (f) ((f x)::acc); in _parcours_envers l (f) [];;
  343.  
  344. parcours_envers a f;; (* El Famous Test *)
  345.  
  346.  
  347.  
  348.  
  349.  
  350. (* Ex 16 *)
  351.  
  352. (* Voici une liste de liste *)
  353. (* je rappelle que ceci est équivalent :
  354.     - let a = 1::2::[3];;
  355.     - let a = [1; 2; 3];;
  356.    du coup on va se servir de ces 2 syntaxes pour avoir quelque chose d'agréable au niveau visuel *)
  357.  
  358. let a = [1::2::[3]; 4::5::[6]; 7::8::[9]];;
  359. (*
  360.   correspond à ceci : [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]]
  361.   et bien sûr pour accéder à l'élément 3 de la 2ème liste, il faut faire une double récursion mdr
  362. *)
  363.  
  364. (* maintenant qu'on posait les bases, on y va *)
  365. let aplatir l =
  366.    
  367.     (* on déclare 2 fonctions récrusive *)
  368.     (* et on va utiliser un accumulateur pour sotcker succesivement la double récursion *)
  369.    
  370.     (* 1ère récursion, on itère de liste en liste *)
  371.     let rec _aplatir l acc  = match l with
  372.         | [] -> acc
  373.         | x::q -> _aplatir q (_concat acc x);
  374.    
  375.     (* 2ème récursion imbriqué dans la 1ère, on itère de int en int *)
  376.     (* cette fonction permet de concatener de liste (plus de détail Exercice 13 *)
  377.     and _concat m l = match m with
  378.         | [] -> if l=[] then [] else _concat l []
  379.         | x::q -> x::(_concat q l);
  380.        
  381.     (* plus qu'à appeler tranquillement notre fonction aplatir ;) avec l'accumulateur vide *)
  382.     in _aplatir l [];;
  383.  
  384. (* et on teste :D *)
  385. aplatir a;;
  386. (*
  387. on obtients bien                          : 1::2::3::4::5::6::7::8::[9]
  388. ou suivant la syntaxe que vous préférez   : [1; 2; 3; 4; 5; 6; 7; 8; 9]   (* équivalent *)
  389. *)
  390.  
  391.  
  392.  
  393.  
  394.  
  395. (* Ex 17 *)
  396.  
  397. (* la liste est sous la forme : *)
  398. let a = [(1,2); (3,4); (5,6)];;
  399.  
  400. let separe l =
  401.     let rec _separe l acc1 acc2 = match l with
  402.    
  403.         (* Si la liste est vide, c'est qu'on terminé du coup on renvoie acc1 et acc2 dans une liste *)
  404.         | [] -> [acc1; acc2]
  405.        
  406.         (* Sinon on explore en mettant d'un côté la 1ère composante et de l'autre la 2ème composante *)
  407.         | x::q -> _separe q (acc1@[(fst x)]) (acc2@[(snd x)]);
  408.    
  409.     in _separe l [] [];;
  410.    
  411. (* le mega teste de malade -----> *)
  412. separe a;; (* output: [[1; 3; 5]; [2; 4; 6]] *)
  413.  
  414.  
  415.  
  416.  
  417.  
  418. (* Ex 18 *)
  419. let create_pile = [];; (* trop dure, je me suis fait mal *)
  420.  
  421. let append_pile l x = x::l;; (* beaucoup trop dure cette exo, limite c'est impossible en fait *)
  422.  
  423. let pop_pile l = match l with | [] -> [] | x::q -> q;; (* nan mais là, même moi j'ai du mal *)
  424.  
  425. let isEmpty_pile l = if l=[] then true else false;; (* je viens de perdre un bras *)
  426.  
  427.  
  428. (* le mega test *)
  429. let ma_pile = create_pile;;
  430. isEmpty_pile ma_pile;;
  431. let ma_pile = append_pile ma_pile 1;;
  432. let ma_pile = append_pile ma_pile 2;;
  433. let ma_pile = append_pile ma_pile 3;;
  434. let ma_pile = pop_pile ma_pile;;
  435. let ma_pile = pop_pile ma_pile;;
  436. isEmpty_pile ma_pile;;
  437.  
  438.  
  439.  
  440.  
  441.  
  442. (* Ex 19 *)
  443. let create_file = [];; (* ça y est, je pourrais plus jamais nager, quoique il me reste mes jambes *)
  444.  
  445. let append_file l x = x::l;; (* woooooow chaud *)
  446.  
  447. (* enfin un petit challenge *)
  448. let rec pop_file l = match l with
  449.     | [] -> []
  450.     | [x] -> []
  451.     | x::q -> x::(pop_file q);;
  452.  
  453. let isEmpty_file l = if l=[] then true else false;; (* je viens de perdre une jambe *)
  454.  
  455.  
  456. (* le mega test *)
  457. let ma_file = create_file;;
  458. isEmpty_file ma_file;;
  459. let ma_file = append_file ma_file 1;;
  460. let ma_file = append_file ma_file 2;;
  461. let ma_file = append_file ma_file 3;;
  462. let ma_file = pop_file ma_file;;
  463. let ma_file = pop_file ma_file;;
  464. isEmpty_file ma_file;;
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top