68 lines
2.0 KiB
Markdown
68 lines
2.0 KiB
Markdown
C 6
|
|
=
|
|
|
|
### Exercice 3
|
|
|
|
Le programme suivant ne compile pas, car la fonction `f` appelée dans la fonction `main` n'est pas déclarée. Le compilateur `C` en crée donc une, et râle quand il en croise une nouvelle. Il suffit donc d'ajouter la ligne suivante juste au dessus de la fonction `main` pour définir correctement la fonction `f` qui sera utilisée et définie à posteriori.
|
|
|
|
```
|
|
float f(float x);
|
|
```
|
|
|
|
### Exercice 4
|
|
À la fin de ce programme, `x` vaut `0` parce que le paramètre `int x` indique que l'appel à `f(x)` transmet *la valeur* de `x`. Afin de passer la référence, il aurait fallu mettre un parametre de type `int* x` et ensuite appeler `*x = *x+1`. (pourquoi y a t'il un `float` d'ailleurs ?)
|
|
|
|
### Exercice 5
|
|
À la fin de ce programme, tab vaut `[1, 2]`. Le tableau est un pointeur déguisé, et ce sont donc des références qui sont passées.
|
|
|
|
|
|
### Exercice 6
|
|
|
|
Calculer la suite de fibonnaci avec une boucle se fait en complexité O(n). Ça va.
|
|
|
|
Calculer la suite de fibonnaci avec une (mauvaise) récursivité, complexité exponentielle. Le coût suit en effet la relation de récurence `M_n = M_n-1 + M_n-2`. On peut aussi faire une récurence plus sympa en renvoyant deux termes de la suite.
|
|
|
|
```
|
|
#include <stdio.h>
|
|
#define N 50
|
|
|
|
/**
|
|
* Renvoie le couple (F_k, F_k+1)
|
|
*/
|
|
void fiboRec(int aa[N], int k){
|
|
if(k<=1)aa[k] = 1;
|
|
else aa[k] = aa[k-2]+aa[k-1];
|
|
if(k+1<N)fiboRec(aa, k+1);
|
|
}
|
|
|
|
/**
|
|
* Est-ce ce qui a été demandé ? Si oui, c'est très long.
|
|
*/
|
|
int fiboRecMoche(int k){
|
|
if(k<=1) return 1;
|
|
return (fiboRecMoche(k-1) + fiboRecMoche(k-2));
|
|
}
|
|
void fiboPlain(int aa[N]){
|
|
aa[0] = aa[1] = 1;
|
|
for(int k=2;k<N;k++)
|
|
aa[k] = aa[k-2] + aa[k-1];
|
|
}
|
|
|
|
int main() {
|
|
|
|
int fiboArr[N];
|
|
int fiboArrRec[N];
|
|
|
|
fiboRec(fiboArrRec,0);
|
|
fiboPlain(fiboArr);
|
|
|
|
printf("Fibo récursif : %d\n", fiboArrRec[N-1]);
|
|
printf("Fibo non récursif : %d\n", fiboArr[N-1]);
|
|
|
|
// Avec cette ligne ça met trop de temps. Complexité exponentielle, miam miam.
|
|
printf("Fibo très moche : %d\n", fiboRecMoche(N-1));
|
|
|
|
return 0;
|
|
}
|
|
```
|