Ex PGCD

[wai]

Bonjour,
j'ai l'exercice de PGCD , aide moi svp
on a :
x>y>=0;
fonction PGCD(x, y entier)
{
if y=0 then return x ;
else return PGCD(y, x mod y);
}
Question:
Soit n(x,y) le nombre divisions ("mod")effectuees par l'algorithme
Montrer que n(x,y) = 0 si y =0
= 1+n(y, x mod y) sinon

Montrer par récurrence que pour x>y>=0 , si n(x,y)=k alors x> F(k+2) (ou F(k+2) est le k+2 éme terme de la suite de Fibonacci
F(n): =0 si n=0
=1 si n=1
=F(n-1)+ F(n-2) si n>=2
et F(n) = 1\sqrt5 *(phi^n - phi'^n).


merci d'avance

[leon1789]

Au brouillon, tu en es où ?

[wai]

Apres :mur: j'ai fini :++: