Cours du 29 au 3 octobre

4 files changed, 119 insertions, 0 deletions

diff --git a/semestre 3/structures des données/td/td3/exo1.md b/semestre 3/structures des données/td/td3/exo1.md
new file mode 100644
index 0000000..7aba849
--- /dev/null
+++ b/semestre 3/structures des données/td/td3/exo1.md
@@ -0,0 +1,14 @@
+Une hashmap semble pertinente, car on a une association clé/valeur.
+
+La fonction de hachage devra donc renvoyé sur [0, 100 000-1], i.e. être modulo 100 000.
+
+Elle provoque beaucoup de collisions, notamment si au moins une valeur est à 0. 
+Pour régler ce problème, on pourrait utiliser
+```c
+int g(int x1, int x2, int x3, int x4, int x5, int x6) {
+    return (x1+1)*(x2+1)*(x3+1)*(x4+1)*(x5+1)*(x6+1) % 100000;
+}
+```
+
+La fonction ne prend pas en compte l'ordre des valeurs.
+
diff --git a/semestre 3/structures des données/td/td3/exo2.md b/semestre 3/structures des données/td/td3/exo2.md
new file mode 100644
index 0000000..9c013a1
--- /dev/null
+++ b/semestre 3/structures des données/td/td3/exo2.md
@@ -0,0 +1,17 @@
+1. 14
+2. 8
+3. 3
+4. 5
+5. 1
+6. 8
+7. 4
+8. 4
+9. 6
+10. 8
+11. 5
+12. 5
+13. 4
+
+1. On aurait 3 valeurs en case 8, en 4, en 5
+2. La 6e valeur serait en 9 (+1), la 8e serait en 6 (+2), la 9e serait en 7 (+1), la 8e serait en 10 (+2), la 11e serait en 9 (+4), la 12e serait en (+5) et la 13e en 10 (+6).
+3. flemme
diff --git a/semestre 3/structures des données/td/td3/exo3.py b/semestre 3/structures des données/td/td3/exo3.py
new file mode 100644
index 0000000..93dde73
--- /dev/null
+++ b/semestre 3/structures des données/td/td3/exo3.py
@@ -0,0 +1,44 @@
+val = [
+    ("le", 123), ("cours", 22), ("appelé", 88), ("structure", 43), ("de", 4),
+    ("données", 28), ("est", 73), ("absolument", 7), ("génial", 13)
+]
+
+
+def f1(x):
+    return x
+
+
+def f2(x):
+    return 10*x
+
+
+def f3(x):
+    return 2*x
+
+
+def f4(x):
+    if x == 0:
+        return 0
+    return 8 * f4(int(x/10)) + x % 10
+
+
+print([(a,f1(b)) for a, b in val])
+print("")
+print([(a,f2(b)) for a, b in val])
+print("")
+print([(a,f3(b)) for a, b in val])
+print("")
+print([(a,f4(b)) for a, b in val])
+
+print("")
+print("collisions f1", len(val) - len({ f1(b) % 10 for _, b in val }))
+print("")
+print("collisions f2", len(val) - len({ f2(b) % 10 for _, b in val }))
+print("")
+print("collisions f3", len(val) - len({ f3(b) % 10 for _, b in val }))
+print("")
+print("collisions f4", len(val) - len({ f4(b) % 10 for _, b in val }))
+
+
+print("")
+print("La meilleure fonction est donc f4, car elle génère moins de collisions que les autres")
diff --git a/semestre 3/structures des données/td/td3/exo4.c b/semestre 3/structures des données/td/td3/exo4.c
new file mode 100644
index 0000000..02134c8
--- /dev/null
+++ b/semestre 3/structures des données/td/td3/exo4.c
@@ -0,0 +1,44 @@
+typedef struct cell{
+    int val;
+    int key;
+    cell* next;
+} Cell;
+
+typedef struct hashMap{
+    int size;
+    cell** map;
+} HashMap;
+
+void mapInsert(HashMap* map, int val){
+    map->map[g(val)] = val;
+}
+
+int mapLen(HashMap* map){
+    int len = 0;
+    for (int i = 0; i < map->size; i++){
+        Cell* v = map->map[i];
+        while (v){
+            len++;
+            v = v->next;
+        }
+    }
+    return len;
+}
+
+void mapDel(HashMap* map, int val){
+    Cell* f = map->map[g(val)];
+    Cell* v = f;
+    Cell* b;
+    while (v && v->val != val){
+        b = v;
+        v = v->next;
+    }
+    if (v->val != val) return;
+    if (!b){
+        f = v->next;
+    } else {
+        b = v->next;
+    }
+    free(v);
+}
+