From 4a3afaf44aa29e66a6c879c60322015a2920a5ab Mon Sep 17 00:00:00 2001 From: Anhgelus Morhtuuzh Date: Mon, 10 Mar 2025 10:31:33 +0100 Subject: Ajout de la semaine des cours du 3 au 7 mars --- "semestre 2/informatique/6- R\303\251cursion.md" | 45 +++++++++++ "semestre 2/informatique/6- r\303\251cursion.md" | 45 ----------- .../7- Structure (ou enregistrement).md | 91 ++++++++++++++++++++++ .../td/5- cha\303\256nes de caract\303\250re.md" | 9 +-- .../td/6- r\303\251cursivit\303\251.md" | 25 ++++++ .../informatique/tme/semaine5/27_comptage_mots.c | 19 +++++ .../tme/semaine5/28_participation_frais.c | 52 +++++++++++++ semestre 2/informatique/tme/semaine5/29_filtre.c | 25 ++++++ .../informatique/tme/semaine5/30_compression.c | 64 +++++++++++++++ .../informatique/tme/semaine5/31_image_mystere.c | 29 +++++++ 10 files changed, 351 insertions(+), 53 deletions(-) create mode 100644 "semestre 2/informatique/6- R\303\251cursion.md" delete mode 100644 "semestre 2/informatique/6- r\303\251cursion.md" create mode 100644 semestre 2/informatique/7- Structure (ou enregistrement).md create mode 100644 "semestre 2/informatique/td/6- r\303\251cursivit\303\251.md" create mode 100644 semestre 2/informatique/tme/semaine5/27_comptage_mots.c create mode 100644 semestre 2/informatique/tme/semaine5/28_participation_frais.c create mode 100644 semestre 2/informatique/tme/semaine5/29_filtre.c create mode 100644 semestre 2/informatique/tme/semaine5/30_compression.c create mode 100644 semestre 2/informatique/tme/semaine5/31_image_mystere.c (limited to 'semestre 2/informatique') diff --git "a/semestre 2/informatique/6- R\303\251cursion.md" "b/semestre 2/informatique/6- R\303\251cursion.md" new file mode 100644 index 0000000..7ce5af6 --- /dev/null +++ "b/semestre 2/informatique/6- R\303\251cursion.md" @@ -0,0 +1,45 @@ +--- +tags: + - sorbonne + - informatique +semestre: 2 +--- +Une fonction récursive est une fonction qui s'appelle elle-même, e.g. +```c +int somme(int n){ + if (n == 0) return 0; + return somme(n-1) + n; +} +``` + +Besoin d'avoir une hypothèse de récurrence quand on fait une récursion +|> besoin d'avoir une convergence, sinon la récursion est infinie + +| Indice | = | valeur | +| ---------------- | --- | ---------------------- | +| (1) somme_int(3) | = | 3+somme_int(2) | +| (2) | = | 3+(2+somme_int(1)) | +| (3) | = | 3+(2+(1+somme_int(0))) | +| (4) | = | 3+(2+(1+0)) | +| (5) | = | 6 | +La pile ressemble à la même chose que le tableau + +Si l'appel est trop vénère, alors il remplit la mémoire et provoque une erreur + +Autre exemple : +```c +int factoriel(int n){ + if (n <= 1) return 1; + return factoriel(n-1) * n; +} +``` + +La suite de Fibonacci, +$$ F_n=\left\{\begin{matrix}1&\text{si $n=0$ ou $n=1$}\\F_{n-1}+F_{n-2}&\text{sinon}\end{matrix}\right. $$ +sert à faire une dichotomie plus rapide en pratique (mais pas en théorie) +```c +int fibonacci(int n){ + if (n <= 1) return 1 + return fibonacci(n-1)+fibonacci(n-2) +} +``` \ No newline at end of file diff --git "a/semestre 2/informatique/6- r\303\251cursion.md" "b/semestre 2/informatique/6- r\303\251cursion.md" deleted file mode 100644 index 7ce5af6..0000000 --- "a/semestre 2/informatique/6- r\303\251cursion.md" +++ /dev/null @@ -1,45 +0,0 @@ ---- -tags: - - sorbonne - - informatique -semestre: 2 ---- -Une fonction récursive est une fonction qui s'appelle elle-même, e.g. -```c -int somme(int n){ - if (n == 0) return 0; - return somme(n-1) + n; -} -``` - -Besoin d'avoir une hypothèse de récurrence quand on fait une récursion -|> besoin d'avoir une convergence, sinon la récursion est infinie - -| Indice | = | valeur | -| ---------------- | --- | ---------------------- | -| (1) somme_int(3) | = | 3+somme_int(2) | -| (2) | = | 3+(2+somme_int(1)) | -| (3) | = | 3+(2+(1+somme_int(0))) | -| (4) | = | 3+(2+(1+0)) | -| (5) | = | 6 | -La pile ressemble à la même chose que le tableau - -Si l'appel est trop vénère, alors il remplit la mémoire et provoque une erreur - -Autre exemple : -```c -int factoriel(int n){ - if (n <= 1) return 1; - return factoriel(n-1) * n; -} -``` - -La suite de Fibonacci, -$$ F_n=\left\{\begin{matrix}1&\text{si $n=0$ ou $n=1$}\\F_{n-1}+F_{n-2}&\text{sinon}\end{matrix}\right. $$ -sert à faire une dichotomie plus rapide en pratique (mais pas en théorie) -```c -int fibonacci(int n){ - if (n <= 1) return 1 - return fibonacci(n-1)+fibonacci(n-2) -} -``` \ No newline at end of file diff --git a/semestre 2/informatique/7- Structure (ou enregistrement).md b/semestre 2/informatique/7- Structure (ou enregistrement).md new file mode 100644 index 0000000..d06d805 --- /dev/null +++ b/semestre 2/informatique/7- Structure (ou enregistrement).md @@ -0,0 +1,91 @@ +--- +tags: + - sorbonne + - informatique +semestre: 2 +--- +Pour organiser les données, on utilise `struct` +```c +struct s_int_pair { + int fst; + int snd; +}; // vraiment utile le ; ? +``` +Est toujours au début du fichier `.c` ou dans le `.h` si elle est utilisée par plusieurs fichiers +|> possède deux champs nommés `fst` et `snd` + +Les fichiers headers (`.h`) spécifient les interfaces utilisables par l'extérieur du fichier C +|> contient les struct publics, les functions publiques... +|> ne contient pas tout ce qui est privé + +Pour qu'une variable utilise un struct, on écrit +```c +struct s_int_pair point; +``` +sauf que c'est long à écrire, donc on renomme tout ça avec un `typedef` : +```c +typedef struct s_int_pair int_pair; +int main(){ + int_pair point; + return 0; +} +``` +on peut aussi tout définir d'un coup +```c +typedef struct s_int_pair{ + int fst; + int snd; +} int_pair; +``` + +> [!NOTE] Nom de la structure et nom du type associé +> Souvent, on nomme `_ABC` le nom de la structure et `ABC` le nom du type associé +> |> permet d'avoir un nom similaire mais différent +> |> est une convention + +Pour initialiser un struct, on utilise les parenthèses +```c +int_pair p = {1,2}; // initialisation séquentielle +int_pair p2 = {.snd=3, .fst=4}; // initialisation sélective +``` +la première est traditionnelle et est commune + +Pour modifier les valeurs dans un struct, on accède aux champs avec l'opérateur `.` : +```c +p.fst = -1; +p.snd = -2; + +p = p2; // copie la structure p2 dans p +``` + +*voir le cours pour la représentation dans le stack* + +Quand on définit une structure, on peut perdre de la mémoire, notamment si on utilise pas tout un octet + +Structures et fonctions +|> on peut retourner des structures depuis des fonctions sans aucun problème (pas besoin de faire un `malloc`) +|> il n'y a pas d'effet de bord quand on utilise des structures dans une fonctions -> on a besoin d'utiliser un pointeur pour en réaliser un + +Il n'existe pas d'arithmétique des structures + +On peut chaîner les structures, i.e. +```c +struct _cell { + int v; + struct cell* next; +} +``` +(ce qui donne une liste chaînée) + +L'opérateur `->` est un raccourcie permettant le déférencement rapide +```c +Foo *foo; + +foo->bar = 10; +// est équivalent à +(*foo).bar = 10; + +foo->baz(); +// est équivalent à +(*foo).baz(); +``` diff --git "a/semestre 2/informatique/td/5- cha\303\256nes de caract\303\250re.md" "b/semestre 2/informatique/td/5- cha\303\256nes de caract\303\250re.md" index 0587412..8bea089 100644 --- "a/semestre 2/informatique/td/5- cha\303\256nes de caract\303\250re.md" +++ "b/semestre 2/informatique/td/5- cha\303\256nes de caract\303\250re.md" @@ -28,14 +28,7 @@ int int_to_str(int val){ for (i = 1; tmp_val % 10 != tmp_val; i++) tmp_val /= 10; char *str = malloc(sizeof(char) * (i+1)); // +1 car on n'oublie pas le '\0' str[i] = '\0'; // on rajoute de suite le '\0' - for (int j = 0; j <= i; j++) { - int c = val % pow(10, j); - val -= c; - str[j] = c + 48; - } + for (int j = 0; j < i; j++) str[j-1] = val % pow(10, j) + 48; return str; } ``` - -On ne peut pas écrire `int arr[][];` ! -|> on doit forcément indiquer la taille des sous-tableaux, e.g. `int arr[][5];` diff --git "a/semestre 2/informatique/td/6- r\303\251cursivit\303\251.md" "b/semestre 2/informatique/td/6- r\303\251cursivit\303\251.md" new file mode 100644 index 0000000..94124e3 --- /dev/null +++ "b/semestre 2/informatique/td/6- r\303\251cursivit\303\251.md" @@ -0,0 +1,25 @@ +--- +tags: + - sorbonne + - informatique + - td +semestre: 2 +--- +Fonction récursive pour trouver si deux chaînes sont égales +```c +int str_equal(char *s1, char *s2){ + int b = *s1 != *s2; + if (b || *s1 == '\0') return !b; + return str_equal(s1+1, s2+1); +} +``` + +Recherche par dichotomie : +```c +int dichotomie(int *a, int e, int taille){ + if (taille <= 0) return -1; + int m = (start+end) / 2; + if (a[m] == e) return m; + return dichotomie(e > a[m] ? tab+m+1 : tab, e, taille-m-1); +} +``` diff --git a/semestre 2/informatique/tme/semaine5/27_comptage_mots.c b/semestre 2/informatique/tme/semaine5/27_comptage_mots.c new file mode 100644 index 0000000..7ea19e7 --- /dev/null +++ b/semestre 2/informatique/tme/semaine5/27_comptage_mots.c @@ -0,0 +1,19 @@ +#include + +int compte_mots(char *s){ + int i = 0; + int cnt = 0; + int counted = 0; + while (s[i] != '\0'){ + if (s[i] != ' ' && !counted) { + cnt++; + counted = 1; + } else if (s[i] == ' ') counted = 0; + i++; + } + return cnt; +} + +int main() { + printf("%d", compte_mots(" bonjour je suis un mot ")); +} diff --git a/semestre 2/informatique/tme/semaine5/28_participation_frais.c b/semestre 2/informatique/tme/semaine5/28_participation_frais.c new file mode 100644 index 0000000..e5aff0d --- /dev/null +++ b/semestre 2/informatique/tme/semaine5/28_participation_frais.c @@ -0,0 +1,52 @@ +#include +#include +#include +#define NB_AMIS 4 +#define NB_JOURS 7 + +void init_tab(float tab[NB_AMIS][NB_JOURS]){ + for (int i = 0; i < NB_AMIS; i++) { + for (int j = 0; j < NB_JOURS; j++) tab[i][j] = 0; + } +} + +void random_tab(float tab[NB_AMIS][NB_JOURS], int j) { + int a = rand()%NB_AMIS; + int v = rand()%21+30; + tab[a][j] = v; + for (int i = 0; i < NB_AMIS; i++) { + if (i != a) tab[i][j] = (float) v/(-NB_AMIS+1); + } +} + +void show_tab(float tab[NB_AMIS][NB_JOURS]){ + printf("Jour/Ami||\t"); + for (int i = 0; i < NB_AMIS; i++) printf("%d\t|\t", i+1); + printf("\n"); + for (int i = 0; i < NB_AMIS*18; i++) printf("-"); + printf("\n"); + for (int j = 0; j < NB_JOURS;j++){ + for (int i = 0; i < NB_AMIS; i++) { + if (i == 0) printf("%d\t||\t", j+1); + printf("%.2f\t|\t", tab[i][j]); + if (i == NB_AMIS-1) printf("\n"); + } + } +} + +void show_solde(float tab[NB_AMIS][NB_JOURS], int a){ + float s = 0; + for (int j = 0; j < NB_JOURS; j++) s += tab[a][j]; + printf("Ami %d a pour solde %.02f\n", a, s); +} + +int main() { + float tab[NB_AMIS][NB_JOURS] = {}; + srand(time(NULL)); + init_tab(tab); + for (int d = 0; d < NB_JOURS; d++) random_tab(tab, d); + show_tab(tab); + for (int i = 0; i < NB_AMIS; i++) show_solde(tab, i); + return 0; +} + diff --git a/semestre 2/informatique/tme/semaine5/29_filtre.c b/semestre 2/informatique/tme/semaine5/29_filtre.c new file mode 100644 index 0000000..37a5625 --- /dev/null +++ b/semestre 2/informatique/tme/semaine5/29_filtre.c @@ -0,0 +1,25 @@ +#include +#include +#include + +void show_filtre(char *s){ + for (int i = 0; s[i] != '\0'; i++) { + if (s[i] >= 'A' && s[i] <= 'z') printf("%c", s[i]); + } +} + +char *filtre(char *s) { + char *ns = malloc(sizeof(char) * strlen(s)); + int j = 0; + for (int i = 0; s[i] != '\0'; i++){ + if (s[i] >= 'A' && s[i] <= 'z') ns[j++] = s[i]; + } + return ns; +} + +int main() { + char *s = "Hello World! What's up guys?"; + show_filtre(s); + printf("\n%s\n", filtre(s)); + return 0; +} diff --git a/semestre 2/informatique/tme/semaine5/30_compression.c b/semestre 2/informatique/tme/semaine5/30_compression.c new file mode 100644 index 0000000..161cd00 --- /dev/null +++ b/semestre 2/informatique/tme/semaine5/30_compression.c @@ -0,0 +1,64 @@ +#include +#include +#include +#define MIN 2 +#define MAX 15 + +int init_tab(int tab[MAX+1]) { + int size = rand()%(MAX-MIN+1)+MIN; + for (int i = 0; i < size; i++) { + tab[i] = rand()%2; + } + tab[size] = -1; + return size; +} + +void compress_tab(int tab_brut[], int tab_compress[]){ + int j = 0; + int last = -1; + int cnt = 0; + for (int i = 0; tab_brut[i] != -1; i++) { + if (last == -1 || tab_brut[i] != last) { + if (last != -1) { + int id = j++; + tab_compress[id*2] = cnt; + tab_compress[id*2+1] = last; + } + last = tab_brut[i]; + cnt = 0; + } + cnt++; + } + if (last != -1) { + int id = j++; + tab_compress[id*2] = cnt; + tab_compress[id*2+1] = last; + } + tab_compress[j*2] = -1; +} + +int compare(int tab_brut[], int tab_compress[]){ + int j = 0; + for (int i = 0; tab_compress[i] != -1; i += 2) { + int n = tab_compress[i]; + int v = tab_compress[i+1]; + for (int cnt = 0; cnt < n; cnt++) { + if (tab_brut[j++] != v) return 0; + } + } + return 1; +} + +int main(){ + srand(time(NULL)); + int tab[MAX+1] = {}; + int tab_compress[MAX+1] = {}; + init_tab(tab); + compress_tab(tab, tab_compress); + for (int i = 0; tab[i] != -1; i++) printf("%d, ", tab[i]); + printf("\n"); + for (int i = 0; tab_compress[i] != -1; i += 2) printf("%d:%d, ", tab_compress[i], tab_compress[i+1]); + printf("\n"); + printf("%s", compare(tab, tab_compress) ? "True" : "False"); + return 0; +} diff --git a/semestre 2/informatique/tme/semaine5/31_image_mystere.c b/semestre 2/informatique/tme/semaine5/31_image_mystere.c new file mode 100644 index 0000000..51ca321 --- /dev/null +++ b/semestre 2/informatique/tme/semaine5/31_image_mystere.c @@ -0,0 +1,29 @@ +#include +#include +#include + +void calcule_borne_sup(int *tab, int taille){ + int dec = -1; + for (int i = 0; i < taille; i++) { + tab[i] += dec; + dec = tab[i]; + } +} + +int tire_non_equi(int *tab, int taille){ + int tire = rand()%100; + int i; + for (i = taille -1; tab[i] > tire; i--); + printf("%d - %d <= %d\n", i, tab[i], tire); + return i; +} + +int main() { + srand(time(NULL)); + int tab[] = {17, 28, 50, 5}; + calcule_borne_sup(tab, 4); + for (int i = 0; i < 4; i++) printf("%d, ", tab[i]); + printf("\n"); + printf("%d", tire_non_equi(tab, 4)); + return 0; +} -- cgit v1.2.3