Ex PGCD
Bonjour,
j'ai l'exercice de PGCD , aide moi svp
on a :
fonction PGCD(x, y entier) // x>y>=0;
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
j'ai l'exercice de PGCD , aide moi svp
on a :
fonction PGCD(x, y entier) // x>y>=0;
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
Configuration: Windows XP Firefox 3.0.3
3 réponses
-
Bonjour.
Voir ICI pour un bon début.
Ensuite, si tu peux nous expliquer un peu ce qui te bloque, et ce que tu as déjà fait ?
-
ModérateurVa plutôt sur un forum de maths...
-
désole , parce que je sais pas comment faire Montrer par récurrence que pour x>y>=0 , si n(x,y)=k alors x> F(k+2)
mais je sais pas un autre forum math pr demander-
Re...
1. On n'est pas là pour t'éviter de réfléchir.
Vu le niveau, je suppose que tu es à l'école (ou en formation).
Profites-en ! Si vraiment tu ne comprends pas, demande à ton prof, il est là pour t'expliquer (et si tu ne lui dis rien, il ne peut pas deviner que tu ne comprends pas).
Si tu n'apprends pas maintenant, ce n'est pas à ton travail que tu pourras te permettre de demander de l'aide comme ça !
2. A défaut de réfléchir, essaye de faire au moins l'effort de chercher !
Il y a déjà un de tes collègues qui a demandé ça sur ce forum, et il a eu la réponse...
-
