Algorithme de Lucas

Bonjour,
J'aimerai écrire une fonction récursive me permettant de calculer xⁿ pour x réel et n entier naturel en utilisant la définition récursive suivante :
xⁿ = 1 pour n = 0,
xⁿ = (x^(n/2))² pour n pair,
xⁿ = xⁿ⁻¹.x pour n impair.

Merci de m'apporter votre aide.

Peut-être que je n'ai pas compris, mais je ne vois rien de récursif dans ce que tu demandes.
D’après ce que j'ai compris c'est un code qui ressemble à:

Code:

---

1 2 3 4 5 6 7

float lucas(float x, unsigned n) { if (n == 0) return (1); if (n & 1) return (x * pow(x, n - 1)); return (2 * pow(x, n / 2)); }

---

Bref la fonction ne s'appelle pas elle même.

Merci Baragouine pour ta réponse, je viens de porter une modification au sujet.
J'ai effectivement écrire la fonction de façon normal mais j'aimerai l'écrire d'une autre façon(récursive)

Je comprends mieux, d'ailleurs je dois admettre que c'est un bon petit exo à faire. :D

Oui bien intéressant j'avoue

Finalement cette exo est tellement simple que le seul moyen de t'aider (que j'ai trouver) c'est de te donner le code.
Il suffit simplement de traduire ton énoncer en code:

lucas: (x : réel, n : entier naturel) -> réel
si n = 0 renvoie 1
si n est impaire renvoie lucas(x, n - 1);
renvoie lucas(x, n / 2) * lucas(x, n / 2);

Je ne vois rien de compliquer.

renvoie lucas(x, n / 2) * lucas(x, n / 2);

n paire dans ce cas? ouais plutôt simple j'ai pas eu le flair

Oui n paire dans ce cas. En tout cas bonne chance pour la suite (si il y en a une).
Et tu peux optimiser soit en stockant la valeur, soit en utilisant pow (pour élever au carré) histoire de ne pas faire deux fois la même chose.

Merci beaucoup pour ton aide

Bonjour

Citation:

---

Envoyé par baragouine

Je comprends mieux, d'ailleurs je dois admettre que c'est un bon petit exo à faire. :D

---

En C probablement. Parce qu'en Python ça va pas super loin...:aie:

Code:

---

1 2 3 4

def lucas(n, p): if p == 0: return 1 return n * lucas(n, p-1) if p & 1 else lucas(n, p//2) ** 2 # lucas()

---

8-)

Citation:

---

Envoyé par steph_ntic

renvoie lucas(x, n / 2) * lucas(x, n / 2);

---

Ceci fera 2 fois l'opération. Si n est petit ce n,est pas très grave, sinon tu vas effectuer beaucoup plus/trop d'opérations.
Perso je ferais ça plus ça:

Code:

---

1 2 3 4 5 6 7

float power(float value, unsigned int p) { if (p == 0) return 1; if (p == 2) return value * value; if (p % 2 == 1) return value * power(value, p-1); return power(power(value, p/2), 2); }

---

Citation:

---

Envoyé par Bousk

Ceci fera 2 fois l'opération....Perso je ferais ça plus ça

---

Mmmmoui...Toutefois tu invoques quand-même un appel de fonction et un test supplémentaire juste pour éviter de multiplier un résultat par lui-même. Est-ce vraiment optimum comme rendement ?

Code:

---

1 2 3 4 5 6

float power(float value, unsigned int p) { if (p == 0) return 1; if (p % 2) return value * power(value, p-1); float f=power(value, p/2); return f*f; }

---

...

Citation:

---

Envoyé par Sve@r

Mmmmoui...Toutefois tu invoques quand-même un appel de fonction et un test supplémentaire juste pour éviter de multiplier un résultat par lui-même. Est-ce vraiment optimum comme rendement ?

---

Aucune idée, en pratique j'aurais fait comme ta dernière réponse.
Mais dans le cadre d'un exercice, je préfère faire apparaître la puissance de 2.

Citation:

---

Envoyé par Sve@r

Est-ce vraiment optimum comme rendement ?

---

Juste pour t'embêter :whistle:, avec des fonctions avec un return final, mais elle n'est pas réentrante

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

float lucas(float value, unsigned int p) { float tmp;   if (p == 0) { tmp = 1; } else tmp = lucas_1(value, p, &tmp); }   return tmp; }   // XXX : tmp never NULL float lucas_1(float value, unsigned int p, float* tmp) { if (p % 2) { (*tmp) = (value * lucas_1(value, (p - 1), tmp); } else { (*tmp) = lucas_1(value, (p / 2), tmp); (*tmp) = (*tmp) * (*tmp); }   return (*tmp); }

---

Citation:

---

Envoyé par foetus

Juste pour t'embêter :whistle:

---

Oui, c'est d'ailleurs à ça qu'on te reconnait :mouarf:

Citation:

---

Envoyé par foetus

avec des fonctions avec un return final, mais elle n'est pas réentrante

Code:

---

1 2 3 4 5 6 7 8 9 10 11

float lucas(float value, unsigned int p) { float tmp;   if (p == 0) { tmp = 1; } else tmp = lucas_1(value, p, &tmp); }   return tmp; }

---

---

Euh ouais... La fonction reçoit l'adresse d'une variable (donc à priori elle va la modifier durant son exécution) mais cette variable est ensuite écrasée par le retour de la fonction !!!
Là j'ai... peur :aie:

@steph_ntic
fais pas attention, on déconne, on s'amuse, mais surtout ne prends pas exemple sur nos codes. Enfin si, tu peux prendre exemple sur les miens car ils sont une référence mais n'utilise surtout pas ceux de foetus :mrgreen:

J'apprend vraiment de tout ça.