Discussion :

[esteller]

Bonjour à tous.
si vous pouviez m'aider à résoudre ce problème.
Même si ce n'est que le début. Je suis débutante en complexité

1. Ecrire une procédure récursive Puissance (a, n) qui retourne la valeur de an. On rappelle que a0 = 1
2. On pose P(a,n) la complexité en nombre de comparaisons de cette procédure en fonction de a et de n. Trouvez une relation de récurrence pour P(a,n) et en déduire la formule de P(a,n). Quel est l'ordre de cette complexité?
3. Ecrire une procédure récursive SommePuissance(a,n) qui retourne la valeur de Σ(somme de a à la puissance i.pour i allant de 0 à n)
4. On pose S(a,n) la complexité en nombre de comparaisons de cette dernière procédure.
Trouvez une relation de récurrence pour S(a,n). En déduire la formule de S(a,n). Quel est l'ordre de cette complexité?

merci d'avance

[Invité(e)]

Bonjour,

Qu'as tu fait jusqu'à maintenant ?
Qu'est ce qui te pose problème ?

[esteller]

j'ai essayé de traiter le N°1 c'est a dire la recursivité mais je n'arrive pas.

[Invité(e)]

L'idée de la récursivité c'est d'avoir une fonction qui s'appelle elle-même.

Sachant qu'une fonction puissance, c'est
a^n = a x a x a x ... a,
On peut aussi écrire
a^n = a x a^(n-1).

Donc, on aura quelque chose qui ressemble à (attention, le cas n <= 1 n'est pas encore pris en compte) :

Code c :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
double puissance(double a, int n) {
    return a * puissance(a, n-1);
}