validité et terminaison d'un algo
bonjour a tous,
je dois démontrer la validité et la terminaison d'un algorithme en langage C que voici :
Code:
1
2
3
4
5
6
7
8
9
10
11
| int FiboIt(n){
if(n==0)return 0;
int x=0,y=1,i=1,z;
while(i<n){
z=x+y;
x=y;
y=z;
i++;
}
return y;
} |
Démontrez la terminaison de la fonction FiboIt(n) pour tout n appartenant a N
- Que valent les suites xi et yi en fonction de la suite de Fibonacci ?
- Démontrez ce résultat par récurrence sur i
- En déduire la validité de la fonction FiboIt
- quelle est la complexité de la fonction FiboIt(n) ? justifiez votre réponse
Pour la terminaison, il n'y a pas de problème mais je bloque pour la validité, il faut que je démontre d'abord le resultat par récurrence et je n'y arrive pas, j'ai supposé la propriété vrai au rang i et je veux montrer que ça l'est aussi au rang i+1 mais je n'aboutis pas si quelqu'un pouvait m'aider ça serait sympa
(j'ai xi=yi-1 et yi=x(i-1)+y(i-1)
merci d'avance
