Implementer une addition recursivement. en c++

Recherche :

Dernière réponse

Sujet : Implementer une addition recursivement. en c++

ayachi

flo850 a écrit a écrit :

pour fibbo , il existe une methode de calculno recursive ( la demo est un peu longue )
je me souvient plus exactement , mais il apparait le nombre d'or ( 1+racine(5))/2

F(n)= ( u^n - (-u)^n ) / sqrt(5), avec u = (1+sqrt(5)) / 2 et -u = (1 - sqrt(5)) / 2.

mais la formule était récursive avec caml, pour ceux qui on fait caml à la fac, si vous savez n'hésitez pas.

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

ayachi

F(n)= ( u^n - (-u)^n ) / sqrt(5), avec u = (1+sqrt(5)) / 2 et -u = (1 - sqrt(5)) / 2.

mais la formule était récursive avec caml, pour ceux qui on fait caml à la fac, si vous savez n'hésitez pas.

flo850

pour fibbo , il existe une methode de calculno recursive ( la demo est un peu longue )
je me souvient plus exactement , mais il apparait le nombre d'or ( 1+racine(5))/2

ayachi

y'a bien cette méthode
allocate array for memo;
initialize memo[1] and memo[2] to 1;
fib(n)
{
if memo[n] is not zero, return memo[n];
memo[n] = fib(n-1) + fib(n-2);
return memo[n];
}

mais je me rappelle d'une autre méthode en caml quand j'étais à la fac qui utilisais des paires pour stocker la variable interm. Mais impossible de retrouver cette méthode :cry:

ayachi

désolé de te piquer le topic mais est-ce que qqun à l'algorithme récursif de fibonacci,
u(n)=u(n-1)+u(n-2)
pas l'évident mais celui qui évite de recalculer u(n-2) puisqu'il a été calculé dans u(n-1).

flo850

pour la puissance pense a ce petit algo
a exp b:
si b est pair
renvoyer a exp b * a exp b
sinon
si b vaut 1
renvoyer a
sinon renvoyer a * a exp (b-1)

donc des que tu as la multiplication ca marche

barbarella

apprendre a programmer ?

oui en partie, mais il existe tellement d'exercices qui peuvent avoir une application dans le concret que je me demandais si celui-ci en avait une.

personnelement je donne plutot comme exercice sur les grands nombres. Karastuba en recursive c'est cool.

Je pense qu'on abuse sur l'importance non seulement de la récursivité mais aussi sur les listes chainées. Les connaitre c'est une chose, les mettre à toutes les sauces comme je le vois régulièrement c'en est une autre.

Mais aujourd'hui je me sens d'humeur espiègle, alors ne prenez pas tout ce que je dis trop au sérieux ;)

[edtdd]--Message édité par barbarella--[/edtdd]

cedric80

L'utilité c'est d'apprendre à programmer! Ce sont des programmes simples à faire et qui t'exercent à la logique.

gizmo

barbarella a écrit a écrit :

humm,

je m'interroge sur l'utilité de tels exercices :(. Bon courage KiLiK

l'approche récursive peut-être, mais c'est clair que ce n'est pas trépidant comme exercice.

barbarella

humm,

je m'interroge sur l'utilité de tels exercices :(. Bon courage KiLiK

kilik

Remarque c bien fait pour ma guele, la prochaine fois je commencerais plus tot :D

Sinon merci de votre aide.

kilik

La puissance jai deja fait c juste pour voir une autre approche. La multiplication ca me saoule. Mais c vrai que c la solution de facilite, mais putain je suis trop a la bourre je my suis prit trop mal, jamaias je vais reussir a terminer.

gizmo

t'apprendra rien du tout si tu ne fais pas tes projets toi-même, surtout pour les bases comme ici. :sarcastic:

kilik

Je dois faire pareil pour la multiplication et la puissance ^.

Si tu te sens d attake hesites pas :D

kilik

J'en demandais pas tant.
Merci beaucoup.
:jap:

cedric80

int add(type *p1, type *p2, int lg1, int lg2)
{
if(lg1 != lg2)
{
if(lg1 > lg2)
{
return (p1->val * 10^lg1 + add(p1->next,p2,lg1-1,lg2));
}
else ...
}
else
{
if(lg1 != 0)
{
return ((p1->val + p2->val) * 10^lg1 + add(p1->next,p2->next,lg1-1,lg2-1)); }
else
{
return p1->val + p2->val;
}
}
}

gizmo

Bon alors si la longueur est connue dès le départ, c'est très con. tu parcours la chaine la plus longue récursivement jusqu'a te positionner au même endroit que la plus courte et ensuite, il ne te reste plus qu'a faire des additions en descendant et en ajoutant le reste.

H4dd3R

325+57:

Ton opération addition fait 5+7=2 et retenue de 1
Tu extrais 32 et 5 que tu n´as pas encore utilisés..
Et tu relances ton même opérateur d´addtion pour 32+5+1

Le résultat de cette relance tu le colle a gauche de ton 2.. :)

C tordu mais c joli!! :) :)

kilik

Oui la longueur des chaines peut etre connue au depart mais elles peuvent ne pas etre de meme taille.

[edtdd]--Message édité par KiLiK--[/edtdd]

gizmo

tu dispose de la longueur des chaines au départ? elles sont de longueurs différente l'une de l'autre ou identique?

kilik

Voila mon problemem. Je dispose de 2 listes chainees representant 2 chiffres. Chaque noeud de la liste represente un digit. Par exemple 325 est une liste chainee de 3 elements ; 3-->2-->5

Il faut que j additionne ces 2 chiffres, digit par digit (+ la retenue). Le truc c est que la fonction addition doit etre implementee recursivement et je ne vois pas trop comment faire.

Merci a tous ceux qui m aideront
:jap: