Java
ayaf
Messages postés
3
Statut
Membre
-
Misdrhaal Messages postés 49 Statut Membre -
Misdrhaal Messages postés 49 Statut Membre -
Bonjour a tous,
Je suis Florence et j'etudie Informatique en Allemagne,ce qui n'est pas tres facile.J'aimerais avoir votre aide par rapport a cet exercice svp. Soit la methode suivante:
double p (double a,unsigned int n) (
double x;
if (n == 0)
return (1.0) ;
else (
if ((n & 1) == 1) // est ce n paire ?
return (a * p(a, n-1)) ;
else (
x = p(a, n/2) ;
return (x * x) ;
)
)
)
1. Que calcule t elle?
2.Quel est son temps de validite(nombre de multipications) ?
Excusez laforme decriture,mon clavier n est pas francais
Je compte sur votre aide et attends impatiemment vos reponses
Merci d avance, Florence
Je suis Florence et j'etudie Informatique en Allemagne,ce qui n'est pas tres facile.J'aimerais avoir votre aide par rapport a cet exercice svp. Soit la methode suivante:
double p (double a,unsigned int n) (
double x;
if (n == 0)
return (1.0) ;
else (
if ((n & 1) == 1) // est ce n paire ?
return (a * p(a, n-1)) ;
else (
x = p(a, n/2) ;
return (x * x) ;
)
)
)
1. Que calcule t elle?
2.Quel est son temps de validite(nombre de multipications) ?
Excusez laforme decriture,mon clavier n est pas francais
Je compte sur votre aide et attends impatiemment vos reponses
Merci d avance, Florence
A voir également:
- Java
- Jeux java itel - Télécharger - Jeux vidéo
- Waptrick java football - Télécharger - Jeux vidéo
- Waptrick java voiture - Télécharger - Jeux vidéo
- Java apk - Télécharger - Langages
- Eclipse java - Télécharger - Langages
4 réponses
pour la comprendre, il faut que tu te dises que c'est une fonction récursive :
au niveau du return, on appelle de nouveau la fonction mais cette fois avec un n plus petit (divisé par deux si n paire, n-1 sinon)
Donc si on regarde n impaire:
on va retourner
a*p(a,n-1)
Entrons maintenant dans p(a,n-1)
n-1 est pair, on va donc rester constamment dans le deuxieme test désormais.
on aura donc :
x=(a* [p(a,n/2)*p(a,n/2)])
Si on entre à nouveau dans la fonction suivante :
x=(a* [(p(a,(n/2)/2))^4)
etc etc...
Si je ne me suis pas trompé c'est ca (dans le cas d'un n paire enlever le a*)
Tu peux vérifier en prenant un papier et un crayon, c'est le mieux à fair epour les fonctions récursives, en tous cas voila l'idée.
son temps de validité et bien quand tu auras trouvé comment elle fonctionne, tu comprendras vite, à vue de nez je dirais que c'est une n-exponentielle, à confirmer.
au niveau du return, on appelle de nouveau la fonction mais cette fois avec un n plus petit (divisé par deux si n paire, n-1 sinon)
Donc si on regarde n impaire:
on va retourner
a*p(a,n-1)
Entrons maintenant dans p(a,n-1)
n-1 est pair, on va donc rester constamment dans le deuxieme test désormais.
on aura donc :
x=(a* [p(a,n/2)*p(a,n/2)])
Si on entre à nouveau dans la fonction suivante :
x=(a* [(p(a,(n/2)/2))^4)
etc etc...
Si je ne me suis pas trompé c'est ca (dans le cas d'un n paire enlever le a*)
Tu peux vérifier en prenant un papier et un crayon, c'est le mieux à fair epour les fonctions récursives, en tous cas voila l'idée.
son temps de validité et bien quand tu auras trouvé comment elle fonctionne, tu comprendras vite, à vue de nez je dirais que c'est une n-exponentielle, à confirmer.
(Je n'ai pas pu éditer le message donc si des modos passent par là)
pour la comprendre, il faut que tu te dises que c'est une fonction récursive :
au niveau du return, on appelle de nouveau la fonction mais cette fois avec un n plus petit (divisé par deux si n pair, n-1 sinon)
Donc si on regarde n impaire:
on va retourner
a*p(a,n-1)
Entrons maintenant dans p(a,n-1)
n-1 est pair, on va donc rester constamment dans le deuxieme test désormais.
on aura donc :
x*x=[a* p(a,(n-1)/2) * a*p(a,(n-1)/2)]
un produit
on entre alors dans les deux fonctions :
x*x=[a* p(a,((n-1)/2/2))* p(a,((n-1)/2/2))] *[a* p(a,((n-1)/2/2))* p(a,((n-1)/2/2))]
d'où
x*x=[a* p(a,(n-1)/4)* p(a,(n-1)/4)] *[a* p(a,(n-1)/4)* (a,(n-1)/4)]
2 produits
On entre alors dans 4 fonctions identiques et chacune d'elle nous rammenera un produit de deux fonctions où n sera encore divisé par deux d'où
x*x=(a* [p(a,(n-1)/8)*p(a,(n-1)/8)]*[p(a,(n-1)/8*p(a,(n-1)/8)*(a* [p(a,(n-1)/8*p(a,(n-1)/8)]*[p(a,(n-1)/8*p(a,(n-1)/8])
etc etc
compter les produits :
à chaque appel de fonction, on double le nombre de produits de fonctions:
premiere iteration : un produit ( deux fonctions)
seconde iteration trois produits (4 fonctions)
troisieme : sept produits (8fonctions)
d'ou ( p^2)-1 (+2 si n pair)
avec p nombre d'itérations.
Ce nombre dépend de n;
Tu peux vérifier en prenant un papier et un crayon, c'est le mieux à fair epour les fonctions récursives, en tous cas voila l'idée.
pour la comprendre, il faut que tu te dises que c'est une fonction récursive :
au niveau du return, on appelle de nouveau la fonction mais cette fois avec un n plus petit (divisé par deux si n pair, n-1 sinon)
Donc si on regarde n impaire:
on va retourner
a*p(a,n-1)
Entrons maintenant dans p(a,n-1)
n-1 est pair, on va donc rester constamment dans le deuxieme test désormais.
on aura donc :
x*x=[a* p(a,(n-1)/2) * a*p(a,(n-1)/2)]
un produit
on entre alors dans les deux fonctions :
x*x=[a* p(a,((n-1)/2/2))* p(a,((n-1)/2/2))] *[a* p(a,((n-1)/2/2))* p(a,((n-1)/2/2))]
d'où
x*x=[a* p(a,(n-1)/4)* p(a,(n-1)/4)] *[a* p(a,(n-1)/4)* (a,(n-1)/4)]
2 produits
On entre alors dans 4 fonctions identiques et chacune d'elle nous rammenera un produit de deux fonctions où n sera encore divisé par deux d'où
x*x=(a* [p(a,(n-1)/8)*p(a,(n-1)/8)]*[p(a,(n-1)/8*p(a,(n-1)/8)*(a* [p(a,(n-1)/8*p(a,(n-1)/8)]*[p(a,(n-1)/8*p(a,(n-1)/8])
etc etc
compter les produits :
à chaque appel de fonction, on double le nombre de produits de fonctions:
premiere iteration : un produit ( deux fonctions)
seconde iteration trois produits (4 fonctions)
troisieme : sept produits (8fonctions)
d'ou ( p^2)-1 (+2 si n pair)
avec p nombre d'itérations.
Ce nombre dépend de n;
Tu peux vérifier en prenant un papier et un crayon, c'est le mieux à fair epour les fonctions récursives, en tous cas voila l'idée.
