Cours du 22 au 26 septembre

2 files changed, 80 insertions, 12 deletions

diff --git a/semestre 3/structures des données/tme/tme1-2/exo2/question2.c b/semestre 3/structures des données/tme/tme1-2/exo2/question2.c
index 33182ea..19d29cc 100644
--- a/semestre 3/structures des données/tme/tme1-2/exo2/question2.c
+++ b/semestre 3/structures des données/tme/tme1-2/exo2/question2.c
@@ -14,22 +14,16 @@ int diff_quad(int *t, int n){
 
 /* Calcule la somme des carrés des différences entre les éléments des tableaux pris deux à deux (version linéaire)
  *
- * On a que sum(sum(x_ix_j)) = (sum(x_i))^2.
- * En developpant, on obtient : sum(sum(T_i^2-2*T_i*T_j+T_j^2))
- * i.e. : sum(sum(T_i^2))-sum(sum(2*T_i*T_j))+sum(sum(T_j^2))
- * i.e. : sum(sum(T_i^2))-2*sum(sum(T_i*T_j))+sum(sum(T_j^2))
- * i.e. : 2*sum(T_i^2)-2*sum(sum(T_i*T_j))+2*sum(T_j^2)
- * i.e. : 2*sum(T_i^2)-2*(sum(T_i))^2+2*sum(T_j^2)
- * Ainsi : 2*(2*sum(T_i^2)-(sum(T_i))^2)
+ * Après diverses simplifications, on obtient que sum(sum(T_i-T_j)^2) est egale à 2 * sum(n*T_i*T_j - T_i^2)
  * */
 int diff_lin(int *t, int n){
-    int sum1 = 0;
-    int sum2 = 0;
+    int sum = 0;
+    int sub_sum = 0;
     for (int i = 0; i < n; i++){
-        sum1 += t[i]*t[i];
-        sum2 += t[i];
+        sum += n*t[i]*t[i];
+        sub_sum += t[i];
     }
-    return 2*(2*sum1-sum2*sum2);
+    return 2 * (sum - sub_sum * sub_sum); 
 }
 
 int main(void){
diff --git a/semestre 3/structures des données/tme/tme1-2/exo2/question4-6.c b/semestre 3/structures des données/tme/tme1-2/exo2/question4-6.c
new file mode 100644
index 0000000..d75179a
--- /dev/null
+++ b/semestre 3/structures des données/tme/tme1-2/exo2/question4-6.c
@@ -0,0 +1,74 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <time.h>
+
+typedef struct{
+    int size;
+    int* content;
+} Matrice;
+
+Matrice* alloue_matrice(int n){
+    int** content = (int**) malloc(n*n*sizeof(int));
+    Matrice* m = (Matrice*) malloc(sizeof(Matrice));
+    m->content = content;
+    return m
+}
+
+void desalloue_matrice(Matrice* m){
+    free(m->content);
+    free(m);
+}
+
+void remplir_matrice(Matrice* m, int max){
+    srand(time(null));
+    for (int i = 0; i < n; i++){
+        for (int j = 0; j < n; j++){
+            m->content[i][j] = rand()%max;
+        }
+    }
+}
+
+void affiche_matrice(Matrice* m){
+    printf("[");
+    for (int i = 0; i < n; i++){
+        printf(" [");
+        for (int j = 0; j < n; j++){
+            printf("%d ", m->content[i][j]);
+        }
+        printf("]%c", i != n -1 ? '\n' : ' ');
+    }
+    printf("]\n");
+}
+
+Matrice* produit_matrice(Matrice* m1, Matrice* m2){
+    if (m1->size != m2->size){
+        return NULL;
+    }
+    Matrice* prod = alloue_matrice(m1->size);
+    for (int i = 0; i < m1->size; i++){
+        for (int k = 0; k < m1->size; k++){
+            prod->content[i][k] = 0;
+            for (int j = 0; j < m1->size; j++){
+                prod->content[i][k] += m1->content[i][j]*m2->content[j][k];
+            }
+        }
+    }
+    return prod;
+}
+
+/* Reste en O(n3), mais est plus rapide que produit_matrice car on arrete les boucles plus tot */
+Matrice* produit_matrice_trian(Matrice* m_sup, Matrice* m_inf){
+    if (m_sup->size != m_inf->size){
+        return NULL;
+    }
+    Matrice* prod = alloue_matrice(m_sup->size);
+    for (int i = 0; i < m_sup->size; i++){
+        for (int k = 0; k < m_sup->size; k++){
+            prod->content[i][k] = 0;
+            for (int j = i; j < m_sup->size; j++){
+                prod->content[i][k] = m_sup->content[i][j]*m_inf->content[j][k];
+            }
+        }
+    }
+    return prod;
+}