« Return to Teaching
Programmation 2
Comptage du nombre d’itérations
Quand vous avez une boucle for :
1
2
3
| for (i=0; i<n; i++) {
...
}
|
entre 0 et n (exclus), alors on a n étapes (car on commence à 0). Plus généralement, si on avait i=k alors on aurait n-k étapes. Par contre si on a deux boucles imbriquées :
1
2
3
4
5
| for (i=0; i<n; i++) {
for (j=0; j<m; j++) {
...
}
}
|
alors on a n*m étapes. Attention, si on a <= à la place de < alors on a une étape de plus (par exemple pour i<=n on fait n+1 étapes). La mise à jour du compteur (paramètre du for) influence aussi le nombre d’étapes. Si on avait i+=2 ou i = i + 2 alors on avancerait deux par deux et on aurait n/2 étapes pour le compteur i.
Comptage du nombre d’appels récursifs
Pour les fonctions récursives c’est un peu plus subtil. Je rappelle que l’idée est d’avoir une définition d’une fonction par récurrence puis de la transformer en C avec des conditions et un rappel récursif. Par exemple pour la puissance, on aurait :
puiss(n, k) = { 1 si k=0
{ n*puiss(n, k-1) sinon
Qui devient
1
2
3
4
5
6
| double puiss(double n, unsigned k) {
if (k==0)
return 1;
else
return n*puiss(n, k-1);
}
|
Si on veut compter le nombre d’étapes, on remarque que seul k décrémente à chaque appel récursif. Donc le nombre d’appels sera k. Plus généralement, l’idée est de définir le nombre d’appels par récurrences, par exemple :
Cpuiss(n, k) = { 0 si k=0
{ 1+Cpuiss(n, k-1) sinon
On peut ensuite calculer le nombre d’appels et le prouver par récurrence. Par exemple on pourrait montrer que Cpuiss(n, k) = k. Si on veut compter le nombre d’appels pour puiss(2, 5) alors on aura Cpuiss(2, 5) = 5.
Si on a une fonction dont le nombre d’appels se divise successivement par n alors on aura un logarithme de base n. Prenons un exemple simple :
f(n) = { 0 si n=1
{ 1+f((n-1)/2)) si n est impair
{ 1+f(n/2) si n est pair
On a une somme de 1 un nombre de k fois pour chaque appels récursifs. Ce nombre de fois correspond au nombre de division par 2 qu’on peut faire sur n. On a donc l’expression n*(1/2^k) = n/(2^k). On s’arrête quand n=1 donc on veut résoudre l’équation n/(2^k) = 1 pour k. On a :
n/(2^k) = 1
<=> log2(n/(2^k)) = log2(1)
<=> log2(n/(2^k)) = 0
<=> log2(n) - log2(2^k) = 0
<=> log2(n) - k = 0
<=> log2(n) = k
Donc le nombre d’étapes est log2(n) = ln(n)/ln(2) (tronqué si on est sur des entiers).
Maintenant, prenons l’exemple de la fonction :
1
2
3
4
5
6
7
8
| double puiss_rap(double x, unsigned n) {
if (n == 0)
return 1;
if (n%2 == 0)
return puiss_rap (x*x, n/2);
else
return x * puiss_rap (x*x, (n-1)/2);
}
|
La relation de récurrence du nombre d’appels est :
Cpuiss_rap(x, n) = { 0 si n=0
{ 1+Cpuiss(x*x), (n-1)/2) si n impair
{ 1+Cpuiss(x*x, n/2) si n pair
On se retrouve avec la même chose que la fonction f sauf que l’on s’arrête à n=0 et non n=1. Donc on se retrouve avec un appel en plus. On a donc un nombre d’appel de log(n)+1. Pour en être sûr on peut le prouver par récurrence (je ne le fais pas ici).
Pour les coefficients binomiaux, on a cette définition par récurrence :
bin(n, p) = { 0 si p > n
{ 1 si p=0 ou p=n
{ bin(n-1, p) + bin(n-1, p-1) si 0<p<n
et la définition par récurrence suivante pour le nombre d’appels :
Cbin(n, p) = { 0 si p > n
{ 0 si p=0 ou p=n
{ 2 + Cbin(n-1, p) + Cbin(n-1, p-1) si 0<p<n
Remarquez qu’on a deux appels récursifs plus ceux obtenus par les sous-appels dans la troisième ligne. On peut calculer le nombre d’appels pour des petites valeurs mais la formule qui permet de calculer directement est plus compliquée à obtenir. Une fois qu’on l’a obtenue, on la prouve par récurrence pour s’assurer que tout marche.
Récursion (non-)terminale
La récursion est terminale lorsqu’il ne reste plus d’opérations à faire sur la pile d’appel en dehors de l’appel récursif (qui est la dernière chose à faire). Par exemple pour la puissance on a l’exécution suivante :
puiss(2, 3)
= 2*puiss(2, 2)
= 2*2*puiss(2, 1)
= 2*2*2*puiss(2, 0)
= 2*2*2*1
= 8
On remarque qu’il est impossible de calculer 2*puiss(2, 2) car puiss(2, 2) doit être calculé pour fournir un résultat mais il demande lui-même de rappeler la fonction. Il faut imaginer des parenthèses vers la droite par exemple 2*(2*(2*puiss(2, 0))) donc on ne peut pas juste multiplier les 2 entre eux. On accumule donc des informations supplémentaires dans la mémoire.
On peut cependant programmer la fonction différemment. Pour cela on utilise un troisième paramètre appelé accumulateur qui permet d’accumuler le résultat et de faire des calculs directement sans attendre le résultat d’une fonction. On a donc :
1
2
3
4
5
6
7
8
9
10
11
12
| // C'est la fonction auxiliaire avec accumulateur
double puiss_ter2(double n, unsigned k, double acc) {
if (k==0)
return acc; // on renvoie ce qu'on a accumulé à la fin
else
return puiss(n, k-1, n*acc); // on accumule dans acc
}
// C'est la vraie fonction puissance qui cache l'accumulateur en interne
double puiss_ter(double n, unsigned k) {
return puiss_ter2(n, k, 1); // on accumule avec des multiplications sur 1
}
|
On obtient l’exécution suivante où les opérations peuvent être évaluées directement et donc la taille de la pile d’appel n’évolue plus en fonction du second paramètre.
puiss_ter(2, 3)
= puiss_ter2(2, 3, 1)
= puiss_ter2(2, 2, 2)
= puiss_ter2(2, 1, 4)
= puiss_ter2(2, 0, 8)
= 8
Mémoïsation
Quand on fait des appels récursifs, il se peut que l’on calcule plusieurs fois la même chose inutilement. Par exemple avec les coefficient binomiaux, on a :
bin(n, p) = { 0 si p > n
{ 1 si p=0 ou p=n
{ bin(n-1, p) + bin(n-1, p-1) si 0<p<n
bin(3, 4)
= bin(2, 4) + bin(2, 3)
= bin(1, 4) + bin(1, 3) + bin(1, 3) + bin(1, 2)
= ...
On remarque que bin(1, 3) est calculé deux fois. Si on continue on aura encore plus de redondances. Au lieu de recalculer pour rien, on peut calculer une seule fois puis les autres fois on accèdera à la valeur qu’on a sauvegardé. On obtient cette fonction (que je commente) :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| /* Le principe est d'utiliser un tableau pour sauvegarder les valeurs, on a deux
dimensions pour les deux paramètres de la fonction */
unsigned long long bin_mem_2(unsigned long long n, unsigned long long p, unsigned long long bin_tab[][N]) {
// Cette partie est la même qu'avant
if (n < p) return 0;
if (p == 0 || p == n) return (bin_tab[n][p] = 1);
// Si on a jamais calculé la valeur de bin(n, p)
// Remarquez qu'on passe le tableau en paramètre pour le propager
if (bin_tab[n][p] == 0)
bin_tab[n][p] = bin_mem_2(n-1, p, bin_tab) + bin_mem_2(n-1, p-1, bin_tab);
// A la fin on renvoie toujours la valeur qu'on a déjà sauvegardée
return bin_tab[n][p];
}
unsigned long long bin_mem(unsigned long long n, unsigned long long p) {
/* Toutes les valeurs sont mises à 0 par défaut, donc si on a jamais calculé
la valeur, la case sera à 0 */
unsigned long long bin_tab[N][N] = {0};
return bin_mem_2 (n, p, bin_tab);
}
|
Pointeurs
Ce sont des variables qui contiennent des adresses dans la mémoire. Les opérations de base sont les suivantes :
1
2
3
4
5
6
7
8
| &x; // renvoie l'adresse de x
*p; // renvoie la valeur à l'adresse dans p
p+k; // renvoie l'adresse à p + k cases dans la mémoire (selon le type de p)
*(p+k); // renvoie la valeur à l'adresse p+k
p[k]; // même chose que *(p+k)
// On peut aussi faire d'autres opérations arithmétiques (-, *, ...) comme avec des entiers
// Si le pointeur est de type int* alors on se déplace de 4 octets (taille d'un int)
|
On peut réserver un nouvel espace mémoire pour un pointeur en demandant un certain nombre de blocs pour un certain type. On utilise la fonction malloc qui renvoie une adresse dans la mémoire qui nous est offert. On peut se déplacer dans la zone réservée et cela nous permet en particulier de simuler un tableau. On utilise ensuite free pour dire qu’on ne se sert plus de cette portion de mémoire.
1
2
3
4
5
6
7
| int* p = malloc(sizeof(int)); // on demande 1 bloc de type entier
*p = 3; // on met la valeur 3 dans la case d'adresse p
int* tab = malloc(5*sizeof(int)); // on demande 5 blocs de type entier
*(tab+2) = 3; // on met la valeur 3 à la 2 cases après tab
tab[2] = 4; // on met la valeur 4 à la même case
*tab = 1; // par défaut, tab pointe sur la première case, on aurait pu écrire tab[0] = 1
|
Attention, si on utilise p+1 ou tab+10, on sort de la zone réservée et on risque d’avoir un Segmentation fault.
Si on veut comparer les pointeurs et les tableaux alors voici deux codes équivalents :
1
2
3
4
5
6
7
8
9
10
11
12
| // Version tableau
int tab[5];
tab[0] = 2;
scanf("%d", &tab[1]);
printf("%d\n", tab[2]);
// Version pointeur
int* tab = malloc(5*sizeof(int));
*tab = 2; // on aurait pu écrire tab[0]
scanf("%d", tab+1);
printf("%d\n", *(tab+2)); // on aurait pu écrire tab[2]
free(p);
|
On a pas forcément besoin de faire un malloc, on aurait très bien pu travailler directement sur un tableau qui a déjà de la mémoire allouée :
1
2
3
4
5
| // Tableau + pointeurs
int tab[5];
*tab = 2; // on aurait pu écrire tab[0]
scanf("%d", tab+1);
printf("%d\n", *(tab+2)); // on aurait pu écrire tab[2]
|
Avec des tableaux à deux dimensions, ça reste le même principe. Il ne faut pas oublier qu’un tableau à deux dimensions est un tableau qui contient des tableaux. Cela correspond donc à des pointeurs de pointeurs.
1
2
3
4
5
6
7
| int tab[2][2];
// tab est un pointeur int**
// *tab est un pointeur int*
// **tab est un entier int correspondant à tab[0][0]
*(*(tab+1)+1) = 2; // on aurait pu écrire tab[0][2]
scanf("%d", (*tab+1)+1); // on aurait pu écrire &tab[1][1]
printf("%d\n", *(*(tab+1)+1)); // on aurait pu écrire tab[1][1]
|
Si on travaille avec des structures, on utilise . pour accéder à un champs. Par exemple pers.prenom. Cependant si on a un pointeur on doit écrire (*p).prenom ou utiliser la syntaxe plus pratique p->prenom. Voici un exemple :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <stdlib.h>
#include <stdio.h>
#include <string.h>
struct personne {
char* nom;
char* prenom;
int age;
};
int main()
{
// on aurait pu faire sans malloc en déclarant une structure directement
struct personne* p = malloc(sizeof(struct personne));
p->age = 5;
printf("%d\n", p->age);
p->nom = malloc(3*sizeof(char));
strcpy(p->nom, "Eng");
p->prenom = "Boris"; // const char*
printf("%s %s\n", p->prenom, p->nom);
return EXIT_SUCCESS;
}
|
La différence entre définir un pointeur ou une structure (ou une variable d’un type de donnée classique) est que la structure existe localement dans le bloc d’une fonction et qu’elle disparaît à la fin de la fonction. Si on veut vraiment modifier des données depuis l’extérieur alors on doit utiliser des pointeurs. Voici un exemple simple utilisant des variables entières :
1
2
3
4
5
6
7
| void f(int x) {
x = 3; // on modifie x seulement dans cette fonction mais pas à l'extérieur (on travaille donc avec une copie de x)
}
void g(int* x) {
*x = 3; // on modifie la valeur de x (on travaille avec l'adresse d'une variable du programme entier)
}
|
Tri par insertion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void tri_insertion(int* t, int taille) {
int i, j;
// On parcourt chaque case à partir de la première
for (i=1; i<taille; i++) {
/* Pour chaque case du tableau, on cherche où bien placer sa valeur derrière
selon l'ordre du tableau */
j = i;
// Tant qu'on ne trouve pas une valeur plus grande que la précédente, on continue à chercher
while (j > 0 && t[j] < t[j-1]) {
echanger(t+j, t+j-1); // on échange chaque paire côte-à-côte qui est désordonnée
j--;
}
}
}
// Remarquez qu'on modifie réellement les entiers à l'extérieur, donc on veut les adresses
void echanger(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
|
Exemple d’exécution du tri par insertion :
| Indice |
0 |
1 |
2 |
3 |
4 |
5 |
| Valeurs |
1 |
3 |
4 |
2 |
0 |
5 |
| Indice |
0 |
<1> |
2 |
3 |
4 |
5 |
| Valeurs |
1 |
3 |
4 |
2 |
0 |
5 |
On commence sur la case 1. On cherche une valeur supérieure à gauche. Il n’y en a pas. On passe à la prochaine valeur de i.
| Indice |
0 |
1 |
<2> |
3 |
4 |
5 |
| Valeurs |
1 |
3 |
4 |
2 |
0 |
5 |
Pareil.
| Indice |
0 |
1 |
2 |
<3> |
4 |
5 |
| Valeurs |
1 |
3 |
4 |
2 |
0 |
5 |
La valeur à la case 3 est 2. Il y a plus grand juste à gauche (4). On échange.
| Indice |
0 |
1 |
2 |
<3> |
4 |
5 |
| Valeurs |
1 |
3 |
<2> |
4 |
0 |
5 |
On est sur j=2. On voit qu’il y a plus grand juste à gauche. On échange.
| Indice |
0 |
1 |
2 |
<3> |
4 |
5 |
| Valeurs |
1 |
<2> |
3 |
4 |
0 |
5 |
Il n’y a plus rien de plus grand. On continue avec le i suivant.
| Indice |
0 |
1 |
2 |
3 |
<4> |
5 |
| Valeurs |
1 |
2 |
3 |
4 |
0 |
5 |
On a un 0 et c’est le plus petit. Donc on va le décaler successivement par échanges successifs jusqu’à qu’à arriver au début.
| Indice |
0 |
1 |
2 |
3 |
<4> |
5 |
| Valeurs |
0 |
1 |
2 |
3 |
4 |
5 |
Il nous reste plus qu’à regarder la case 5 qui ne trouvera rien de plus grand à gauche et donc le programme s’arrête. Le tableau est bien trié.
Reorganisation de tableau
Supposons que nous avons un tableau d’entiers et que l’on souhaite placer toutes les occurrences d’un entier à l’avant du tableau. On peut parcourir à partir de la gauche jusqu’à trouver ce qu’on ne veut pas devant et parcourir à partir de la droite jusqu’à trouver ce qu’on veut mettre devant puis faire un échange. On utilise cette fonction :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| void echanger(int* a, int* b)
{
int tmp = *a;
int *a = *b;
int *b = tmp;
}
int reorganiser(int* tab, int taille)
{
int g = 0; // compteur gauche ->
int d = taille-1; // compteur droit <-
// on continue jusqu'à que les compteurs se croisent
while (g < d)
{
/* on continue tant qu'on a pas trouvé
et qu'on est pas arrivé à la fin */
while (tab[g]==tab[d] && g < taille)
g++;
/* on continue tant qu'on a pas trouvé
et qu'on est pas arrivé au début */
while (tab[g]!=tab[d] && d >= 0)
d--;
echanger(tab+i, tab+j);
}
}
|
Recherche dans un tableau trié
Commençons par le cas des tableaux d’entiers pour faire plus simple. On suppose que le tableau est trié dans l’ordre croissant. On renvoie 1 lorsque l’élément x est trouvé. Si on renvoie 0.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int recherche(int* tab, int taille, int x) {
if (taille > 0) {
// On découpe le tableau en deux
int milieu = taille/2;
// Si la valeur qu'on cherche est plus grande, on cherche à gauche
if (x > tab[milieu])
recherche(tab+milieu+1, taille-milieu-1, x);
// Sinon on cherche à droite
else if (x < tab[milieu])
recherche(tab, milieu, an);
// x est exactement le milieu donc on l'a trouvé
else
return 1;
}
else
return 0; // x n'a pas été trouvé
}
|
Maintenant, comme dans le TD9, on applique la recherche dichotomique avec les opéras. Nous chercons un opéra avec une certaine date de création. Attention, la difficulté est qu’on ne manipule pas un tableau d’opéras mais un tableau d’adresses d’opéras. Chaque élément de notre tableau est donc une adresse vers un opéra dans la mémoire.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void rechercher_tab_annee_creation(struct opera** tab, int taille, unsigned an)
{
if (taille > 0)
{
int milieu = taille/2;
/* Remarques :
- tab et tab+milieu sont de type struct opera**
- tab[milieu] est de type struct opera*
- *tab[milieu] est de type opera */
if (an > tab[milieu]->date_creation->annee)
rechercher_tab_annee_creation(tab+milieu+1, taille-milieu-1, an);
else if (an < tab[milieu]->date_creation->annee)
rechercher_tab_annee_creation(tab, milieu, an);
else
afficher_opera(tab[milieu]);
}
else
{
printf("Aucun opéra trouvé.");
}
}
|
Pointeurs et structures
On reprend l’exemple du TD9 avec des opéras. On rappelle que l’on a un tableau qui contient des adresses d’opéra (et un tableau est lui-même défini avec un pointeur).
1
2
3
4
5
6
7
8
9
10
11
12
| /* on a deux pointeurs qui pointent vers des adresses d'opéra
utiliser des pointeurs nous permet de modifier les valeurs
à une certaine adresse */
void echange(struct opera** op1, struct opera** op2)
{
// on sauvegarde l'adresse d'opéra pointée par op1
struct opera* tmp = *op1;
// on remplace la valeur à l'adresse op1 par celle d'op2
*op1 = *op2;
// on place l'adresse contenue par tmp dans la case d'adresse op2
*op2 = tmp;
}
|
1
2
3
4
5
6
7
8
9
| void echange(struct opera** op1, struct opera** op2)
{
// on sauvegarde l'adresse d'opéra pointée par op1
struct opera* tmp = *op1;
// on remplace la valeur à l'adresse op1 par celle d'op2
*op1 = *op2;
// on place l'adresse contenue par tmp dans la case d'adresse op2
*op2 = tmp;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
| // on renvoie une adresse qui contiendra un espace pour une adresse d'opéra
struct opera* allouer_opera()
{
// on demande un espace mémoire pour contenir une structure opera
struct opera* op = malloc(sizeof(struct opera));
// on vérifie si l'allocation a bien fonctionné
if (op == NULL) {
perror("Échec allocation opéra");
exit(EXIT_FAILURE); // on quitte le programme en signalant un échec
}
return op;
}
struct opera** allouer_tab_opera (int taille) {
int i;
// on demande un espace mémoire pour taille * la taille d'un pointeur d'opéra
struct opera** res = malloc (sizeof(struct opera*) * taille);
for (i=0; i < taille; i++)
res[i] = allouer_opera();
return res;
}
// on libère la mémoire utilisée par un opéra
// Remarque : on utilise une variable struct opera** afin de rediriger l'adresse d'opéra vers le vide (NULL)
void detruire_opera (struct opera ** op) {
// on libère chaque champs
// Remarque : on accède à l'adresse d'opéra avec *op car **op est un pointeur vers une adresse d'opéra
free((*op)->titre);
free((*op)->ville_creation);
/* les libérateurs de mémoire utilisent le type struct date** et struct individu**
donc il faut passer l'adresse d'un pointeur de date et d'individu */
detruire_date(&(*op)->date_creation);
detruire_individu(&(*op)->compositeur);
/* op est un pointeur vers une adresse d'opéra, on libère la mémoire
de ce pointeur */
free(*op);
/* on redirige le pointeur vers NULL */
*op = NULL;
}
void detruire_tab_opera (struct opera **tab, int taille) {
int i;
for (i = 0; i < taille; i ++) {
detruire_opera(tab+i);
}
free(tab);
}
/** Fonction qui échange les adresses d'opéra pointées par les deux arguments */
void echanger_opera (struct opera **op1, struct opera **op2) {
struct opera *temp = *op1;
*op1 = *op2;
*op2 = temp;
}
/** Fonction qui trie le tableau d'opéras tab, de taille n, */
/* selon l'ordre chronologique de création (tri à bulles avec A-R) */
void trier_tab_date_creation (struct opera **tab, int n) {
int j, deb = 0, fin = n-1, der;
while (deb < fin) {
der = 0;
for (j = deb; j < fin; ++j) {
if (comparer_date(tab[j]->date_creation, tab[j+1]->date_creation) > 0) {
echanger_opera(tab+j, tab+j+1);
der = j;
}
}
fin = der;
for (j = fin; j > deb; --j) {
if (comparer_date(tab[j-1]->date_creation, tab[j]->date_creation) > 0) {
echanger_opera(tab+j, tab+j-1);
der = j;
}
}
deb = der;
}
}
/** Fonction qui recherche dans le tableau d'opéras tab, de taille taille, */
/* SUPPOSÉ TRIÉ DANS L'ORDRE CHRONOLOGIQUE DE CRÉATION, un opéra créé au cours de l'année an */
/** Cette fonction affiche un tel opéra s'il s'en trouve un dans le tableau */
/* et affiche un message d'absence sinon */
void recherche_tab_annee_creation (struct opera *tab[], int taille, unsigned an) {
if (taille > 0) {
int milieu = taille/2;
if (an > tab[milieu]->date_creation->annee)
recherche_tab_annee_creation (tab+milieu+1, taille-milieu-1, an);
else
if (an < tab[milieu]->date_creation->annee)
recherche_tab_annee_creation (tab, milieu, an);
else
afficher_opera(tab[milieu]);
}
else
printf("Aucun opéra créé en %d dans le tableau \n", an);
}
|