bonjour a tous,
je dois démontrer la validité et la terminaison d'un algorithme en langage C que voici :
Démontrez la terminaison de la fonction FiboIt(n) pour tout n appartenant a N
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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; }
- 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
Partager