bonjour à tous,
j'ai un exo a rendre dans quelques jours et je suis bloqué à la question 3.2. Pour les premières questions, je vous
donne mes réponses. Je vous remercie de bien vouloir me corriger si jamais vous trouvez que ce que j'ai écrit est erroné :
Je commence a partir de la question2 car la réponse à la question1 est trivial.
pour la terminaison, on peut voir que la boucle while s'acheve toujours(elle contient au plus n-1 iterations donc l'algo se termine apres un nombre fini d'etape.
pour la question3.1, xi=y(i-1) et yi=x(i-1) + y(i-1).
Je bloque a partir de la question suivante, j'ai commencé par supposer que xi et yi soient vrais et je montre au rang xi+1 et yi+1 et ensuite je ne vois pas comment poursuivre.
pour la question3.1, on doit deduire de la question précedente pour l'invariant de boucle while que les i-1 premiers elements sont calculés d'ou la preuve de la validité
pour la question4, la complexité est O(n) car la boucle while fait au plus n-1 iteration or n-1 appartient à O(n) (je ne suis pas vraiment sûr que c'est de cette manière qu'il faut demontrer)
merci d'avance de l'aide et bonne journée
enoncé de l'exo :
soit le code en langage C de la fonction FiboIt :
question1Code: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; }
donnez les valeurs successives des suites xi et yi pour l'appel FiboIt(5)
question2
demontrez la terminaison de la fonction FiboIt(n) pour tout n appartenant a N
question3
1)que valent les suites xi et yi en fonction de la suite de Fbonacci ?
2)demontrez ce resultat par recurrence sur i
3)en deduire la validité de la fonction FiboIt
question4
quelle est la complexité de la fonction FiboIt(n) ? justifiez votre réponse
-----