162 lines
3.0 KiB
Plaintext
162 lines
3.0 KiB
Plaintext
#show enum.item: it => {
|
|
let (number, body, ..fields) = it.fields()
|
|
if body.func() == block { return it }
|
|
|
|
body = block(breakable: false, body)
|
|
enum.item(number, body, ..fields)
|
|
}
|
|
|
|
= DS n°3
|
|
|
|
== TD et TP
|
|
|
|
#set enum(numbering: "T1.")
|
|
\
|
|
+ ```ocaml
|
|
let points main = Array.fold_left
|
|
(fun acc carte -> acc + (points_carte carte))
|
|
0
|
|
main
|
|
;;
|
|
```
|
|
|
|
+ ```ocaml
|
|
let creer_fileb capacite init = {
|
|
taille = 0;
|
|
tete = 0;
|
|
queue = 0;
|
|
donnees = Array.make capacite init
|
|
};;
|
|
|
|
let enfiler_fileb f x =
|
|
let capacite = Array.length f.donnees in
|
|
if f.taille = capacite then
|
|
failwith "File pleine"
|
|
else
|
|
f.donnees.(f.queue) <- x;
|
|
f.queue <- (f.queue + 1) mod capacite;
|
|
f.taille <- f.taille + 1
|
|
;;
|
|
|
|
let defiler_fileb f =
|
|
let capacite = Array.length f.donnees in
|
|
if f.taille = 0 then
|
|
failwith "File vide"
|
|
else
|
|
let x = f.donnees.(f.tete) in
|
|
f.tete <- (f.tete + 1) mod capacite;
|
|
f.taille <- f.taille - 1;
|
|
x
|
|
;;
|
|
|
|
let est_vide_fileb f = f.taille = 0;;
|
|
```
|
|
|
|
+ ```ocaml
|
|
let rec map func l = match l with
|
|
| [] -> []
|
|
| x::q -> (func x)::map func q
|
|
;;
|
|
```
|
|
|
|
+ ```c
|
|
void tri_denombrement(int t[], int taille, int k) {
|
|
int *counts = malloc((k+1)*sizeof(int));
|
|
for (int i=0; i<k+1; i+=1) {
|
|
counts[i] = 0;
|
|
}
|
|
for (int i=0; i<taille; i+=1) {
|
|
counts[t[i]] += 1;
|
|
}
|
|
int i = 0;
|
|
for (int j=0; j<k+1 && i < taille; j+=1) {
|
|
while (counts[j] > 0) {
|
|
t[i] = j;
|
|
i += 1;
|
|
counts[j] -= 1;
|
|
}
|
|
}
|
|
}
|
|
```
|
|
|
|
== Exercices
|
|
|
|
=== Exercice 1
|
|
\
|
|
Première fonction :
|
|
```ocaml
|
|
let rec somme l = match l with
|
|
| [] | _::[] -> l
|
|
| (x,a)::(y,b)::q ->
|
|
if x = y then
|
|
(x,a+.b)::somme q
|
|
else
|
|
(x,a)::somme ((y,b)::q)
|
|
;;
|
|
let func1 l = somme (List.fast_sort compare l);;
|
|
```
|
|
\
|
|
Deuxième fonction :
|
|
```ocaml
|
|
(* On suppose que l est une liste de Hashtbl *)
|
|
let rec func2 l = match l with
|
|
| [] -> Hashtbl.create 0
|
|
| ht::q ->
|
|
let ht2 = func2 q in
|
|
Hashtbl.iter
|
|
(fun cle x ->
|
|
Hashtbl.replace ht2 cle (
|
|
match Hashtbl.find_opt ht2 cle with
|
|
| None -> x
|
|
| Some x2 -> x+.x2
|
|
)
|
|
)
|
|
ht;
|
|
ht2
|
|
;;
|
|
```
|
|
#pagebreak()
|
|
Troisième fonction :
|
|
```c
|
|
struct couple {
|
|
int cle;
|
|
double val;
|
|
};
|
|
typedef struct couple cpl;
|
|
void sort(cpl t[], int taille) {
|
|
if (taille <= 1) {
|
|
return;
|
|
}
|
|
int pivot = t[taille-1].cle;
|
|
int i = 0;
|
|
int j = taille-2;
|
|
while (i<j) {
|
|
while (t[i].cle<=pivot && i<j) i+=1;
|
|
while (t[j].cle>=pivot && i<j) j-=1;
|
|
cpl temp = t[i];
|
|
t[i] = t[j];
|
|
t[j] = temp;
|
|
}
|
|
cpl temp = t[taille-1];
|
|
t[taille-1] = t[i];
|
|
t[i] = temp;
|
|
sort(t, i);
|
|
sort(t+i+1, taille-i-1);
|
|
}
|
|
// Renvoie la nouvelle taille du tableau
|
|
int func3(cpl t[], int taille) {
|
|
sort(t, taille);
|
|
int i=0;
|
|
for (int j=1; j<taille; j+=1) {
|
|
if (t[j-1].cle == t[j].cle) {
|
|
t[i].val += t[j].val;
|
|
} else {
|
|
i+=1;
|
|
t[i] = t[j];
|
|
}
|
|
}
|
|
i += 1;
|
|
return i;
|
|
}
|
|
```
|